The vast majority of real-world networks are scale-free, loopy, and sparse, with a power-law degree distribution and a constant average degree. In this paper, we study first-order consensus dynamics in binary scale-free networks, where vertices are subject to white noise. We focus on the coherence of networks characterized in terms of the @math -norm, which quantifies how closely agents track the consensus value. We first provide a lower bound of coherence of a network in terms of its average degree, which is independent of the network order. We then study the coherence of some sparse, scale-free real-world networks, which approaches a constant. We also study numerically the coherence of Barab 'asi-Albert networks and high-dimensional random Apollonian networks, which also converges to a constant when the networks grow. Finally, based on the connection of coherence and the Kirchhoff index, we study analytically the coherence of two deterministically-growing sparse networks and obtain the exact expressions, which tend to small constants. Our results indicate that the effect of noise on the consensus dynamics in power-law networks is negligible. We argue that scale-free topology, together with loopy structure, is responsible for the strong robustness with respect to noisy consensus dynamics in power-law networks.
From Table , we can observe that the leading behavior for @math in different networks is rich. For a network with @math vertices, @math can behave linearly, sub-linearly, logarithmically, inversely with @math , or independently of @math . For example, in the path graph @cite_33 , 1-dimensional torus @cite_49 @cite_29 , 1-dimensional Cayley graph @cite_20 , and regular ring lattice @cite_15 , @math ; in some fractal tree-like graphs @cite_46 including Vicsek fractal, T fractal, and Peano Basin fractal, @math grows sub-linearly with @math as @math with @math ; in 2-dimensional torus @cite_49 , 2-dimensional Cayley graph @cite_20 , Farey graph @cite_15 , and Koch graph @cite_2 , @math ; in the complete graph @cite_33 , @math ; while in @math -dimensional torus ( @math ) @cite_49 , @math -dimensional Cayley graph ( @math ) @cite_20 , as well as star graph @cite_33 , @math is a constant, irrespective of @math .
@cite_33 @cite_46 @cite_29 @cite_49 @cite_2 @cite_15 @cite_20
2099689250 1998200279 2129248505 2345718780 2029940092
In this paper we study robustness of consensus in networks of coupled single integrators driven by white noise. Robustness is quantified as the H 2 norm of the closed-loop system. In particular we investigate how robustness depends on the properties of the underlying (directed) communication graph. To this end several classes of directed and undirected communication topologies are analyzed and compared. The trade-off between speed of convergence and robustness to noise is also investigated. We consider first- and second-order consensus algorithms in networks with stochastic disturbances. We quantify the deviation from consensus using the notion of network coherence, which can be expressed as an @math norm of the stochastic system. We use the setting of fractal networks to investigate the question of whether a purely topological measure, such as the fractal dimension, can capture the asymptotics of coherence in the large system size limit. Our analysis for first-order systems is facilitated by connections between first-order stochastic consensus and the global mean first passage time of random walks. We then show how to apply similar techniques to analyze second-order stochastic consensus systems. Our analysis reveals that two networks with the same fractal dimension can exhibit different asymptotic scalings for network coherence. Thus, this topological characterization of the network does not uniquely determine coherence behavior. The question of whether the performance of stochastic consensus algorithms in large networks can be captured by purely topological measures, such as the spatial dimension, remains open. We consider distributed consensus and vehicular formation control problems. Specifically we address the question of whether local feedback is sufficient to maintain coherence in large-scale networks subject to stochastic disturbances. We define macroscopic performance measures which are global quantities that capture the notion of coherence; a notion of global order that quantifies how closely the formation resembles a solid object. We consider how these measures scale asymptotically with network size in the topologies of regular lattices in 1, 2, and higher dimensions, with vehicular platoons corresponding to the 1-D case. A common phenomenon appears where a higher spatial dimension implies a more favorable scaling of coherence measures, with a dimensions of 3 being necessary to achieve coherence in consensus and vehicular formations under certain conditions. In particular, we show that it is impossible to have large coherent 1-D vehicular platoons with only local feedback. We analyze these effects in terms of the underlying energetic modes of motion, showing that they take the form of large temporal and spatial scales resulting in an accordion-like motion of formations. A conclusion can be drawn that in low spatial dimensions, local feedback is unable to regulate large-scale disturbances, but it can in higher spatial dimensions. This phenomenon is distinct from, and unrelated to string instability issues which are commonly encountered in control problems for automated highways. This paper examines the close interplay between cooperation and adaptation for distributed detection schemes over fully decentralized networks. The combined attributes of cooperation and adaptation are necessary to enable networks of detectors to continually learn from streaming data and to continually track drifts in the state of nature when deciding in favor of one hypothesis or another. The results in this paper establish a fundamental scaling law for the steady-state probabilities of miss detection and false alarm in the slow adaptation regime, when the agents interact with each other according to distributed strategies that employ small constant step-sizes. The latter are critical to enable continuous adaptation and learning. This paper establishes three key results. First, it is shown that the output of the collaborative process at each agent has a steady-state distribution. Second, it is shown that this distribution is asymptotically Gaussian in the slow adaptation regime of small step-sizes. Third, by carrying out a detailed large deviations analysis, closed-form expressions are derived for the decaying rates of the false-alarm and miss-detection probabilities. Interesting insights are gained from these expressions. In particular, it is verified that as the step-size @math decreases, the error probabilities are driven to zero exponentially fast as functions of @math , and that the exponents governing the decay increase linearly in the number of agents. It is also verified that the scaling laws governing the errors of detection and the errors of estimation over the network behave very differently, with the former having exponential decay proportional to @math , while the latter scales linearly with decay proportional to @math . Moreover, and interestingly, it is shown that the cooperative strategy allows each agent to reach the same detection performance, in terms of detection error exponents, of a centralized stochastic-gradient solution. The results of this paper are illustrated by applying them to canonical distributed detection problems. Abstract Linear consensus is a distributed algorithm which ensures that, under certain assumptions, a set of agents reach asymptotically the same opinion over a certain variable. Moreover this occurs with only a local exchange of information, namely the information exchange takes place only between agents which are neighbors in a graph representing the system communication architecture. Several performance metrics have been proposed for the evaluation of this algorithm. Particularly interesting and challenging is to relate performance to the communication topology. Different performance metrics may yield to different answers in comparing alternative communication topologies. In this paper, we present a number of possible performance metrics. Moreover, we show how these metrics are related to the communication topology. In particular, when available, we present bounds by which it is possible to relate performance and topology for general graphs, for graphs with symmetries, called Cayley graphs, and for geometric graphs.