Topology of evolving networks: local events and universality

Abstract

Networks grow and evolve by local events, such as the addition of new nodes and links, or rewiring of links from one node to another. We show that depending on the frequency of these processes two topologically different networks can emerge, the connectivity distribution following either a generalized power-law or an exponential. We propose a continuum theory that predicts these two regimes as well as the scaling function and the exponents, in good agreement with the numerical results. Finally, we use the obtained predictions to fit the connectivity distribution of the network describing the professional links between movie actors.

13 pages, 3 figures

References in corpus (3)

• The large-scale organization of metabolic networks
• Connectivity of Growing Random Networks
• Evolution of reference networks with aging

Cited by in corpus (200)

• Statistical mechanics of complex networks
• The structure and function of complex networks
• Evolution of networks
• Hierarchical Organization in Complex Networks
• Evolution of the social network of scientific collaborations
• Epidemic dynamics and endemic states in complex networks
• Dynamical and correlation properties of the Internet
• Bose-Einstein condensation in complex networks
• Large-scale topological and dynamical properties of Internet
• Co-evolution of strategy and structure in complex networks with dynamical linking
• Spectra of "Real-World" Graphs: Beyond the Semi-Circle Law
• Random Geometric Graphs
• Deterministic Scale-Free Networks
• Are randomly grown graphs really random?
• Average path length in random networks
• Average path length in uncorrelated random networks with hidden variables
• Degree Distributions of Growing Networks
• Stability and topology of scale-free networks under attack and defense strategies
• Cut-offs and finite size effects in scale-free networks
• 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
• Self-organization of collaboration networks
• Scaling properties of scale-free evolving networks: Continuous approach
• A General Formalism for Inhomogeneous Random Graphs
• Vertex overload breakdown in evolving networks
• Edge overload breakdown in evolving networks
• Effect of the accelerating growth of communications networks on their structure
• Exact solutions for models of evolving networks with addition and deletion of nodes
• Identifying "communities" within energy landscapes
• Google matrix analysis of directed networks
• What should a statistical mechanics satisfy to reflect nature?
• Link Prediction in Complex Networks: A Mutual Information Perspective
• World-Wide Web scaling exponent from Simon's 1955 model
• Dynamical scenario for nonextensive statistical mechanics
• Scale-Free and Stable Structures in Complex {\em Ad hoc} networks
• Group entropies, correlation laws and zeta functions
• 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
• Preferential attachment growth model and nonextensive statistical mechanics
• Small-world structure of earthquake network
• Maximal planar scale-free Sierpinski networks with small-world effect and power-law strength-degree correlation
• Multiplicative noise: A mechanism leading to nonextensive statistical mechanics
• Shortest paths and load scaling in scale-free trees
• Weighted Scale-Free Networks with Stochastic Weight Assignments
• High dimensional random Apollonian networks
• Complex earthquake networks: Hierarchical organization and assortative mixing
• Behavior of susceptible-infected-susceptible epidemics on heterogeneous networks with saturation
• How does Europe Make Its Mind Up? Connections, cliques, and compatibility between countries in the Eurovision Song Contest
• Principles of statistical mechanics of random networks
• Measure for degree heterogeneity in complex networks and its application to recurrence network analysis
• Networks in life: Scaling properties and eigenvalue spectra
• Effect of congestion costs on shortest paths through complex networks
• Diversity of information pathways drives scaling and sparsity in real-world networks
• Random Graphs with Hidden Color
• Recoverable prevalence in growing scale-free networks and the effective immunization
• Evolving Apollonian Networks with Small-world Scale-free topologies
• Properties of Random Graphs with Hidden Color
• Human Sexual Contact Network as a Bipartite Graph
• Interplay between function and structure in complex networks
• Graph Annotations in Modeling Complex Network Topologies
• Stochastic Opinion Formation in Scale-Free Networks
• Role of dimensionality in complex networks: Connection with nonextensive statistics
• Fractional Dynamics of Network Growth Constrained by aging Node Interactions
• Analysis of scale-free networks based on a threshold graph with intrinsic vertex weights
• Quantum statistics in complex networks
• Hidden Symmetries in Real and Theoretical Networks
• Evolving small-world scale-free networks consist of cliques
• The Spread of Opinions and Proportional Voting
• Spectral properties of the Google matrix of the World Wide Web and other directed networks
• Phase transition in the recoverability of network history
• Natural emergence of clusters and bursts in network evolution
• Comment on "Critique of q-entropy for thermal statistics" by M. Nauenberg
• Degree Correlation in Scale-Free Graphs
• Neural Subgraph Matching
• Empirical nonextensive laws for the county distribution of total personal income and gross domestic product
• Unified model for network dynamics exhibiting nonextensive statistics
• Exactly solvable scale-free network model
• Thermodynamic characterization of networks using graph polynomials
• A Unified Framework for the Pareto Law and Matthew Effect using Scale-Free Networks
• Structural preferential attachment: Network organization beyond the link
• Accelerating, hyper-accelerating, and decelerating probabilistic networks
• Uncovering Randomness and Success in Society
• Delocalization transition for the Google matrix
• Effect of node deleting on network structure
• Multifractal properties of growing networks
• Phase Changes in the Evolution of the IPv4 and IPv6 AS-Level Internet Topologies
• Growing Scale-free Networks by a Mediation-Driven Attachment Rule
• Evolving networks by merging cliques
• Emergence of a non-scaling degree distribution in bipartite networks: a numerical and analytical study
• Degree Distribution, Rank-size Distribution, and Leadership Persistence in Mediation-Driven Attachment Networks
• Two complementary representations of a scale-free network
• Correlations in Scale-Free Networks: Tomography and Percolation
• The Fractional Preferential Attachment Scale-Free Network Model
• Emergence of Global Preferential Attachment From Local Interaction
• A preferential attachment model with Poisson growth for scale-free networks
• Omori's law in the Internet traffic
• Spin glass behavior of the antiferromagnetic Ising model on a scale-free network
• Evolving Networks and the Development of Neural Systems
• On the Tomography of Networks and Multicast Trees
• Multiple Scale-Free Structures in Complex Ad-Hoc Networks
• Hyperbolic Geometric Graph Representation Learning for Hierarchy-imbalance Node Classification
• Growing community networks with local events
• Distribution of infected mass in disease spreading in scale-free networks
• Temporal network modeling with online and hidden vertices based on the birth and death process
• Bridging the ARCH model for finance and nonextensive entropy
• Preferential Attachment in the Interaction between Dynamically Generated Interdependent Networks
• A Comprehensive Taxonomy of Cellular Automata
• Characteristics of Real Futures Trading Networks
• Social distancing and epidemic resurgence in agent-based Susceptible-Infectious-Recovered models
• Evolving Scale-Free Network Model with Tunable Clustering
• Nonlinear preferential rewiring in fixed-size networks as a diffusion process
• Fast Sparsely Synchronized Brain Rhythms in A Scale-Free Neural Network
• Preferential attachment during the evolution of a potential energy landscape
• Power-law distributions from additive preferential redistributions
• Features and heterogeneities in growing network models
• Quantum games on evolving random networks
• Quantitative description and modeling of real networks
• Growing dynamics of Internet providers
• Quantum social networks
• Preferential survival in models of complex ad hoc networks
• Modeling Discrete Combinatorial Systems as Alphabetic Bipartite Networks: Theory and Applications
• Robustness of the in-degree exponent for the world-wide web
• Emergence of multiscaling in heterogeneous complex networks
• Local rewiring rules for evolving complex networks
• Memory effects induce structure in social networks with activity-driven agents
• Thermodynamic approach for community discovering within the complex networks: LiveJournal study
• Can recurrence networks show small world property?
• Effects of decision-making on the transport costs across complex networks
• Effects of aging and links removal on epidemic dynamics in scale-free networks
• The missing links in the BGP-based AS connectivity maps
• Scale-free networks with tunable degree distribution exponents
• Evolution of the Internet AS-Level Ecosystem
• Network community structure and resilience to localized damage: application to brain microcirculation
• Google matrix of the citation network of Physical Review
• Rewiring hierarchical scale-free networks: Influence on synchronizability and topology
• Complex structures in generalized small worlds
• A self-consistent approach to measure preferential attachment in networks and its application to an inherent structure network
• Dynamical Networks in Function Dynamics
• Vertex labeling and routing in expanded Apollonian networks
• Evolving Networks with Multi-species Nodes and Spread in the Number of Initial Links
• Modeling the IPv6 Internet AS-level Topology
• Discretization of Time Series Data
• Directed cycles and related structures in random graphs: I- Static properties
• "Winner takes it all": strongest node rule for evolution of scale free networks
• A Latent Parameter Node-Centric Model for Spatial Networks
• Condensation phenomena with distinguishable particles
• Generation of scale-free networks using a simple preferential rewiring dynamics
• Modelling Selforganization and Innovation Processes in Networks
• Complex networks with scale-free nature and hierarchical modularity
• Evolutionary Neural Gas (ENG): A Model of Self Organizing Network from Input Categorization
• Unsupervised Machine Learning of Open Source Russian Twitter Data Reveals Global Scope and Operational Characteristics
• Large Very Dense Subgraphs in a Stream of Edges
• On "Sexual contacts and epidemic thresholds," models and inference for Sexual partnership distributions
• DeSCo: Towards Generalizable and Scalable Deep Subgraph Counting
• Inferring Actual Treatment Pathways from Patient Records
• Temporal Dynamics of Connectivity and Epidemic Properties of Growing Networks
• Complex networks and public funding: the case of the 2007-2013 Italian program
• The co-evolutionary dynamics of directed network of spin market agents
• Growing Hypergraphs with Preferential Linking
• Unifying Evolutionary and Network Dynamics
• Spectral and Dynamic Consequences of Network Specialization
• The effect of linguistic constraints on the large scale organization of language
• Exploring Academic Influence of Algorithms by Co-occurrence Network Based on Full-text of Academic Papers
• Temporal stability in human interaction networks
• The clash of the Titans: how preferential attachment helps the survival of the smallest
• A graph model for the clustering of dark matter halos
• A likelihood based framework for assessing network evolution models tested on real network data
• Degree-distribution Stability of Growing Networks
• Degree and connectivity of the Internet's scale-free topology
• The dual-Barabási-Albert model
• Temporal rich club phenomenon and its formation mechanisms
• Fitness-driven deactivation in network evolution
• Solving the Multiobjective Quasi-Clique Problem
• Generating Preferential Attachment Graphs via a Pólya Urn with Expanding Colors
• Ad-hoc Limited Scale-Free Models for Unstructured Peer-to-Peer Networks
• Network Structure, Self-Organization and the Growth of International Collaboration in Science
• Scaling exponents and phase separation in a nonlinear network model inspired by the gravitational accretion
• Efficient Semi-External Depth-First Search
• Flux of information in scale-free networks
• Computational Human Dynamics
• Modeling real spatial networks
• A Simple Model of Scale-free Networks Driven by both Randomness and Adaptability
• General Connectivity Distribution Functions for Growing Networks with Preferential Attachment of Fractional Power
• Interplay between Network Topology and Dynamics in Neural Systems
• The emergence of pseudo-stable states in network dynamics
• Identifying early-warning indicators of tipping points in networked systems against sequential attacks
• SPAN: Subgraph Prediction Attention Network for Dynamic Graphs
• Scale-Free Overlay Topologies with Hard Cutoffs for Unstructured Peer-to-Peer Networks
• T. Dauxois' "Non-Gaussian distributions under scrutiny" under scrutiny
• Your Tribe Decides Your Vibe: Analyzing Local Popularity in the US Patent Citation Network
• Time series of Internet AS-level topology graphs: four patterns and one model
• Study of Network Migration to New Technologies using Agent-based Modeling Techniques
• Topology Properties of Written Human Language
• Mixbiotic society measures: Assessment of community well-going as living system
• Evolutionary dynamics on sequential temporal networks
• Analysis of a Model for Generating Weakly Scale-free Networks
• Measuring the likelihood of models for network evolution
• A Markov Chain-Based Numerical Method for Calculating Network Degree Distributions