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

Socpus ID

33947181359 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/33947181359

This document is currently not available here.

Share

COinS