`louvain_clustering`

template <typename QualityFunction = newman_and_girvan,
          typename Graph, typename ComponentMap,
          typename WeightMap, typename URBG>
typename property_traits<WeightMap>::value_type
louvain_clustering(const Graph& g,
                   ComponentMap components,
                   const WeightMap& w,
                   URBG&& gen,
                   QualityFunction f = QualityFunction{},
                   typename property_traits<WeightMap>::value_type min_improvement_inner = 0,
                   typename property_traits<WeightMap>::value_type min_improvement_outer = 0);

This algorithm implements the Louvain method for community detection [1]. It finds a partition of the vertices into communities that approximately maximizes a quality function (by default, Newman–Girvan modularity).

The algorithm alternates two phases:

Local optimization. Each vertex is moved to the neighboring community that yields the largest improvement in the quality function. Vertices are visited in random order and the process repeats until no single-vertex move improves the quality by more than min_improvement_inner.
Aggregation. The graph is contracted by collapsing each community into a single super-vertex. Edge weights between super-vertices are the sums of the original inter-community edge weights and self-loops carry the total intra-community weight.

These two phases are applied repeatedly on the coarsened graph, discovering communities of communities, until the quality improvement between successive levels falls below min_improvement_outer, or the graph can no longer be coarsened.

Once every level has converged, the algorithm iterates from the coarsest aggregated graph down to the original graph to trace assignment of vertices to communities to produce the final community label written into components.

The speed of the local optimization phase depends on the quality function's interface. A quality function that only models GraphPartitionQualityFunctionConcept requires a full O(V+E) recomputation of the quality for every candidate vertex move. A quality function that also models GraphPartitionQualityFunctionIncrementalConcept evaluates each candidate move in O(1) using incremental bookkeeping, making the total cost per vertex O(degree). The algorithm detects which interface is available at compile time and selects the appropriate code path automatically.

Where Defined

boost/graph/louvain_clustering.hpp

Parameters

IN: const Graph& g

An undirected graph. Must model Vertex List Graph and Incidence Graph. The graph is not modified by the algorithm. Passing a directed graph produces a compile-time error.

OUT: ComponentMap components

Records the community each vertex belongs to. After the call, get(components, v) returns a contiguous integer label in the range [0, k) where k is the number of communities found. Two vertices with the same label are in the same community. This matches the convention used by connected_components.
Must model Read/Write Property Map with the graph's vertex descriptor as key type and an integer type (e.g. std::size_t) as value type.

IN: const WeightMap& w

Edge weights. Must model Readable Property Map with the graph's edge descriptor as key type. Weights must be non-negative.

IN: URBG&& gen

A random number generator used to shuffle the vertex processing order at each pass. Any type meeting the C++ UniformRandomBitGenerator requirements works (e.g. std::mt19937).

IN: QualityFunction f

An instance of the quality function to use for evaluating and incrementally updating partition quality.
Default: QualityFunction{}

IN: weight_type min_improvement_inner

The inner loop (local optimization) stops when a full pass over all vertices improves quality by less than this value.
Default: 0

IN: weight_type min_improvement_outer

The outer loop (aggregation) stops when quality improves by less than this value between successive levels.
Default: 0

Template Parameters

QualityFunction

The partition quality metric to maximize. Must model GraphPartitionQualityFunctionConcept. If it also models GraphPartitionQualityFunctionIncrementalConcept, the faster incremental code path is selected automatically.
Default: newman_and_girvan

Return Value

The quality (e.g. modularity) of the best partition found. For Newman–Girvan modularity this is a value in [−0.5, 1).

Complexity

With the incremental quality function (the default), each local optimization pass costs O(E) since every vertex is visited once and each visit scans its neighbors. With a non-incremental quality function, each candidate move requires a full O(V+E) traversal, making each pass O(E · (V+E)). The number of passes per level and the number of aggregation levels are both small in practice, so the incremental path typically runs in O(E log V) overall on sparse graphs.

Preconditions

The graph must be undirected (enforced at compile time).
Edge weights must be non-negative.
The graph must have a vertex_index property mapping vertices to contiguous integers in [0, num_vertices(g)).

Example

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/louvain_clustering.hpp>
#include <random>
#include <iostream>

int main()
{
    using Graph = boost::adjacency_list<
        boost::vecS, boost::vecS, boost::undirectedS,
        boost::no_property,
        boost::property<boost::edge_weight_t, double>>;

    // Two triangles connected by a weak bridge
    Graph g(6);
    boost::add_edge(0, 1, 1.0, g);
    boost::add_edge(1, 2, 1.0, g);
    boost::add_edge(0, 2, 1.0, g);
    boost::add_edge(3, 4, 1.0, g);
    boost::add_edge(4, 5, 1.0, g);
    boost::add_edge(3, 5, 1.0, g);
    boost::add_edge(2, 3, 0.1, g);

    std::vector<std::size_t> communities(boost::num_vertices(g));
    auto cmap = boost::make_iterator_property_map(
        communities.begin(), boost::get(boost::vertex_index, g));

    std::mt19937 rng(42);
    double Q = boost::louvain_clustering(
        g, cmap, boost::get(boost::edge_weight, g), rng);

    std::cout << "Modularity: " << Q << "\n";
    for (auto v : boost::make_iterator_range(boost::vertices(g)))
        std::cout << "  vertex " << v
                  << " -> community " << boost::get(cmap, v) << "\n";
}

References

[1] V. D. Blondel, J.‑L. Guillaume, R. Lambiotte, and E. Lefebvre, “Fast unfolding of communities in large networks,” Journal of Statistical Mechanics: Theory and Experiment, vol. 2008, no. 10, P10008, 2008. doi:10.1088/1742-5468/2008/10/P10008

[2] V. A. Traag, L. Waltman, and N. J. van Eck, “From Louvain to Leiden: guaranteeing well-connected communities,” Scientific Reports, vol. 9, 5233, 2019. doi:10.1038/s41598-019-41695-z

Arnaud Becheler

louvain_clustering