Structure of Growing Networks: Exact Solution of the Barabasi--Albert's Model

Abstract

We generalize the Barabási--Albert's model of growing networks accounting for initial properties of sites and find exactly the distribution of connectivities of the network $P(q)$ and the averaged connectivity $\bar{q}(s,t)$ of a site $s$ in the instant $t$ (one site is added per unit of time). At long times $P(q)\sim q^{-\gamma }$ at $q\to \infty$ and $\bar{q}(s,t)\sim (s/t{)}^{-\beta }$ at $s/t\to 0$, where the exponent $\gamma$ varies from 2 to $\infty$ depending on the initial attractiveness of sites. We show that the relation $\beta (\gamma -1)=1$ between the exponents is universal.

4 pages revtex (twocolumn, psfig), 1 figure

References in corpus (2)

• Connectivity of Growing Random Networks
• Evolution of reference networks with aging

Cited by in corpus (403)

• Statistical mechanics of complex networks
• The structure and function of complex networks
• Community structure in social and biological networks
• Power laws, Pareto distributions and Zipf's law
• Assortative mixing in networks
• Epidemic processes in complex networks
• Synchronization in complex networks
• Evolution of networks
• 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
• Dynamical and correlation properties of the Internet
• Immunization of complex networks
• Universal Behavior of Load Distribution in Scale-free Networks
• The Kuramoto model in complex networks
• Vertex similarity in networks
• Epidemic dynamics on an adaptive network
• Statistical physics of vaccination
• Bose-Einstein condensation in complex networks
• Activity driven modeling of time varying 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
• Efficient routing on complex networks
• Measuring preferential attachment for evolving networks
• Growing networks with local rules: preferential attachment, clustering hierarchy and degree correlations
• Pseudofractal Scale-free Web
• Efficiency of Scale-Free Networks: Error and Attack Tolerance
• Deterministic Scale-Free Networks
• The Matthew effect in empirical data
• Do the rich get richer? An empirical analysis of the BitCoin transaction network
• Paths to Synchronization on Complex Networks
• Citation Statistics from 110 Years of Physical Review
• Highly clustered scale-free networks
• The Statistical Physics of Real-World Networks
• Classification of scale-free networks
• Percolation on complex networks: Theory and application
• Average path length in random networks
• Average path length in uncorrelated random networks with hidden variables
• Growing multiplex networks
• Degree Distributions of Growing Networks
• Generic scale of the "scale-free" growing networks
• Giant strongly connected component of directed networks
• Bipartite Graphs as Models of Complex Networks
• Maximal planar networks with large clustering coefficient and power-law degree distribution
• Power laws and Self-Organized Criticality in Theory and Nature
• Scaling properties of scale-free evolving networks: Continuous approach
• Characterizing and modeling the dynamics of online popularity
• Spectra and eigenvectors of scale-free networks
• Preferential attachment in the protein network evolution
• Truncation of power law behavior in "scale-free" network models due to information filtering
• A Model for Social Networks
• Generalized Network Dismantling
• Efficiency of informational transfer in regular and complex networks
• Effect of the accelerating growth of communications networks on their structure
• Power-law Strength-Degree Correlation From a Resource-Allocation Dynamics on Weighted Networks
• Characterizing and modeling citation dynamics
• Exact solutions for models of evolving networks with addition and deletion of nodes
• Analytical Solution of the Voter Model on Disordered Networks
• A Geometric Fractal Growth Model for Scale Free Networks
• Citation Networks in High Energy Physics
• Statistical ensemble of scale-free random graphs
• Scale-free Networks Well Done
• Coevolution and correlated multiplexity in multiplex networks
• Evolutionary game dynamics in a growing structured population
• Spectral centrality measures in complex networks
• Risk perception in epidemic modeling
• All scale-free networks are sparse
• Network geometry with flavor: from complexity to quantum geometry
• Scale-free network growth by ranking
• From Scale-free to Erdos-Renyi Networks
• Anomalous percolating properties of growing networks
• World-Wide Web scaling exponent from Simon's 1955 model
• Growing Random Networks with Fitness
• Finiteness and Fluctuations in Growing Networks
• Network properties of written human language
• Scale-free networks without growth
• Langevin approach for the dynamics of the contact process on annealed scale-free networks
• Network Cosmology
• Elephant Random Walks and their connection to Pólya-type urns
• Scale-Free Networks Generated By Random Walkers
• Spectral and Dynamical Properties in Classes of Sparse Networks with Mesoscopic Inhomogeneities
• Nonuniversal power law scaling in the probability distribution of scientific citations
• Signatures of small-world and scale-free properties in large computer programs
• Dynamics of directed graphs: the world-wide Web
• Collective synchronization induced by epidemic dynamics on complex networks with communities
• Rate equation approach for correlations in growing network models
• Synchronizability determined by coupling strengths and topology on Complex Networks
• Evolving networks with disadvantaged long-range connections
• An evolving network model with community structure
• Growth and structure of Slovenia's scientific collaboration network
• Urban road networks -- Spatial networks with universal geometric features? A case study on Germany's largest cities
• Component sizes in networks with arbitrary degree distributions
• Emergence of Soft Communities from Geometric Preferential Attachment
• Random graph models for directed acyclic networks
• Random Networks with Tunable Degree Distribution and Clustering
• True scale-free networks hidden by finite size effects
• Maximal planar scale-free Sierpinski networks with small-world effect and power-law strength-degree correlation
• Relations between Average Distance, Heterogeneity and Network Synchronizability
• An adaptive routing strategy for packet delivery in complex networks
• Self-organization of progress across the century of physics
• Weighted Scale-Free Networks with Stochastic Weight Assignments
• High dimensional random Apollonian networks
• Recent advances of percolation theory in complex networks
• Principles of statistical mechanics of random networks
• Bankruptcy risk model and empirical tests
• Complex networks renormalization: flows and fixed points
• Relating Topological Determinants of Complex Networks to Their Spectral Properties: Structural and Dynamical Effects
• Random walks on complex trees
• The discretised lognormal and hooked power law distributions for complete citation data: Best options for modelling and regression
• Scale Free Networks from Self-Organisation
• Zero Pearson Coefficient for Strongly Correlated Growing Trees
• Evolving Apollonian Networks with Small-world Scale-free topologies
• Dynamics of Microtubule Growth and Catastrophe
• Human Sexual Contact Network as a Bipartite Graph
• Evolution and structure of technological systems - An innovation output network
• A Condition for Cooperation in a Game on Complex Networks
• Scale-free networks with exponent one
• Stability of shortest paths in complex networks with random edge weights
• Equilibrium statistical mechanics of network structures
• Information Dynamics in the Networked World
• A Tractable Complex Network Model based on the Stochastic Mean-field Model of Distance
• Extremal Properties of Random Structures
• Modelling Citation Networks
• Tree Networks with Causal Structure
• Networking - A Statistical Physics Perspective
• Random Walks on Directed Networks: the Case of PageRank
• Fractional Dynamics of Network Growth Constrained by aging Node Interactions
• Exponential Random Simplicial Complexes
• Complex network view of evolving manifolds
• An extended formalism for preferential attachment in heterogeneous complex networks
• Identifying the role that individual animals play in their social network
• Condensation in a zero range process on weighted scale-free networks
• Stationary and dynamical properties of a zero range process on scale-free networks
• Universality of Performance Indicators based on Citation and Reference Counts
• Evolving small-world scale-free networks consist of cliques
• A message-passing approach to epidemic tracing and mitigation with apps
• Mapping Koch curves into scale-free small-world networks
• A Mutual Attraction Model for Both Assortative and Disassortative Weighted Networks
• Fame and Obsolescence: Disentangling growth and ageing dynamics of patent citations
• Runaway Events Dominate the Heavy Tail of Citation Distributions
• A Preferential Attachment Paradox: How Preferential Attachment Combines with Growth to Produce Networks with Log-normal In-degree Distributions
• Network growth models and genetic regulatory networks
• Degree Correlation in Scale-Free Graphs
• The urban economy as a scale-free network
• Dense Power-law Networks and Simplicial Complexes
• Assortative mixing enhances the irreversible nature of explosive synchronization in growing scale-free networks
• Exactly solvable scale-free network model
• The Degree Distribution of Random k-Trees
• Better synchronizability predicted by a new coupling method
• Unraveling the dynamics of growth, aging and inflation for citations to scientific articles from specific research fields
• 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
• Addition-Deletion Networks
• Mean first-passage time for maximal-entropy random walks in complex networks
• Growing Multiplex Networks with Arbitrary Number of Layers
• Social Diversity Reduces the Complexity and Cost of Fostering Fairness
• Degree-dependent intervertex separation in complex networks
• Underestimated cost of targeted attacks on complex networks
• Metastability and anomalous fixation in evolutionary games on scale-free networks
• Influence of reciprocal arcs on the degree distribution and degree correlations
• Power-law citation distributions are not scale-free
• Evolutionary Games on Isothermal Graphs
• Effect of node deleting on network structure
• A directed network model for World-Wide Web
• Preferencial growth: exact solution of the time dependent distributions
• Local-world evolving networks with tunable clustering
• Choosing among alternative histories of a tree
• Accelerated growth in outgoing links in evolving networks: deterministic vs. stochastic picture
• Multifractal properties of growing networks
• Renormalization flows in complex networks
• Spectral analysis of deformed random networks
• Temporal fractal structures: Origin of power-laws in the world-wide Web
• Network Risk and Forecasting Power in Phase-Flipping Dynamical Networks
• General expression for the component size distribution in infinite configuration networks
• Crossover phenomena of percolation transition in evolution networks with hybrid attachment
• Brand effect versus competitiveness in hypernetworks
• Preferential attachment mechanism of complex network growth: "rich-gets-richer" or "fit-gets-richer"?
• Sparse Maximum-Entropy Random Graphs with a Given Power-Law Degree Distribution
• Correlations in Scale-Free Networks: Tomography and Percolation
• A consensus opinion model based on the evolutionary game
• Scale-free behavior of networks with the copresence of preferential and uniform attachment rules
• Optimal Channel Efficiency in a Sensory Network
• Bias in generation of random graphs
• A preferential attachment model with Poisson growth for scale-free networks
• The Fractional Preferential Attachment Scale-Free Network Model
• Spectral classes of regular, random, and empirical graphs
• Topological phase transition in a network model with preferential attachment and node removal
• BioCode: A Data-Driven Procedure to Learn the Growth of Biological Networks
• Parallel Dynamics and Computational Complexity of Network Growth Models
• Multiple Scale-Free Structures in Complex Ad-Hoc Networks
• Continuous-time quantum walk spatial search on the Bollobás scale-free network
• Supercritical percolation on large scale-free random trees
• Assortativity and leadership emergence from anti-preferential attachment in heterogeneous networks
• Scaling Properties in Time-Varying Networks with Memory
• FastSIR Algorithm: A Fast Algorithm for simulation of epidemic spread in large networks by using SIR compartment model
• Analytical results for stochastically growing networks: connection to the zero range process
• Scaling in the structure of directory trees in a computer cluster
• Preferential Attachment in the Interaction between Dynamically Generated Interdependent Networks
• Random Birth-and-Death Networks
• Random Graphs Associated to some Discrete and Continuous Time Preferential Attachment Models
• Finite size effects in Barabasi-Albert growing networks
• Duality between equilibrium and growing networks
• Minimal models of weighted scale-free networks
• From regular to growing small-world networks
• Emergence of scale-free close-knit friendship structure in online social networks
• Power-law distributions from additive preferential redistributions
• Features and heterogeneities in growing network models
• Dynamics of Microtubule Instabilities
• A general model of hierarchical fractal scale-free networks
• Entropy rate of non-equilibrium growing networks
• Same Stats, Different Graphs: Exploring the Space of Graphs in Terms of Graph Properties
• Network Growth with Arbitrary Initial Conditions: Analytical Results for Uniform and Preferential Attachment
• Mandelbrot Law of Evolving Networks
• Memory and burstiness in dynamic networks
• Dynamics in online social networks
• Scaling exponents and clustering coefficients of a growing random network
• Observability transitions in correlated networks
• Core organization of directed complex networks
• Synchronization on Effective Networks
• Analysis of the convergence of the degree distribution of contracting random networks towards a Poisson distribution using the relative entropy
• Emergence of multiscaling in heterogeneous complex networks
• Shortest path discovery of complex networks
• Sublinear but Never Superlinear Preferential Attachment by Local Network Growth
• Critical Phase of Bond Percolations on Growing Networks
• Scaling of load in communications networks
• Distribution of Edge Load in Scale-free Trees
• Master-equation analysis of accelerating networks
• The Role of Diverse Strategies in Sustainable Knowledge Production
• Memory effects induce structure in social networks with activity-driven agents
• Percolation properties of growing networks under an Achlioptas process
• Directed Accelerated Growth: Application in Citation Network
• Convergence towards an Erd{\H o}s-Rényi graph structure in network contraction processes
• Growing hyperbolic networks beyond two dimensions: the generalised popularity-similarity optimisation model
• Effects of Preference for Attachment to Low-degree Nodes on the Degree Distributions of a Growing Directed Network and a Simple Food-Web Model
• Islands of stability in motif distributions of random networks
• Preferential attachment with information filtering - node degree probability distribution properties
• Highly Dispersed Networks Generated by Enhanced Redirection
• Dynamical Stationarity as a Result of Sustained Random Growth
• Time-invariant degree growth in preferential attachment network models
• Wikipedia edition dynamics
• A Formal Treatment of Generalized Preferential Attachment and its Empirical Validation
• Statistics of leaders and lead changes in growing networks
• S-curve networks and an approximate method for estimating degree distributions of complex networks
• Stratification in the Preferential Attachment Network
• Link-space formalism for network analysis
• 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
• Complex networks as an emerging property of hierarchical preferential attachment
• Self-organized bistability on scale-free networks
• Evolution of the Internet AS-Level Ecosystem
• Highly Dispersed Networks
• Emergence of scale-free networks from local connectivity and communication trade-offs
• Derivation of the percolation threshold for the network model of Barabasi and Albert
• Sustainable growth in complex networks
• Self-organized Emergence of Navigability on Small-World Networks
• Contact graphs of disk packings as a model of spatial planar networks
• Heterogeneity shapes groups growth in social online communities
• Mixing properties of growing networks and the Simpson's paradox
• Towards a more realistic citation model: The key role of research team sizes
• Do extremists impose the structure of social networks?
• Optimal portfolio for a robust financial system
• Patterns of Emotional Blogging and Emergence of Communities: Agent-Based Model on Bipartite Networks
• Traffic-driven epidemic spreading on scale-free networks with tunable degree distribution
• Power Laws, the Price Model, and the Pareto type-2 Distribution
• Generalized Nonlinear Yule Models
• Analyzing Trails in Complex Networks
• Two types of densification scaling in the evolution of temporal networks
• Hamiltonian Dynamics of Preferential Attachment
• Mesoscopics and fluctuations in networks
• Vertex labeling and routing in expanded Apollonian networks
• Motif-based success scores in coauthorship networks are highly sensitive to author name disambiguation
• Modeling the IPv6 Internet AS-level Topology
• Preferential growth: Solution and application to modeling stock market
• Evolving Networks with Multi-species Nodes and Spread in the Number of Initial Links
• Fragmentation of Random Trees
• Emergence of Clusters in Growing Networks with Aging
• Mechanism for linear preferential attachment in growing networks
• Preferential attachment with location-based choice: Degree distribution in the noncondensation phase
• Finite-time fluctuations in the degree statistics of growing networks
• "Winner takes it all": strongest node rule for evolution of scale free networks
• Popularity-Driven Networking
• Generation of scale-free networks using a simple preferential rewiring dynamics
• Sparse power-law network model for reliable statistical predictions based on sampled data
• Random Ancestor Trees
• Phase diagram of epidemic spreading - unimodal vs. bimodal probability distributions
• Mechanisms for tuning clustering and degree-correlations in directed networks
• How Complex Contagions Spread Quickly in the Preferential Attachment Model and Other Time-Evolving Networks
• Condensation in preferential attachment models with location-based choice
• A complementary view on the growth of directory trees
• Topics in social network analysis and network science
• Graph Theory and Networks in Biology
• Multi-directed Eulerian growing networks
• Structural tendencies - Effects of adaptive evolution of complex (chaotic) systems
• Extensive Condensation in a model of Preferential Attachment with Fitnesses
• Degree and component size distributions in generalized uniform recursive tree
• Information slows down hierarchy growth
• The Dynamics of Hierarchical Evolution of Complex Networks
• The Magic of Networks Grown by Redirection
• Characterizing Internet Worm Infection Structure
• The origin of preferential attachment and the generalized preferential attachment for weighted networks
• Mutual selection in network evolution: the role of the intrinsic fitness
• Universality in survivor distributions: Characterising the winners of competitive dynamics
• Ferromagnetic Ising spin systems on the growing random tree
• Growing Networks: Limit in-degree distribution for arbitrary out-degree one
• Quantum statistics and networks by asymmetric preferential attachment of nodes -- between bosons and fermions
• Analytic solutions for links and triangles distributions in finite Barabási-Albert networks
• Constraints and Entropy in a Model of Network Evolution
• A Generative Hypergraph Model for Double Heterogeneity
• Structure and modeling of the network of two-Chinese-character compound words in the Japanese language
• A random walker's view of networks whose growth it shapes
• Phase transition in evolving networks that combine preferential attachment and random node deletion
• Growing Hypergraphs with Preferential Linking
• Non-convergence of proportions of types in a preferential attachment graph with three co-existing types
• Disagreement and fragmentation in growing groups
• Typical Performance of Approximation Algorithms for NP-hard Problems
• Ageing of complex networks
• Percolation on a maximally disassortative network
• Temporal Dynamics of Connectivity and Epidemic Properties of Growing Networks
• Stochastic resetting in a networked multiparticle system with correlated transitions
• Approaching the thermodynamic limit in equilibrated scale-free networks
• Estimating Formation Mechanisms and Degree Distributions in Mixed Attachment Networks
• Unifying Evolutionary and Network Dynamics
• Generalised thresholding of hidden variable network models with scale-free property
• Compressibility of random walker trajectories on growing networks
• Degree-distribution Stability of Growing Networks
• Random degree-degree correlated networks
• Unimodular lattice triangulations as small-world and scale-free random graphs
• Edge Union of Networks on the Same Vertex Set
• A large-scale study of the World Wide Web: network correlation functions with scale-invariant boundaries
• A graph model for the clustering of dark matter halos
• How the fittest compete for leadership: A tale of tails
• Generating Scale-free Networks with Adjustable Clustering Coefficient Via Random Walks
• Equilibrium distributions in entropy driven balanced processes
• A hybrid percolation transition at a finite transition point in scale-free networks
• Preferential compactness of networks
• A geometric preferential attachment model with fitness
• The co-evolution of brand effect and competitiveness in evolving networks
• Degree distributions under general node removal: Power-law or Poisson?
• Fitness-driven deactivation in network evolution
• Model-based reconstruction of real-world fractal complex networks
• Distinct Degrees and Their Distribution in Complex Networks
• Error-correcting codes on scale-free networks
• Universality of competitive networks for weighted networks
• Relative Canonical Network Ensembles -- (Mis)characterizing Small-World Networks
• Larger holes as narrower degree distributions in complex networks
• Two-level relationships and Scale-Free Networks
• Evolution of robustness in growing random networks
• The degree distribution and the number of edges between nodes of given degrees in the Buckley-Osthus model of a random web graph
• A Survey of Evolving Models for Weighted Complex Networks based on their Dynamics and Evolution
• Growing a Network on a Given Substrate
• Coherence in complex networks of oscillators
• Searchability of central nodes in networks
• Problems with classification, hypothesis testing, and estimator convergence in the analysis of degree distributions in networks
• Missing Data as Part of the Social Behavior in Real-World Financial Complex Systems
• Growing Networks with Super-Joiners
• Structure of a media co-occurrence network
• On the Degree Distribution of Pólya Urn Graph Processes
• The degree distribution and the number of edges between nodes of given degrees in directed scale-free graphs
• Modeling Risk Perception in Networks with Community Structure
• Dynamic scaling and universality in evolution of fluctuating random networks
• Directed preferential attachment models
• Local majority dynamics on preferential attachment graphs
• Uncovering hidden flows in physical networks
• Network Growth with Feedback
• Link-Space and Network Analysis
• Emergence of scale-free behavior in networks from limited-horizon linking and cost trade-offs
• A Simple Model of Scale-free Networks Driven by both Randomness and Adaptability
• Emergence of network communities driven by local rules
• General Connectivity Distribution Functions for Growing Networks with Preferential Attachment of Fractional Power
• Analytic solution for preferential attachment probabilities scheme
• Will Scale-free Popularity Develop Scale-free Geo-social Networks?
• Characterizing the head of the degree distributions of growing networks
• Analysis of a Model for Generating Weakly Scale-free Networks
• A Stochastic Model for the Evolution of the Web
• Evolution of grammatical forms: some quantitative approaches
• Preferential attachment: a multi-attribute growth process generating scale-free networks of different topologies
• The Role of Trends in Evolving Networks
• An Optimization-Based Generative Model of Power Laws Using a New Information Theory Based Metric
• The distribution of second degrees in the Buckley-Osthus random graph model
• Evolving Network With Different Edges
• Same Stats, Different Graphs (Graph Statistics and Why We Need Graph Drawings)
• Time series of Internet AS-level topology graphs: four patterns and one model
• The Degree Distribution of Random Birth-and-Death Network with Network Size Decline
• Zero forcing number of graphs with a power law degree distribution
• Impact of Random Failures and Attacks on Poisson and Power-Law Random Networks
• A critique of the Mean Field Approximation in preferential attachment networks
• Starvation suppression in dense scale-free metabolic networks: Dynamical mean-field analysis of catalytic reaction networks
• Opinion Diffusion Software with Strategic Opinion Revelation and Unfriending
• The effect of preferential node deletion on the structure of networks that evolve via preferential attachment
• Detecting new edge types in a temporal network model
• Heavy-tails in economic data: fundamental assumptions, modelling and analysis
• Evolutionary dynamics on sequential temporal networks
• Carrying capacity in growing networks
• Explicit Solutions to the Continuous Time Albert-Barabási Scale-Free Model
• Impact of credit default swaps on financial contagion
• Decay of Scale-Free Property in Birth-and-Death Network
• Replicator Dynamics of Co-Evolving Networks
• Incomplete information in scale-free networks
• Stability of the LCD Model
• A Markov Chain-Based Numerical Method for Calculating Network Degree Distributions
• Emergent Probability - A directed Scale-Free Network Approach to Lonergan's Generic Model of Development