Continuous random networks from graphs to glasses

The direct connection between the structure of amorphous materials, modelled geometrically by graphs, and their physical properties is demonstrated. The structural and physical differences between glasses and crystals are emphasized.     

Polymers and random graphs

We establish a precise connection between gelation of polymers in Lushnikov's model and the emergence of the giant component in random graph theory. This is achieved by defining a modified version of the Erdös-Rényi process; when contracting to a polymer state space, this process becomes a discrete-time Markov chain embedded in Lushnikov's process. The asymptotic distribution of the number of transitions in Lushnikov's model is studied. A criterion for a general Markov chain to retain the Markov property under the grouping of states is derived. We obtain a noncombinatorial proof of a theorem of Erdös-Rényi type.     

Dependence of the average to-node distance on the node degree for random graphs and growing networks

In a connected graph, nodes can be characterised locally (with their degree k) or globally (e.g. with their average length path to other nodes). Here we investigate how depends on k. The numerical algorithm based on the construction of the distance matrix is applied to random graphs and the growing networks: the scale-free ones and the exponential ones. The results are relevant for search strategies in different networks.Received: 15 June 2004, Published online: 21 October 2004PACS: 02.10.Ox Combinatorics; graph theory - 05.10.-a Computational methods in statistical physics and nonlinear dynamics     

Scale-free random graphs and Potts model

We introduce a simple algorithm that constructs scale-free random graphs efficiently: each vertexi has a prescribed weight P_i ∝ i^-μ (0 < μ< 1) and an edge can connect verticesi andj with rateP _i P _j . Corresponding equilibrium ensemble is identified and the problem is solved by theq → 1 limit of the q-state Potts model with inhomogeneous interactions for all pairs of spins. The number of loops as well as the giant cluster size and the mean cluster size are obtained in the thermodynamic limit as a function of the edge density. Various critical exponents associated with the percolation transition are also obtained together with finite-size scaling forms. The process of forming the giant cluster is qualitatively different between the cases of λ > 3 and 2 < λ < 3, whereλ = 1 +μ ^-1 is the degree distribution exponent. While for the former, the giant cluster forms abruptly at the percolation transition, for the latter, however, the formation of the giant cluster is gradual and the mean cluster size for finiteN shows double peaks.     

Polymers and random graphs: Asymptotic equivalence to branching processes

In 1974, Falk and Thomas did a computer simulation of Flory's Equireactive RA _f Polymer model, rings forbidden and rings allowed. Asymptotically, the Rings Forbidden model tended to Stockmayer's RA _f distribution (in which the sol distribution sticks after gelation), while the Rings Allowed model tended to the Flory version of the RA _f distribution. In 1965, Whittle introduced the Tree and Pseudomultigraph models. We show that these random graphs generalize the Falk and Thomas models by incorporating first-shell substitution effects. Moreover, asymptotically the Tree model displays postgelation sticking. Hence this phenomenon results from the absence of rings and occurs independently of equireactivity. We also show that the Pseudomultigraph model is asymptotically identical to the Branching Process model introduced by Gordon in 1962. This provides a possible basis for the Branching Process model in standard statistical mechanics.     

Localization of eigenvectors in random graphs

We consider spatial organization of point defects in the generalized model of defects formation in elastic medium by taking into account defects production by irradiation influence and stochastic contribution for defects dynamics satisfying the fluctuation dissipation relation. We have found that depending on initial conditions and control parameters reduced to defects generation rate caused by irradiation, temperature and the stochastic source intensity different stationary structures of defects can be organized during the system evolution. Studying phase transitions between phases characterized by low- and high defect densities in stochastic system we have shown that such phenomena are described by mechanisms inherent in entropy-driven phase transitions. Stationary patterns are studied by amplitude analysis of unstable slow modes.     

The statistics of random directed graphs

The analysis of random graphs developed by the author, principally as a model for polymerization processes, is extended to the case of directed random graphs, with models of neural nets in mind. The principal novelty of the directed case is the representation of the partition function by a complex rather than a real integral, and the replacement of simple maxima in asymptotic evaluations by an interesting form of saddle point.     

Scale-free networks via attaching to random neighbors

Preferential attachment is considered one of the key factors in the formation of scale-free networks. However, complete random attachment without a preferential mechanism can also generate scale-free networks in nature, such as protein interaction networks in cells. This article presents a new scale-free network model that applies the following general mechanisms: (i) networks expand continuously by the addition of new vertices, and (ii) new vertices attach to random neighbors of random vertices that are already well connected. The proposed model does not require global-based preferential strategies and utilizes only the random attachment method. Theoretical analysis and numerical simulation results denote that the proposed model has steady scale-free network characteristics, and random attachment without a preferential mechanism may generate scale-free networks.     

Maximal spanning trees,asset graphs and random matrix denoising in the analysis of dynamics of financial networks

We study the time dependence of maximal spanning trees and asset graphs based on correlation matrices of stock returns. In these networks the nodes represent companies and links are related to the correlation coefficients between them. Special emphasis is given to the comparison between ordinary and denoised correlation matrices. The analysis of single- and multi-step survival ratios of the corresponding networks reveals that the ordinary correlation matrices are more stable in time than the denoised ones. Our study also shows that some information about the cluster structure of the companies is lost in the denoising procedure. Cluster structure that makes sense from an economic point of view exists, and can easily be observed in networks based on denoised correlation matrices. However, this structure is somewhat clearer in the networks based on ordinary correlation matrices. Some technical aspects, such as the random matrix denoising procedure, are also presented.     

Dynamics of excitable nodes on random graphs

We study the interplay of topology and dynamics of excitable nodes on random networks. Comparison is made between systems grown by purely random (Erdős–Rényi) rules and those grown by the Achlioptas process. For a given size, the growth mechanism affects both the thresholds for the emergence of different structural features as well as the level of dynamical activity supported on the network.     

Synchronizability of dynamical scale-free networks subject to random errors

In this paper the robustness of network synchronizability against random deletion of nodes, i.e. errors, in dynamical scale-free networks was studied. To this end, two measures of network synchronizability, namely, the eigenratio of the Laplacian and the order parameter quantifying the degree of phase synchrony were adopted, and the synchronizability robustness on preferential attachment scale-free graphs was investigated. The findings revealed that as the network size decreases, the robustness of its synchronizability against random removal of nodes declines, i.e. the more the number of randomly removed nodes from the network, the worse its synchronizability. We also showed that this dependence of the synchronizability on the network size is different with that in the growing scale-free networks. The profile of a number of network properties such as clustering coefficient, efficiency, assortativity, and eccentricity, as a function of the network size was investigated in these two cases, growing scale-free networks and those with randomly removed nodes. The results showed that these processes are also different in terms of these metrics.     

Euler characteristic and related measures for random geometric sets

By an elementary calculation we obtain the exact mean values of Minkowksi functionals for a standard model of percolating sets. In particular, a recurrence theorem for the mean Euler characteristic recently put forward is shown to be incorrect. Related previous mathematical work is mentioned. We also conjecture bounds for the threshold density of continuum percolation, which are associated with the Euler characteristic.     

Connectivity of growing random networks

A solution for the time- and age-dependent connectivity distribution of a growing random network is presented. The network is built by adding sites that link to earlier sites with a probability A(k) which depends on the number of preexisting links k to that site. For homogeneous connection kernels, A(k) approximately k(gamma), different behaviors arise for gamma<1, gamma>1, and gamma = 1. For gamma<1, the number of sites with k links, N(k), varies as a stretched exponential. For gamma>1, a single site connects to nearly all other sites. In the borderline case A(k) approximately k, the power law N(k) approximately k(-nu) is found, where the exponent nu can be tuned to any value in the range 2相似文献   

Localization transition of biased random walks on random networks

We study random walks on large random graphs that are biased towards a randomly chosen but fixed target node. We show that a critical bias strength bc exists such that most walks find the target within a finite time when b > bc. For b < bc, a finite fraction of walks drift off to infinity before hitting the target. The phase transition at b=bc is a critical point in the sense that quantities such as the return probability P(t) show power laws, but finite-size behavior is complex and does not obey the usual finite-size scaling ansatz. By extending rigorous results for biased walks on Galton-Watson trees, we give the exact analytical value for bc and verify it by large scale simulations.     

Large-deviation properties of largest component for random graphs

Distributions of the size of the largest component, in particular the large-deviationtail, are studied numerically for two graph ensembles, for Erdös-Rényi random graphs withfinite connectivity and for two-dimensional bond percolation. Probabilities as small as10^-180 are accessed using an artificial finite-temperature (Boltzmann)ensemble. The distributions for the Erdös-Rényi ensemble agree well with previouslyobtained analytical results. The results for the percolation problem, where no analyticalresults are available, are qualitatively similar, but the shapes of the distributions aresomehow different and the finite-size corrections are sometimes much larger. Furthermore,for both problems, a first-order phase transition at low temperatures Twithin the artificial ensemble is found in the percolating regime, respectively.     

Tapping spin glasses and ferromagnets on random graphs.

We consider a tapping dynamics, analogous to that in experiments on granular media, on spin glasses and ferromagnets on random thin graphs. Between taps, zero temperature single spin flip dynamics takes the system to a metastable state. Tapping corresponds to flipping simultaneously any spin with probability p. This dynamics leads to a stationary regime with a steady state energy E(p). We analytically solve this dynamics for the one-dimensional ferromagnet and +/-J spin glass. Numerical simulations for spin glasses and ferromagnets of higher connectivity are carried out; in particular, we find a novel first order transition for the ferromagnetic systems.     

Dynamics of heuristic optimization algorithms on random graphs

In this paper, the dynamics of heuristic algorithms for constructing small vertex covers (or independent sets) of finite-connectivity random graphs is analysed. In every algorithmic step, a vertex is chosen with respect to its vertex degree. This vertex, and some environment of it, is covered and removed from the graph. This graph reduction process can be described as a Markovian dynamics in the space of random graphs of arbitrary degree distribution. We discuss some solvable cases, including algorithms already analysed using different techniques, and develop approximation schemes for more complicated cases. The approximations are corroborated by numerical simulations. Received 14 March 2002 Published online 31 July 2002     

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.