In this paper, we study the relationship between two crucial properties in linear dynamical networks of diffusively coupled agents, that is controllability and robustness to noise and structural changes in the network. In particular, for any given network size and diameter, we identify networks that are maximally robust and then analyze their strong structural controllability. We do so by determining the minimum number of leaders to make such networks completely controllable with arbitrary coupling weights between agents. Similarly, we design networks with the same given parameters that are completely controllable independent of coupling weights through a minimum number of leaders, and then also analyze their robustness. We utilize the notion of Kirchhoff index to measure network robustness to noise and structural changes. Our controllability analysis is based on novel graph-theoretic methods that offer insights on the important connection between network robustness and strong structural controllability in such networks.
Kirchhoff index or equivalently effective graph resistance based measures have been instrumental in quantifying the effect of noise on the expected steady state dispersion in linear dynamical networks, particularly in the ones with the consensus dynamics, for instance see @cite_23 @cite_8 @cite_22 . Furthermore, limits on robustness measures that quantify expected steady-state dispersion due to external stochastic disturbances in linear dynamical networks are also studied in @cite_9 @cite_10 . To maximize robustness in networks by minimizing their Kirchhoff indices, various optimization approaches (e.g., @cite_26 @cite_1 ) including graph-theoretic ones @cite_0 have been proposed. The main objective there is to determine crucial edges that need to be added or maintained to maximize robustness under given constraints @cite_11 .
@cite_26 @cite_22 @cite_8 @cite_9 @cite_1 @cite_0 @cite_23 @cite_10 @cite_11
2247236687 1980652450 2206841333 2962884567
We investigate the (generalized) Walsh decomposition of point-to-point effective resistances on countable random electric networks with i.i.d. resistances. We show that it is concentrated on low levels, and thus point-to-point effective resistances are uniformly stable to noise. For graphs that satisfy some homogeneity property, we show in addition that it is concentrated on sets of small diameter. As a consequence, we compute the right order of the variance and prove a central limit theorem for the effective resistance through the discrete torus of side length n in Zd, when n goes to infinity. This paper considers the inverse problem with observed variables Y = BGX ⊕Z, where BG is the incidence matrix of a graph G, X is the vector of unknown vertex variables with a uniform prior, and Z is a noise vector with Bernoulli(e) i.i.d. entries. All variables and operations are Boolean. This model is motivated by coding, synchronization, and community detection problems. In particular, it corresponds to a stochastic block model or a correlation clustering problem with two communities and censored edges. Without noise, exact recovery of X is possible if and only the graph G is connected, with a sharp threshold at the edge probability log(n) n for Erdős-Renyi random graphs. The first goal of this paper is to determine how the edge probability p needs to scale to allow exact recovery in the presence of noise. Defining the degree (oversampling) rate of the graph by α = np log(n), it is shown that exact recovery is possible if and only if α > 2 (1−2e)+o(1 (1−2e)). In other words, 2 (1−2e) is the information theoretic threshold for exact recovery at lowSNR. In addition, an efficient recovery algorithm based on semidefinite programming is proposed and shown to succeed in the threshold regime up to twice the optimal rate. Full version available in [1]. Given a background graph with n vertices, the binary censored block model assumes that vertices are partitioned into two clusters, and every edge is labeled independently at random with labels drawn from Bern(1 − e) if two endpoints are in the same cluster, or from Bern(e) otherwise, where e ∈ [0; 1 2] is a fixed constant. For Erdős-Renyi graphs with edge probability p = a log n n and fixed a, we show that the semidefinite programming relaxation of the maximum likelihood estimator achieves the optimal threshold equation for exactly recovering the partition from the labeled graph with probability tending to one as n → ∞. For random regular graphs with degree scaling as a log n, we show that the semidefinite programming relaxation also achieves the optimal recovery threshold aD(Bern(1 2)∥Bern(e)) > 1, where D denotes the Kullback-Leibler divergence. We study a graph-theoretic property known as robustness, which plays a key role in the behavior of certain classes of dynamics on networks (such as resilient consensus and contagion). This property is much stronger than other graph properties such as connectivity and minimum degree, in that one can construct graphs with high connectivity and minimum degree but low robustness. In this paper, we investigate the robustness of common random graph models for complex networks (Erdős-Renyi, geometric random, and preferential attachment graphs). We show that the notions of connectivity and robustness coincide on these random graph models: the properties share the same threshold function in the Erdős-Renyi model, cannot be very different in the geometric random graph model, and are equivalent in the preferential attachment model. This indicates that a variety of purely local diffusion dynamics will be effective at spreading information in such networks.