The evolution of network topology by selective removal.

Abstract

The topology of large social, technical and biological networks such as the World Wide Web or protein interaction networks has caught considerable attention in the past few years (reviewed in Newman 2003), and analysis of the structure of such networks revealed that many of them can be classified as broad-tailed, scale-free-like networks, since their vertex connectivities follow approximately a power-law. Preferential attachment of new vertices to highly connected vertices is commonly seen as the main mechanism that can generate scale-free connectivity in growing networks (Watts 2004). Here, we propose a new model that can generate broad-tailed networks even in the absence of network growth, by not only adding vertices, but also selectively eliminating vertices with a probability that is inversely related to the sum of their first- and second order connectivity.