Community Detection¶

Community detection (or clustering) algorithms identify groups of nodes that are more densely connected to each other than to the rest of the network.

Label Propagation¶

A fast algorithm for finding communities in large networks. Nodes adopt the label that most of their neighbors have.

Function Signature¶

pub fn label_propagation<A, W, Ty>(
    graph: &BaseGraph<A, W, Ty>,
    max_iter: usize,
    seed: Option<u64>,
) -> Result<Vec<usize>>

Example¶

use graphina::community::label_propagation::label_propagation;

// Returns a Result containing a Vec of community IDs, where the index matches internal node order
let communities = label_propagation(&graph, 100, None).unwrap();

// Group nodes by community ID
let mut groups: std::collections::HashMap<usize, Vec<graphina::core::types::NodeId>> = std::collections::HashMap::new();
for (idx, &comm_id) in communities.iter().enumerate() {
    let node_id = graph.node_ids().nth(idx).unwrap();
    groups.entry(comm_id).or_default().push(node_id);
}

Infomap¶

A flow-based method that minimizes the map equation to detect communities. Efficient for understanding flow constraints in networks.

use graphina::community::infomap::infomap;

// infomap(graph, max_iterations, optional_seed)
let communities = infomap(&graph, 100, Some(42)).unwrap();

Girvan-Newman¶

A hierarchical method that progressively removes edges with high betweenness centrality. Good for small to medium graphs where hierarchy is important.

use graphina::community::girvan_newman::girvan_newman;

// girvan_newman(graph, target_communities)
let communities = girvan_newman(&graph, 3).unwrap();

Spectral Clustering¶

Uses the eigenvectors of the graph Laplacian to partition the graph.

use graphina::community::spectral::spectral_clustering;

// spectral_clustering(graph, num_clusters, optional_seed)
let communities = spectral_clustering(&graph, 3, Some(42)).unwrap();

Louvain Method¶

A heuristic method to extract communities by optimizing modularity. It is widely considered one of the best algorithms for community detection due to its speed and quality of results.

Weight Type

The Louvain method only accepts graphs with f64 edge weights (BaseGraph<A, f64, Ty>).

use graphina::community::louvain::louvain;

// Returns a Result containing a Vec of communities (each a Vec of NodeIds)
let communities = louvain(&graph, None).unwrap();

Connected Components¶

Finds isolated subgraphs where every node is reachable from every other node.

Weakly Connected: Ignoring edge direction.
Strongly Connected: Respecting edge direction (every node must reach every other node).

use graphina::community::connected_components::connected_components;

let components = connected_components(&graph);
println!("Found {} components", components.len());