Exact solutions for models of evolving networks with addition and deletion of nodes
- 28 September 2006
- journal article
- research article
- Published by American Physical Society (APS) in Physical Review E
- Vol. 74 (3), 036121
- https://doi.org/10.1103/physreve.74.036121
Abstract
There has been considerable recent interest in the properties of networks, such as citation networks and the worldwide web, that grow by the addition of vertices, and a number of simple solvable models of network growth have been studied. In the real world, however, many networks, including the web, not only add vertices but also lose them. Here we formulate models of the time evolution of such networks and give exact solutions for a number of cases of particular interest. For the case of net growth and so-called preferential attachment—in which newly appearing vertices attach to previously existing ones in proportion to vertex degree—we show that the resulting networks have power-law degree distributions, but with an exponent that diverges as the growth rate vanishes. We conjecture that the low exponent values observed in real-world networks are thus the result of vigorous growth in which the rate of addition of vertices far exceeds the rate of removal. Were growth to slow in the future—for instance, in a more mature future version of the web—we would expect to see exponents increase, potentially without bound.Keywords
This publication has 21 references indexed in Scilit:
- The Structure and Function of Complex NetworksSiam Review, 2003
- Evolution of networksAdvances in Physics, 2002
- Statistical mechanics of complex networksReviews of Modern Physics, 2002
- The degree sequence of a scale‐free random graph processRandom Structures & Algorithms, 2001
- Connectivity of Growing Random NetworksPhysical Review Letters, 2000
- Structure of Growing Networks with Preferential LinkingPhysical Review Letters, 2000
- Diameter of the World-Wide WebNature, 1999
- How popular is your paper? An empirical study of the citation distributionZeitschrift für Physik B Condensed Matter, 1998
- A general theory of bibliometric and other cumulative advantage processesJournal of the American Society for Information Science, 1976
- Networks of Scientific PapersScience, 1965