اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدNon-Asymptotic Connectivity of Random Graphs and Their Unions
118
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
Graph-theoretic methods have seen wide use throughout the literature on multi-agent control and optimization. When communications are intermittent and unpredictable, such networks have been modeled using random communication graphs. When graphs are time-varying, it is common to assume that their unions are connected over time, yet, to the best of our knowledge, there are not results that determine the number of finite-size random graphs needed to attain a connected union. Therefore, this paper bounds the probability that individual random graphs are connected and bounds the same probability for connectedness of unions of random graphs. The random graph model used is a generalization of the classic Erdos-Renyi model which allows some edges never to appear. Numerical results are presented to illustrate the analytical developments made.
قيم البحث
اقرأ أيضاً
We study non-Bayesian social learning on random directed graphs and show that under mild connectivity assumptions, all the agents almost surely learn the true state of the world asymptotically in time if the sequence of the associated weighted adjace
ncy matrices belongs to Class $pstar$ (a broad class of stochastic chains that subsumes uniformly strongly connected chains). We show that uniform strong connectivity, while being unnecessary for asymptotic learning, ensures that all the agents beliefs converge to a consensus almost surely, even when the true state is not identifiable. We then provide a few corollaries of our main results, some of which apply to variants of the original update rule such as inertial non-Bayesian learning and learning via diffusion and adaptation. Others include extensions of known results on social learning. We also show that, if the network of influences is balanced in a certain sense, then asymptotic learning occurs almost surely even in the absence of uniform strong connectivity.
In this paper, we study the phase transition behavior emerging from the interactions among multiple agents in the presence of noise. We propose a simple discrete-time model in which a group of non-mobile agents form either a fixed connected graph or
a random graph process, and each agent, taking bipolar value either +1 or -1, updates its value according to its previous value and the noisy measurements of the values of the agents connected to it. We present proofs for the occurrence of the following phase transition behavior: At a noise level higher than some threshold, the system generates symmetric behavior (vapor or melt of magnetization) or disagreement; whereas at a noise level lower than the threshold, the system exhibits spontaneous symmetry breaking (solid or magnetization) or consensus. The threshold is found analytically. The phase transition occurs for any dimension. Finally, we demonstrate the phase transition behavior and all analytic results using simulations. This result may be found useful in the study of the collective behavior of complex systems under communication constraints.
Consider a dynamic random geometric social network identified by $s_t$ independent points $x_t^1,ldots,x_t^{s_t}$ in the unit square $[0,1]^2$ that interact in continuous time $tgeq 0$. The generative model of the random points is a Poisson point mea
sures. Each point $x_t^i$ can be active or not in the network with a Bernoulli probability $p$. Each pair being connected by affinity thanks to a step connection function if the interpoint distance $|x_t^i-x_t^j|leq a_mathsf{f}^star$ for any $i eq j$. We prove that when $a_mathsf{f}^star=sqrt{frac{(s_t)^{l-1}}{ppi}}$ for $lin(0,1)$, the number of isolated points is governed by a Poisson approximation as $s_ttoinfty$. This offers a natural threshold for the construction of a $a_mathsf{f}^star$-neighborhood procedure tailored to the dynamic clustering of the network adaptively from the data.
As data analytics becomes more crucial to digital systems, so grows the importance of characterizing the database queries that admit a more efficient evaluation. We consider the tractability yardstick of answer enumeration with a polylogarithmic dela
y after a linear-time preprocessing phase. Such an evaluation is obtained by constructing, in the preprocessing phase, a data structure that supports polylogarithmic-delay enumeration. In this paper, we seek a structure that supports the more demanding task of a random permutation: polylogarithmic-delay enumeration in truly random order. Enumeration of this kind is required if downstream applications assume that the intermediate results are representative of the whole result set in a statistically valuable manner. An even more demanding task is that of a random access: polylogarithmic-time retrieval of an answer whose position is given. We establish that the free-connex acyclic CQs are tractable in all three senses: enumeration, random-order enumeration, and random access; and in the absence of self-joins, it follows from past results that every other CQ is intractable by each of the three (under some fine-grained complexity assumptions). However, the three yardsticks are separated in the case of a union of CQs (UCQ): while a union of free-connex acyclic CQs has a tractable enumeration, it may (provably) admit no random access. For such UCQs we devise a random-order enumeration whose delay is logarithmic in expectation. We also identify a subclass of UCQs for which we can provide random access with polylogarithmic access time. Finally, we present an implementation and an empirical study that show a considerable practical superiority of our random-order enumeration approach over state-of-the-art alternatives.
Random geometric graphs consist of randomly distributed nodes (points), with pairs of nodes within a given mutual distance linked. In the usual model the distribution of nodes is uniform on a square, and in the limit of infinitely many nodes and shri
nking linking range, the number of isolated nodes is Poisson distributed, and the probability of no isolated nodes is equal to the probability the whole graph is connected. Here we examine these properties for several self-similar node distributions, including smooth and fractal, uniform and nonuniform, and finitely ramified or otherwise. We show that nonuniformity can break the Poisson distribution property, but it strengthens the link between isolation and connectivity. It also stretches out the connectivity transition. Finite ramification is another mechanism for lack of connectivity. The same considerations apply to fractal distributions as smooth, with some technical differences in evaluation of the integrals and analytical arguments.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
