key to network searches
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
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
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
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:
29/June 5, 2002
Crystal turns heat to
fuels atom lasers
Groups key to network
Reverb keeps secrets
safe and sound
Research News Roundup
Research Watch blog
View from the High Ground Q&A
How It Works
News | Blog
Buy an ad link