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


Communication Boundaries in Networks
A. Trusina and M. Rosvall and K. Sneppen, 2005 , (Paper URL)
Thursday, July 14, 2005

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.

[The fact] that (club) hierarchies are used in many human organizations may thus be seen as a way to regulate and thus limit the information exchange, rather than optimize it.

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.

Home | About | Quotes | Recent | Archives

Copyright -- Gary Warren King, 2004 - 2006