A better way to find communities in networks

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 .

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 . 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 Zhang and Moore are looking for.

More information: "Scalable detection of statistically significant communities and hierarchies, using message passing for modularity" PNAS 2014 ; published ahead of print December 8, 2014, DOI: 10.1073/pnas.1409770111

Provided by Santa Fe Institute

Citation: A better way to find communities in networks (2014, December 9) retrieved 14 July 2024 from https://phys.org/news/2014-12-networks.html
This document is subject to copyright. Apart from any fair dealing for the purpose of private study or research, no part may be reproduced without the written permission. The content is provided for information purposes only.

Explore further

New technique for dataset cluster detection


Feedback to editors