On Large Deviation Properties of Erdös–Rényi Random Graphs

We show that large deviation properties of Erdös-Rényi random graphs can be derived from the free energy of the q-state Potts model of statistical mechanics. More precisely the Legendre transform of the Potts free energy with respect to ln q is related to the component generating function of the graph ensemble. This generalizes the well-known mapping between typical properties of random graphs and the q 1 limit of the Potts free energy. For exponentially rare graphs we explicitly calculate the number of components, the size of the giant component, the degree distributions inside and outside the giant component, and the distribution of small component sizes. We also perform numerical simulations which are in very good agreement with our analytical work. Finally we demonstrate how the same results can be derived by studying the evolution of random graphs under the insertion of new vertices and edges, without recourse to the thermodynamics of the Potts model.     

Yang–Lee zeros of the Ising model on random graphs of non planar topology

We obtain in a closed form the 1/N² contribution to the free energy of the two Hermitian N×N random matrix model with nonsymmetric quartic potential. From this result, we calculate numerically the Yang–Lee zeros of the 2D Ising model on dynamical random graphs with the topology of a torus up to n=16 vertices. They are found to be located on the unit circle on the complex fugacity plane. In order to include contributions of even higher topologies we calculated analytically the nonperturbative (sum over all genus) partition function of the model for the special cases of N=1,2 and graphs with n≤20 vertices. Once again the Yang–Lee zeros are shown numerically to lie on the unit circle on the complex fugacity plane. Our results thus generalize previous numerical results on random graphs by going beyond the planar approximation and strongly indicate that there might be a generalization of the Lee–Yang circle theorem for dynamical random graphs.     

Chaos synchronization in networks of coupled maps with time-varying topologies

Complexity of dynamical networks can arise not only from the complexity of the topological structure but also from the time evolution of the topology. In this paper, we study the synchronous motion of coupled maps in time-varying complex networks both analytically and numerically. The temporal variation is rather general and formalized as being driven by a metric dynamical system. Four network models are discussed in detail in which the interconnections between vertices vary through time randomly. These models are: 1) i.i.d. sequences of random graphs with fixed wiring probability, 2) groups of graphs with random switches between the individual graphs, 3) graphs with temporary random failures of nodes, and 4) the meet-for-dinner model where the vertices are randomly grouped. We show that the temporal variation and randomness of the connection topology can enhance synchronizability in many cases; however, there are also instances where they reduce synchronizability. In analytical terms, the Hajnal diameter of the coupling matrix sequence is presented as a measure for the synchronizability of the graph topology. In topological terms, the decisive criterion for synchronization of coupled chaotic maps is that the union of the time-varying graphs contains a spanning tree.     

Network robustness and fragility: percolation on random graphs

Recent work on the Internet, social networks, and the power grid has addressed the resilience of these networks to either random or targeted deletion of network nodes or links. Such deletions include, for example, the failure of Internet routers or power transmission lines. Percolation models on random graphs provide a simple representation of this process but have typically been limited to graphs with Poisson degree distribution at their vertices. Such graphs are quite unlike real-world networks, which often possess power-law or other highly skewed degree distributions. In this paper we study percolation on graphs with completely general degree distribution, giving exact solutions for a variety of cases, including site percolation, bond percolation, and models in which occupation probabilities depend on vertex degree. We discuss the application of our theory to the understanding of network resilience.     

A Sharp Threshold for a Modified Bootstrap Percolation with Recovery

Bootstrap percolation is a type of cellular automaton on graphs, introduced as a simple model of the dynamics of ferromagnetism. Vertices in a graph can be in one of two states: ‘healthy’ or ‘infected’ and from an initial configuration of states, healthy vertices become infected by local rules. While the usual bootstrap processes are monotone in the sets of infected vertices, in this paper, a modification is examined in which infected vertices can return to a healthy state. Vertices are initially infected independently at random and the central question is whether all vertices eventually become infected. The model examined here is such a process on a square grid for which healthy vertices with at least two infected neighbours become infected and infected vertices with no infected neighbours become healthy. Sharp thresholds are given for the critical probability of initial infections for all vertices eventually to become infected.     

Correlated random networks

We develop a statistical theory of networks. A network is a set of vertices and links given by its adjacency matrix c, and the relevant statistical ensembles are defined in terms of a partition function Z= summation operator exp([-betaH(c)]. The simplest cases are uncorrelated random networks such as the well-known Erd?s-Rényi graphs. Here we study more general interactions H(c) which lead to correlations, for example, between the connectivities of adjacent vertices. In particular, such correlations occur in optimized networks described by partition functions in the limit beta--> infinity. They are argued to be a crucial signature of evolutionary design in biological networks.     

Anderson localization for radial tree-like random quantum graphs

We prove that certain random models associated with radial, tree-like, rooted quantum graphs exhibit Anderson localization at all energies. The two main examples are the random length model (RLM) and the random Kirchhoff model (RKM). In the RLM, the lengths of each generation of edges form a family of independent, identically distributed random variables (iid). For the RKM, the iid random variables are associated with each generation of vertices and moderate the current flow through the vertex. We consider extensions to various families of decorated graphs and prove stability of localization with respect to decoration. In particular, we prove Anderson localization for the random necklace model.     

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.     

Network formed by traces of random walks

We propose a model of time evolving networks in which a kind of transport between vertices generates new edges in the graph. We call the model “Network formed by traces of random walks”, because the transports are represented abstractly by random walks. Our numerical calculations yield several important properties observed commonly in complex networks, although the graph at initial time is only a one-dimensional lattice. For example, the distribution of vertex degree exhibits various behaviors such as exponential, power law like, and bi-modal distribution according to change of probability of extinction of edges. Another property such as strong clustering structure and small mean vertex–vertex distance can also be found. The transports represented by random walks in a framework of strong links between regular lattice is a new mechanisms which yields biased acquisition of links for vertices.     

Scale-Free Graph with Preferential Attachment and Evolving Internal Vertex Structure

We extend the classical Barabási-Albert preferential attachment procedure to graphs with internal vertex structure given by weights of vertices. In our model, weight dynamics depends on the current vertex degree distribution and the preferential attachment procedure takes into account both weights and degrees of vertices. We prove that such a coupled dynamics leads to scale-free graphs with exponents depending on parameters of the weight dynamics.     

Planar unclustered scale-free graphs as models for technological and biological networks

Many real life networks present an average path length logarithmic with the number of nodes and a degree distribution which follows a power law. Often these networks have also a modular and self-similar structure and, in some cases — usually associated with topological restrictions — their clustering is low and they are almost planar. In this paper we introduce a family of graphs which share all these properties and are defined by two parameters. As their construction is deterministic, we obtain exact analytic expressions for relevant properties of the graphs including the degree distribution, degree correlation, diameter, and average distance, as a function of the two defining parameters. Thus, the graphs are useful to model some complex networks, in particular several families of technological and biological networks, and in the design of new practical communication algorithms in relation to their dynamical processes. They can also help understanding the underlying mechanisms that have produced their particular structure.     

Principles of statistical mechanics of uncorrelated random networks

We develop a statistical mechanics approach for random networks with uncorrelated vertices. We construct equilibrium statistical ensembles of such networks and obtain their partition functions and main characteristics. We find simple dynamical construction procedures that produce equilibrium uncorrelated random graphs with an arbitrary degree distribution. In particular, we show that in equilibrium uncorrelated networks, fat-tailed degree distributions may exist only starting from some critical average number of connections of a vertex, in a phase with a condensate of edges.     

Theory of rumour spreading in complex social networks

We introduce a general stochastic model for the spread of rumours, and derive mean-field equations that describe the dynamics of the model on complex social networks (in particular, those mediated by the Internet). We use analytical and numerical solutions of these equations to examine the threshold behaviour and dynamics of the model on several models of such networks: random graphs, uncorrelated scale-free networks and scale-free networks with assortative degree correlations. We show that in both homogeneous networks and random graphs the model exhibits a critical threshold in the rumour spreading rate below which a rumour cannot propagate in the system. In the case of scale-free networks, on the other hand, this threshold becomes vanishingly small in the limit of infinite system size. We find that the initial rate at which a rumour spreads is much higher in scale-free networks than in random graphs, and that the rate at which the spreading proceeds on scale-free networks is further increased when assortative degree correlations are introduced. The impact of degree correlations on the final fraction of nodes that ever hears a rumour, however, depends on the interplay between network topology and the rumour spreading rate. Our results show that scale-free social networks are prone to the spreading of rumours, just as they are to the spreading of infections. They are relevant to the spreading dynamics of chain emails, viral advertising and large-scale information dissemination algorithms on the Internet.     

Accuracy and scaling phenomena in Internet mapping

It was recently argued that sampling a network by traversing it with paths from a small number of sources, as with traceroutes on the Internet, creates a fundamental bias in observed topological features like the degree distribution. We examine this bias analytically and experimentally. For Erdo s-Re nyi random graphs with mean degree c, we show analytically that such sampling gives an observed degree distribution P(k) approximately k(-1) for k less, similarc, despite the underlying distribution being Poissonian. For graphs whose degree distributions have power-law tails P(k) approximately k(-alpha), sampling can significantly underestimate alpha when the graph has a large excess (i.e., many more edges than vertices). We find that in order to accurately estimate alpha, one must use a number of sources which grows linearly in the mean degree of the underlying graph. Finally, we comment on the accuracy of the published values of alpha for the Internet.     

Ferromagnetic ordering in graphs with arbitrary degree distribution

We present a detailed study of the phase diagram of the Ising model in random graphs with arbitrary degree distribution. By using the replica method we compute exactly the value of the critical temperature and the associated critical exponents as a function of the moments of the degree distribution. Two regimes of the degree distribution are of particular interest. In the case of a divergent second moment, the system is ferromagnetic at all temperatures. In the case of a finite second moment and a divergent fourth moment, there is a ferromagnetic transition characterized by non-trivial critical exponents. Finally, if the fourth moment is finite we recover the mean field exponents. These results are analyzed in detail for power-law distributed random graphs. Received 4 April 2002 Published online 19 July 2002     

Intrinsic degree-correlations in the static model of scale-free networks

We calculate the mean neighboring degree function and the mean clustering function C(k) of vertices with degree k as a function of k in finite scale-free random networks through the static model. While both are independent of k when the degree exponent γ≥3, they show the crossover behavior for 2 < γ< 3 from k-independent behavior for small k to k-dependent behavior for large k. The k-dependent behavior is analytically derived. Such a behavior arises from the prevention of self-loops and multiple edges between each pair of vertices. The analytic results are confirmed by numerical simulations. We also compare our results with those obtained from a growing network model, finding that they behave differently from each other.     

Phase Transitions on Markovian Bipartite Graphs—an Application of the Zero-range Process

We analyze the existence and the size of the giant component in the stationary state of a Markovian model for bipartite multigraphs, in which the movement of the edge ends on one set of vertices of the bipartite graph is a zero-range process, the degrees being static on the other set. The analysis is based on approximations by independent variables and on the results of Molloy and Reed for graphs with prescribed degree sequences. The possible types of phase diagrams are identified by studying the behavior below the zero-range condensation point. As a specific example, we consider the so-called Evans interaction. In particular, we examine the values of a critical exponent, describing the growth of the giant component as the value of the dilution parameter controlling the connectivity is increased above the critical threshold. Rigorous analysis spans a large portion of the parameter space of the model exactly at the point of zero-range condensation. These results, supplemented with conjectures supported by Monte Carlo simulations, suggest that the phenomenological Landau theory for percolation on graphs is not broken by the fluctuations.     

Core percolation in random graphs: a critical phenomena analysis

We study both numerically and analytically what happens to a random graph of average connectivity α when its leaves and their neighbors are removed iteratively up to the point when no leaf remains. The remnant is made of isolated vertices plus an induced subgraph we call the core. In the thermodynamic limit of an infinite random graph, we compute analytically the dynamics of leaf removal, the number of isolated vertices and the number of vertices and edges in the core. We show that a second order phase transition occurs at α = e = 2.718 ... : below the transition, the core is small but above the transition, it occupies a finite fraction of the initial graph. The finite size scaling properties are then studied numerically in detail in the critical region, and we propose a consistent set of critical exponents, which does not coincide with the set of standard percolation exponents for this model. We clarify several aspects in combinatorial optimization and spectral properties of the adjacency matrix of random graphs. Received 31 January 2001 and Received in final form 26 June 2001     

Dynamical robustness of networks based on betweenness against multi-node attack

We explore the robustness of a network against failures of vertices or edges where a fraction f of vertices is removed and an overload model based on betweenness is constructed. It is assumed that the load and capacity of vertex i are correlated with its betweenness centrality B_i as B_i~θ and(1 + α)Bθi(θ is the strength parameter, α is the tolerance parameter).We model the cascading failures following a local load preferential sharing rule. It is found that there exists a minimal αc when θ is between 0 and 1, and its theoretical analysis is given. The minimal αc characterizes the strongest robustness of a network against cascading failures triggered by removing a random fraction f of vertices. It is realized that the minimalαc increases with the increase of the removal fraction f or the decrease of average degree. In addition, we compare the robustness of networks whose overload models are characterized by degree and betweenness, and find that the networks based on betweenness have stronger robustness against the random removal of a fraction f of vertices.     

Pathlength scaling in graphs with incomplete navigational information

The graph-navigability problem concerns how one can find as short paths as possible between a pair of vertices, given an incomplete picture of a graph. We study the navigability of graphs where the vertices are tagged by a number (between 1 and the total number of vertices) in a way to aid navigation. This information is too little to ensure errorfree navigation but enough, as we will show, for the agents to do significantly better than a random walk. In our setup, given a graph, we first assign information to the vertices that agents can utilize for their navigation. To evaluate the navigation, we calculate the average distance traveled over random pairs of source and target and different graph realizations. We show that this type of embedding can be made quite efficiently; the more information is embedded, the more efficient it gets. We also investigate the embedded navigational information in a standard graph layout algorithm and find that although this information does not make algorithms as efficient as the above-mentioned schemes, it is significantly helpful.