Community Detection

Community detection is the task of identifying, within a network or graph, groups of nodes densely connected to each other and with sparser connections to the rest. Those groups—called communities, clusters or modules—reveal the network's internal structure: friendship circles in a social network, functional modules in a protein network.

Modularity

The most used measure for evaluating a division into communities is modularity, introduced by Mark Newman and Michelle Girvan in 2004. It compares how many edges fall within the communities against those that would be expected in a random network with the same degrees. A high value indicates a marked community structure; a value close to zero, that the division does no better than chance. Many algorithms, in fact, simply maximize modularity.

The algorithms

There are several families. The Girvan-Newman method (2002) progressively removes the most “traveled” edges—those with the highest betweenness—to separate communities. The Louvain method (Blondel and colleagues, 2008) optimizes modularity greedily and is very fast, which made it popular for huge networks. The Leiden method (Traag and colleagues, 2019) improves it by guaranteeing that communities are well connected. And label propagation lets each node adopt the majority label of its neighbors until reaching a consensus, in near-linear time.

The challenges

The task has known difficulties. Modularity optimization suffers from a resolution limit—demonstrated by Santo Fortunato and Marc Barthélemy in 2007—: below a certain scale, it tends to merge small, well-defined communities into larger ones. Moreover, in many real networks communities overlap—a node belongs to several—and choosing how many communities there are is not always obvious.

Its relation to AI

Today community detection increasingly relies on machine learning. Graph neural networks tackle the task by first learning vector representations of the nodes and then clustering them, with specific research lines for the overlapping-communities case. It is an active field of research, with applications in biology, social networks and recommender systems.