In this article, we establish orientation and connectivity based criteria for the agreement algorithm to achieve asymptotic consensus in the context of time-varying topology and communication delays. These criteria unify and extend many earlier convergence results on the agreement algorithm for deterministic and discrete-time multiagent systems.
@cite_17 proved that in the case of stochastic matrices with equal positive entries in each row (usually referred to as the equal neighbor model ,), and under assumptions A and B with @math , the agreement algorithm achieves asymptotic consensus when all the communication graphs are oriented. Their convergence result thus coincides with Theorem in the particular case of a synchronous multiagent system and with the equal neighbor model.
@cite_17
2112753256
This paper studies local algorithms for autonomous robot systems, namely, algorithms that use only information of the positions of a bounded number of their nearest neighbors. The paper focuses on the spreading problem. It defines measures for the quality of spreading, presents a local algorithm for the one-dimensional spreading problem, proves its convergence to the equally spaced configuration and discusses its convergence rate in the synchronous and semi-synchronous settings. It then presents a local algorithm achieving the exact equally spaced configuration in finite time in the synchronous setting, and proves it is time optimal for local algorithms. Finally, the paper also proposes a possible algorithm for the two-dimensional case and presents partial simulation results of its effectiveness. We consider distributed plurality consensus in a complete graph of size @math with @math initial opinions. We design an efficient and simple protocol in the asynchronous communication model that ensures that all nodes eventually agree on the initially most frequent opinion. In this model, each node is equipped with a random Poisson clock with parameter @math . Whenever a node's clock ticks, it samples some neighbors, uniformly at random and with replacement, and adjusts its opinion according to the sample. A prominent example is the so-called two-choices algorithm in the synchronous model, where in each round, every node chooses two neighbors uniformly at random, and if the two sampled opinions coincide, then that opinion is adopted. This protocol is very efficient and well-studied when @math . If @math for some small @math , we show that it converges to the initial plurality opinion within @math rounds, w.h.p., as long as the initial difference between the largest and second largest opinion is @math . On the other side, we show that there are cases in which @math rounds are needed, w.h.p. One can beat this lower bound in the synchronous model by combining the two-choices protocol with randomized broadcasting. Our main contribution is a non-trivial adaptation of this approach to the asynchronous model. If the support of the most frequent opinion is at least @math times that of the second-most frequent one and @math , then our protocol achieves the best possible run time of @math , w.h.p. We relax full synchronicity by allowing @math nodes to be poorly synchronized, and the well synchronized nodes are only required to be within a certain time difference from one another. We enforce this synchronicity by introducing a novel gadget into the protocol. This paper gives a lower bound on the convergence rate of a class of network consensus algorithms. Two different approaches using directed graphs as a main tool are introduced: one is to compute the "scrambling constants" of stochastic matrices associated with "neighbor shared graphs" and the other is to analyze random walks on a sequence of graphs. Both approaches prove that the time to reach consensus within a dynamic network is logarithmic in the relative error and is in worst case exponential in the size of the network. Given an n × m nonnegative matrix A = (a ij ) and positive integral vectors r e ℜ n and c e Âm having a common one-norm h, the (r,c)-scaling problem is to obtain positive diagonal matrices X and Y, if they exist, such that XAY has row and column sums equal to r and c, respectively. The entropy minimization problem corresponding to A is to find an n × m matrix z = (z ij ) having the same zero pattern as A, the sum of whose entries is a given number h, its row and column sums are within given integral vectors of lower and upper bounds, and such that the entropy function consisting of the sum of the terms z ij ln (z ij a ij ) is minimized. When the lower and upper bounds coincide, matrix scaling and entropy minimization are closely related. In this paper we present several complexity bounds for the e-approximate (r,c)-scaling problem, polynomial in n,m,h, 1 e, and ln V v, where V and v are the largest and the smallest positive entries of A, respectively. These bounds, although not polynomial in ln(1 1 e), not only provide alternative complexities for the polynomial time algorithms, but could result in better overall complexities. In particular, our theoretical analysis supports the practicality of the well-known RAS algorithm. In our analysis we obtain bounds on the norm of scaling vectors which will be used in deriving not only some of the above complexities, but also a complexity for square nonnegative matrices having positive permanent. In particular, our results extend, nontrivially, many bounds for the doubly stochastic scaling of square nonnegative matrices previously given by Kalantari and Khachiyan to the case of general (r,c)-scaling. Finally, we study a more general entropy minimization problem where row and column sums are constrained to lie in prescribed intervals, and the sum of all entries is also prescribed. Balinski and Demange described an RAS type algorithm for its continuous version, but did not analyze its complexity. We show that this algorithm produces an 1 e-approximate solution within complexity polynomial in n, m, h, V v and 1 1 e. This paper considers the problem of distributed optimization over time-varying graphs. For the case of undirected graphs, we introduce a distributed algorithm, referred to as DIGing, based on a combination of a distributed inexact gradient method and a gradient tracking technique. The DIGing algorithm uses doubly stochastic mixing matrices and employs fixed step-sizes and, yet, drives all the agents' iterates to a global and consensual minimizer. When the graphs are directed, in which case the implementation of doubly stochastic mixing matrices is unrealistic, we construct an algorithm that incorporates the push-sum protocol into the DIGing structure, thus obtaining the Push-DIGing algorithm. Push-DIGing uses column stochastic matrices and fixed step-sizes, but it still converges to a global and consensual minimizer. Under the strong convexity assumption, we prove that the algorithms converge at R-linear (geometric) rates as long as the step-sizes do not exceed some upper bounds. We establish explicit est... Abstract In this paper, we consider a mixed mechanism of a n-site phosphorylation system in which the mechanism of phosphorylation is distributive and that of dephosphorylation is processive. It is assumed that the concentrations of the substrates are much higher than those of the enzymes and their intermediate complexes. This assumption enables us to reduce the system using the steady-state approach to a Michaelis–Menten approximation of the system. It is proved that the resulting system of nonlinear ordinary differential equations admits a unique positive equilibrium in every positive stoichiometric compatibility class using the theory of quadratic equations. We then consider two special cases. In the first case, we assume that the Michaelis constants associated with the different substrates in the phosphorylation reactions are equal and construct a Lyapunov function to prove asymptotic stability of the system. In the second case, we assume that there are just two sites of phosphorylation and dephoshorylation and prove that the resulting system is asymptotically stable using Poincar e ´ Bendixson theorem. The capacity of symmetric instance of the multiple unicast index coding problem with neighboring antidotes (side-information) with number of messages equal to the number of receivers was given by Maleki In this paper, we construct matrices of size @math over @math such that any @math adjacent rows of the matrix are linearly independent. By using such matrices, we give an optimal scalar linear index codes over @math for the symmetric one-sided antidote problems considered by Maleki for any given number of messages and one-sided antidotes. The constructed codes are independent of field size and hence works over every field. Neighbor discovery is one of the first steps in the initialization of a wireless ad hoc network. In this paper, we design and analyze practical algorithms for neighbor discovery in wireless networks. We first consider an ALOHA-like neighbor discovery algorithm in a synchronous system, proposed in an earlier work. When nodes do not have a collision detection mechanism, we show that this algorithm reduces to the classical Coupon Collector's Problem . Consequently, we show that each node discovers all its @math neighbors in an expected time equal to @math , for some constant @math . When nodes have a collision detection mechanism, we propose an algorithm based on receiver status feedback which yields a @math improvement over the ALOHA-like algorithm. Our algorithms do not require nodes to have any estimate of the number of neighbors. In particular, we show that not knowing @math results in no more than a factor of two slowdown in the algorithm performance. In the absence of node synchronization, we develop asynchronous neighbor discovery algorithms that are only a factor of two slower than their synchronous counterparts. We show that our algorithms can achieve neighbor discovery despite allowing nodes to begin execution at different time instants. Furthermore, our algorithms allow each node to detect when to terminate the neighbor discovery phase. Convergence analysis of consensus algorithms is revisited in the light of the Hilbert distance. The Lyapunov function used in the early analysis by Tsitsiklis is shown to be the Hilbert distance to consensus in log coordinates. Birkhoff theorem, which proves contraction of the Hilbert metric for any positive homogeneous monotone map, provides an early yet general convergence result for consensus algorithms. Because Birkhoff theorem holds in arbitrary cones, we extend consensus algorithms to the cone of positive definite matrices. The proposed generalization finds applications in the convergence analysis of quantum stochastic maps, which are a generalization of stochastic maps to non-commutative probability spaces. This article is concerned with a general class of stochastic spatial models for the dynamics of opinions. Like in the voter model, individuals are located on the vertex set of a connected graph and update their opinion at a constant rate based on the opinion of their neighbors. However, unlike in the voter model, the set of opinions is represented by the set of vertices of another connected graph that we call the opinion graph: when an individual interacts with a neighbor, she imitates this neighbor if and only if the distance between their opinions, defined as the graph distance induced by the opinion graph, does not exceed a certain confidence threshold. When the confidence threshold is at least equal to the radius of the opinion graph, we prove that the one-dimensional process fluctuates and clusters and give a universal lower bound for the probability of consensus of the process on finite connected graphs. We also establish a general sufficient condition for fixation of the infinite system based on the structure of the opinion graph, which we then significantly improve for opinion graphs which are distance-regular. Our general results are used to understand the dynamics of the system for various examples of opinion graphs: paths and stars, which are not distance-regular, and cycles, hypercubes and the five Platonic solids, which are distance-regular. We consider the problem of community detection in the Stochastic Block Model with a finite number @math of communities of sizes linearly growing with the network size @math . This model consists in a random graph such that each pair of vertices is connected independently with probability @math within communities and @math across communities. One observes a realization of this random graph, and the objective is to reconstruct the communities from this observation. We show that under spectral algorithms, the number of misclassified vertices does not exceed @math with high probability as @math grows large, whenever @math , @math and where @math and @math denote the (fixed) proportions of vertices in the two smallest communities. In view of recent work by and , this establishes that the proposed spectral algorithms are able to exactly recover communities whenever this is at all possible in the case of networks with two communities with equal sizes. We conjecture that condition (1) is actually necessary to obtain less than @math misclassified vertices asymptotically, which would establish the optimality of spectral method in more general scenarios. The largest eigenvalue of a matrix is always larger or equal than its largest diagonal entry. We show that for a class of random Laplacian matrices with independent off-diagonal entries, this bound is essentially tight: the largest eigenvalue is, up to lower order terms, often the size of the largest diagonal. entry. Besides being a simple tool to obtain precise estimates on the largest eigenvalue of a class of random Laplacian matrices, our main result settles a number of open problems related to the tightness of certain convex relaxation-based algorithms. It easily implies the optimality of the semidefinite relaxation approaches to problems such as ( Z _2 ) Synchronization and stochastic block model recovery. Interestingly, this result readily implies the connectivity threshold for Erdős–Renyi graphs and suggests that these three phenomena are manifestations of the same underlying principle. The main tool is a recent estimate on the spectral norm of matrices with independent entries by van Handel and the author. The paper presents a fully distributed approach for economic dispatch in power systems. The approach is based on the consensus + innovations framework, in which each network agent participates in a collaborative process of neighborhood message exchange and local computation. The distributed approach is shown to converge to the optimal dispatch under rather weak assumptions on the agent communication network connectivity. Intuitively, the proposed approach includes a consensus term which achieves convergence to a common incremental cost value and an innovation term which ensures that the total generation is equal to the load to be supplied. Further, in the proposed approach each network bus only needs to be aware of its local cost parameters and the local predicted load and the neighborhood communication involves exchanging only the locally determined marginal energy price with a few neighbors. Robustness of the proposed approach and techniques for convergence rate improvement are discussed. Finally, simulation studies on the benchmark IEEE 14 bus system demonstrate the effectiveness of the approach. The planted bisection model is a random graph model in which the nodes are divided into two equal-sized communities and then edges are added randomly in a way that depends on the community membership. We establish necessary and sufficient conditions for the asymptotic recoverability of the planted bisection in this model. When the bisection is asymptotically recoverable, we give an efficient algorithm that successfully recovers it. We also show that the planted bisection is recoverable asymptotically if and only if with high probability every node belongs to the same community as the majority of its neighbors. Our algorithm for finding the planted bisection runs in time almost linear in the number of edges. It has three stages: spectral clustering to compute an initial guess, a "replica" stage to get almost every vertex correct, and then some simple local moves to finish the job. An independent work by Abbe, Bandeira, and Hall establishes similar (slightly weaker) results but only in the sparse case where pn, qn = Θ(log n n). Resolving a conjecture of Abbe, Bandeira and Hall, the authors have recently shown that the semidefinite programming (SDP) relaxation of the maximum likelihood estimator achieves the sharp threshold for exactly recovering the community structure under the binary stochastic block model of two equal-sized clusters. The same was shown for the case of a single cluster and outliers. Extending the proof techniques, in this paper it is shown that SDP relaxations also achieve the sharp recovery threshold in the following cases: (1) Binary stochastic block model with two clusters of sizes proportional to network size but not necessarily equal; (2) Stochastic block model with a fixed number of equal-sized clusters; (3) Binary censored block model with the background graph being Erd o s-R 'enyi. Furthermore, a sufficient condition is given for an SDP procedure to achieve exact recovery for the general case of a fixed number of clusters plus outliers. These results demonstrate the versatility of SDP relaxation as a simple, general purpose, computationally feasible methodology for community detection. We introduce and study the reverse voter model, a dynamics for spin variables similar to the well‐known voter dynamics. The difference is in the way neighbors influence each other: once a node is selected and one among its neighbors chosen, the neighbor is made equal to the selected node, while in the usual voter dynamics the update goes in the opposite direction. The reverse voter dynamics is studied analytically, showing that on networks with degree distribution decaying as k−v, the time to reach consensus is linear in the system size N for all v > 2. The consensus time for link‐update voter dynamics is computed as well. We verify the results numerically on a class of uncorrelated scale‐free graphs. The stochastic block model (SBM) with two communities, or equivalently the planted bisection model, is a popular model of random graph exhibiting a cluster behaviour. In the symmetric case, the graph has two equally sized clusters and vertices connect with probability @math within clusters and @math across clusters. In the past two decades, a large body of literature in statistics and computer science has focused on providing lower-bounds on the scaling of @math to ensure exact recovery. In this paper, we identify a sharp threshold phenomenon for exact recovery: if @math and @math are constant (with @math ), recovering the communities with high probability is possible if @math and impossible if @math . In particular, this improves the existing bounds. This also sets a new line of sight for efficient clustering algorithms. While maximum likelihood (ML) achieves the optimal threshold (by definition), it is in the worst-case NP-hard. This paper proposes an efficient algorithm based on a semidefinite programming relaxation of ML, which is proved to succeed in recovering the communities close to the threshold, while numerical experiments suggest it may achieve the threshold. An efficient algorithm which succeeds all the way down to the threshold is also obtained using a partial recovery algorithm combined with a local improvement procedure. The stochastic block model with two communities, or equivalently the planted bisection model, is a popular model of random graph exhibiting a cluster behavior. In the symmetric case, the graph has two equally sized clusters and vertices connect with probability @math within clusters and @math across clusters. In the past two decades, a large body of literature in statistics and computer science has focused on providing lower bounds on the scaling of @math to ensure exact recovery. In this paper, we identify a sharp threshold phenomenon for exact recovery: if @math and @math are constant (with @math ), recovering the communities with high probability is possible if @math and is impossible if $( + 2 ) - . In particular, this improves the existing bounds. This also sets a new line of sight for efficient clustering algorithms. While maximum likelihood (ML) achieves the optimal threshold (by definition), it is in the worst case NP-hard. This paper proposes an efficient algorithm based on a semidefinite programming relaxation of ML, which is proved to succeed in recovering the communities close to the threshold, while numerical experiments suggest that it may achieve the threshold. An efficient algorithm that succeeds all the way down to the threshold is also obtained using a partial recovery algorithm combined with a local improvement procedure. We study an interference network where equally-numbered transmitters and receivers lie on two parallel lines, each transmitter opposite its intended receiver. We consider two short-range interference models: the "asymmetric network," where the signal sent by each transmitter is interfered only by the signal sent by its left neighbor (if present), and a "symmetric network," where it is interfered by both its left and its right neighbors. Each transmitter is cognizant of its own message, the messages of the @math transmitters to its left, and the messages of the @math transmitters to its right. Each receiver decodes its message based on the signals received at its own antenna, at the @math receive antennas to its left, and the @math receive antennas to its right. For such networks we provide upper and lower bounds on the multiplexing gain, i.e., on the high-SNR asymptotic logarithmic growth of the sum-rate capacity. In some cases our bounds meet, e.g., for the asymmetric network. Our results exhibit an equivalence between the transmitter side-information parameters @math and the receiver side-information parameters @math in the sense that increasing decreasing @math or @math by a positive integer @math has the same effect on the multiplexing gain as increasing decreasing @math or @math by @math . Moreover---even in asymmetric networks---there is an equivalence between the left side-information parameters @math and the right side-information parameters @math . A cluster algorithm for graphs called the (MCL algorithm) is introduced. The algorithm provides basically an interface to an algebraic process defined on stochastic matrices, called the MCL process. The graphs may be both weighted (with nonnegative weight) and directed. Let @math be such a graph. The MCL algorithm simulates flow in @math by first identifying @math in a canonical way with a Markov graph @math . Flow is then alternatingly expanded and contracted, leading to a row of Markov Graphs @math . Flow expansion corresponds with taking the @math power of a stochastic matrix, where @math . Flow contraction corresponds with a parametrized operator @math , @math , which maps the set of (column) stochastic matrices onto itself. The image @math is obtained by raising each entry in @math to the @math power and rescaling each column to have sum @math again. The heuristic underlying this approach is the expectation that flow between dense regions which are sparsely connected will evaporate. The invariant limits of the process are easily derived and in practice the process converges very fast to such a limit, the structure of which has a generic interpretation as an overlapping clustering of the graph @math . Overlap is limited to cases where the input graph has a symmetric structure inducing it. The contraction and expansion parameters of the MCL process influence the granularity of the output. The algorithm is space and time efficient and lends itself to drastic scaling. This report describes the MCL algorithm and process, convergence towards equilibrium states, interpretation of the states as clusterings, and implementation and scalability. The algorithm is introduced by first considering several related proposals towards graph clustering, of both combinatorial and probabilistic nature.