Exact solutions for models of evolving networks with addition and deletion of nodes

Abstract

There has been considerable recent interest in the properties of networks, such as citation networks and the worldwide web, that grow by the addition of vertices, and a number of simple solvable models of network growth have been studied. In the real world, however, many networks, including the web, not only add vertices but also lose them. Here we formulate models of the time evolution of such networks and give exact solutions for a number of cases of particular interest. For the case of net growth and so-called preferential attachment -- in which newly appearing vertices attach to previously existing ones in proportion to vertex degree -- we show that the resulting networks have power-law degree distributions, but with an exponent that diverges as the growth rate vanishes. We conjecture that the low exponent values observed in real-world networks are thus the result of vigorous growth in which the rate of addition of vertices far exceeds the rate of removal. Were growth to slow in the future, for instance in a more mature future version of the web, we would expect to see exponents increase, potentially without bound.

9 pages, 3 figures

Cited by in corpus (40)

• Modern temporal network theory: A colloquium
• Experience versus Talent Shapes the Structure of the Web
• Natural emergence of clusters and bursts in network evolution
• Simple and efficient self-healing strategy for damaged complex networks
• Addition-Deletion Networks
• Growing distributed networks with arbitrary degree distributions
• Growing networks with preferential addition and deletion of edges
• Topological phase transition in a network model with preferential attachment and node removal
• Random Birth-and-Death Networks
• Scale free networks by preferential depletion
• A Mean-Field Approach to Evolving Spatial Networks, with an Application to Osteocyte Network Formation
• Memory and burstiness in dynamic networks
• Preferential survival in models of complex ad hoc networks
• Mandelbrot Law of Evolving Networks
• Dynamic Hidden-Variable Network Models
• The structure of networks that evolve under a combination of growth, via node addition and random attachment, and contraction, via random node deletion
• Randomly Evolving Idiotypic Networks: Structural Properties and Architecture
• Random Ancestor Trees
• Fragmentation of Random Trees
• Higher-order distributions and nongrowing complex networks without multiple connections
• Preservation of network Degree Distributions from non-uniform failures
• Temporal Dynamics of Connectivity and Epidemic Properties of Growing Networks
• Phase transition in evolving networks that combine preferential attachment and random node deletion
• Stochastic resetting in a networked multiparticle system with correlated transitions
• Simulating systematic bias in attributed social networks and its effect on rankings of minority nodes
• A Maximum Entropy Method for the Prediction of Size Distributions
• The Accuracy of Tree-based Counting in Dynamic Networks
• Modeling Transitivity in Complex Networks
• Research on Life Characteristics of Internet Based on Network Motifs
• The Truth about Power Laws: Theory and Reality
• Structural Changes and Percolation Transition in Networks after Aging Processes
• Preferential attachment hypergraph with vertex deactivation
• Epidemic Transmission Modelling on the Birth-death Evolving Network with Indirect Contacts
• The evolving networks of debtor-creditor relationships with addition and deletion of nodes: a case of P2P lending
• The Degree Distribution of Random Birth-and-Death Network with Network Size Decline
• The effect of preferential node deletion on the structure of networks that evolve via preferential attachment
• Efficiency and shrinking in evolving networks
• Decay of Scale-Free Property in Birth-and-Death Network
• Scalable Analysis for Large Social Networks: the data-aware mean-field approach
• General Connectivity Distribution Functions for Growing Networks with Preferential Attachment of Fractional Power