Addition-Deletion Networks
E. Ben-Naim and P.L. Krapivsky
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.
source,
ps,
pdf