opening it up with Common Lisp
Book review: Darwinia
Summer reading: Spin
the Omnivoire's Delimma
the Golem's Eye
Most of the systems we view as networks exist in part to communicate something from one vertex to another (the internet, World Wide Web, food networks, cell metabolism, phone networks, and so on). How well do they succeed in doing so? How easy, in other words, is it to send a message from one vertex to another and what factors influence the ease and speed of transmission. This paper quantifies these questions by defining the search information in going from vertex s to vertex t as the number of bits needed to describe the path. This is the sum of the log (base 2) of the degree of each vertex along the path (actually, you subtract one from the degree of each vertex except for the first, because you know that you're not going to backtrack). (If there are multiple shortest paths, then one takes the sum before applying the log). They then measure this for some real graph and for the corresponding random graph (which they define as one that has the same degree distribution and remains connected). This value, delta S = S-graph - S-random, measures how much more (or less) information we need to describe paths in our graph due to its topology. If delta S is positive, then we have longer descriptions; if negative, shorter ones. Interestingly, many real world networks optimize communication for paths of length around 2 or 3. They then go on to investigate modular, hierarchical and scale-free graphs as compared to random ones and find, for example, that hierarchies are not (necessarily) optimal for search.
This points a way towards measuring information flow in real organizations and perhaps finding structures that enhance the actual goals of an organization rather than hinder them.
The paper continues with a discussion of how global information can aid search and how to stratify information so that the best properties of local and global search are achieved simultaneously. This "scale invariant" strategy selects directions "according to the average traffic to nodes at distances similar to that of the searched target node."
I found this paper very interesting. Its writing is clear, the content useful and the results non-trivial. The Nordic Institute for Theoretical Physics is doing some neat stuff.
Copyright -- Gary Warren King, 2004 - 2006