opening it up with Common Lisp |
||
Favorite weblogs Lisp Related Politics Other home Recent Readings
Book review: Darwinia
Summer reading: Spin
Runner
the Omnivoire's Delimma
the Golem's Eye |
Emergence of a small world from local interactions: modeling acquaintance networks Returning to the "how do you generate a random network" theme, we have this ditty by Davidsen, Ebel and Bornholdt. Rather than growing a network (as in Holme's and Kim's work), they start with a network of some fixed size and add transactions. The model is based on the idea that you meet many of your friends via other friends. Thus, they begin with a graph of size N and a bunch of links. At each step, one vertex is picked at random and two of its neighbors are "introduced" to one another. If the vertex picked has less than two neighbors, it adds a link to some other random vertex. Finally, with probability p a randomly chosen vertex is removed from the graph (together with its edges) and replaced by a new vertex with only one (randomly chosen) link. When these steps are iterated, the behavior of the graph in its steady state will depend on p. If p is close to one, then the "death" process will equal the linking process and the graph will be very Poissonian (i.e., the vertex degree distribution will be Poisson). If p is small, however, then the introductions will outweigh the deaths and the graph will have scale-free (power-law) degree distribution. It will also have high clustering coefficient and short path lengths. Thus, this simple model produces graphs small world graphs whose degree distribution can be tuned (using p) between scale-free and exponential. Pretty neat. |
Home | About | Quotes | Recent | Archives Copyright -- Gary Warren King, 2004 - 2006 |