100 node power law net; click for full size.
Search statistics for large net; click for full size
Computing and Networking have been getting great help from the oddest places lately: Mathematicians and Sociologists! The Santa Fe Institute's Summer School had two of the best talking about Small Worlds, Power Laws, near-optimal search paths, and the meaning of life. As far out as this seems, many of us in the trenches are seeing the tools of complex adaptive systems very applicable to our current work. Is Math the Next Big Thing? Could be!
I was lucky enough to catch the two days of this year's Complex Systems Summer School at the Santa Fe Institute which discussed networks. The two speakers were 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 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 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.