Re: [>Htech] Cornell News: How small worlds work

Date view Thread view Subject view Author view

From: Gordon Mohr (
Date: Fri Sep 08 2000 - 17:33:00 PDT

Cornell News wrote:
> > So Kleinberg designed a model in which nodes are arranged in a square grid
> > and each node is connected randomly to others but with "a bias based on
> > geography." As a result each node is connected to many nearby, a few at a
> > longer distance and even fewer at a great distance -- the "inverse square"
> > structure. "This bias builds in the structural cues in my long-range
> > connections, and it's the bias that is implicitly guiding you to the
> > target," Kleinberg explains. "In the Strogatz-Watts model, there is no bias
> > at all and, hence, no cues -- the structure of the long-range connections
> > gives you no information at all about the underlying network structure."
Seems like the next abstract step would be to start with a situation where
nodes only know local connections, but then discover lengthier routes, in
the optimal proportions. Something like, "I know how to reach all of my
neighbors, then how to reach 1/(n^x) of all the nodes reachable in x-1

Exactly which distant nodes to discover/remember would be determined by a
broadcast probe and consistent hashing: that is, bias the probe message to
go "further" (more geographic hops) as it finds nodes "closer" (on the
hashed unit circle).

Or is such an approach already "old hat" in this field?

- Gordon

Date view Thread view Subject view Author view

This archive was generated by hypermail 2b29 : Fri Sep 08 2000 - 17:39:13 PDT