Spectral Statistics of Erdős-Rényi Graphs II: Eigenvalue Spacing and the Extreme Eigenvalues

We consider the ensemble of adjacency matrices of Erd?s-Rényi random graphs, i.e. graphs on N vertices where every edge is chosen independently and with probability p ≡ p(N). We rescale the matrix so that its bulk eigenvalues are of order one. Under the assumption \({p N \gg N^{2/3}}\), we prove the universality of eigenvalue distributions both in the bulk and at the edge of the spectrum. More precisely, we prove (1) that the eigenvalue spacing of the Erd?s-Rényi graph in the bulk of the spectrum has the same distribution as that of the Gaussian orthogonal ensemble; and (2) that the second largest eigenvalue of the Erd?s-Rényi graph has the same distribution as the largest eigenvalue of the Gaussian orthogonal ensemble. As an application of our method, we prove the bulk universality of generalized Wigner matrices under the assumption that the matrix entries have at least 4 + ε moments.     

Central Limit Theorems for Linear Statistics of Heavy Tailed Random Matrices

We show central limit theorems (CLT) for the linear statistics of symmetric matrices with independent heavy tailed entries, including entries in the domain of attraction of α-stable laws and entries with moments exploding with the dimension, as in the adjacency matrices of Erdös-Rényi graphs. For the second model, we also prove a central limit theorem of the moments of its empirical eigenvalues distribution. The limit laws are Gaussian, but unlike the case of standard Wigner matrices, the normalization is the one of the classical CLT for independent random variables.     

Generating Simple Random Graphs with Prescribed Degree Distribution

Let F be a probability distribution with support on the non-negative integers. Four methods for generating a simple undirected graph with (approximate) degree distribution F are described and compared. Two methods are based on the so called configuration model with modifications ensuring a simple graph, one method is an extension of the classical Erdös-Rényi graph where the edge probabilities are random variables, and the last method starts with a directed random graph which is then modified to a simple undirected graph. All methods are shown to give the correct distribution in the limit of large graph size, but under different assumptions on the degree distribution F and also using different order of operations.     

Erdős-Rényi laws for Gibbs measures

Can one detect a phase transition from a single, large sample of a Gibbs measure? What information does one get on the other Gibbs distributions with the same potential? We approach these questions via Erd?s-Rényi laws. In particular we prove almost-sure limit theorems for sets of empirical distributions of sub-samples of the given one: for suitable sub-samples size this set converges to the set of stationary Gibbs measures. Moreover we formulate Erd?s-Rényi laws for general families of random variables with suitable large deviation principles.     

Effects of heterogeneous adoption thresholds on contact-limited social contagions

Limited contact capacity and heterogeneous adoption thresholds have been proven to be two essential characteristics of individuals in natural complex social systems, and their impacts on social contagions exhibit complex nature. With this in mind, a heterogeneous contact-limited threshold model is proposed, which adopts one of four threshold distributions, namely Gaussian distribution, log-normal distribution, exponential distribution and power-law distribution. The heterogeneous edge-based compartmental theory is developed for theoretical analysis, and the calculation methods of the final adoption size and outbreak threshold are given theoretically. Many numerical simulations are performed on the Erdös-Rényi and scale-free networks to study the impact of different forms of the threshold distribution on hierarchical spreading process, the final adoption size, the outbreak threshold and the phase transition in contact-limited propagation networks. We find that the spreading process of social contagions is divided into three distinct stages. Moreover, different threshold distributions cause different spreading processes, especially for some threshold distributions, there is a change from a discontinuous first-order phase transition to a continuous second-order phase transition. Further, we find that changing the standard deviation of different threshold distributions will cause the final adoption size and outbreak threshold to change, and finally tend to be stable with the increase of standard deviation.     

Modelling epidemics on networks

Infectious disease remains, despite centuries of work to control and mitigate its effects, a major problem facing humanity. This paper reviews the mathematical modelling of infectious disease epidemics on networks, starting from the simplest Erdös–Rényi random graphs, and building up structure in the form of correlations, heterogeneity and preference, paying particular attention to the links between random graph theory, percolation and dynamical systems representing transmission. Finally, the problems posed by networks with a large number of short closed loops are discussed.     

Networks of noisy oscillators with correlated degree and frequency dispersion

We investigate how correlations between the diversity of the connectivity of networks andthe dynamics at their nodes affect the macroscopic behavior. In particular, we study thesynchronization transition of coupled stochastic phase oscillators that represent the nodedynamics. Crucially in our work, the variability in the number of connections of the nodesis correlated with the width of the frequency distribution of the oscillators. Bynumerical simulations on Erdös-Rényi networks, where the frequencies of the oscillatorsare Gaussian distributed, we make the counterintuitive observation that an increase in thestrength of the correlation is accompanied by an increase in the critical couplingstrength for the onset of synchronization. We further observe that the critical couplingcan solely depend on the average number of connections or even completely lose itsdependence on the network connectivity. Only beyond this state, a weighted mean-fieldapproximation breaks down. If noise is present, the correlations have to be stronger toyield similar observations.     

Solving the undirected feedback vertex set problem by local search

An undirected graph consists of a set of vertices and a set of undirected edges between vertices. Such a graph may contain an abundant number of cycles, in which case a feedback vertex set (FVS) is a set of vertices intersecting with each of these cycles. Constructing a FVS of cardinality approaching the global minimum value is an optimization problem in the nondeterministic polynomial-complete complexity class, and therefore it might be extremely difficult for some large graph instances. In this paper we develop a simulated annealing local search algorithm for the undirected FVS problem by adapting the heuristic procedure of Galinier et al. [P. Galinier, E. Lemamou, M.W. Bouzidi, J. Heuristics 19, 797 (2013)], which worked for the directed FVS problem. By defining an order for the vertices outside the FVS, we replace the global cycle constraints by a set of local vertex constraints on this order. Under these local constraints the cardinality of the focal FVS is then gradually reduced by the simulated annealing dynamical process. We test this heuristic algorithm on large instances of Erdös-Rényi random graph and regular random graph, and find that this algorithm is comparable in performance to the belief propagation-guided decimation algorithm.     

Triangle Percolation in Mean Field Random Graphs—with PDE

We apply a PDE-based method to deduce the critical time and the size of the giant component of the “triangle percolation” on the Erdős-Rényi random graph process investigated by Derényi, Palla and Vicsek in (Phys. Rev. Lett. 94:160202, [2005]; J. Stat. Phys. 128:219–227, [2007]).     

On Connected Diagrams and Cumulants of Erdős-Rényi Matrix Models

Regarding the adjacency matrices of n-vertex graphs and related graph Laplacian we introduce two families of discrete matrix models constructed both with the help of the Erdős-Rényi ensemble of random graphs. Corresponding matrix sums represent the characteristic functions of the average number of walks and closed walks over the random graph. These sums can be considered as discrete analogues of the matrix integrals of random matrix theory. We study the diagram structure of the cumulant expansions of logarithms of these matrix sums and analyze the limiting expressions as n → ∞ in the cases of constant and vanishing edge probabilities.     

基于相继故障信息的网络节点重要度演化机理分析

分析了过载机制下节点重要度的演化机理.首先,在可调负载重分配级联失效模型基础上,根据节点失效后其分配范围内节点的负载振荡程度,提出了考虑级联失效局域信息的复杂网络节点重要度指标.该指标具有两个特点:一是值的大小可以清晰地指出节点的失效后果;二是可以依据网络负载分配范围、负载分配均匀性、节点容量系数及网络结构特征分析节点重要度的演化情况.然后,给出该指标的仿真算法,并推导了最近邻择优分配和全局择优分配规则下随机网络和无标度网络节点重要度的解析表达式.最后,实验验证了该指标的有效性和可行性,并深入分析了网络中节点重要度的演化机理,即非关键节点如何演化成影响网络级联失效行为的关键节点.     

Stability and dynamical properties of material flow systems on random networks

The theory of complex networks and of disordered systems is used to study the stability and dynamical properties of a simple model of material flow networks defined on random graphs. In particular we address instabilities that are characteristic of flow networks in economic, ecological and biological systems. Based on results from random matrix theory, we work out the phase diagram of such systems defined on extensively connected random graphs, and study in detail how the choice of control policies and the network structure affects stability. We also present results for more complex topologies of the underlying graph, focussing on finitely connected Erdös-Réyni graphs, Small-World Networks and Barabási-Albert scale-free networks. Results indicate that variability of input-output matrix elements, and random structures of the underlying graph tend to make the system less stable, while fast price dynamics or strong responsiveness to stock accumulation promote stability.     

Transport between multiple users in complex networks

We study the transport properties of model networks such as scale-free and Erd?s-Rényi networks as well as a real network. We consider few possibilities for the trnasport problem. We start by studying the conductance G between two arbitrarily chosen nodes where each link has the same unit resistance. Our theoretical analysis for scale-free networks predicts a broad range of values of G, with a power-law tail distribution $\Phi_{\rm SF}(G)\sim G^{-g_G}$ , where g_G=2λ-1, and λ is the decay exponent for the scale-free network degree distribution. The power-law tail in Φ_SF(G) leads to large values of G, thereby significantly improving the transport in scale-free networks, compared to Erd?s-Rényi networks where the tail of the conductivity distribution decays exponentially. We develop a simple physical picture of the transport to account for the results. The other model for transport is the max-flow model, where conductance is defined as the number of link-independent paths between the two nodes, and find that a similar picture holds. The effects of distance on the value of conductance are considered for both models, and some differences emerge. We then extend our study to the case of multiple sources ans sinks, where the transport is defined between two groups of nodes. We find a fundamental difference between the two forms of flow when considering the quality of the transport with respect to the number of sources, and find an optimal number of sources, or users, for the max-flow case. A qualitative (and partially quantitative) explanation is also given.     

Nonlinear signal transduction network with multistate

Signal transduction is an important and basic mechanism to cell life activities. The stochastic state transition of receptor induces the release of signaling molecular, which triggers the state transition of other receptors. It constructs a nonlinear sigaling network, and leads to robust switchlike properties which are critical to biological function. Network architectures and state transitions of receptor affect the performance of this biological network. In this work, we perform a study of nonlinear signaling on biological polymorphic network by analyzing network dynamics of the Ca²⁺-induced Ca²⁺ release (CICR) mechanism, where fast and slow processes are involved and the receptor has four conformational states. Three types of networks, Erdös-Rényi (ER) network, Watts-Strogatz (WS) network, and BaraBási-Albert (BA) network, are considered with different parameters. The dynamics of the biological networks exhibit different patterns at different time scales. At short time scale, the second open state is essential to reproduce the quasi-bistable regime, which emerges at a critical strength of connection for all three states involved in the fast processes and disappears at another critical point. The pattern at short time scale is not sensitive to the network architecture. At long time scale, only monostable regime is observed, and difference of network architectures affects the results more seriously. Our finding identifies features of nonlinear signaling networks with multistate that may underlie their biological function.     

Transitions in spatial networks

Networks embedded in space can display all sorts of transitions when their structure is modified. The nature of these transitions (and in some cases crossovers) can differ from the usual appearance of a giant component as observed for the Erdös–Rényi graph, and spatial networks display a large variety of behaviors. We will discuss here some (mostly recent) results about topological transitions, ‘localization’ transitions seen in the shortest paths pattern, and also about the effect of congestion and fluctuations on the structure of optimal networks. The importance of spatial networks in real-world applications makes these transitions very relevant, and this review is meant as a step towards a deeper understanding of the effect of space on network structures.     

Evolution of imitation networks in Minority Game model

The Minority Game is adapted to study the “imitation dilemma”, i.e. the tradeoff between local benefit and global harm coming from imitation. The agents are placed on a substrate network and are allowed to imitate more successful neighbours. Imitation domains, which are oriented trees, are formed. We investigate size distribution of the domains and in-degree distribution within the trees. We use four types of substrate: one-dimensional chain; Erd?s-Rényi graph; Barabási-Albert scale-free graph; Barabási-Albert 'model A' graph. The behaviour of some features of the imitation network strongly depend on the information cost epsilon, which is the percentage of gain the imitators must pay to the imitated. Generally, the system tends to form a few domains of equal size. However, positive epsilon makes the system stay in a long-lasting metastable state with complex structure. The in-degree distribution is found to follow a power law in two cases of those studied: for Erd?s-Rényi substrate for any epsilon and for Barabási-Albert scale-free substrate for large enough epsilon. A brief comparison with empirical data is provided.     

Die Anwendung von 77Ge-markierten germaniumorganischen Verbindungen zur Untersuchung von Materialflüssen in Erdöverarbeitungsanlagen

Für Traceruntersuchungen in der erdölverarbeitenden Industrie wird der Einsatz von ⁷⁷Ge-markierten germaniumorganischen Verbindungen vorgeschlagen. Mit Hilfe von ⁷⁷Ge-markierten Germaniumtetraäthyl werden die Zirkulationszeit des Rücklaufs und die Verdampfungszeit der Erdölfraktionen auf den entsprechenden Stufen der Destillationskolonnen sowie mit ⁷⁷Ge-markiertem Germanium-tetra-n-amyl die lineare Geschwindigkeit des Erdöls in den einzelnen Sektionen des Vorheizers bestimmt.     

Infinite Systems of Interacting Chains with Memory of Variable Length—A Stochastic Model for Biological Neural Nets

We consider a new class of non Markovian processes with a countable number of interacting components. At each time unit, each component can take two values, indicating if it has a spike or not at this precise moment. The system evolves as follows. For each component, the probability of having a spike at the next time unit depends on the entire time evolution of the system after the last spike time of the component. This class of systems extends in a non trivial way both the interacting particle systems, which are Markovian (Spitzer in Adv. Math. 5:246–290, 1970) and the stochastic chains with memory of variable length which have finite state space (Rissanen in IEEE Trans. Inf. Theory 29(5):656–664, 1983). These features make it suitable to describe the time evolution of biological neural systems. We construct a stationary version of the process by using a probabilistic tool which is a Kalikow-type decomposition either in random environment or in space-time. This construction implies uniqueness of the stationary process. Finally we consider the case where the interactions between components are given by a critical directed Erdös-Rényi-type random graph with a large but finite number of components. In this framework we obtain an explicit upper-bound for the correlation between successive inter-spike intervals which is compatible with previous empirical findings.     

Mean Field Frozen Percolation

We define a modification of the Erd?s-Rényi random graph process which can be regarded as the mean field frozen percolation process. We describe the behavior of the process using differential equations and investigate their solutions in order to show the self-organized critical and extremum properties of the critical frozen percolation model. We prove two limit theorems about the distribution of the size of the component of a typical frozen vertex.     

Antiferromagnetic Potts Model on the Erdős-Rényi Random Graph

We study the antiferromagnetic Potts model on the Poissonian Erd?s-Rényi random graph. By identifying a suitable interpolation structure and an extended variational principle, together with a positive temperature second-moment analysis we prove the existence of a phase transition at a positive critical temperature. Upper and lower bounds on the temperature critical value are obtained from the stability analysis of the replica symmetric solution (recovered in the framework of Derrida-Ruelle probability cascades) and from an entropy positivity argument.