graphs, the universe and everything
Apr. 25th, 2004 07:57 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
jayThe past couple of weeks or so, I should have been working on my crater gravity paper or air traffic bureaucracy for JL... instead, I've been playing with graph theory in odd moments. :-)
I've been pleased to recently discover that over the past several years, a subset of graph theory has addressed complex networks. Web page links, Kevin Bacon links, co-authors of papers all follow the same hub-and-spoke model -- a tiny number of hubs have many links, while most nodes (spokes) have few. This concentrated connectivity also drives the notorious "six degrees of separation" in social networks. They appear to happen as new nodes in a network preferentially link to nodes that already have many links. We see this often online as purveyors of new websites try to get noticed (or highly-indexed) by Google, Yahoo, Amazon, etc. to draw more hits on their sites. But the overwhelming majority of sites are not Google -- they sit in relative obscurity, getting a few hits now and then and containing only a few links to/from other similar sites.
Rather that a network full of nodes that have roughly the same number of links, many complex systems are "scale -free" -- the connections per node don't follow a Gaussian distribution around some median value. Instead, some nodes (hubs) may have 5x, 10x, 100x, etc. the median... such as described in a 2002 paper in New Scientist .
That author has written a book (Linked) about graph theory and the representation of complexity... reviewed and summarized in an American Scientist
book review.
"The ubiquity of the scale-free topology calls for a general underlying mechanism. One possible mechanism is a "rich get richer" scenario: As the network grows node by node, each new node links to some of the existing nodes, and the probability of getting one of the new links is proportional to the number of links already present. "
This appears to hold true for citation networks, the Web, Hollywood actors, dating, supercooled molecular condensates... most complex organizations in nature that can be represented as networks. This is a piece of how the universe appears to work, and it explains previous mysteries... fascinating!
More in a later posting about the poly implications thereof, and ability to now make sense of certain patterns. :-)
I've been pleased to recently discover that over the past several years, a subset of graph theory has addressed complex networks. Web page links, Kevin Bacon links, co-authors of papers all follow the same hub-and-spoke model -- a tiny number of hubs have many links, while most nodes (spokes) have few. This concentrated connectivity also drives the notorious "six degrees of separation" in social networks. They appear to happen as new nodes in a network preferentially link to nodes that already have many links. We see this often online as purveyors of new websites try to get noticed (or highly-indexed) by Google, Yahoo, Amazon, etc. to draw more hits on their sites. But the overwhelming majority of sites are not Google -- they sit in relative obscurity, getting a few hits now and then and containing only a few links to/from other similar sites.
Rather that a network full of nodes that have roughly the same number of links, many complex systems are "scale -free" -- the connections per node don't follow a Gaussian distribution around some median value. Instead, some nodes (hubs) may have 5x, 10x, 100x, etc. the median... such as described in a 2002 paper in New Scientist .
That author has written a book (Linked) about graph theory and the representation of complexity... reviewed and summarized in an American Scientist
book review.
"The ubiquity of the scale-free topology calls for a general underlying mechanism. One possible mechanism is a "rich get richer" scenario: As the network grows node by node, each new node links to some of the existing nodes, and the probability of getting one of the new links is proportional to the number of links already present. "
This appears to hold true for citation networks, the Web, Hollywood actors, dating, supercooled molecular condensates... most complex organizations in nature that can be represented as networks. This is a piece of how the universe appears to work, and it explains previous mysteries... fascinating!
More in a later posting about the poly implications thereof, and ability to now make sense of certain patterns. :-)
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Date: 2004-04-26 11:59 am (UTC)Both the paper and the book.