I was lucky enough to catch the two days of this year’s
>Complex Systems Summer School at the href="http://www.santafe.edu/">Santa Fe Institute which
discussed networks. The two speakers were href="http://smallworld.sociology.columbia.edu/watts.html">Duncan
Watts and Mark
Newman. They have revolutionized our understanding of how
messy hairball adhoc networks have surprisingly pleasant properties.
One of these is the href="http://pup.princeton.edu/titles/6768.html">Small Worlds
characteristics .. two nodes on a peer network can actually find
each other quickly with near-optimal path length, using only the
local knowledge the nodes have .. no central, global structure.
You know the idea: you meet a stranger at a party, and after a
few minutes you find you have a common friend, and you both say,
“Wow, what a small world it is!”
I had earlier explored Small
Worlds and Power Law networks as part of a P2P project,
basically kicking the tires to see if this stuff works. It
does! And how! For example, this power law graph of 100
nodes looks like a mess, but with the recent results from analyzing
these graphs, order is teased out and quite good, near-optimal
searching emerges. The plot to the right shows the search
lengths (degrees of separation) we get, compared to the more usual
breadth or depth first searching. Dramatic, even more so
considering the search scale is logarithmetic!
100 node power law net; click for full size.
Search statistics for large net; click for full size
But I had always had a nagging concern that this was just the
beginning, and we needed to figure out how to include more natural
searching ideas such as peer groups (occupation, geographical
location, age, and so on), much like people do when trying to surf
their social network. Well, Mark, Duncan and others have been
busy working on the problem and the good news is that studies of
“identity” (read meta-data) in social networks have led the way to
better searching! The earlier searches were pretty dumb: just
look for an exact match on the data (Do you have file “X”?).
The new methods use a nice blend of meta-data (Check out the
folks “like me” and “near me” for file “X”) which tame the power law
nets even more. Mark’s href="http://www.santafe.edu/%7Emark/pubs.html">Networks and Graph
Theory page has a good selection of papers on the topic.
So hang in there gang. Math, The Next Big Thing, with the help of
very interdiciplanary folks at the Santa Fe Institute, are cracking
some of the tough nuts of peer systems, robustness, data mining and
other core problems. Wait’ll I show you how these guys are
using the way ants forage to optimize the data centers! That’ll have
to wait for another day.
I’d be interested in any reader’s experiences in this general area too.