If there is a group of nodes such that they are densely connected within the group but sparsely connected to the outside, that group is called a community (or cluster). Community detection is the problem of finding these groups automatically from the graph structure.
Applications
Community detection is useful across many domains:
- Social networks
- Meta-structure analysis
- Protein interaction networks
- Rumor and epidemic spreading
Social Networks
Communities appear prominently in social networks — as friend groups, families, colleagues, or people who share interests. Detecting them enables hierarchical analysis and more precise advertisement targeting.
Meta-Structure
Community detection helps understand the overall nature of a graph — abstracting out the important structural patterns and compressing complex networks into interpretable summaries.
Protein Interaction Networks
In protein interaction networks, communities correspond to groups of proteins that perform similar biological functions, which is critical for drug discovery and systems biology.
Rumor and Epidemic Spreading
By detecting inter-community links, community detection can help control the spread of rumors or epidemics — identifying the bridges between clusters is key to containment strategies.
Modularity
Most community detection algorithms optimize a quality metric called modularity. Modularity is high when detected communities have dense internal connections and sparse external ones. It provides a principled way to compare different community detection approaches and evaluate their quality.
In further posts we will discuss specific community detection algorithms and trace through how they work step by step.
Back to Blog