Preferential deletion in dynamic models of web-like networks

    Authors

    N. Deo;A. Cami

    Comments

    Authors: contact us about adding a copy of your work at STARS@ucf.edu

    Abbreviated Journal Title

    Inf. Process. Lett.

    Keywords

    Web-like networks; interconnection networks; dynamic random graph; modeling; preferential node deletion; scale-free; power-law degree; distribution; GRAPHS; Computer Science, Information Systems

    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-)(2p/2p(-1)). (c) 2007 Elsevier B.V. All rights reserved.

    Journal Title

    Information Processing Letters

    Volume

    102

    Issue/Number

    4

    Publication Date

    1-1-2007

    Document Type

    Article

    Language

    English

    First Page

    156

    Last Page

    162

    WOS Identifier

    WOS:000245770000006

    ISSN

    0020-0190

    Share

    COinS