LISTSERV mailing list manager LISTSERV 15.5

Help for SOCNET Archives

SOCNET Archives

SOCNET Archives


Next Message | Previous Message
Next in Topic | Previous in Topic
Next by Same Author | Previous by Same Author
Chronologically | Most Recent First
Proportional Font | Monospaced Font


Join or Leave SOCNET
Reply | Post New Message
Search Archives

Subject: Re: another scientist discovers 6 degrees
From: "Karim R. Lakhani" <[log in to unmask]>
Reply-To:[log in to unmask]
Date:Wed, 7 Sep 2005 21:07:23 -0400

text/plain (169 lines)

*****  To join INSNA, visit  *****

I guess sociologists better start putting out press releases and back
dating them as well. :)

Miller McPherson wrote:
> *****  To join INSNA, visit  *****
> Well,
>      It's good to see that the computer scientists have invented homophily
> too...
> Miller
> On Wed, 7 Sep 2005, Barry Wellman wrote:
>>*****  To join INSNA, visit  *****
>>A U Mass Amherst press release, courtesy of ACM TechNet
>>Like almost all other write-ups, they do not note that the great majority
>>of networks did Not reach the target.*
>>Indeed, when I replicated via email with my cousin Lloyd** in Calif a few
>>years ago, I gave up when I realized how few were reaching the target.
>>But then again I am not a computer scientist or a physicist!
>>*Thanks to Charles Kadushin for pointing this out.
>>** The dropouts missed a wonderful guy and a hunk who may be on The
>>Bachelor this year.
>> Barry
>> _____________________________________________________________________
>>  Barry Wellman         Professor of Sociology        NetLab Director
>>  wellman at
>>  Centre for Urban & Community Studies          University of Toronto
>>  455 Spadina Avenue    Toronto Canada M5S 2G8    fax:+1-416-978-7162
>>             To network is to live; to live is to network
>> _____________________________________________________________________
>>“Six Degrees of Separation” Theory Explained in New Algorithm by UMass
>>Amherst Researchers
>>Sept. 6, 2005
>>Contact:        Rachel Ehrenberg
>>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.
>>SOCNET is a service of INSNA, the professional association for social
>>network researchers ( To unsubscribe, send
>>an email message to [log in to unmask] containing the line
>>UNSUBSCRIBE SOCNET in the body of the message.
> ********************************        *
> Miller McPherson                     *  *
> Professor of Sociology               ******
> University of Arizona                   *
> [log in to unmask]                  *
> ********************************        *
> _____________________________________________________________________
> SOCNET is a service of INSNA, the professional association for social
> network researchers ( To unsubscribe, send
> an email message to [log in to unmask] containing the line
> UNSUBSCRIBE SOCNET in the body of the message.

Karim R. Lakhani
MIT Sloan | The Boston Consulting Group
Mobile: +1 (617) 851-1224 |
My *new* book:

SOCNET is a service of INSNA, the professional association for social
network researchers ( To unsubscribe, send
an email message to [log in to unmask] containing the line
UNSUBSCRIBE SOCNET in the body of the message.

Back to: Top of Message | Previous Page | Main SOCNET Page



CataList Email List Search Powered by the LISTSERV Email List Manager