Groups key to network searches

By Kimberly Patch, Technology Research News

Sociologists and marketers alike recognize that links between people follow patterns that can be exploited to more clearly understand group behavior.

One tantalizing clue to the way very large groups of people are connected is the tidy 1967 result of sociologist Stanley Milgram's postal experiment. The six-degrees-of-separation cliche was spawned when Milgram found that it took an average of only six exchanges, or hops, between people and their acquaintances for a letter to find its way from a person in Omaha, Nebraska to a Boston recipient the original sender did not know.

It's taken much longer for scientists to tease out a theory that explains Milgram's empirical evidence.

A group of researchers from Columbia University have constructed a mathematical model that explains just how this can be. The model promises to provide insights into social behavior and also shed light on the structure of other networks, like the World Wide Web. The relationship between two people who know each other is analogous to a link between Web pages. The work could lead to better search techniques for the Web.

Groups are the crux of the matter, according to Duncan Watts, an associate professor of sociology at Columbia University. "We all belong to groups, and the set of groups each of us belongs to is one way to characterize us."

Groups are responsible for determining who we meet and helping us measure how similar we are to others, said Watts. "So when I show you a description of someone and you think 'I am nothing like this person' you're really thinking 'I don't belong to any of the social groups that this person belongs to, therefore I'm not likely to run into [him].'" Someone who belongs to a country club in Bel Air, for instance, is unlikely to be in the same group as a Georgia farmer.

What makes the six-degrees-of-separation, or small-world, phenomenon possible is that although we tend to aggregate into groups, any given person tends to be a member of several groups, said Watts. "This is where the trick is," he said. Although we tend to associate with people who are like us, we have more than one way of assessing these similarities, Watts said. "For instance, you're close to the people you work with. And you're close to the people you went to college with. But they're not necessarily all that close to each other."

Because of this, individuals can span very different groups, or social dimensions, said Watts. Take, for instance, three people: A, B, and C. A can be close to B in a group defined by geography, and B can be close to C in occupation, but A and C may perceive each other as far apart.

To get from one person to any other, a message can be directed through these groups to find its target relatively quickly, said Watts. "As long as A knows that B is more like C than A... all A needs to do is pass the message to B and rely on B having better information. B then makes use of her other dimension to direct the message," he said.

Previous research pointed out that if Milgram's results were true, these types of short paths must not only exist in social networks, but people must be able to find them without much information about the world, said Watts. "Our contribution has been to show how this can be done in a way that is sociologically plausible," he said.

Surprisingly, the model showed that people don't have to belong to very many groups for the small-world phenomenon to kick in, said Watts. The optimal performance of a social network occurs when individuals are members of an average of only two or three groups, which is the number people actually tend to be in, he said. "We expected there to be a trade-off between too few and too many social dimensions, but we didn't expect the optimal number to be so low," he said.

Ultimately, there is more to a network than the pattern of connections between people or Web pages, said Watts. Network nodes like people and Web pages "have classifiable properties that predate the network structure," said Watts.

A full understanding of the structure of a network requires an understanding of this social structure, which is, after all, what brought about the network's connections, Watts said. "You can't understand the network structure without first understanding social structure. They're related, but they're not the same thing," he said.

The model could eventually improve the algorithms used for searching computer networks like the Web, said Watts. This is a case of observing people's behavior, then teaching it computers. "We're... reverse-engineering an empirically-observed capability that people in social networks seem to possess," and using it to solve problems in computer networks, he said.

This natural social model is different from the traditional computer science approach of building complicated search software that operates over a relatively simple network structure, said Watts. The structure of the social network is more complicated, and requires only simple search strategies. "The capabilities... are not due to people using particularly sophisticated [methods] for conducting searches. Rather, the bulk of the work is done for them by the network, which is built in just such a way that even a simple search procedure works," he said.

The model may also have practical applications for sociological problems. It could lead to ways to improve people's access to information through their social networks, said Watts.

Understanding how messages and ideas travel in social networks is an open problem in both sociology and marketing, said Albert-Laszlo Barabasi, a physics professor at the University of Notre Dame and author of the recent book Linked: The New Science of Networks. Structure is easier to analyze in networks like the World Wide Web than in social networks because search engines can map out how pages are connected to each other, he said. "We're missing such tools for... society," he said.

The researchers' searchable model arranges societies' links into a hierarchical topology based on shared geographical habits and interests. "This is an interesting hypothesis, which indeed allows them to explain certain features of how messages travel," said Barabasi.

The work may also provide insights into the Web, Barabasi said. "Such shared-interest-based local organization could be present within the Web as well."

In addition, the Web could help quantitatively prove that this type of hierarchy is present in networks, said Barabasi. "One important step... needs to be taken," he said. The researchers hypothesis should be tested on the link-based topology of the Web, he said.

The researchers are currently turning their model by gathering more empirical evidence. They are also planning to look into what this new network knowledge means for network properties other than searching, said Watts. The model could be used for practical purposes like improving Web searches within two years, he added.

Watts' research colleagues were Peter Sheridan Dodds of Columbia University and Mark E. J. Newman of the Santa Fe Institute. They published the research in the May 17, 2002 issue of the journal Science. The research was funded by the National Science Foundation (NSF), Intel Corporation, and Columbia University.

Timeline:   2 years
Funding:   Corporate, Government, University
TRN Categories:   Internet
Story Type:   News
Related Elements:  Technical paper, "Identity and Search in Social Networks," Science, May 17, 2002; Small World Research Project:


May 29/June 5, 2002

Page One

Speck-sized microscope nears

Crystal turns heat to light

Frozen reservoir fuels atom lasers

Groups key to network searches

Reverb keeps secrets safe and sound


Research News Roundup
Research Watch blog

View from the High Ground Q&A
How It Works

RSS Feeds:
News  | Blog  | Books 

Ad links:
Buy an ad link


Ad links: Clear History

Buy an ad link

Home     Archive     Resources    Feeds     Offline Publications     Glossary
TRN Finder     Research Dir.    Events Dir.      Researchers     Bookshelf
   Contribute      Under Development     T-shirts etc.     Classifieds
Forum    Comments    Feedback     About TRN

© Copyright Technology Research News, LLC 2000-2006. All rights reserved.