yog/community/clique_percolation

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

1. Find all maximal cliques (using Bron-Kerbosch)
2. Extract all k-cliques from maximal cliques
3. Build adjacency between k-cliques (share k-1 nodes)
4. Find connected components of k-cliques
5. Merge cliques in each component to form communities

When to Use

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

import yog
import yog/community/clique_percolation as cpm

let graph =
  yog.undirected()
  |> yog.add_node(1, "A")
  |> yog.add_node(2, "B")
  |> yog.add_node(3, "C")
  |> yog.add_edges([#(1, 2, 1), #(2, 3, 1), #(3, 1, 1)])  // Triangle

// Detect overlapping communities (k=3 finds triangles)
let overlapping = cpm.detect_overlapping(graph)
// overlapping.communities contains sets of nodes

// Convert to non-overlapping (assigns node to first community)
let communities = cpm.to_communities(overlapping)

// With custom k
let options = cpm.CPMOptions(k: 4)
let overlapping = cpm.detect_overlapping_with_options(graph, options)

References

• Palla et al. 2005 - Uncovering overlapping community structure
• Wikipedia: Clique Percolation Method

pub type CPMOptions {
  CPMOptions(k: Int)
}

pub type OverlappingCommunities {
  OverlappingCommunities(communities: List(set.Set(Int)))
}

pub fn default_options() -> CPMOptions

pub fn detect_overlapping(
  graph: model.Graph(n, e),
) -> OverlappingCommunities

pub fn detect_overlapping_with_options(
  graph: model.Graph(n, e),
  options: CPMOptions,
) -> OverlappingCommunities

pub fn to_communities(
  overlapping: OverlappingCommunities,
) -> community.Communities