yog - v5.1.0

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

Use CaseRecommendation
Overlapping communities✓ Only algorithm in this module
Dense networks with cliques✓ Excellent
Sparse graphs✗ May find no communities
Non-overlapping neededConvert with to_communities/1

Complexity

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

Types

CPMOptions

</>

Options for Clique Percolation Method.

pub type CPMOptions {
  CPMOptions(k: Int)
}

Constructors 

  • CPMOptions(k: Int)

    Arguments

    k

    Size of the clique (k). Typically 3 or 4.

OverlappingCommunities

</>

Result of overlapping community detection.

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

Constructors 

  • OverlappingCommunities(communities: List(set.Set(Int)))

    Arguments

    communities

    List of communities, where each community is a set of node IDs.

Values

default_options

</> 
pub fn default_options() -> CPMOptions

Default options for CPM.

detect_overlapping

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

Detects overlapping communities using CPM with default options.

detect_overlapping_with_options

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

Detects overlapping communities using CPM with custom options.

to_communities

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

Converts overlapping communities to hard assignments by picking the first community for each node.

✨ Search Document