Statistical ensemble of scale-free random graphs

Abstract

A thorough discussion of the statistical ensemble of scale-free connected random tree graphs is presented. Methods borrowed from field theory are used to define the ensemble and to study analytically its properties. The ensemble is characterized by two global parameters, the fractal and the spectral dimensions, which are explicitly calculated. It is discussed in detail how the geometry of the graphs varies when the weights of the nodes are modified. The stability of the scale-free regime is also considered: when it breaks down, either a scale is spontaneously generated or else, a "singular" node appears and the graphs become crumpled. A new computer algorithm to generate these random graphs is proposed. Possible generalizations are also discussed. In particular, more general ensembles are defined along the same lines and the computer algorithm is extended to arbitrary (degenerate) scale-free random graphs.

10 pages, 6 eps figures, 2-column revtex format, minor corrections

Cited by in corpus (92)

• Statistical mechanics of complex networks
• The structure and function of complex networks
• Evolution of networks
• Critical phenomena in complex networks
• Self-similarity of complex networks
• The statistical mechanics of networks
• Nonequilibrium Statistical Mechanics of the Zero-Range Process and Related Models
• Network Synchronization, Diffusion, and the Paradox of Heterogeneity
• Pseudofractal Scale-free Web
• Percolation on complex networks: Theory and application
• Average path length in random networks
• Average path length in uncorrelated random networks with hidden variables
• Percolation Critical Exponents in Scale-Free Networks
• The entropy of network ensembles
• Skeleton and fractal scaling in complex networks
• The entropy of randomized network ensembles
• Subgraphs in random networks
• Maximum likelihood: extracting unbiased information from complex networks
• Correlated random networks
• Fractality in complex networks: critical and supercritical skeletons
• Canonical Analysis of Condensation in Factorised Steady State
• Entropy of stochastic blockmodel ensembles
• Finiteness and Fluctuations in Growing Networks
• Sampling properties of random graphs: the degree distribution
• Network Transitivity and Matrix Models
• A box-covering algorithm for fractal scaling in scale-free networks
• Uncorrelated Random Networks
• Shortest paths and load scaling in scale-free trees
• Recent advances of percolation theory in complex networks
• Kinetic Theory of Random Graphs: from Paths to Cycles
• Metric structure of random networks
• Evolution of scale-free random graphs: Potts model formulation
• Principles of statistical mechanics of random networks
• Random Graphs with Hidden Color
• Statistical mechanics of topological phase transitions in networks
• The spectral dimension of generic trees
• Exact Solution for the Time Evolution of Network Rewiring Models
• Properties of Random Graphs with Hidden Color
• Homogeneous complex networks
• Scale-free networks with exponent one
• Condensation in nongeneric trees
• Generation of arbitrarily two-point correlated random networks
• Tree Networks with Causal Structure
• Quantum statistics in complex networks
• Topological phase transitions of random networks
• Correlations in connected random graphs
• A statistical mechanics approach for scale-free networks and finite-scale networks
• Exactly solvable scale-free network model
• Probability Models for Degree Distributions of Protein Interaction Networks
• Perturbing General Uncorrelated Networks
• Fluctuation-dissipation relations for complex networks
• Organization of complex networks without multiple connections
• Condensation transitions in a model for a directed network with weighted links
• Networks with given two-point correlations: hidden correlations from degree correlations
• Finite size effects in Barabasi-Albert growing networks
• Path Percolation in Quantum Communication Networks
• Statistical mechanics of scale-free networks at a critical point: Complexity without irreversibility?
• Statistical mechanics of random graphs
• Networks with many structural scales: a Renormalization Group perspective
• Bond and site color-avoiding percolation in scale free networks
• Statistical mechanics of coevolving spin system
• Evolving network - simulation study. From regular lattice to scale free network
• Critical field-exponents for secure message-passing in modular networks
• Dismantling Efficiency and Network Fractality
• Optimization and Scale-freeness for Complex Networks
• Mesoscopics and fluctuations in networks
• Finite-time fluctuations in the degree statistics of growing networks
• Exotic trees
• Anisotropic generalization of Stinchcombe's solution for conductivity of random resistor network on a Bethe lattice
• The statistical geometry of scale-free random trees
• Scale-freeness for networks as a degenerate ground state: A Hamiltonian formulation
• A Statistical Mechanical Load Balancer for the Web
• Ferromagnetic Ising spin systems on the growing random tree
• Segregation in the annihilation of two-species reaction-diffusion processes on fractal scale-free networks
• Statistical thermodynamics for choice models on graphs
• Spectral dimension of trees with a unique infinite spine
• Approaching the thermodynamic limit in equilibrated scale-free networks
• Ageing of complex networks
• Finite-size scaling of percolation on scale-free networks
• Appearance of vertices of infinite order in a model of random trees
• Condensation phase transition in nonlinear fitness networks
• Viral spread with or without emotions in online community
• Disassortativity of random critical branching trees
• Reverse engineering of linking preferences from network restructuring
• A program generating homogeneous random graphs with given weights
• Memory effect in growing trees
• Statistical model selection methods applied to biological networks
• Long-range disassortative correlations in generic random trees
• Some measure theory on stacks of graphs
• Spectral densities of scale-free networks
• From Spatial to Spectral: Network Renormalization via Dynamical Correlations
• Random walks on bifractal networks