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_iterations: usize
) -> HashMap<NodeId, usize>

Example¶

use graphina::community::label_propagation;

let communities = label_propagation(&graph, 100);

// Group nodes by community ID
let mut groups: HashMap<usize, Vec<NodeId>> = HashMap::new();
for (node, comm_id) in communities {
    groups.entry(comm_id).or_default().push(node);
}

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_map = 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();

Personalized PageRank Communities¶

Detects communities based on random walk proximity to a seed set.

use graphina::community::personalized_pagerank::personalized_page_rank;

let ppr_scores = personalized_page_rank(&graph, None, 0.85, 1e-6, 100).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.

use graphina::community::louvain;

// Returns mapping from NodeId -> Community ID
let communities = louvain(&graph);

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;

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