Community Detection
In social networks, people naturally form groups — friends, colleagues, interest groups. In graph theory, a community is a group of nodes that are more densely connected to each other than to the rest of the network.
Explicit Community
Groups defined externally (e.g., departments, classes)
Implicit Community
Groups that emerge from the pattern of connections
Strong Internal Connections
Many edges within the community
Weak External Connections
Few edges between communities
Disjoint Communities
Every node belongs to exactly one community
Overlapping Communities
A node can belong to multiple communities (e.g., someone in two friend groups)
Community Explorer
Node Information
Click on a node to see its community information
Cliques
What is a clique?
A clique is a subset of nodes where every pair is directly connected — a complete subgraph. A maximal clique is a clique that cannot be extended by adding another node while keeping all edges.
Clique Percolation Method
Intuition
CPM finds overlapping communities by connecting k-cliques that share k-1 nodes.
Step-by-step Process
- Find all k-cliques (use k=3 by default)
- Build a 'clique graph': each k-clique is a node, edges connect cliques sharing k-1 nodes
- Find connected components in the clique graph
- Each component = one community (nodes may overlap!)
Member-based vs Group-based Detection
Member-based (Bottom-up)
Start with individual nodes and group them based on similarity.
Example: Louvain algorithm
Group-based (Top-down)
Look for specific structures like cliques and merge them.
Example: Clique percolation
Common Misunderstanding
Communities are NOT just clusters of highly connected nodes. The definition is relative — a community has MORE internal connections than expected by chance. This is why we need modularity to measure community quality (covered in the next page).