Uncorrelated Random Networks

Abstract

We define a statistical ensemble of non-degenerate graphs, i.e. graphs without multiple- and self-connections between nodes. The node degree distribution is arbitrary, but the nodes are assumed to be uncorrelated. This completes our earlier publication \cite{bck}, where trees and degenerate graphs were considered. An efficient algorithm generating non-degenerate graphs is constructed. The corresponding computer code is available on request. Finite-size effects in scale-free graphs, i.e. those where the tail of the degree distribution falls like $n^{-\beta }$, are carefully studied. We find that in the absence of dynamical internode correlations the degree distribution is cut at a degree value scaling like $N^{\gamma }$, with $\gamma =\min [1/2,1/(\beta -1)]$, where $N$ is the total number of nodes. The consequence is that, independently of any specific model, the inter-node correlations seem to be a necessary ingredient of the physics of scale-free networks observed in nature.

7 pages, 4 eps figures, 2-column revtex format, final corrections before publication

References in corpus (3)

• Statistical mechanics of complex networks
• Evolution of networks
• Statistical ensemble of scale-free random graphs

Cited by in corpus (54)

• Critical phenomena in complex networks
• Generation of uncorrelated random scale-free networks
• The Statistical Physics of Real-World Networks
• Percolation on complex networks: Theory and application
• Cut-offs and finite size effects in scale-free networks
• Spectra of complex networks
• Optimization of Robustness of Complex Networks
• Efficient and exact sampling of simple graphs with given arbitrary degree sequence
• Clustering in complex networks. I. General formalism
• Tuning clustering in random networks with arbitrary degree distributions
• Local structure of directed networks
• Network Transitivity and Matrix Models
• Loops of any size and Hamilton cycles in random scale-free networks
• Evolution of scale-free random graphs: Potts model formulation
• Percolation transition in networks with degree-degree correlation
• Resilience of Complex Networks to Random Breakdown
• Synchronization in Weighted Uncorrelated Complex Networks in a Noisy Environment: Optimization and Connections with Transport Efficiency
• Statistical mechanics of topological phase transitions in networks
• Homogeneous complex networks
• Loops structure of the Internet at the Autonomous System Level
• Routes to thermodynamic limit on scale-free networks
• Scale-free networks with exponent one
• Bosonic reaction-diffusion processes on scale-free networks
• Topological phase transitions of random networks
• Correlations in connected random graphs
• Optimization of Network Robustness to Random Breakdowns
• A statistical mechanics approach for scale-free networks and finite-scale networks
• Percolation theory applied to measures of fragmentation in social networks
• Bounding network spectra for network design
• Clustering of random scale-free networks
• Algorithm for counting large directed loops
• Complex networks created by aggregation
• Perturbing General Uncorrelated Networks
• Fluctuation-dissipation relations for complex networks
• Hidden Variables in Bipartite Networks
• Organization of complex networks without multiple connections
• Statistical Mechanics of Multi-Edge Networks
• Probabilistic prediction in scale-free networks: Diameter changes
• Finite size effects in Barabasi-Albert growing networks
• Percolation and Loop Statistics in Complex Networks
• Statistical mechanics of scale-free networks at a critical point: Complexity without irreversibility?
• Statistical mechanics of random graphs
• Power laws in zero-range processes on random networks
• Statistical mechanics of coevolving spin system
• Generation of scale-free networks using a simple preferential rewiring dynamics
• A Statistical Mechanical Load Balancer for the Web
• Boolean decision problems with competing interactions on scale-free networks: Critical thermodynamics
• Approaching the thermodynamic limit in equilibrated scale-free networks
• Finite-size scaling of percolation on scale-free networks
• A program generating homogeneous random graphs with given weights
• Reverse engineering of linking preferences from network restructuring
• Boolean decision problems with competing interactions on scale-free networks: Equilibrium and nonequilibrium behavior in an external bias
• Random walk with priorities in communication-like networks
• Impact of Random Failures and Attacks on Poisson and Power-Law Random Networks