"Six Degrees of Separation" Theory Explained in NewAlgorithm

[David Farber <dave () farber net>]

Begin forwarded message:

From: Dewayne Hendricks <dewayne () warpspeed com>
Date: October 16, 2005 2:54:47 PM EDT
To: Dewayne-Net Technology List <dewayne-net () warpspeed com>
Subject: [Dewayne-Net] "Six Degrees of Separation" Theory Explained  
in NewAlgorithm
Reply-To: dewayne () warpspeed com


[Note:  This item comes from reader Scott Berry.  A bit date, but I'm  
in catch up mode.  DLH]


> From: Scott Berry <sjb () optonline net>
> Date: September 8, 2005 11:42:20 AM PDT
> To: dewayne-net () warpspeed com
> Subject: FW: [CAnet - news] "Six Degrees of Separation" Theory  
> Explained in NewAlgorithm
>
>
> Dewayne,
>
> Not sure if you're on Bill's news list, but
> I found this very interesting, nonetheless.
>
>    Scott
>
>
> -----Original Message-----
> From: news-bounces () canarie ca [mailto:news-bounces () canarie ca] On  
> Behalf Of
> Bill St.Arnaud
> Sent: Thursday, September 08, 2005 2:08 PM
> To: news () canarie ca
> Subject: [CAnet - news] "Six Degrees of Separation" Theory  
> Explained in
> NewAlgorithm
>
> For more information on this item please visit the CANARIE CA*net 4  
> Optical
> Internet program web site at http://www.canarie.ca/canet4/library/ 
> list.html
> -------------------------------------------
>
> [Thanks to Harvey Newman for this pointer.  This theory has  
> interesting
> implications for networking -- BSA]
>
>
>
>  http://www.umass.edu/newsoffice/newsreleases/articles/20618.php
>
> "Six Degrees of Separation" Theory Explained in New Algorithm by UMass
> Amherst Researchers
>
> Sept. 6, 2005
>
> Contact:        Rachel Ehrenberg <mailto:rachele () admin umass edu>
> 413/545-0444
>
> AMHERST, Mass. - University of Massachusetts Amherst researchers have
> invented a new algorithm that solves a network-searching conundrum  
> that has
> puzzled computer scientists and sociologists for years.
>
> The scientists created an algorithm that helps explain the  
> sociological
> findings that led to the theory of "six degrees of separation," and  
> could
> have broad implications for how networks are navigated, from improving
> emergency response systems to preventing the spread of computer  
> viruses.
>
> Dubbed expected-value navigation, the algorithm describes an  
> efficient way
> of searching a particular class of networks and was presented by  
> doctoral
> student Ozgur S,ims,ek, and David Jensen, professor of computer  
> science, at
> the 19th International Joint Conference on Artificial Intelligence in
> Edinburgh, Scotland.
>
> The algorithm is applicable to a number of networks say the  
> researchers.
> Ad-hoc wireless networks, peer-to-peer file sharing networks and  
> the World
> Wide Web are all systems that could benefit from more efficient
> message-passing. The algorithm could work especially well with dynamic
> systems such as ad-hoc wireless networks where the structure may  
> change so
> quickly that a centralized hub becomes obsolete.
>
> The work was inspired by research pioneered in the late 1960s that  
> focused
> on navigating social networks, explains S,ims,ek. In a now famous  
> study by
> psychologists Milgram and Travers, individuals in Boston and Omaha,  
> Neb.,
> were asked to deliver a letter to a target person in Boston, but  
> via an
> unconventional route: the message had to be passed through a chain of
> acquaintances. The people starting the chain had some basic  
> information
> about the target individual-including name, age and occupation-and  
> were
> asked to forward the letter to someone they knew on a first-name  
> basis in an
> effort to deliver it through as few intermediaries as possible. Of the
> letters that reached the target, the median number of people in the
> message-passing chain was a mere six.
>
> "What came out of that study was that we are all connected," says  
> S,ims,ek.
> But the findings also raised a number of questions about how we are
> connected, she says. What are the properties of these networks and  
> how do
> people efficiently navigate them?
>
> The social network exploited by Travers and Milgram isn't a  
> straightforward,
> evenly patterned web. For one thing, network topology is only known
> locally-individuals starting with the letter did not know the target
> individual-and the network is decentralized-it didn't use a formal  
> hub such
> as the post office. If navigating such a network is to succeed-and  
> tasks
> such as searching peer-to-peer file sharing systems or the  
> navigating the
> Web by jumping from link to link do just that-there must be parts  
> of the
> underlying structure that successfully guide the search, argue  
> Jensen and
> S,ims,ek.
>
> Participants in the Travers and Milgram study who efficiently sent the
> message probably acted intuitively by combining two human traits  
> that apply
> to computerized network-searching as well, say the researchers.  
> People tend
> to associate with people who are like themselves, and some  
> individuals are
> more gregarious than others. "Searching" using both of these  
> factors, one
> can efficiently get to a target even when little is known about the
> network's structure.
>
> The tendency of like to associate with like, or homophily, means that
> attributes of a node-an individual in the Travers and Milgram study- 
> tend to
> be correlated. Bostonians often know other Bostonians, and the same  
> holds
> true for qualities such as age or occupation. The second important
> characteristic of these networks is that some people have many more
> acquaintances than others. This "degree disparity" leads to some  
> individuals
> acting as hubs.
>
> Taking these factors into account simultaneously results in a  
> searching
> algorithm that gets messages to the target by passing it to gregarious
> individuals who are most like the target. Or in the language of
> network-searching, it favors nodes that maximize the probability of  
> linking
> directly to the target, which is a function of both degree and  
> homophily,
> say the scientists.
>
> Previous research had explored these aspects separately, but  
> S,ims,ek and
> Jensen are the first to step back and incorporate both these  
> qualities into
> one broadly applicable algorithm with a strong basis in probability  
> theory.
> And the combination yields a powerful punch. It is remarkably  
> efficient at
> finding the short paths between nodes without knowing the central  
> network's
> structure, say the researchers
>
> "In this case, one plus one is more than two," says S,ims,ek.

Weblog at: <http://weblog.warpspeed.com>



-------------------------------------
You are subscribed as lists-ip () insecure org
To manage your subscription, go to
 http://v2.listbox.com/member/?listname=ip

Archives at: http://www.interesting-people.org/archives/interesting-people/