yog/community

Community detection and clustering algorithms.

Provides types and utility functions for working with community structures in graphs. Community detection algorithms identify groups of nodes that are more densely connected internally than with the rest of the graph.

Algorithms

Algorithm	Module	Best For
Louvain	`yog/community/louvain`	Large graphs, modularity optimization
Leiden	`yog/community/leiden`	Quality guarantee, well-connected communities
Label Propagation	`yog/community/label_propagation`	Speed, near-linear time
Girvan-Newman	`yog/community/girvan_newman`	Hierarchical structure, edge betweenness
Infomap	`yog/community/infomap`	Information-theoretic, flow-based
Clique Percolation	`yog/community/clique_percolation`	Overlapping communities
Walktrap	`yog/community/walktrap`	Random walk-based distances
Local Community	`yog/community/local_community`	Massive graphs, seed expansion
Fluid Communities	`yog/community/fluid_communities`	Exact `k` partitions, fast

Core Types

Communities - Community assignment mapping nodes to community IDs
Dendrogram - Hierarchical community structure with multiple levels
CommunityId - Integer identifier for a community

Example

import yog
import yog/community
import yog/community/louvain

let graph = // ... build your graph

// Detect communities
let communities = louvain.detect(graph)
io.debug(communities.num_communities)  // => 4

// Get nodes in each community
let communities_dict = community.communities_to_dict(communities)
// => dict.from_list([#(0, set.from_list([1, 2, 3])), #(1, set.from_list([4, 5]))])

// Find largest community
case community.largest_community(communities) {
  Some(community_id) -> io.debug(community_id)
  None -> io.println("No communities found")
}

Choosing an Algorithm

Louvain: Fast and widely used, good for most cases
Leiden: Better quality than Louvain, guarantees well-connected communities
Label Propagation: Fastest option for very large graphs
Girvan-Newman: When you need hierarchical structure
Infomap: When flow/random walk structure matters
Clique Percolation: When nodes may belong to multiple communities
Walktrap: Good for capturing local structure via random walks
Local Community: When the graph is massive/infinite and you only care about the immediate community around specific seeds
Fluid Communities: Fast and allows finding exactly k communities

Types

Communities

</>

Represents a community partition of a graph.

Fields

assignments: Dictionary mapping each node ID to its community ID
num_communities: Total number of distinct communities

Example

Communities(
  assignments: dict.from_list([#(1, 0), #(2, 0), #(3, 1)]),
  num_communities: 2
)
// Node 1 and 2 are in community 0, node 3 is in community 1

pub type Communities {
  Communities(
    assignments: dict.Dict(Int, Int),
    num_communities: Int,
  )
}

Constructors

Communities(
  assignments: dict.Dict(Int, Int),
  num_communities: Int,
)

CommunityId

</>

Community assignment for nodes

pub type CommunityId =
  Int

Dendrogram

</>

Hierarchical community structure with multiple levels of granularity.

Fields

levels: List of community partitions from finest to coarsest
merge_order: Order in which communities were merged (for dendrogram reconstruction)

Example

A dendrogram might have 3 levels:

Level 0: Each node in its own community (finest)
Level 1: Communities merged based on similarity
Level 2: All nodes in one community (coarsest)

pub type Dendrogram {
  Dendrogram(
    levels: List(Communities),
    merge_order: List(#(Int, Int)),
  )
}

Constructors

Dendrogram(
  levels: List(Communities),
  merge_order: List(#(Int, Int)),
)

Values

communities_to_dict

</>

pub fn communities_to_dict(
  communities: Communities,
) -> dict.Dict(Int, set.Set(Int))

Converts community assignments to a dictionary mapping community IDs to sets of node IDs.

This is useful when you need to iterate over all nodes in each community rather than looking up the community for each node.

Example

let communities = Communities(
  assignments: dict.from_list([#(1, 0), #(2, 0), #(3, 1)]),
  num_communities: 2
)

community.communities_to_dict(communities)
// => dict.from_list([
//      #(0, set.from_list([1, 2])),
//      #(1, set.from_list([3]))
//    ])

community_sizes

</>

pub fn community_sizes(
  communities: Communities,
) -> dict.Dict(Int, Int)

Returns a dictionary mapping community IDs to their sizes (number of nodes).

Example

let communities = Communities(
  assignments: dict.from_list([#(1, 0), #(2, 0), #(3, 1), #(4, 1), #(5, 1)]),
  num_communities: 2
)

community.community_sizes(communities)
// => dict.from_list([#(0, 2), #(1, 3)])

largest_community

</>

pub fn largest_community(
  communities: Communities,
) -> option.Option(Int)

Returns the community ID with the largest number of nodes.

Returns None if there are no communities (empty graph or no assignments).

Example

let communities = Communities(
  assignments: dict.from_list([#(1, 0), #(2, 0), #(3, 0), #(4, 1)]),
  num_communities: 2
)

community.largest_community(communities)
// => Some(0)  // Community 0 has 3 nodes vs 1 for community 1

merge_communities

</>

pub fn merge_communities(
  communities: Communities,
  source: Int,
  target: Int,
) -> Communities

Merges two communities into one.

All nodes from the source community are reassigned to the target community. The source community ID is effectively removed.

Parameters

communities: The current community partition
source: The community ID to merge from (will be removed)
target: The community ID to merge into (will be kept)

Example

let communities = Communities(
  assignments: dict.from_list([#(1, 0), #(2, 0), #(3, 1), #(4, 1)]),
  num_communities: 2
)

// Merge community 1 into community 0
let merged = community.merge_communities(communities, source: 1, target: 0)
// merged.assignments => dict.from_list([#(1, 0), #(2, 0), #(3, 0), #(4, 0)])
// merged.num_communities => 1