A better way to find communities in networks

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.