Module community

Expand description

Community detection, modularity, partition comparison and hierarchical random graphs (igraph_community.h, igraph_hrg.h).

Community detection clusters the vertices of a network into groups that are densely connected internally and sparsely connected with each other. A clustering is represented, as everywhere in igraph, by a membership vector: membership[v] is the community id of vertex v, ids being numbered from zero. Hierarchical methods also return a dendrogram as a list of merges (a, b): the i-th merge joins the clusters a and b into a new cluster with id n + i (n being the number of vertices).

Good introductions to the topic are S. Fortunato, Community Detection in Graphs, Physics Reports 486 (2010) and S. Fortunato and D. Hric, Community Detection in Networks: A User Guide, Physics Reports 659 (2016).

§Examples

Two 5-cliques joined by a single edge are split into their cliques by every reasonable method:

use igraph::prelude::*;
use igraph::community::compare_communities;

let mut edges = vec![];
for base in [0, 5] {
    for i in 0..5 {
        for j in i + 1..5 {
            edges.push((base + i, base + j));
        }
    }
}
edges.push((0, 5));
let g = Graph::from_edges(&edges, 10, false).unwrap();

let louvain = g.community_multilevel(None, 1.0).unwrap();
assert_eq!(louvain.membership, vec![0, 0, 0, 0, 0, 1, 1, 1, 1, 1]);
assert!((louvain.modularity() - 0.4524).abs() < 1e-4);

let greedy = g.community_fastgreedy(None).unwrap();
let nmi = compare_communities(&louvain.membership, &greedy.membership,
                              CommunityComparison::Nmi).unwrap();
assert!((nmi - 1.0).abs() < 1e-12);

A typical workflow on a real network: Zachary’s karate club (from Graph::famous) is clustered with a seeded Leiden run, and the communities are then collapsed into a weighted “community graph” with Graph::contract_vertices, whose modularity for the singleton partition is, by definition, the modularity of the clustering:

use igraph::prelude::*;
use igraph::community::{LeidenObjective, LeidenOptions};

let karate = Graph::famous("Zachary").unwrap();
rng::seed(42).unwrap();
let leiden = karate
    .community_leiden_simple(None, LeidenObjective::Modularity,
                             &LeidenOptions::default().with_iterations(None))
    .unwrap();
assert_eq!(leiden.nb_clusters, 4);
assert!((leiden.quality - 0.4198).abs() < 1e-4); // the known optimum

let mut quotient = karate.clone();
quotient.contract_vertices(&leiden.membership).unwrap();
let singletons: Vec<i64> = (0..leiden.nb_clusters as i64).collect();
let q = quotient.modularity(&singletons, None, 1.0, false).unwrap();
assert!((q - leiden.quality).abs() < 1e-12);

§Provided functionality

Rust API	C function	What
`Graph::community_multilevel`	`igraph_community_multilevel`	Louvain modularity optimization
`Graph::community_leiden`	`igraph_community_leiden`	Leiden, raw vertex weights
`Graph::community_leiden_simple`	`igraph_community_leiden_simple`	Leiden with modularity / CPM / ER objective
`Graph::community_fastgreedy`	`igraph_community_fastgreedy`	Clauset–Newman–Moore greedy agglomeration
`Graph::community_walktrap`	`igraph_community_walktrap`	random-walk distances (Pons–Latapy)
`Graph::community_edge_betweenness`	`igraph_community_edge_betweenness`	Girvan–Newman divisive method
`Graph::community_eb_get_merges`	`igraph_community_eb_get_merges`	dendrogram from an edge removal order
`Graph::community_leading_eigenvector`, `Graph::community_leading_eigenvector_with`	`igraph_community_leading_eigenvector`	Newman’s spectral method
`Graph::community_spinglass`	`igraph_community_spinglass`	Reichardt–Bornholdt Potts model
`Graph::community_spinglass_single`	`igraph_community_spinglass_single`	community of a single vertex
`Graph::community_label_propagation`	`igraph_community_label_propagation`	label propagation
`Graph::community_infomap`	`igraph_community_infomap`	map equation (Infomap)
`Graph::community_fluid_communities`	`igraph_community_fluid_communities`	fluid communities
`Graph::community_voronoi`	`igraph_community_voronoi`	Voronoi partitioning
`Graph::community_optimal_modularity`	`igraph_community_optimal_modularity`	exact maximum modularity (GLPK)
`Graph::modularity`	`igraph_modularity`	modularity of a partition
`Graph::modularity_matrix`	`igraph_modularity_matrix`	the modularity matrix `B`
`Graph::coreness`	`igraph_coreness`	k-core decomposition
`Graph::trussness`	`igraph_trussness`	k-truss decomposition
`community_to_membership`, `Dendrogram::cut`	`igraph_community_to_membership`	cut a dendrogram
`le_community_to_membership`	`igraph_le_community_to_membership`	cut a leading eigenvector dendrogram
`reindex_membership`	`igraph_reindex_membership`	make community ids contiguous
`compare_communities`	`igraph_compare_communities`	VI, NMI, split-join, (adjusted) Rand
`split_join_distance`	`igraph_split_join_distance`	both projection distances
`Graph::hrg_fit`, `Graph::hrg_refit`	`igraph_hrg_fit`	fit a hierarchical random graph by MCMC
`Graph::hrg_consensus`, `Graph::hrg_predict`	`igraph_hrg_consensus`, `igraph_hrg_predict`	consensus dendrogram, missing link prediction
`Hrg::create`, `Hrg::size`	`igraph_hrg_create`, `igraph_hrg_size`	build / inspect an `Hrg`
`Hrg::sample`, `Hrg::sample_many`, `Graph::hrg_game`	`igraph_hrg_sample`, `igraph_hrg_sample_many`, `igraph_hrg_game`	sample graphs from an HRG
`Graph::from_hrg_dendrogram`, `Hrg::dendrogram`	`igraph_from_hrg_dendrogram`	an HRG dendrogram as a tree

Not bound: igraph_hrg_resize (plain storage sizing: Hrg::create and Graph::hrg_fit size the model themselves, and resizing leaves the new tree entries uninitialized, which Hrg::sample would then read as vertex ids), and igraph_hrg_init / igraph_hrg_destroy, which the constructors and Drop of Hrg call.

Randomized methods (Louvain, Leiden, label propagation, spinglass, Infomap, fluid communities, Voronoi generator ties, HRG, …) draw from the random number generator of the calling thread (each thread has its own): call rng::seed first for reproducible results, or run them with a dedicated generator through Rng::scoped.

§See also

components: Graph::connected_components (spinglass and fluid communities need connected graphs, the leading eigenvector method starts from the components).
centrality: Graph::edge_betweenness, the quantity driving Graph::community_edge_betweenness.
mixing: Graph::assortativity_nominal, whose unnormalized value is the modularity of a partition, and Graph::ecc, the edge clustering coefficient used by Graph::community_voronoi.
paths: Graph::voronoi, the plain Voronoi partition around given generators.
operators: Graph::contract_vertices and Graph::induced_subgraph to build the community graph or extract a community.
games: Graph::sbm_game generates graphs with a planted community structure, to benchmark the methods.
cliques and Graph::list_triangles for the dense substructures behind Graph::coreness and Graph::trussness.

Structs§

Clustering: A flat partition of the vertices together with its modularity.
Dendrogram: A hierarchical clustering (dendrogram) together with the modularity of each of its levels and the best cut.
EdgeBetweennessCommunities: Result of the Girvan–Newman algorithm, see Graph::community_edge_betweenness.
EdgeRemovalMerges: Result of Graph::community_eb_get_merges.
Hrg: A hierarchical random graph (HRG) model (igraph_hrg_t), after Clauset, Moore and Newman.
HrgConsensus: Result of Graph::hrg_consensus.
HrgPrediction: Result of Graph::hrg_predict.
Infomap: Result of Infomap, see Graph::community_infomap.
InfomapOptions: Options of Graph::community_infomap.
LabelPropagationOptions: Options of Graph::community_label_propagation.
LeadingEigenvector: Result of Newman’s leading eigenvector method, see Graph::community_leading_eigenvector.
LeadingEigenvectorStep: The state passed to the callback of Graph::community_leading_eigenvector_with after each eigenvector computation.
Leiden: Result of the Leiden algorithm, see Graph::community_leiden.
LeidenOptions: Options of Graph::community_leiden and Graph::community_leiden_simple.
Multilevel: Result of the multi-level (Louvain) algorithm, see Graph::community_multilevel.
Spinglass: Result of the spinglass method, see Graph::community_spinglass.
SpinglassOptions: Options of Graph::community_spinglass and Graph::community_spinglass_single, with the defaults suggested by igraph.
SpinglassSingle: Result of Graph::community_spinglass_single.
Voronoi: Result of Voronoi partitioning, see Graph::community_voronoi.

Enums§

LeadingEigenvectorEvent: One step of the history of Graph::community_leading_eigenvector (igraph_leading_eigenvector_community_history_t).
LeidenObjective: Objective function optimized by Graph::community_leiden_simple (igraph_leiden_objective_t).

Functions§

community_to_membership: Cuts a dendrogram after steps merges, returning the membership vector and the size of each community.
compare_communities: Compares two partitions of the same set with the given measure.
le_community_to_membership: Applies steps merges of a leading eigenvector dendrogram to an initial partition, returning the new membership vector and community sizes.
reindex_membership: Relabels a membership vector in place so that community ids are 0..k, and returns the mapping from new to old ids (its length k is the number of communities).
split_join_distance: The two projection distances between two partitions, whose sum is the split-join distance of van Dongen.