The dynamics of an agreement protocol interacting with a disagreement process over a common random network is considered. The model can represent the spreading of true and false information over a communication network, the propagation of faults in a large-scale control system, or the development of trust and mistrust in a society. At each time instance and with a given probability, a pair of network nodes are selected to interact. At random each of the nodes then updates its state towards the state of the other node (attraction), away from the other node (repulsion), or sticks to its current state (neglect). Agreement convergence and disagreement divergence results are obtained for various strengths of the updates for both symmetric and asymmetric update rules. Impossibility theorems show that a specific level of attraction is required for almost sure asymptotic agreement and a specific level of repulsion is required for almost sure asymptotic disagreement. A series of sufficient and or necessary conditions are then established for agreement convergence or disagreement divergence. In particular, under symmetric updates, a critical convergence measure in the attraction and repulsion update strength is found, in the sense that the asymptotic property of the network state evolution transits from agreement convergence to disagreement divergence when this measure goes from negative to positive. The result can be interpreted as a tight bound on how much bad action needs to be injected in a dynamic network in order to consistently steer its overall behavior away from consensus.
Convergence to agreement for averaging algorithms have been extensively studied in the literature. Early results were developed in a general setting for studying the ergodicity of nonhomogeneous Markov chains @cite_46 @cite_18 . Deterministic models have been investigated in finding proper connectivity conditions that ensure consensus convergence @cite_27 @cite_24 @cite_36 @cite_22 @cite_55 @cite_2 @cite_31 @cite_3 @cite_51 . Averaging algorithms over random graphs have also been considered @cite_37 @cite_56 @cite_0 @cite_8 @cite_14 @cite_4 @cite_42 .
@cite_18 @cite_31 @cite_37 @cite_22 @cite_14 @cite_8 @cite_36 @cite_4 @cite_55 @cite_42 @cite_3 @cite_56 @cite_24 @cite_0 @cite_27 @cite_2 @cite_46 @cite_51
2032803680 2115428923 2134252677 2154834860 2099589402
exists and all the rows of Q are the same. SIA matrices are defined differently in books on probability theory; see, for example, [1] or [2]. The latter definition is more intuitive, takes longer to state, is easier to verify, and explains why the probabilist is interested in SIA matrices. A theorem in probability theory or matrix theory then says that the customary definition is equivalent to the one we have given. The latter is brief and emphasizes the property which will interest us in this note. We define S(P) by We consider the agreement problem over random information networks. In a random network, the existence of an information channel between a pair of elements at each time instance is probabilistic and independent of other channels; hence, the topology of the network varies over time. In such a framework, we address the asymptotic agreement for the networked elements via notions from stochastic stability. Furthermore, we delineate on the rate of convergence as it relates to the algebraic connectivity of random graphs. Various randomized consensus algorithms have been proposed in the literature. In some case randomness is due to the choice of a randomized network communication protocol. In other cases, randomness is simply caused by the potential unpredictability of the environment in which the distributed consensus algorithm is implemented. Conditions ensuring the convergence of these algorithms have already been proposed in the literature. As far as the rate of convergence of such algorithms, two approaches can be proposed. One is based on a mean square analysis, while a second is based on the concept of Lyapunov exponent. In this paper, by some concentration results, we prove that the mean square convergence analysis is the right approach when the number of agents is large. Differently from the existing literature, in this paper we do not stick to average preserving algorithms. Instead, we allow to reach consensus at a point which may differ from the average of the initial states. The advantage of such algorithms is that they do not require bidirectional communication among agents and thus they apply to more general contexts. Moreover, in many important contexts it is possible to prove that the displacement from the initial average tends to zero, when the number of agents goes to infinity. We present a model for asynchronous distributed computation and then proceed to analyze the convergence of natural asynchronous distributed versions of a large class of deterministic and stochastic gradient-like algorithms. We show that such algorithms retain the desirable convergence properties of their centralized counterparts, provided that the time between consecutive interprocessor communications and the communication delays are not too large. We study a model of opinion dynamics introduced by Krause: each agent has an opinion represented by a real number, and updates its opinion by averaging all agent opinions that differ from its own by less than one. We give a new proof of convergence into clusters of agents, with all agents in the same cluster holding the same opinion. We then introduce a particular notion of equilibrium stability and provide lower bounds on the inter-cluster distances at a stable equilibrium. To better understand the behavior of the system when the number of agents is large, we also introduce and study a variant involving a continuum of agents, obtaining partial convergence results and lower bounds on inter-cluster distances, under some mild assumptions.