A remarkable feature of many complex systems is the occurrence of large and stable network structures as, for example, networks on the protein or gene level, ecological webs, communication networks, and social networks [1 -3]. Simple models based on disordered networks are quite successful in describing basic properties of such systems. When addressing topological properties, however, neither random networks nor regular lattices provide an adequate framework. A helpful concept along this line is the idea of "small-world networks" introduced by Watts and Strogatz [4, 5] which initiated an avalanche of scientific activity in this field [6] [7] [8] [9] [10] [11] . Small-world networks interpolate between the two limiting cases of regular lattices with high local clustering and of random graphs with short distances between nodes. High clustering implies that, if node A is linked to node B, and B is linked to node C, there is an increased probability that A will also be linked to C. Another useful measure is the distance between two nodes, defined as the number of edges along the shortest path connecting them. A network is called a "small-world network" if it exhibits the following two characteristic properties [4, 12] : (i) high clustering and (ii) a small average shortest path between two random nodes (sometimes called the diameter of the network), scaling logarithmically with the number of nodes. Thus, two randomly chosen nodes in the network are likely to be connected through only a small number of links. The most popular manifestation of a small world is known as "six degrees of separation," a postulate by the social psychologist Stanley Milgram [13] stating that most pairs of people in the United States can be connected through a path of only about six acquaintances [14] . Let us here focus on social networks, and acquaintance networks in particular, which are typical examples for the small-world property [1, 2, 12] . What does the concept of small-world networks tell us about such real world systems? In its original definition [4, 5] it serves as an elegant toy model demonstrating the consequences of high clustering and short path length. However, since these networks are derived from regular graphs, their applicability to real world systems is very limited. In particular, how a network in a natural system dynamically forms a small-world topology, often starting from a completely random structure, remains unexplained. The main goal of this Letter is to provide one possible answer to this problem. A similar problem of dynamical origin is faced (and much progress has been made) in a different, but not completely unrelated field: the dynamics of scale-free networks. Scale-free properties are commonly studied in diverse contexts from the stability of the internet [15] to the spreading of epidemics [16] and are observed in some social networks [1] [2] [3] 17, 18] . The origin of scale-free properties is well understood in terms of interactions that generate this topology dynamically, e.g., on the basis of network growth and preferential linking [2, 3, 19] . While these models generate scale-free structures they do not, in general, lead to clustering and are therefore of limited use when modeling social networks. In this Letter, an attempt is made to unify ideas from the two fields of "small-world networks" and "scale-free networks" in order to address the dynamics of social networks and the dynamical emergence of the small-world structure. In particular, a simple dynamical model for the evolution of acquaintance networks is studied. It generates highly clustered networks with small average path lengths that scale logarithmically with network size. Furthermore, for small death-and-birth rates of nodes this model converges towards scale-free degree distributions, in addition to its small-world behavior. Basic ingredients are a local connection rule based on "transitive linking," and a finite age of nodes. To be specific, let us formulate a model of an acquaintance network with a fixed number N of nodes (as persons) and undirected links between those pairs of nodes that represent people who know each other. Acquaintance networks evolve, with new acquaintances forming between individuals, and old ones dying. Let us assume that people are introduced to each other by a common acquaintance and that the network is formed only by people who are still alive. The dynamics is defined as follows: (i) One randomly chosen person picks two random acquaintances of his and introduces them to each another. If they have not met before, a new link between them is formed. In case the person chosen has less than two 128701-1 0031-9007͞02͞ 88(12)͞128701(4)$20.00
REF present a referral model that connections are always formed between two nodes that share a common neighbour.
Emergence of a small world from local interactions: modeling acquaintance networks.
Physical review letters
Physical review letters
Medicine Physics