Connectivity of Growing Random Networks

Abstract

A solution for the time- and age-dependent connectivity distribution of a growing random network is presented. The network is built by adding sites which link to earlier sites with a probability A_k which depends on the number of pre-existing links k to that site. For homogeneous connection kernels, A_k ~ 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 stretched exponential. For gamma>1, a single site connects to nearly all other sites. In the borderline case A_k ~ k, the power law N_k ~k^{-nu} is found, where the exponent nu can be tuned to any value in the range 2<nu<infinity.

4 pages, 2 figures, 2 column revtex format final version to appear in PRL; contains additional results

References in corpus (1)

• Evolution of reference networks with aging

Cited by in corpus (408)

• Statistical mechanics of complex networks
• The structure and function of complex networks
• Community structure in social and biological networks
• Power-law distributions in empirical data
• Power laws, Pareto distributions and Zipf's law
• Assortative mixing in networks
• Evolution of networks
• Evolutionary games on graphs
• Who is the best connected scientist? A study of scientific coauthorship networks
• Critical phenomena in complex networks
• Evolution of the social network of scientific collaborations
• Clustering and preferential attachment in growing networks
• Epidemic dynamics and endemic states in complex networks
• Networks beyond pairwise interactions: structure and dynamics
• Dynamical and correlation properties of the Internet
• Structure of Growing Networks: Exact Solution of the Barabasi--Albert's Model
• Topology of evolving networks: local events and universality
• Universal Behavior of Load Distribution in Scale-free Networks
• Vertex similarity in networks
• Bose-Einstein condensation in complex networks
• Large-scale topological and dynamical properties of Internet
• The statistical mechanics of networks
• Modeling the Internet's Large-Scale Topology
• Popularity versus Similarity in Growing Networks
• Measuring preferential attachment for evolving networks
• Growing networks with local rules: preferential attachment, clustering hierarchy and degree correlations
• Nonequilibrium Statistical Mechanics of the Zero-Range Process and Related Models
• Pseudofractal Scale-free Web
• Random Geometric Graphs
• Efficiency of Scale-Free Networks: Error and Attack Tolerance
• Weighted Evolving Networks
• Deterministic Scale-Free Networks
• Class of correlated random networks with hidden variables
• Are randomly grown graphs really random?
• The Matthew effect in empirical data
• Do the rich get richer? An empirical analysis of the BitCoin transaction network
• Citation Statistics from 110 Years of Physical Review
• Classification of scale-free networks
• Preferential attachment in the growth of social networks: the case of Wikipedia
• Degree Distributions of Growing Networks
• Stability and topology of scale-free networks under attack and defense strategies
• Generic scale of the "scale-free" growing networks
• Giant strongly connected component of directed networks
• Maximal planar networks with large clustering coefficient and power-law degree distribution
• Scaling properties of scale-free evolving networks: Continuous approach
• Information dynamics shape the networks of Internet-mediated prostitution
• Spectra and eigenvectors of scale-free networks
• Preferential attachment in the protein network evolution
• Collective emotions online and their influence on community life
• Truncation of power law behavior in "scale-free" network models due to information filtering
• Accurately modeling the Internet topology
• Efficiency of informational transfer in regular and complex networks
• Effect of the accelerating growth of communications networks on their structure
• Characterizing and modeling citation dynamics
• Exact solutions for models of evolving networks with addition and deletion of nodes
• Random walks with preferential relocations to places visited in the past and their application to biology
• A Geometric Fractal Growth Model for Scale Free Networks
• Citation Networks in High Energy Physics
• Infinite-Order Percolation and Giant Fluctuations in a Protein Interaction Network
• Statistical ensemble of scale-free random graphs
• Statistical physics approaches to the complex Earth system
• Scale-free Networks Well Done
• Human dynamics revealed through Web analytics
• Evolutionary game dynamics in a growing structured population
• Emergent Hyperbolic Network Geometry
• All scale-free networks are sparse
• Exploring complex networks by walking on them
• Temporal effects in the growth of networks
• The Large Scale Curvature of Networks
• Scale-free network growth by ranking
• The egalitarian effect of search engines
• Anomalous percolating properties of growing networks
• World-Wide Web scaling exponent from Simon's 1955 model
• Finiteness and Fluctuations in Growing Networks
• Growing Random Networks with Fitness
• Network properties of written human language
• Scale-free networks without growth
• Emergent Hierarchical Structures in Multiadaptive Games
• Network Cosmology
• Lobby index in networks
• Scale-Free Networks Generated By Random Walkers
• Dynamics of directed graphs: the world-wide Web
• Collective synchronization induced by epidemic dynamics on complex networks with communities
• Signatures of small-world and scale-free properties in large computer programs
• Rate equation approach for correlations in growing network models
• Evolving networks with disadvantaged long-range connections
• Growth and structure of Slovenia's scientific collaboration network
• Emergence of Soft Communities from Geometric Preferential Attachment
• Component sizes in networks with arbitrary degree distributions
• Anomalous Transport in Complex Networks
• Travel and tourism: Into a complex network
• An adaptive routing strategy for packet delivery in complex networks
• Spectral Analysis and the Dynamic Response of Complex Networks
• Triadic closure dynamics drives scaling-laws in social multiplex networks
• Self-organization of progress across the century of physics
• High dimensional random Apollonian networks
• Weighted Scale-Free Networks with Stochastic Weight Assignments
• Recent advances of percolation theory in complex networks
• Mapping the evolution of scientific fields
• Principles of statistical mechanics of random networks
• Non-linear growth and condensation in multiplex networks
• Networks in life: Scaling properties and eigenvalue spectra
• Network Structures from Selection Principles
• Synchronization on community networks
• Diversity of information pathways drives scaling and sparsity in real-world networks
• Scale Free Networks from Self-Organisation
• Zero Pearson Coefficient for Strongly Correlated Growing Trees
• Constraint driven condensation in large fluctuations of linear statistics
• Competitive cluster growth in complex networks
• Evolving Apollonian Networks with Small-world Scale-free topologies
• Exact Solution for the Time Evolution of Network Rewiring Models
• Evolutionary games of condensates in coupled birth-death processes
• Modeling the structure and evolution of discussion cascades
• Dynamics of Microtubule Growth and Catastrophe
• Stochastic dynamical model of a growing network based on self-exciting point process
• Scale-free networks with exponent one
• Stability of shortest paths in complex networks with random edge weights
• Random Sierpinski network with scale-free small-world and modular structure
• Network model of human aging: frailty limits and information measures
• Complex Networks
• Exponential Random Simplicial Complexes
• Analysis of scale-free networks based on a threshold graph with intrinsic vertex weights
• A critical look at power law modelling of the Internet
• Solvable random walk model with memory and its relations with Markovian models of anomalous diffusion
• Using graph concepts to understand the organization of complex systems
• Understanding Flash Crash Contagion and Systemic Risk: A Micro-Macro Agent-Based Approach
• Identifying the role that individual animals play in their social network
• Evolving small-world scale-free networks consist of cliques
• An extended formalism for preferential attachment in heterogeneous complex networks
• Condensation in a zero range process on weighted scale-free networks
• Correlations in Bipartite Collaboration Networks
• Network comparison and the within-ensemble graph distance
• Spectral dimension reduction of complex dynamical networks
• Phase transition in the recoverability of network history
• A Preferential Attachment Paradox: How Preferential Attachment Combines with Growth to Produce Networks with Log-normal In-degree Distributions
• Runaway Events Dominate the Heavy Tail of Citation Distributions
• Understanding the internet topology evolution dynamics
• Degree Correlation in Scale-Free Graphs
• Limited path percolation in complex networks
• Crossovers in ScaleFree Networks on Geographical Space
• Condensation in stochastic mass transport models: beyond the zero-range process
• A general model for collaboration networks
• Assortative mixing enhances the irreversible nature of explosive synchronization in growing scale-free networks
• Explosive condensation in a mass transport model
• Exactly solvable scale-free network model
• Preferential attachment in growing spatial networks
• Tuning the shape of the condensate in spontaneous symmetry breaking
• Zipf's law and log-normal distributions in measures of scientific output across fields and institutions: 40 years of Slovenia's research as an example
• Impacts of preference and geography on epidemic spreading
• Addition-Deletion Networks
• The synchronizability of highly clustered scale-free networks
• Geographical networks evolving with optimal policy
• Growing Multiplex Networks with Arbitrary Number of Layers
• Preferential Exchange: Strengthening Connections in Complex Networks
• Degree-dependent intervertex separation in complex networks
• Quantum Gravity as an Information Network: Self-Organization of a 4D Universe
• Phase transition in non-Markovian animal exploration model with preferential returns
• The partially asymmetric zero range process with quenched disorder
• Unidirectional Random Growth with Resetting
• Critical phase in non-conserving zero-range processes and equilibrium networks
• Efficient sampling of spreading processes on complex networks using a composition and rejection algorithm
• Life, Death and Preferential Attachment
• Systematic identification of statistically significant network measures
• Scale-free networks as preasymptotic regimes of superlinear preferential attachment
• Correlations in random Apollonian network
• Choosing among alternative histories of a tree
• Scaling Invariance in Spectra of Complex Networks: A Diffusion Factorial Moment Approach
• Local-world evolving networks with tunable clustering
• Preferencial growth: exact solution of the time dependent distributions
• A coevolving model based on preferential triadic closure for social media networks
• Multifractal properties of growing networks
• Crossover phenomena of percolation transition in evolution networks with hybrid attachment
• Network Risk and Forecasting Power in Phase-Flipping Dynamical Networks
• Sparse Maximum-Entropy Random Graphs with a Given Power-Law Degree Distribution
• The distribution of shortest path lengths in a class of node duplication network models
• Ising model in clustered scale-free networks
• Correlations in Scale-Free Networks: Tomography and Percolation
• Scale-free behavior of networks with the copresence of preferential and uniform attachment rules
• Competition for Popularity in Bipartite Networks
• A Master Equation for Power Laws
• The Dynamics of Faculty Hiring Networks
• A preferential attachment model with Poisson growth for scale-free networks
• Condensation transitions in a model for a directed network with weighted links
• Mass condensation in one dimension with pair-factorized steady states
• Evolving Networks and the Development of Neural Systems
• Topological phase transition in a network model with preferential attachment and node removal
• Parallel Dynamics and Computational Complexity of Network Growth Models
• Multiple Scale-Free Structures in Complex Ad-Hoc Networks
• Growing community networks with local events
• Distribution of infected mass in disease spreading in scale-free networks
• Analytical results for stochastically growing networks: connection to the zero range process
• Preferential Attachment in the Interaction between Dynamically Generated Interdependent Networks
• Duality between equilibrium and growing networks
• Finite size effects in Barabasi-Albert growing networks
• Transport of multiple users in complex networks
• Nonlinear preferential rewiring in fixed-size networks as a diffusion process
• Minimal models of weighted scale-free networks
• Random Birth-and-Death Networks
• Collective Chaos Induced by Structures of Complex Networks
• Preferential attachment during the evolution of a potential energy landscape
• Power laws for family sizes in a duplication model
• Emergence of scale-free close-knit friendship structure in online social networks
• Identifying time dependence in network growth
• Entropy rate of non-equilibrium growing networks
• Individual popularity and activity in online social systems
• Features and heterogeneities in growing network models
• Dynamics of Microtubule Instabilities
• Supremacy distribution in evolving networks
• Growing dynamics of Internet providers
• Observability transitions in correlated networks
• Network Growth with Arbitrary Initial Conditions: Analytical Results for Uniform and Preferential Attachment
• Mandelbrot Law of Evolving Networks
• Core organization of directed complex networks
• Growing network with j-redirection
• Parallel Generation of Massive Scale-Free Graphs
• Scaling exponents and clustering coefficients of a growing random network
• The Effect of Exogenous Inputs and Defiant Agents on Opinion Dynamics with Local and Global Interactions
• Analysis of the convergence of the degree distribution of contracting random networks towards a Poisson distribution using the relative entropy
• Dynamics of condensation in growing complex networks
• Analytical results for the distribution of shortest path lengths in directed random networks that grow by node duplication
• Sublinear but Never Superlinear Preferential Attachment by Local Network Growth
• Scale-free properties of weighted networks with connectivity-driven topology
• Nonlinear Barabási-Albert Network
• Convergence towards an Erd{\H o}s-Rényi graph structure in network contraction processes
• Memory effects induce structure in social networks with activity-driven agents
• Stochastic and mixed flower graphs
• Master-equation analysis of accelerating networks
• Functional-Friction Networks: New Insights on the Laboratory Earthquakes
• Non-stationary Statistics and Formation Jitter in Transient Photon Condensation
• Scaling of load in communications networks
• Structural preferential attachment: Stochastic process for the growth of scale-free, modular and self-similar systems
• Islands of stability in motif distributions of random networks
• Highly Dispersed Networks Generated by Enhanced Redirection
• A Formal Treatment of Generalized Preferential Attachment and its Empirical Validation
• Condensation and topological phase transitions in a dynamical network model with rewiring of the links
• Wikipedia edition dynamics
• Network of two-Chinese-character compound words in Japanese language
• Effects of Preference for Attachment to Low-degree Nodes on the Degree Distributions of a Growing Directed Network and a Simple Food-Web Model
• Preferential attachment with information filtering - node degree probability distribution properties
• Dynamical Stationarity as a Result of Sustained Random Growth
• A k-deformed Model of Growing Complex Networks with Fitness
• Time-invariant degree growth in preferential attachment network models
• Anomalous electrical and frictionless flow conductance in complex networks
• The structure of networks that evolve under a combination of growth, via node addition and random attachment, and contraction, via random node deletion
• Scale-free networks with tunable degree distribution exponents
• Agent-based model for the h-index - Exact solution
• Statistics of leaders and lead changes in growing networks
• Stratification in the Preferential Attachment Network
• Link-space formalism for network analysis
• Balls-in-boxes condensation on networks
• Complex networks as an emerging property of hierarchical preferential attachment
• Self-organized bistability on scale-free networks
• Evolution of the Internet AS-Level Ecosystem
• Fast asynchronous updating algorithms for k-shell indices
• Emergence of scale-free networks from local connectivity and communication trade-offs
• Sustainable growth in complex networks
• Statistical analysis of emotions and opinions at Digg website
• Stretched exponential dynamics in a chain of coupled chaotic oscillators
• Inference for growing trees
• Highly Dispersed Networks
• Emergence of Robust and Efficient Networks in a Family of Attachment Models
• Epistemic Phase Transitions in Mathematical Proofs
• A self-consistent approach to measure preferential attachment in networks and its application to an inherent structure network
• Scaling of disordered recursive networks
• Generalized Nonlinear Yule Models
• Tuning degree distributions of scale-free networks
• Interspecific competition underlying mutualistic networks
• Condensation of degrees emerging through a first-order phase transition in classical random graphs
• Towards a more realistic citation model: The key role of research team sizes
• Do extremists impose the structure of social networks?
• Identifying hubs in directed networks
• Network growth for enhanced natural selection
• Studies on generalized Yule models
• Vertex labeling and routing in expanded Apollonian networks
• Evolving Networks with Multi-species Nodes and Spread in the Number of Initial Links
• Hamiltonian Dynamics of Preferential Attachment
• Mesoscopics and fluctuations in networks
• Modeling the IPv6 Internet AS-level Topology
• Go viral or go broadcast? Characterizing the virality and growth of cascades
• Motif-based success scores in coauthorship networks are highly sensitive to author name disambiguation
• "Winner takes it all": strongest node rule for evolution of scale free networks
• Parameterizing Network Graph Heterogeneity using a Modified Weibull Distribution
• Mechanisms for tuning clustering and degree-correlations in directed networks
• Mechanism for linear preferential attachment in growing networks
• Fragmentation of Random Trees
• Popularity-Driven Networking
• Random Ancestor Trees
• Finite-time fluctuations in the degree statistics of growing networks
• Analytical results for the in-degree and out-degree distributions of directed random networks that grow by node duplication
• Sparse power-law network model for reliable statistical predictions based on sampled data
• Likelihood-based approach to discriminate mixtures of network models that vary in time
• A Simple and Generic Paradigm for Creating Complex Networks Using the Strategy of Vertex Selecting-and-Pairing
• Graph Theory and Networks in Biology
• A complementary view on the growth of directory trees
• Exact Solutions for Models of Cultural Transmission and Network Rewiring
• Live and Dead Nodes
• Diophantine Networks
• The effect of the initial network configuration on preferential attachment
• Complex Networks: effect of subtle changes in nature of randomness
• Topics in social network analysis and network science
• On dynamic random graphs with degree homogenization via anti-preferential attachment probabilities
• Information slows down hierarchy growth
• Explaining the stellar initial mass function with the theory of spatial networks
• Universality in survivor distributions: Characterising the winners of competitive dynamics
• Spontaneous centralization of control in a network of company ownerships
• Mutual selection in network evolution: the role of the intrinsic fitness
• Ferromagnetic Ising spin systems on the growing random tree
• Rank-based model for weighted network with hierarchical organization and disassortative mixing
• Quantum statistics and networks by asymmetric preferential attachment of nodes -- between bosons and fermions
• Growing random networks under constraints
• The Magic of Networks Grown by Redirection
• Growing Networks: Limit in-degree distribution for arbitrary out-degree one
• Degree and component size distributions in generalized uniform recursive tree
• A random walker's view of networks whose growth it shapes
• Complex networks and public funding: the case of the 2007-2013 Italian program
• Temporal Dynamics of Connectivity and Epidemic Properties of Growing Networks
• Phase transition in evolving networks that combine preferential attachment and random node deletion
• Growing Hypergraphs with Preferential Linking
• Analytic solutions for links and triangles distributions in finite Barabási-Albert networks
• Stochastic resetting in a networked multiparticle system with correlated transitions
• Modeling Connectivity in Terms of Network Activity
• Constraints and Entropy in a Model of Network Evolution
• Boolean decision problems with competing interactions on scale-free networks: Critical thermodynamics
• Zero range and finite range processes with asymmetric rate functions
• Ageing of complex networks
• Degree-dependent network growth: From preferential attachment to explosive percolation
• Simplex triangulation induced scale-free networks
• Network interpolation
• Maintenance of order in a moving strong condensate
• Network Growth with Preferential Attachment for High Indegree and Low Outdegree
• Estimating Formation Mechanisms and Degree Distributions in Mixed Attachment Networks
• Activity ageing in growing networks
• Kinetics of node splitting in evolving complex networks
• Compressibility of random walker trajectories on growing networks
• A hybrid percolation transition at a finite transition point in scale-free networks
• A phase transition creates the geometry of the continuum from discrete space
• Condensation phase transition in nonlinear fitness networks
• A large-scale study of the World Wide Web: network correlation functions with scale-invariant boundaries
• Degree-distribution Stability of Growing Networks
• Localization in boundary-driven lattice models
• Structural Properties of Networks Grown via an Achlioptas Process
• Preferential compactness of networks
• Unimodular lattice triangulations as small-world and scale-free random graphs
• A graph model for the clustering of dark matter halos
• Analysis of centrality in sublinear preferential attachment trees via the CMJ branching process
• A generalized theory of preferential linking
• Heavy-Tailed Distribution of the Number of Papers within Scientific Journals
• Topological phase transition in anti-symmetric Lotka-Volterra doublet chain
• Fragmentation instability in aggregating systems
• Reverse engineering of linking preferences from network restructuring
• Collaboration and followership: a stochastic model for activities in social networks
• Error-correcting codes on scale-free networks
• Phase transitions in atypical systems induced by a condensation transition on graphs
• Fitness-driven deactivation in network evolution
• Tsallis mapping in growing complex networks with fitness
• Predicting Lifetime of Dynamical Networks Experiencing Persistent Random Attacks
• Distinct Degrees and Their Distribution in Complex Networks
• Maximum likelihood estimation of burst-merging kernels for bursty time series
• Network Growth with Feedback
• Continuum rich-get-richer processes: Mean field analysis with an application to firm size
• Coherence in complex networks of oscillators
• Growing a Network on a Given Substrate
• Link-Space and Network Analysis
• Network growth with preferential attachment and without "rich get richer" mechanism
• Problems with classification, hypothesis testing, and estimator convergence in the analysis of degree distributions in networks
• Generating Preferential Attachment Graphs via a Pólya Urn with Expanding Colors
• Emergence of scale-free behavior in networks from limited-horizon linking and cost trade-offs
• Evolution of robustness in growing random networks
• On the Degree Distribution of Pólya Urn Graph Processes
• Searchability of central nodes in networks
• Entropy and Hausdorff Dimension in Random Growing Trees
• Nearest-neighbour directed random hyperbolic graphs
• A Simple Model of Scale-free Networks Driven by both Randomness and Adaptability
• Coevolution of Glauber-like Ising dynamics on typical networks
• Long-run patterns in the discovery of the adjacent possible
• Slow dynamics of Zero Range Process in the Framework of Traps Model
• Dynamic scaling and universality in evolution of fluctuating random networks
• Universal emergence of local Zipf-Mandelbrot law
• Time series of Internet AS-level topology graphs: four patterns and one model
• Network growth under opportunistic attachment
• Decay of Scale-Free Property in Birth-and-Death Network
• Microscopic Evolution of Social Networks by Triad Position Profile
• An integrated model of traffic, geography and economy in the Internet
• Stability of the LCD Model
• A Stochastic Evolutionary Model Exhibiting Power-Law Behaviour with an Exponential Cutoff
• A classification of the natural and social distributions Part 2: the explanations
• High degree vertices in the Power of Choice model combined with Preferential Attachment
• Analysis of a Model for Generating Weakly Scale-free Networks
• An Optimization-Based Generative Model of Power Laws Using a New Information Theory Based Metric
• Preferential attachment hypergraph with vertex deactivation
• A Model for Collaboration Networks Giving Rise to a Power Law Distribution with an Exponential Cutoff
• A critique of the Mean Field Approximation in preferential attachment networks
• Beyond the Steady-State: Analytical Study of Network Growth at Arbitrary Times, for Arbitrary Initial Conditions
• Birth-Burst in Evolving Networks
• Growth of Random Trees by Leaf Attachment
• A Markov Chain-Based Numerical Method for Calculating Network Degree Distributions
• Interplay between Network Topology and Dynamics in Neural Systems
• Stochastic modeling of scientific impact
• The Truth about Power Laws: Theory and Reality
• A New Benchmark For Evaluation Of Graph-Theoretic Algorithms
• Explicit Solutions to the Continuous Time Albert-Barabási Scale-Free Model
• Growth Dynamics of Value and Cost Trade-off in Temporal Networks
• Estimating the dynamics of kernel-based evolving networks
• General Connectivity Distribution Functions for Growing Networks with Preferential Attachment of Fractional Power
• The effect of preferential node deletion on the structure of networks that evolve via preferential attachment
• Condensation transition in a conserved generalized interacting zero-range process
• The Degree Distribution of Random Birth-and-Death Network with Network Size Decline
• Scale-Free Overlay Topologies with Hard Cutoffs for Unstructured Peer-to-Peer Networks