Bootstrap Percolation in Power-Law Random Graphs

A bootstrap percolation process on a graph $G$ is an “infection” process which evolves in rounds. Initially, there is a subset of infected nodes and in each subsequent round each uninfected node which has at least $r$ infected neighbours becomes infected and remains so forever. The parameter $r\ge 2$ is fixed. Such processes have been used as models for the spread of ideas or trends within a network of individuals. We analyse this process in the case where the underlying graph is an inhomogeneous random graph, which exhibits a power-law degree distribution, and initially there are $a(n)$ randomly infected nodes. The main focus of this paper is the number of vertices that will have been infected by the end of the process. The main result of this work is that if the degree sequence of the random graph follows a power law with exponent $\beta $ , where $2 < \beta < 3$ , then a sublinear number of initially infected vertices is enough to spread the infection over a linear fraction of the nodes of the random graph, with high probability. More specifically, we determine explicitly a critical function $a_c(n)$ such that $a_c(n) = o(n)$ with the following property. Assuming that $n$ is the number of vertices of the underlying random graph, if $a(n) \ll a_c(n)$ , then the process does not evolve at all, with high probability as $n$ grows, whereas if $a(n)\gg a_c(n)$ , then there is a constant $\varepsilon > 0$ such that, with high probability, the final set of infected vertices has size at least $\varepsilon n$ . This behaviour is in sharp contrast with the case where the underlying graph is a $G(n, p)$ random graph with $p=d/n$ . It follows from an observation of Balogh and Bollobás that in this case if the number of initially infected vertices is sublinear, then there is lack of evolution of the process. It turns out that when the maximum degree is $o(n^{1/(\beta - 1)})$ , then $a_c(n)$ depends also on $r$ . But when the maximum degree is $\Theta (n^{1/(\beta - 1)})$ , then $a_c (n) = n^{\beta - 2 \over \beta - 1}$ .     

Ising Critical Behavior of Inhomogeneous Curie-Weiss Models and Annealed Random Graphs

We study the critical behavior for inhomogeneous versions of the Curie-Weiss model, where the coupling constant \({J_{ij}(\beta)}\) for the edge \({ij}\) on the complete graph is given by \({J_{ij}(\beta)=\beta w_iw_j/( {\sum_{k\in[N]}w_k})}\). We call the product form of these couplings the rank-1 inhomogeneous Curie-Weiss model. This model also arises [with inverse temperature \({\beta}\) replaced by \({\sinh(\beta)}\) ] from the annealed Ising model on the generalized random graph. We assume that the vertex weights \({(w_i)_{i\in[N]}}\) are regular, in the sense that their empirical distribution converges and the second moment converges as well. We identify the critical temperatures and exponents for these models, as well as a non-classical limit theorem for the total spin at the critical point. These depend sensitively on the number of finite moments of the weight distribution. When the fourth moment of the weight distribution converges, then the critical behavior is the same as on the (homogeneous) Curie-Weiss model, so that the inhomogeneity is weak. When the fourth moment of the weights converges to infinity, and the weights satisfy an asymptotic power law with exponent \({\tau}\) with \({\tau\in(3,5)}\), then the critical exponents depend sensitively on \({\tau}\). In addition, at criticality, the total spin \({S_N}\) satisfies that \({S_N/N^{(\tau-2)/(\tau-1)}}\) converges in law to some limiting random variable whose distribution we explicitly characterize.     

Ising Models on Hyperbolic Graphs II

We consider Ising models with ferromagnetic interactions and zero external magnetic field on the hyperbolic graph (v, f), where v is the number of neighbors of each vertex and f is the number of sides of each face. Let T _c be the critical temperature and T _c =supTT _c: ^f=( ⁺+ ^–)/2, where ^f is the free boundary condition (b.c.) Gibbs state, ⁺ is the plus b.c. Gibbs state and ^– is the minus b.c. Gibbs state. We prove that if the hyperbolic graph is self-dual (i.e., v=f) or if v is sufficiently large (how large depends on f, e.g., v35 suffices for any f3 and v17 suffices for any f17) then 0<T _c <T _c, in contrast with that T _c =T _c for Ising models on the hypercubic lattice Z ^d with d2, a result due to Lebowitz.⁽²²⁾ While whenever T<T _c , ^f=( ⁺+ ^–)/2. The last result is an improvement in comparison with the analogous statement in refs. 28 and 33, in which it was only proved that ^f=( ⁺+ ^–)/2 when TT _c and it remains to show in both papers that ^f =( ⁺+ ^–)/2 whenever T<T _c . Therefore T _c and T _c divide [0, ] into three intervals: [0, T _c ), (T _c , T _c), and (T _c, ] in which ^{+ –} but ^f =( ⁺+ ^–)/2, ^{+ –} and ^f ( ⁺+ ^–)/2, and ⁺= ^–, respectively.     

Cluster Tails for Critical Power-Law Inhomogeneous Random Graphs

Recently, the scaling limit of cluster sizes for critical inhomogeneous random graphs of rank-1 type having finite variance but infinite third moment degrees was obtained in Bhamidi et al. (Ann Probab 40:2299–2361, 2012). It was proved that when the degrees obey a power law with exponent \(\tau \in (3,4)\), the sequence of clusters ordered in decreasing size and multiplied through by \(n^{-(\tau -2)/(\tau -1)}\) converges as \(n\rightarrow \infty \) to a sequence of decreasing non-degenerate random variables. Here, we study the tails of the limit of the rescaled largest cluster, i.e., the probability that the scaling limit of the largest cluster takes a large value u, as a function of u. This extends a related result of Pittel (J Combin Theory Ser B 82(2):237–269, 2001) for the Erd?s–Rényi random graph to the setting of rank-1 inhomogeneous random graphs with infinite third moment degrees. We make use of delicate large deviations and weak convergence arguments.     

Ising Critical Exponents on Random Trees and Graphs

We study the critical behavior of the ferromagnetic Ising model on random trees as well as so-called locally tree-like random graphs. We pay special attention to trees and graphs with a power-law offspring or degree distribution whose tail behavior is characterized by its power-law exponent τ > 2. We show that the critical inverse temperature of the Ising model equals the hyperbolic arctangent of the reciprocal of the mean offspring or mean forward degree distribution. In particular, the critical inverse temperature equals zero when ${\tau \in (2,3]}$ where this mean equals infinity. We further study the critical exponents δ, β and γ, describing how the (root) magnetization behaves close to criticality. We rigorously identify these critical exponents and show that they take the values as predicted by Dorogovstev et al. (Phys Rev E 66:016104, 2002) and Leone et al. (Eur Phys J B 28:191–197, 2002). These values depend on the power-law exponent τ, taking the same values as the mean-field Curie-Weiss model (Exactly solved models in statistical mechanics, Academic Press, London, 1982) for τ > 5, but different values for ${\tau \in (3,5)}$ .     

Sparse Maximum-Entropy Random Graphs with a Given Power-Law Degree Distribution

Even though power-law or close-to-power-law degree distributions are ubiquitously observed in a great variety of large real networks, the mathematically satisfactory treatment of random power-law graphs satisfying basic statistical requirements of realism is still lacking. These requirements are: sparsity, exchangeability, projectivity, and unbiasedness. The last requirement states that entropy of the graph ensemble must be maximized under the degree distribution constraints. Here we prove that the hypersoft configuration model, belonging to the class of random graphs with latent hyperparameters, also known as inhomogeneous random graphs or W-random graphs, is an ensemble of random power-law graphs that are sparse, unbiased, and either exchangeable or projective. The proof of their unbiasedness relies on generalized graphons, and on mapping the problem of maximization of the normalized Gibbs entropy of a random graph ensemble, to the graphon entropy maximization problem, showing that the two entropies converge to each other in the large-graph limit.     

Critical Behavior of the Annealed Ising Model on Random Regular Graphs

In Giardinà et al. (ALEA Lat Am J Probab Math Stat 13(1):121–161, 2016), the authors have defined an annealed Ising model on random graphs and proved limit theorems for the magnetization of this model on some random graphs including random 2-regular graphs. Then in Can (Annealed limit theorems for the Ising model on random regular graphs, arXiv:1701.08639, 2017), we generalized their results to the class of all random regular graphs. In this paper, we study the critical behavior of this model. In particular, we determine the critical exponents and prove a non standard limit theorem stating that the magnetization scaled by \(n^{3/4}\) converges to a specific random variable, with n the number of vertices of random regular graphs.     

Taming Griffiths' Singularities in Long Range Random Ising Models

We study long range random Ising models and develop modified high temperature and strong magnetic field expansions that give decay of truncated correlation functions and uniqueness of Gibbs states, in spite of the presence of Griffiths' singularities. Received: 30 September 1996 / Accepted: 18 February 1997     

Large Deviations for the Annealed Ising Model on Inhomogeneous Random Graphs: Spins and Degrees

Journal of Statistical Physics - We prove a large deviations principle for the total spin and the number of edges under the annealed Ising measure on generalized random graphs. We also give...     

Convergence to Equilibrium of Random Ising Models in the Griffiths Phase

We consider Glauber-type dynamics for disordered Ising spin systems with nearest neighbor pair interactions in the Griffiths phase. We prove that in a nontrivial portion of the Griffiths phase the system has exponentially decaying correlations of distant functions with probability exponentially close to 1. This condition has, in turn, been shown elsewhere to imply that the convergence to equilibrium is faster than any stretched exponential, and that the average over the disorder of the time-autocorrelation function goes to equilibrium faster than exp[–k(log t) ^d/(d–1)]. We then show that for the diluted Ising model these upper bounds are optimal.     

Swarming on Random Graphs

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.     

Inference of Kinetic Ising Model on Sparse Graphs

Based on dynamical cavity method, we propose an approach to the inference of kinetic Ising model, which asks to reconstruct couplings and external fields from given time-dependent output of original system. Our approach gives an exact result on tree graphs and a good approximation on sparse graphs, it can be seen as an extension of Belief Propagation inference of static Ising model to kinetic Ising model. While existing mean field methods to the kinetic Ising inference e.g., naïve mean-field, TAP equation and simply mean-field, use approximations which calculate magnetizations and correlations at time t from statistics of data at time t?1, dynamical cavity method can use statistics of data at times earlier than t?1 to capture more correlations at different time steps. Extensive numerical experiments show that our inference method is superior to existing mean-field approaches on diluted networks.     

Multistage Random Growing Small-World Networks with Power-Law Degree Distribution

We present a simple rule which could generate scale-free networks with very large clustering coefficient and very small average distance. These networks, called the multistage random growing networks （MRGNs）, are constructed by a two-stage adding process for each new node. The analytic results of the power-law exponent = 3 and the clustering coefficient C = 0.81 are obtained, which agree with the simulation results approximately. In addition, we find that the average distance of the networks increases logarithmically with the network size, which is consistent with the theoretical predictions. Since many real-world networks are both scale-free and small-world, the MRGNs may perform well in mimicking reality.     

Corrected Mean-Field Model for Random Sequential Adsorption on Random Geometric Graphs

A notorious problem in mathematics and physics is to create a solvable model for random sequential adsorption of non-overlapping congruent spheres in the d-dimensional Euclidean space with \(d\ge 2\). Spheres arrive sequentially at uniformly chosen locations in space and are accepted only when there is no overlap with previously deposited spheres. Due to spatial correlations, characterizing the fraction of accepted spheres remains largely intractable. We study this fraction by taking a novel approach that compares random sequential adsorption in Euclidean space to the nearest-neighbor blocking on a sequence of clustered random graphs. This random network model can be thought of as a corrected mean-field model for the interaction graph between the attempted spheres. Using functional limit theorems, we characterize the fraction of accepted spheres and its fluctuations.