Detecting Patterns in Complex Social Networks

By Roland Piquepaille

So-called social networking is very popular these days, as shows the proliferation of services like Friendster, Orkut and dozens of others. But do the companies behind these services have any idea of what is hidden inside their complicated networks? When these networks reach a size of millions of users, it's not an easy task. A researcher at the University of Michigan is trying to help, with a new method for uncovering patterns in complicated networks, from football conferences to food webs.

Let's start with a spectacular representation of the Internet (Credit: Bill Cheswick, Lumeta Corp.). A larger version is viewable here.

A representation of the Internet
"The structure of those networks can tell you quite a lot about how the systems work, but they're far too big to analyze by just putting dots on a piece of paper and drawing lines to connect them," said Mark Newman, an assistant professor of physics and complex systems at the University of Michigan.
One challenge in making sense of a large network is finding clumps -- or communities -- of members that have something in common, such as Web pages that are all about the same topic, people that socialize together or animals that eat the same kind of food.

Newman and his collaborators developed a new method for finding communities in these large networks.

The way most people have approached the problem is to look for the clumps themselves -- to look for things that are joined together strongly," said Newman. "We decided to approach it from the other end," by searching out and then eliminating the links that join clumps together. "When we remove those from the network, what we're left with is the clumps."

They applied their method on networks with well-known structures, such as college football conferences. They also used it for networks with less-known structures, such as a food web of marine organisms living in Chesapeake Bay.

Here is what looks like a food web at Little Rock Lake (Credit: Mark Newman).

A food web at Little Rock Lake

You'll find more illustrations in this gallery of network images.

And for more information about social-network mapping tools, you can look at two previous columns, here or there.

Sources: University of Michigan press release, February 15, 2004; and various websites


Famous quotes containing the words networks, social, detecting, patterns and/or complex:

    To be perfectly, brutally honest, those of us who are still carrying diaper everywhere we go are not at our most scintillating time of life....We need to remember that at one time in our lives, we all had senses of humor and knew things that were going on in the world. And if we just keep our social networks open, there will be people ready to listen when we once again have intelligent things to say.
    Louise Lague (20th century)

    It is thus that the few rare lucid well-disposed people who have had to struggle on the earth find themselves at certain hours of the day or night in the depth of certain authentic and waking nightmare states, surrounded by the formidable suction, the formidable tentacular oppression of a kind of civic magic which will soon be seen appearing openly in social behavior.
    Antonin Artaud (1896–1948)

    In our Mechanics’ Fair, there must be not only bridges, ploughs, carpenter’s planes, and baking troughs, but also some few finer instruments,—rain-gauges, thermometers, and telescopes; and in society, besides farmers, sailors, and weavers, there must be a few persons of purer fire kept specially as gauges and meters of character; persons of a fine, detecting instinct, who note the smallest accumulations of wit and feeling in the bystander.
    Ralph Waldo Emerson (1803–1882)

    One can describe a landscape in many different words and sentences, but one would not normally cut up a picture of a landscape and rearrange it in different patterns in order to describe it in different ways. Because a photograph is not composed of discrete units strung out in a linear row of meaningful pieces, we do not understand it by looking at one element after another in a set sequence. The photograph is understood in one act of seeing; it is perceived in a gestalt.
    Joshua Meyrowitz, U.S. educator, media critic. “The Blurring of Public and Private Behaviors,” No Sense of Place: The Impact of Electronic Media on Social Behavior, Oxford University Press (1985)

    The human mind is so complex and things are so tangled up with each other that, to explain a blade of straw, one would have to take to pieces an entire universe.... A definition is a sack of flour compressed into a thimble.
    Rémy De Gourmont (1858–1915)