TITLE

# Swarming on Random Graphs

AUTHOR(S)
Brecht, James; Kolokolnikov, Theodore; Bertozzi, Andrea; Sun, Hui
PUB. DATE
April 2013
SOURCE
Journal of Statistical Physics;Apr2013, Vol. 151 Issue 1/2, p150
SOURCE TYPE
DOC. TYPE
Article
ABSTRACT
We consider a compromise model in one dimension in which pairs of agents interact through first-order dynamics that involve both attraction and repulsion. In the case of all-to-all coupling of agents, this system has a lowest energy state in which half of the agents agree upon one value and the other half agree upon a different value. The purpose of this paper is to study the behavior of this compromise model when the interaction between the N agents occurs according to an ErdÅ‘s-RÃ©nyi random graph $\mathcal{G}(N,p)$. We study the effect of changing p on the stability of the compromised state, and derive both rigorous and asymptotic results suggesting that the stability is preserved for probabilities greater than $p_{c}=O(\frac{\log N}{N})$. In other words, relatively few interactions are needed to preserve stability of the state. The results rely on basic probability arguments and the theory of eigenvalues of random matrices.
ACCESSION #
86449479

## Related Articles

• The Tracyâ€“Widom Law for Some Sparse Random Matrices. Sodin, Sasha // Journal of Statistical Physics;Sep2009, Vol. 136 Issue 5, p834

Consider the random matrix obtained from the adjacency matrix of a random d-regular graph by multiplying every entry by a random sign. The largest eigenvalue converges, after proper scaling, to the Tracyâ€“Widom distribution.

• Low eigenvalues of Laplacian matrices of large random graphs. Jiang, Tiefeng // Probability Theory & Related Fields;Aug2012, Vol. 153 Issue 3/4, p671

For each n â‰¥ 2, let A = ( Î¾) be an n Ã— n symmetric matrix with diagonal entries equal to zero and the entries in the upper triangular part being independent with mean Î¼ and standard deviation Ïƒ. The Laplacian matrix is defined by {{\bf \Delta}_n={\rm...

• The Integrated Density of States of the Random Graph Laplacian. Aspelmeier, T.; Zippelius, A. // Journal of Statistical Physics;Aug2011, Vol. 144 Issue 4, p759

We analyse the density of states of the random graph Laplacian in the percolating regime. A symmetry argument and knowledge of the density of states in the nonpercolating regime allows us to isolate the density of states of the percolating cluster (DSPC) alone, thereby eliminating trivially...

• Insensitive dependence of delay-induced oscillation death on complex networks. Zou, Wei; Zheng, Xing; Zhan, Meng // Chaos;Jun2011, Vol. 21 Issue 2, p023130

Oscillation death (also called amplitude death), a phenomenon of coupling induced stabilization of an unstable equilibrium, is studied for an arbitrary symmetric complex network with delay-coupled oscillators, and the critical conditions for its linear stability are explicitly obtained. All...

• Gap probability in the spectrum of random matrices and asymptotics of polynomials orthogonal on an arc of the unit circle. Krasovsky, I. V. // IMRN: International Mathematics Research Notices;2004, Vol. 2004 Issue 25, p1249

We obtain uniform asymptotics for polynomials orthogonal on a fixed and varying arc of the unit circle with a positive analytic weight function. We also complete the proof of the large s asymptotic expansion for the Fredholm determinant with the kernel sinz/(Ï€ z) on the interval [0,s],...

• Dynamically Consistent Non-Standard Finite Difference Schemes for the MSEIR Epidemiological Model. Anguelov, Roumen; Dumont, Yves; Lubuma, Jean M.-S.; Shillor, Meir // AIP Conference Proceedings;9/9/2009, Vol. 1168 Issue 1, p1213

We construct a family of non-standard finite difference schemes that are dynamically consistent with the MSEIR model in the sense that they replicate the global asymptotic stability of the disease-free equilibrium, the local asymptotic stability of the endemic equilibrium, as well as the...

• Multicanonical MCMC for sampling rare events: an illustrative review. Iba, Yukito; Saito, Nen; Kitajima, Akimasa // Annals of the Institute of Statistical Mathematics;Jun2014, Vol. 66 Issue 3, p611

Multicanonical MCMC (Multicanonical Markov Chain Monte Carlo; Multicanonical Monte Carlo) is discussed as a method of rare event sampling. Starting from a review of the generic framework of importance sampling, multicanonical MCMC is introduced, followed by applications in random matrices,...

• Random Leslie matrices in population dynamics. C�ceres, Manuel O.; C�ceres-Saez, Iris // Journal of Mathematical Biology;Sep2011, Vol. 63 Issue 3, p519

We generalize the concept of the population growth rate when a Leslie matrix has random elements (correlated or not), i.e., characterizing the disorder in the vital parameters. In general, we present a perturbative formalism to deal with linear non-negative random matrix difference equations,...

• UNIVERSAL SPECTRAL SHOCKS IN RANDOM MATRIX THEORY -- LESSONS FOR QCD. BLAIZOT, JEAN-PAUL; GRELA, JACEK; NOWAK, MACIEJ A.; WARCHOŁ, PIOTR // Acta Physica Polonica B;Sep2015, Vol. 46 Issue 9, p1785

Following Dyson, we treat the eigenvalues of a random matrix as a system of particles undergoing random walks. The dynamics of large matrices is then well-described by fluid dynamical equations. In particular, the inviscid Burgers' equation is ubiquitous and controls the behavior of the spectral...

Share