Title
Preferential Deletion In Dynamic Models Of Web-Like Networks
Keywords
Dynamic random graph modeling; Interconnection networks; Power-law degree distribution; Preferential node deletion; Scale-free; Web-like networks
Abstract
In this paper a discrete-time dynamic random graph process is studied that interleaves the birth of nodes and edges with the death of nodes. In this model, at each time step either a new node is added or an existing node is deleted. A node is added with probability p together with an edge incident on it. The node at the other end of this new edge is chosen based on a linear preferential attachment rule. A node (and all the edges incident on it) is deleted with probability q = 1 - p. The node to be deleted is chosen based on a probability distribution that favors small-degree nodes, in view of recent empirical findings. We analyze the degree distribution of this model and find that the expected fraction of nodes with degree k in the graph generated by this process decreases asymptotically as k- 1 - (2 p / 2 p - 1). © 2007 Elsevier B.V. All rights reserved.
Publication Date
5-16-2007
Publication Title
Information Processing Letters
Volume
102
Issue
4
Number of Pages
156-162
Document Type
Article
Personal Identifier
scopus
DOI Link
https://doi.org/10.1016/j.ipl.2006.12.009
Copyright Status
Unknown
Socpus ID
33947181359 (Scopus)
Source API URL
https://api.elsevier.com/content/abstract/scopus_id/33947181359
STARS Citation
Deo, Narsingh and Cami, Aurel, "Preferential Deletion In Dynamic Models Of Web-Like Networks" (2007). Scopus Export 2000s. 6589.
https://stars.library.ucf.edu/scopus2000/6589