Clique Percolation Method (CPM) for detecting overlapping communities.
Identifies communities by finding "chains" of adjacent k-cliques. Two k-cliques are adjacent if they share k-1 nodes. Unlike other algorithms, CPM can identify nodes that belong to multiple communities.
Algorithm
- Find all maximal cliques (using Bron-Kerbosch)
- Extract all k-cliques from maximal cliques
- Build adjacency between k-cliques (share k-1 nodes)
- Find connected components of k-cliques
- Merge cliques in each component to form communities
When to Use
| Use Case | Recommendation |
|---|---|
| Overlapping communities | ✓ Only algorithm in this module |
| Dense networks with cliques | ✓ Excellent |
| Sparse graphs | ✗ May find no communities |
| Non-overlapping needed | Convert with to_communities/1 |
Complexity
- Time: O(3^(V/3)) for maximal clique enumeration (worst case)
- Space: O(V + E)
Note: Clique enumeration can be expensive on large or dense graphs.
Example
# Detect overlapping communities (k=3 finds triangles)
overlapping = Yog.Community.CliquePercolation.detect_overlapping(graph)
# Convert to non-overlapping (assigns node to first community)
communities = Yog.Community.CliquePercolation.to_communities(overlapping)
# With custom k
overlapping = Yog.Community.CliquePercolation.detect_overlapping_with_options(graph,
k: 4
)References
Summary
Types
Options for Clique Percolation Method
Functions
Returns default options for CPM.
Detects overlapping communities using CPM with default options.
Detects overlapping communities using CPM with custom options.
Converts overlapping communities to standard communities.
Types
@type cpm_options() :: %{k: integer()}
Options for Clique Percolation Method
Functions
@spec default_options() :: cpm_options()
Returns default options for CPM.
Defaults
k: 3 - Size of the clique (typically 3 or 4)
@spec detect_overlapping(Yog.graph()) :: Yog.Community.Overlapping.t()
Detects overlapping communities using CPM with default options.
Returns overlapping communities where each node can belong to multiple communities.
Example
overlapping = Yog.Community.CliquePercolation.detect_overlapping(graph)
IO.inspect(overlapping.num_communities)@spec detect_overlapping_with_options(Yog.graph(), keyword() | map()) :: Yog.Community.Overlapping.t()
Detects overlapping communities using CPM with custom options.
Options
:k- Clique size (default: 3)
Example
overlapping = Yog.Community.CliquePercolation.detect_overlapping_with_options(graph,
k: 4
)@spec to_communities(Yog.Community.Overlapping.t()) :: Yog.Community.Result.t()
Converts overlapping communities to standard communities.
Each node is assigned to the first community in its membership list.
Example
overlapping = Yog.Community.CliquePercolation.detect_overlapping(graph)
communities = Yog.Community.CliquePercolation.to_communities(overlapping)
IO.inspect(communities.num_communities)