Are randomly grown graphs really random?

Abstract

We analyze a minimal model of a growing network. At each time step, a new vertex is added; then, with probability delta, two vertices are chosen uniformly at random and joined by an undirected edge. This process is repeated for t time steps. In the limit of large t, the resulting graph displays surprisingly rich characteristics. In particular, a giant component emerges in an infinite-order phase transition at delta = 1/8. At the transition, the average component size jumps discontinuously but remains finite. In contrast, a static random graph with the same degree distribution exhibits a second-order phase transition at delta = 1/4, and the average component size diverges there. These dramatic differences between grown and static random graphs stem from a positive correlation between the degrees of connected vertices in the grown graph--older vertices tend to have higher degree, and to link with other high-degree vertices, merely by virtue of their age. We conclude that grown graphs, however randomly they are constructed, are fundamentally different from their static random graph counterparts.

8 pages, 5 figures

References in corpus (1)

• Degree Distributions of Growing Networks

Cited by in corpus (120)

• Statistical mechanics of complex networks
• The structure and function of complex networks
• Assortative mixing in networks
• Evolution of networks
• Critical phenomena in complex networks
• Generation of uncorrelated random scale-free networks
• Growing networks with local rules: preferential attachment, clustering hierarchy and degree correlations
• Epidemic spreading in correlated complex networks
• The phase transition in inhomogeneous random graphs
• Random Geometric Graphs
• Ising Model on Networks with an Arbitrary Distribution of Connections
• Percolation on complex networks: Theory and application
• Percolation Critical Exponents in Scale-Free Networks
• Resilience to damage of graphs with degree correlations
• A General Formalism for Inhomogeneous Random Graphs
• Construction and properties of assortative random networks
• Crossover from Scale-Free to Spatial Networks
• Inferring Network Mechanisms: The Drosophila melanogaster Protein Interaction Network
• Explosive Phenomena in Complex Networks
• Spatially localized attacks on interdependent networks: the existence of a finite critical attack size
• Infinite-Order Percolation and Giant Fluctuations in a Protein Interaction Network
• Correlated random networks
• Explosive Percolation: Novel critical and supercritical phenomena
• Percolation of Partially Interdependent Scale-free Networks
• Inverted Berezinskii-Kosterlitz-Thouless Singularity and High-Temperature Algebraic Order in an Ising Model on a Scale-Free Hierarchical-Lattice Small-World Network
• Percolation on correlated networks
• Recent advances and open challenges in percolation
• Construction and Analysis of Random Networks with Explosive Percolation
• Global and local synchrony of coupled neurons in small-world networks
• Anomalous percolating properties of growing networks
• Finiteness and Fluctuations in Growing Networks
• Assortative model for social networks
• A Random Growth Model for Power Grids and Other Spatially Embedded Infrastructure Networks
• Network Archaeology: Uncovering Ancient Networks from Present-day Interactions
• The Structure of Phonological Networks Across Multiple Languages
• Potts model on complex networks
• Affinity Paths and Information Diffusion in Social Networks
• Recent advances of percolation theory in complex networks
• Random Graphs with Hidden Color
• Recoverable prevalence in growing scale-free networks and the effective immunization
• Percolation transition in networks with degree-degree correlation
• Phase Transition with the Berezinskii--Kosterlitz--Thouless Singularity in the Ising Model on a Growing Network
• The k-core and branching processes
• Complete trails of co-authorship network evolution
• Properties of Random Graphs with Hidden Color
• Topological Percolation on Hyperbolic Simplicial Complexes
• BKT-like transition in the Potts model on an inhomogeneous annealed network
• Epidemic Dynamics of Interacting Two Particle Species on Scale-free Networks
• Sparse random graphs with clustering
• A Preferential Attachment Paradox: How Preferential Attachment Combines with Growth to Produce Networks with Log-normal In-degree Distributions
• Assembling thefacebook: Using heterogeneity to understand online social network assembly
• Networks based on collisions among mobile agents
• The path to fracture in granular flows: dynamics of contact networks
• Solution of the explosive percolation quest. II. Infinite-order transition produced by the initial distributions of clusters
• Normal form for renormalization groups
• Homological percolation transitions in growing simplicial complexes
• Patterns in the English Language: Phonological Networks, Percolation and Assembly Models
• Universal Properties of Growing Networks
• Triangular clustering in document networks
• Complex networks created by aggregation
• Percolation transitions in the survival of interdependent agents on multiplex networks, catastrophic cascades, and SOS
• Hidden Variables in Bipartite Networks
• What exactly are the properties of scale-free and other networks?
• Generating-function approach for bond percolations in hierarchical networks
• Patterns in randomly evolving networks: Idiotypic networks
• Complex Network Structure of Flocks in the Standard Vicsek Model
• BioCode: A Data-Driven Procedure to Learn the Growth of Biological Networks
• Multiple Scale-Free Structures in Complex Ad-Hoc Networks
• Modeling and verifying a broad array of network properties
• Extreme robustness of scaling in sample space reducing processes explains Zipf's law in diffusion on directed networks
• A simple asymmetric evolving random network
• Generative Model Selection Using a Scalable and Size-Independent Complex Network Classifier
• Hierarchical scale-free network is fragile against random failure
• Properties of a random attachment growing network
• Critical Phase of Bond Percolations on Growing Networks
• Nonlinear Barabási-Albert Network
• Percolation and Loop Statistics in Complex Networks
• Insights from Graph Theory on the Morphologies of Actomyosin Networks with Multilinkers
• Tuning the average path length of complex networks and its influence to the emergent dynamics of the majority-rule model
• PAFit: an R Package for the Non-Parametric Estimation of Preferential Attachment and Node Fitness in Temporal Complex Networks
• Percolation properties of growing networks under an Achlioptas process
• The q-component static model : modeling social networks
• Equation-Free Multiscale Computations in Social Networks: from Agent-based Modelling to Coarse-grained Stability and Bifurcation Analysis
• Solvable epidemic model on degree-correlated networks
• The fluid limit of a random graph model for a shared ledger
• Profile and scaling of the fractal exponent of percolations in complex networks
• A dynamic network in a dynamic population: asymptotic properties
• Link-space formalism for network analysis
• Condensates in Driven Aggregation Processes
• Absence of the non-percolating phase for percolation on the non-planar Hanoi network
• Emergence of Clusters in Growing Networks with Aging
• Inhomogeneous percolation models for spreading phenomena in random graphs
• Likelihood-based approach to discriminate mixtures of network models that vary in time
• Percolation in Media with Columnar Disorder
• Degree-ordered percolation on hierarchical scale-free network
• The Magic of Networks Grown by Redirection
• Ferromagnetic Ising spin systems on the growing random tree
• Spatially self-organized resilient networks by a distributed cooperative mechanism
• Degree product rule tempers explosive percolation in the absence of global information
• Estimating Formation Mechanisms and Degree Distributions in Mixed Attachment Networks
• Assortativity in random line graphs
• Diversity and critical behavior in prisoner's dilemma game
• Simple evolving random graphs
• Percolation transitions with nonlocal constraint
• Structural Properties of Networks Grown via an Achlioptas Process
• A hybrid percolation transition at a finite transition point in scale-free networks
• How to grow an oscillator network with enhanced synchronization
• Percolation Transitions in Growing Networks Under Achlioptas Processes: Analytic Solutions
• Asymptotic behavior of the node degrees in the ensemble average of adjacency matrix
• Quantitative modeling of degree-degree correlation in complex networks
• Distinct Degrees and Their Distribution in Complex Networks
• Joint Estimation of the Non-parametric Transitivity and Preferential Attachment Functions in Scientific Co-authorship Networks
• Critical Percolation Phase and Thermal BKT Transition in a Scale-Free Network with Short-Range and Long-Range Random Bonds
• Random growth lattice filling model of percolation: a crossover from continuous to discontinuous transition
• Mechanisms of recoverable prevalence and extinction of viruses on linearly growing scale-free networks
• Link-Space and Network Analysis
• General Connectivity Distribution Functions for Growing Networks with Preferential Attachment of Fractional Power
• Susceptibility of random graphs with given vertex degrees
• Anomalous percolation transitions beyond the BKT transition in growing networks
• Scaling limits and universality: Critical percolation on weighted graphs converging to an $L^3$ graphon