Modeling Acquaintance

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 – 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 cluster in...