Navigation in a small world

Navigation in a small world
It is easier to find short chains between points in some networks than others.
NATURE | VOL 406 | 24 AUGUST 2000 | Jon M. Kleinberg | Department of Computer Science, Cornell

---

Content:

• Efficient navigability is a fundamental property of only some small-world structures. The pre-condition is:
• • For d-dimensional lattices (d>1), the critical value of the clustering exponent a to achieve the rapidest delivery time is d. In this case, T is bounded by a function proportional to (logN)^2)
• And d is the only exponent at which any decentralized algorithm can achieve a delivery time bounded by any polynomial in logN: for every other exponent, an asymptotically much larger delivery time is required, regardless of the algorithm
  employed.
• The correlation between local structure and long-range connections provides critical cues for finding paths through the network.e.g. p= r ^ (-a), a = d for lattice structure.

Small-world:

• Phenomenon: Each node, u, has a shortrange connection to its nearest neighbours and a long-range connection to a randomly chosen node, where node v is selected with probability proportional to r^(-a), where r is the lattice ('Manhattan') distance between u and v, and a >= 0 is a fixed clustering exponent. More generally, for p, q>=1, each node u has a short-range connection to all nodes within p lattice steps, and q long-range connections generated independently from a distribution with clustering exponent a.
• Experimental study in 1967 by Milgram, S revealed that it has two fundamental components: first, such short chains are ubiquitous, and second, individuals operating with purely local information are very adept at finding these chains.
• Paradigm: they are rich in structured short-range connections and have a few random long-range connections.
• Characteristic feature: their diameter is exponentially smaller than their size, being bounded by a polynomial in logN, where N is the number of nodes.

Inspiration:

• This is an interesting result. Want to know more about the 'greedy' heuristic. There must be a precondition that the number of long-distance connection is limited.
• Author explain above result by using "gradient" for analog. i.e. the correlation between local strucutre and long-range connections forms a type of gradient to allow individuals to guide a message efficiently towards a target. When correlation drops, the social network becomes more homogeneous, then gradient decrease, i.e. when long-range connections are generated uniformly at random, the result is a world in which individuals, faced with a disorienting array of social contacts, are unable to find them.
• In real world, how to map the lattice to real world? e.g. the real physical distance between people.
• When analyzing P2P network, local strucutre and long-range connections is two critical elements need always keep in mind. The correlation is sth hard to find.

Reference:

• Milgram, S. Psychol. Today 1, 61-67 (1967).

Technorati : small-world