New math mixes networking with socializing

by Tom Siegfried

SEATTLE - When scientists encounter something really complicated, they usually invent a buzzword.

In the late 1970s and early 1980s, the buzzword of choice was chaos. In the late '80s and early '90s, it was complexity. And now, in the zeros, the interdisciplinary buzzword of the day is networks. All of a sudden, anything complicated can seem less so, many scientists suggest, if you view it as a network.

Networks are no longer just targets for FCC censorship. The most famous today include the Internet (a network of computer routers and servers) and the World Wide Web (a software network of information stored on "pages"). Many more networks are found in biology, from food webs to the chains of chemical reactions connecting proteins inside a cell.

And perhaps most entertaining of all are the many "social" networks that appear to describe human society and group behavior.

In the last few years, rapid advances in mathematics have given new meaning to the old notion of networking. New equations have improved science's grasp of how dots on paper can be connected by lines, and novel insights have emerged on how those dots and lines can represent real-world relationships.

For the World Wide Web, the "dots" are Web pages; the "lines" connecting them are called "hyperlinks" - addresses that allow your browser to jump from one page directly to another. In a food web, the dots (or "nodes") are plants and animals; the lines (or "links") correspond to eating. One species is linked to another by virtue of its menu preferences.

Once the nodes and links are identified, the new network math can help you can figure out things like how many jumps it takes to get from one page to another, or which nodes are megaconnected (making them "hubs") and which are the hangers-on with only a few links to other network members.

In social networks, the nodes might be individual people or groups of people; the links are interactions of some sort between the people or the groups. Since humans interact in many ways, people can simultaneously be part of many different networks - which is a way of saying there are many possible network-based methods of describing society.

One way of interacting is by spreading disease. So medical researchers might want to understand the spread of tuberculosis, for instance, by considering people as "linked" in a network if they come into close physical proximity. For the spread of sexually transmitted diseases, such as AIDS, the notion of a link becomes a little more literal.

Another sort of social network would consist of people linked by e-mail messages. An analysis based on network math might help find ways to stem the spread of spam or computer viruses.

"You can do a kind of mathematical epidemiology of computer viruses in a similar way to what you can do for human being infections," says Mark Newman, a physicist and complex systems expert at the University of Michigan.

All the world's problems have not yet been solved, though, because network science is still in its infancy. Many important issues remain murky. How, for example, can you figure out what subgroups exist within a big network?

Identifying subgroups can be useful - such as when looking for the people most likely to spread a computer virus, or AIDS.

It sounds like a simple enough task just to identify similar people (or groups) and lump them into common categories. But network math shows that approach to be less than ideal - lots of people who are actually part of a group can be left out in that approach.

Dr. Newman prefers a new approach, devised with collaborator Michelle Girvan, a postdoctoral fellow at the Santa Fe Institute in New Mexico. Instead of looking for similarities, it's a better strategy to identify people in the network who are the least similar to each other. By eliminating the links between the dissimilar members, you cut the network into segments that are, in fact, tightly interrelated.

Basic simulations show that this approach is quite effective, Dr. Newman reported last week in Seattle at the annual meeting of the American Association for the Advancement of Science. And it seems to work pretty well in some real-world situations.

For example, a previous study of a karate club had measured friendship links between the members to analyze the group's network structure. Later, a dispute between the club's owner and teacher caused a breakup of the 34 members into two new clubs. Drs. Newman and Girvan's method correctly identified who went with which camp for all but one person.

Further support came from a study of the 2000 college football season. College teams participate in conferences, and usually play more games against same-conference opponents than against other schools. So just by analyzing the network of games played (schools are the nodes, schools playing each other are linked), Drs. Newman and Girvan could determine how the nation's teams are organized into conferences with high accuracy.

This progress in network math, then, raises the exciting possibility of explanations for some truly important mysteries - such as what happened to the old Southwest Conference, and why the Horned Frogs keep hopping from one conference to another.