opening it up with Common Lisp

Favorite weblogs

Lisp Related

Bill Clementson

Finding Lisp


Planet Lisp



Talking Points Memo

This Modern World

Working for Change

Other home


Recent Readings

Book review: Darwinia
Reviewed: Friday, August 11, 2006

Summer reading: Spin
Reviewed: Saturday, August 5, 2006

Reviewed: Tuesday, July 18, 2006

the Omnivoire's Delimma
Reviewed: Wednesday, July 12, 2006

the Golem's Eye
Reviewed: Wednesday, May 31, 2006


Emergence of a small world from local interactions: modeling acquaintance networks
Joern Davidsen and Holger Ebel and Stefan Bornholdt, 2002 , (Paper URL)
Thursday, November 3, 2005

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