Google Play icon

A better way to find communities in networks

Posted December 10, 2014

A key challenge network scientists face is figuring out how networks break down into communities — for example, different groups of friends in a high school social network or species in a food web.

Robustly identifying those communities could be essential to understanding how a network functions, but it’s proved difficult. Now, two SFI researchers have found a better way using methods borrowed from statistical physics.

The problem, Pan Zhang and Cris Moore argue in a paper appearing December 8, 2014 in PNAS, is that finding communities is almost too easy. In one popular approach, researchers begin by breaking a network into a set of communities and computing the set’s modularity, or how dense within-community links are compared with between-community ones. In theory, the highest-modularity set reflects the network’s true community structure.

The problem is that method will often find many highly modular structures with nothing in common,

That suggests “you don’t want the ‘best’ community structure,” Moore says. “Instead, you want to understand what all the good community structures have in common with each other. The consensus of many good solutions is better than the ‘best’ single one.”

To find that consensus, the pair turned to the notion of free energy, which in statistical physics takes into account the twin pressures of lowering a system’s energy and increasing its entropy — the number of different configurations a system has at a given energy. In community detection, that translates into finding many structures with high modularity while at the same time ensuring that each individual structure is fairly similar to the next.

But they couldn’t stop there, because they needed an efficient way to find such community structures.

For that, they turned to the cavity method, originally designed to find lowest-energy states in spin glasses, one of the thorniest challenges in statistical physics. The method, known in computer science as belief propagation, is sort of like an elaborate game of telephone, where rather than whisper a word, neighbors tell each other what group they think they’re in. As players get input from their neighbors, their own beliefs about what group they’re in change. Once—and if—that settles down so that everybody’s confident about which group they’re in, the algorithm has found the sorts of communities Zhang and Moore are looking for.


Featured news from related categories:

Technology Org App
Google Play icon
86,908 science & technology articles

Most Popular Articles

  1. You Might Not Need a Hybrid Car If This Invention Works (January 11, 2020)
  2. Toyota Raize a new cool compact SUV that we will not see in this part of the world (November 24, 2019)
  3. An 18 carat gold nugget made of plastic (January 13, 2020)
  4. Human body temperature has decreased in United States, study finds (January 10, 2020)
  5. Often derided as pests, deer and elk can help young Douglas fir trees under some conditions (December 5, 2019)

Follow us

Facebook   Twitter   Pinterest   Tumblr   RSS   Newsletter via Email