From: Eugene Leitl (eugene.leitl@lrz.uni-muenchen.de)
Date: Wed Sep 06 2000 - 13:51:14 PDT
I notice tantalizing similiarities to my routing in randomly connected
hypergrids ravings and rantings from a few years ago (I ran into them
when deriving randomly meshed hyperlattices with decaying connectivity
while playing with the n-hypercube connectivity tables, and had a
strong hunch that they were very handy for routing, provided the Net
would be rewired in a certain fashion).
Can someone with online access to Nature mail me the .pdf of the
paper? (I can reciprocate with .pdf stuff from Science).
Larry Klaes writes:
> Date: Tue, 22 Aug 2000 10:39:25 -0400
> Reply-To: cunews@cornell.edu
> Sender: owner-CUNEWS-SCIENCE-L@cornell.edu
> From: cunews@cornell.edu
> To: CUNEWS-PHYSICAL_SCIENCE-L@cornell.edu, CUNEWS-SCIENCE-L@cornell.edu
> Subject: Cornell News: How small worlds work
> X-PH: V4.1@postoffice.mail.cornell.edu (Cornell Modified)
> X-Sender: cunews-mailbox@postoffice4.mail.cornell.edu
>
> How does 'six degrees of separation' work? Explanation is personal
> networking, Cornell computer scientist says
>
> EMBARGOED FOR RELEASE: 2 p.m., Wednesday, Aug. 23, 2000
>
> Contact: Bill Steele
> Office: (607) 255-7164
> E-mail: ws21@cornell.edu
>
>
> ITHACA, N.Y. -- We all know it's a small world: Any one of us is only about
> six acquaintances away from anyone else. Even in the vast confusion of the
> World Wide Web, on the average, one page is only about 16 to 20 clicks away
> from any other. But how, without being able to see the whole map, can we
> get a message to a person who is only "six degrees of separation" away?
>
> A Cornell University computer scientist has concluded that the answer lies
> in personal networking: We use "structural cues" in our local network of
> friends. "It's a collective phenomenon. Collectively the network knows how
> to find people even if no one person does," says Jon Kleinberg, assistant
> professor of computer science, who published his explanation in the latest
> issue (Aug. 24) of the journal Nature.
>
> His research is based on a computer model showing that an "ideal" network
> structure is one in which connections spread out in an "inverse square"
> pattern. In human terms that means that an "ideal" person in the model
> would have just about as many friends in the rest of the county as in the
> neighborhood, just as many in the rest of the state as in the county, just
> as many in the whole nation as in the state, and so on, as you might find
> in a highly mobile society.
>
> Kleinberg's answers might have a very practical use in helping to reduce
> the number of clicks needed when surfing the web, as well as helping to
> speed up other kinds of networks.
>
> Although Kleinberg has been instrumental in the development of improved
> search engines for the web, he doesn't see this work as applying to
> traditional search engines. They already have the "big picture" of the
> network, he explains, since they work from indexes of the web. Rather, he
> sees it being useful in the construction of "agents," computer programs
> that will jump around the web looking for specific information.
>
> It could also apply to the distribution of data over the Internet, where
> computers called routers must send packets of information on their way
> toward their destinations without knowing what the state of the network is
> outside of their own immediate neighborhood.
>
> Kleinberg has shown that a computer algorithm (the basic design for a
> program) can choose the best way to send a message to a faraway place in a
> network even if it has knowledge only about the characteristics of its
> immediate neighborhood. "The correlation between local structure and
> long-range connections provides fundamental cues for finding paths through
> the network," he writes in the Nature paper.
>
> Kleinberg's work is a refinement of an earlier study by two other
> Cornellians, Steven H. Strogatz, professor of theoretical and applied
> mechanics, and his graduate student, Duncan Watts, now an assistant
> professor in Columbia University's sociology department.
>
> Strogatz and Watts offered a mathematical explanation for the results of a
> landmark experiment performed in the 1960s at Harvard by social
> psychologist Stanley Milgram. The researcher gave letters to randomly
> chosen residents of Omaha, Neb., and asked them to deliver the letters to
> people in Massachusetts by passing them from one person to another. The
> average number of steps turned out to be about six, giving rise to the
> popular notion of "six degrees of separation," and eventually the "six
> degrees of Kevin Bacon" game in which actors are connected by their movie
> appearances with other actors.
>
> Strogatz and Watts created a mathematical model of a network in which each
> point, or node, is closely connected to many other nodes nearby. When they
> added just a few random connections between a few widely separated nodes,
> messages could travel from one node to any other much faster than the size
> of the network would suggest. The six degrees of separation idea works,
> they said, because in every small group of friends there are a few people
> who have wider connections, either geographically or across social
> divisions. They also showed that such cross-connected networks exist not
> only between human beings but also in such diverse places as computer
> networks, power grids and the human brain.
>
> But Kleinberg has found mathematically that the model proposed by Strogatz
> and Watts doesn't explain how messages can travel so quickly through real
> human networks. "The Strogatz-Watts model had random connections between
> nodes. Completely random connections bring everyone closer together,"
> Kleinberg explains, "but a computer algorithm would have only local
> information. The long-range connections are so random that it [the
> algorithm] gets lost."
>
> 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."
>
> The sender of a message in this system doesn't know where all the
> connections are but does know the general geographic direction of the
> destination, and if messages are sent in that direction, Kleinberg says,
> they arrive much faster than they would by completely random travel.
>
> Kleinberg explains, "The Watts and Strogatz model is sort of like a large
> group of people who know each other purely through electronic chat on the
> Internet. If you are given the user ID of someone you don't know, it's
> really hard to guess which of your friends is liable to help you forward a
> message to them.
>
> "The inverse square model is more like the geographic view of Milgram's
> experiment -- if you live on the West Coast and need to forward a message
> to someone in Ithaca, you can guess that a resident of New York state is a
> good first step in the chain. They are more likely to know someone in the
> Finger Lakes region, who in turn is more likely to know someone in Ithaca
> and so forth. Knowing that our distribution of friends is correlated with
> the geography lets you form guesses about how to forward the message
> quickly."
>
> The geographic information on the grid, he adds, is an analogue of the
> social connections between people. Just as nodes on his simulated network
> choose the correct geographical direction to send a message, so humans may
> choose a social direction: A mathematician who wants to send a message to a
> politician might start by handing it to a lawyer.
>
> On the other hand, he says, "When long-range connections are generated
> uniformly at random, our model describes a world in which short chains
> exist but individuals, faced with a disorienting array of social contacts,
> are unable to find them."
>
> The paper in Nature is titled "Navigation in a Small World."
>
> Related World Wide Web sites: The following sites provide
> additional information on this news release. Some might not be part of the
> Cornell University community, and Cornell has no control over their content
> or availability.
>
> -- Jon Kleinberg's home page: <http://www.cs.cornell.edu/home/kleinber>
>
> -- Nature: <http://www.nature.com>
>
> -30-
>
>
>
> The web version of this release may be found at
>
> http://www.news.cornell.edu/releases/Aug00/kleinberg.small.ws.html
>
>
>
> Cornell University News Service
> Surge 3
> Cornell University
> Ithaca, NY 14853
> 607-255-4206
> cunews@cornell.edu
> http://www.news.cornell.edu
>
>
>
>
> -----BEGIN TRANSHUMANTECH SIGNATURE-----
> Post message: transhumantech@egroups.com
> Subscribe: transhumantech-subscribe@egroups.com
> Unsubscribe: transhumantech-unsubscribe@egroups.com
> List owner: transhumantech-owner@egroups.com
> List home: http://www.egroups.com/community/transhumantech/
> Alt archive: http://excelsior.planetx.com/transhumantech/
> Old archive: http://excelsior.planetx.com/transhumantech/threads.html
> -----END TRANSHUMANTECH SIGNATURE-----
This archive was generated by hypermail 2b29 : Wed Sep 06 2000 - 23:44:56 PDT