## 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.

The most common explanation for the emergence of scale-free structures in networks is a process referred to as preferential attachment. In a nutshell, preferential attachment assumes that new vertices attach preferentially to already well-connected vertices in a network (Simon 1955; Barabási & Albert 1999). Various mechanisms leading to preferential attachment have been described, some of them including conscious choice (e.g. the world wide web or collaboration networks; Watts 2004), others assuming an ongoing duplication of nodes and edges (e.g. protein and gene networks; Barabási & Oltvai 2004; Berg *et al*. 2004). However, these mechanisms usually require that the networks are growing, a precondition that is certainly not given in all networks (Dorogovtsev & Mendes 2000). We propose an alternative model that results in the emergence of broad-tailed connectivity distributions that are best described by a power-law (hereafter referred to as scale-free-like networks), both in growing and non-growing networks, without assuming any form of cognition, choice or duplication, leading to apparent preferential attachment.

In the model presented here, the sum of first- and second-order connections of a vertex determines the likelihood of selective removal. A randomly connected network with initially *m* vertices is subjected to selection during *t* generations. In each generation, a proportion (*p*) of the vertices is removed from the network. To simulate a selective process, a random vertex is chosen and removed with a probability of 1/*c*^{a}, where *c* is the sum of its first- and second-order connectivity, that is, the number of vertices with a maximal distance of 2 (i.e. the number of neighbours and secondary neighbours), and *a* measures the strength of selection, since higher values of *a* result in stronger selection against low values of *c*. This procedure is repeated until *r*=*pN* vertices are removed from the network (where *N* is the number of all nodes in the network). Additionally, random vertices can be removed independent of their fitness value with a natural vertex death rate *d*. If after removal the system contains a number of unconnected vertices (denoted by *u*), these are removed too. Finally, *v* new vertices are added and connected to random vertices of the network. The resulting network grows when *v*>*r*+*u* or is constant in size when *v*=*r*+*u*. The net number of added vertices per generation is denoted by *n*=*v*−(*r*+*u*). Thus, after *t* generations, the number of vertices in the network is *m*+*tn*, where *m* is the initial network size. Note that no preferential attachment is occurring during the entire process.

We first looked at growing networks by running simulations over 3000 time steps, starting on a network consisting of only two vertices connected to each other. At each time step, the network grew by one vertex, resulting in a final network of 3002 vertices. The size of these simulated networks is of the general order of larger real-world datasets. Simulations of the described selective removal process resulted in the self-organization of networks with vertex connectivities *p*(*k*) that are best described by a power-law in a wide range of parameter values (figure 1 and table 1). Since network growth has been shown to be an essential component of the preferential attachment mechanism, we wanted to know if the selective removal mechanism would create scale-free-like distributions when applied to non-growing networks. Simulations were started on initially random networks with 3000 vertices, characterized by a Poisson connectivity distribution, and at each time step, the number of randomly attached vertices was equal to the number of removed vertices (thus *n*=0). We found that the connectivity distribution was best described by a power-law very quickly (less than 500 time steps for most of the simulations—for a typical distribution, see figure 1). The scaling of the simulated networks was conserved even over large time-scales (*t*=100 000; table 1); thus growth does not appear to be an essential component for the selective removal mechanism to generate scale-free-like networks.

While many investigated network distributions have only been fitted by eye (Dorogovtsev & Mendes 2003), we follow the approach of Stumpf (submitted). This approach employs the Akaike-information criterion (AIC), which uses the maximum likelihood estimates (MLE) and the number of parameters of a model, to find the distribution that best describes the data (Akaike 1983; Burnham & Anderson 2002). Here, we consider the Poisson, exponential and power-law distribution. Since all of them can be described by one parameter, it is sufficient to compare only the MLE to identify the best model. Our results (table 1) show that scale-free-like structures emerge if selection is strong enough (threshold value for *a*≈1.5). However, an analytical approximation (see appendix A) shows that for the limiting case where selection is extremely strong, the asymptotic distribution is again exponential.

In scale-free networks, the probability *p*(*k*) that a vertex is connected to *k* other vertices decays with *p*(*k*)∼*k*^{−γ}. Empirical evidence from real-world networks has shown that the degree exponent *γ* lies in the range of about 2 to 4. The scale-free-like networks that emerge by selective removal have connectivity distributions following power-laws with degree exponents 1.8<*γ*<3.9 depending on the parameter values used. Thus, selective removal can account for all degree exponents observed in real-world networks.

Interestingly, the described selective removal mechanism does not produce scale-free-like networks if fitness is defined as first-order connectivity only (no second-order connectivity). This seems surprising, since first-order connectivity has been linked to several important properties of vertices, such as essentiality of proteins (Jeong *et al*. 2001) or influence and status of individuals in social networks. However, it is easy to see how removal based on second-order connectivity leads to *apparent* preferential attachment, resulting in scale-free-like networks. Imagine an extreme case of the model where the network size is doubled by creating new vertices and attaching all of them randomly. Then, all of the freshly attached vertices are removed except one, based on the selective removal criteria. As the second-order connectivity of the remaining new vertex is quite high (or else it had probably been removed), it appears as if it had been attached preferentially to an already well-connected node. Yet, the attachment was perfectly random.

Removal of vertices is certainly a decisive process in the dynamics of networks especially in the absence of network growth, and we showed here that if removal probability correlates inversely with second-order connectivity, *apparent* preferential attachment will lead to scale-free-like network topologies. The model can be applied to dynamic networks where the fitness of a vertex is not only defined by the number of direct connections, but also by the number of connections of the connecting vertices. In social networks, for instance, it is not only important how many people one knows, but also how many people those people know (Katz 1953). This is certainly obvious, for example, in economic or political networks. Also, second-order connectivity is somewhat related to the measures of betweenness and closeness (Wasserman & Faust 1994) whose importance is well known in social networks. Thanks to both the advances in network theory and the increasing amount of network data available, we are beginning to reveal many different processes that may lead to similar network connectivity distributions (Ferrer i Cancho & Solé 2001; Caldarelli *et al*. 2002; Eppstein & Wang 2002; Alava & Dorogovtsev 2005). Hence, a pluralistic view should certainly be adopted if we want to fully understand the emergence of network topologies.

## Acknowledgements

We thank Michael P. H. Stumpf for help with the AIC calculations, and Thomas Pfeiffer, Jacob C. Koella and Roger Koyous for valuable comments.

## Footnotes

- Received May 14, 2005.
- Accepted July 28, 2005.

- © 2005 The Royal Society