Addition-Deletion Networks

Abstract

We study structural properties of growing networks where both addition and deletion of nodes are possible. Our model network evolves via two independent processes. With rate r, a node is added to the system and this node links to a randomly selected existing node. With rate 1, a randomly selected node is deleted, and its parent node inherits the links of its immediate descendants. We show that the in-component size distribution decays algebraically, c_k ~ k^{-beta}, as k-->infty. The exponent beta=2+1/(r-1) varies continuously with the addition rate r. Structural properties of the network including the height distribution, the diameter of the network, the average distance between two nodes, and the fraction of dangling nodes are also obtained analytically. Interestingly, the deletion process leads to a giant hub, a single node with a macroscopic degree whereas all other nodes have a microscopic degree.

8 pages, 5 figures

References in corpus (19)

• Emergence of scaling in random networks
• Statistical mechanics of complex networks
• Evolution of networks
• Structure of Growing Networks: Exact Solution of the Barabasi--Albert's Model
• Connectivity of Growing Random Networks
• Organization of Growing Random Networks
• Co-evolution of strategy and structure in complex networks with dynamical linking
• Scaling Theory and Exactly Solved Models In the Kinetics of Irreversible Aggregation
• Emergence of a small world from local interactions: Modeling acquaintance networks
• Generic scale of the "scale-free" growing networks
• Instability of scale-free networks under node-breaking avalanches
• Exact solutions for models of evolving networks with addition and deletion of nodes
• The Beam--Charge Azimuthal Asymmetry and Deeply Virtual Compton Scattering
• Statistics of Lead Changes in Popularity-Driven Systems
• A Solvable Sequence Evolution Model and Genomic Correlations
• Extremal properties of random trees
• Evolving networks through deletion and duplication
• Growing network with j-redirection
• Condensates in Driven Aggregation Processes

Cited by in corpus (9)

• Random Birth-and-Death Networks
• Memory and burstiness in dynamic networks
• Randomly Evolving Idiotypic Networks: Structural Properties and Architecture
• Fragmentation of Random Trees
• Random Ancestor Trees
• Preservation of network Degree Distributions from non-uniform failures
• A Class of Random Recursive Tree Algorithms with Deletion
• Decay of Scale-Free Property in Birth-and-Death Network
• The Degree Distribution of Random Birth-and-Death Network with Network Size Decline