Synopsis: Community spirit

A new algorithm is able to efficiently identify the clusters of nodes, called communities, that tend to form in networks.
Synopsis figure
B. Ball et al., Phys. Rev. E (2011)

A feature of many complex networks—whether they describe social networking or the interactions between proteins in a cell—is that their nodes (the sites of the interactions) tend to cluster into groups, or “communities.”  In a paper appearing in Physical Review E, Brian Ball and his colleagues at the University of Michigan, Ann Arbor, present a new method for finding such communities in a network and determining if and how they overlap, which could be helpful in understanding the functions of a wide range of networked systems.

Most previous attempts to solve the “community detection problem” divide networks into distinct, disjoint groups of nodes, but a better description for many networks would take into account that groups can overlap.  Though this idea has been around for a while, Ball et al. show how to find overlapping groups efficiently, using a principled statistical approach based on a model that assigns edges to groups.  Their algorithm, which they use to analyze passenger airline flights in the US and the interactions between characters in Victor Hugo’s Les Miserables (among other examples), is fast enough to apply to large networks and, as such, represents a promising alternative to other algorithms in the literature.  The largest network the authors analyze—an online social network—has more than four million nodes and 40 million connections between them. – Alex Arenas


Features

More Features »

Announcements

More Announcements »

Subject Areas

Complex Systems

Previous Synopsis

Superconductivity

Rare pressure

Read More »

Next Synopsis

Magnetism

Magnetized plumbing

Read More »

Related Articles

Viewpoint: Language Boundaries Driven by Surface Tension
Interdisciplinary Physics

Viewpoint: Language Boundaries Driven by Surface Tension

A new model of language evolution assumes that changes in the spatial boundaries between dialects are controlled by a surface tension effect. Read More »

Synopsis: Pinpointing Ebbs and Flows of Commuter Traffic
Interdisciplinary Physics

Synopsis: Pinpointing Ebbs and Flows of Commuter Traffic

Vulnerabilities in a city’s public transport system are identified through a network analysis that accounts for the number of passengers and vehicles at any given time. Read More »

Synopsis: Straying from the Norm in Pedestrian Movements
Complex Systems

Synopsis: Straying from the Norm in Pedestrian Movements

Experiments tracking people as they walk down a corridor reveal universal behaviors that, if incorporated into models, could ensure safe flow in large crowds. Read More »

More Articles