Ten
years ago newly hired mathematical physicist Jennifer Chayes told her boss, Microsoft Corp
founder Bill Gates, about new methods, derived from the phase-transition theory of spin glasses,
to solve constraint-satisfaction problems in social and other networks. She warned him, however,
that they "would take 100 years to pay off."
Chayes, who cofounded Microsoft's
theory group with her husband and fellow physicist, Christian Borgs, recently contacted Gates
to say, "I can't believe it, Bill. It has only taken 10 years to pay off."
Now, as director of Microsoft's
new research laboratory in Cambridge, Massachusetts, Chayes will assemble and lead groups of
social, computer, and physical scientists to model and design online social networks. Microsoft
Research New England is the company's sixth research lab and the first with the mission of bringing
together social and computer scientists to work on algorithms for social computing applications.
More than just message boards, online social network applications such as Facebook, MySpace,
and LinkedIn have become popular venues for advertising and search companies; industry analysts
speculate that the new Microsoft lab and the company's bid for internet rival Yahoo Inc point to
the urgency that the software giant is placing on competing online. Microsoft Research New England
is expected to open this summer, just less than a year after it was first proposed, says mathematician
Henry Cohn, a founding member of the new lab. "One of the advantages of industry is that when there
is a compelling case for something, it can get done quickly."
Use of the Web has surged
with the popularity of so-called Web 2.0 applications, which allow users to generate content and
form communities. Several physicists, including Chayes, saw opportunities in the late 1990s
to apply statistical mechanics principles to analyze complex networks like the Web. Peter Norvig,
director of research at Google Inc, says the online search and advertising company employs "well
over 100 people with one or more degrees in physics" to work on mathematical problems. "The reason
I think that physicists do so well [in network theory] is that we are used to dealing with very large
systems with lots of similar and interacting entities," says Chayes. "In the case of the World Wide
Web, for example, there are on the order of 100 billion static webpages and even more dynamically
generated webpages."
Highly connected hubs
Researchers studying self-organizing
social networks look at how links are formed between individuals, whether some individuals or
nodes are better connected than others, and the collective action or behavior of the entire network.
In the past social scientists relied on surveys and questionnaires, but on the Web "social behavior
is self-documenting—it leaves traces behind," says Microsoft research sociologist Marc
Smith, who studies and designs improvements for social online applications.
Duncan Watts, director
of the human social dynamics group at Yahoo Research, is using Friend Sense, an application he wrote
for Facebook that queries users' political attitudes and how well they know their friends. Watts,
who holds a bachelor's degree in physics and is also a Columbia University sociology professor,
may be best known for showing that so-called small-world networks can be characterized by a small
path length between nodes (related to the six degrees of separation) and a large degree of clustering
among nodes (see PHYSICS TODAY, September 1998, page 17). For example, Bernardo Huberman, a physicist
and director of the social computing group at Hewlett-Packard Co labs, recently scoured 362 million
messages, minus the identifying information, of 4.2 million Facebook users and found that college
students cluster by school affiliation.
"Social networks do offer
one of the best-described systems that you can monitor in the most precise way," says Albert-László
Barabási, director of the Center for Complex Network Research at Northeastern University.
"We are using them to find fundamental organizing principles that can be tested in other systems
as well." In 1999, Barabási used Web-crawling data to show that many complex networks were
scale-free—a few nodes are highly connected hubs. Models that involve universality laws
for complex networks are being applied to studies of how viruses spread on the internet and in human
and biological populations, among other things, says physicist Mark Newman of the University
of Michigan Center for the Study of Complex Systems. Online advertisers and developers can also
take advantage of such network models to tailor their services for users based on interaction patterns
or even devise incentives and mechanisms to influence people's behavior, says CSCS physicist
Lada Adamic, who with Huberman in 1999 also showed that Web growth is scale-free.
Spin-glass payoff
Some condensed-matter physicists
are drawn to social network modeling because it is similar to a many-body problem, says Huberman.
Like spin-glass materials that have disordered and unpaired magnetic spins, individuals have
conflicting interactions with their neighbors, and their uniqueness leads to disorder, says
Université de Paris-Sud physicist Marc Mézard. It's a patent from Mézard's spin-glass
theory work that is now paying off for Microsoft: He, Chayes, and collaborators are using that patent
to solve optimization problems such as sending messages from one node to others, bypassing intermediates.
The researchers interviewed
for this story say precautions are taken to protect the privacy of the personal information they
use. "There's a very sticky privacy issue here," says Yahoo Research head Prabhakar Raghavan.
"Data that we get from [our academic collaborators] goes through all manner of scrubbing and approval
procedures within the company from the legal department. The principle we follow is, we use the
data as we need it, then it gets destroyed."
Complex network models
do not capture the nuances of human behavior, says Huberman. "People, unlike atoms and spins, are
intentional beings, which limits the validity of many-body physics approaches." Sometimes individuals
do alter their behavior, adds Barabási, "but at the end of the day, collective behavior doesn't
change."
Featured Jobs
