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: Miller McPherson <[log in to unmask]>
Reply-To:Miller McPherson <[log in to unmask]>
Date:Wed, 7 Sep 2005 18:03:43 -0700

TEXT/PLAIN (146 lines)

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

     It's good to see that the computer scientists have invented homophily

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!
> Notes:
> *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
> 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.
> _____________________________________________________________________
> 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.

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



CataList Email List Search Powered by the LISTSERV Email List Manager