Joining Community, Detecting Communities, Making Community.

Portrait of Arnaud Becheler Arnaud Becheler · Apr 8, 2026

Joining Community

Early in Q1 2026, I joined the C++ Alliance. A very exciting moment.

So I began to work early January under Joaquin’s mentorship, with the idea of having a clear contribution to Boost Graph by the end of Q1. After a few days of auditing the current state of the library versus the literature, it became clear that community detection methods (aka graph clustering algorithms) were sorely lacking for Boost.Graph, and that implementing one would be a great start to revitalizing the library and fill up maybe the largest methodological gap in its current algorithmic coverage.

Detecting Communities

The vision was (and still is) simple: i) begin to implement Louvain algorithm, ii) build upon it to extend to the more complex Leiden algorithm, iii) finally get started with the Stochastic Block Model.

If the plan is straightforward, the Louvain literature is not, and the BGL abstractions even less. But under the review and guidance from Joaquin and Jeremy Murphy (maintainer of the BGL), I was able to put up a satisfying implementation:

Using the Newman-Girvan Modularity as the quality function to optimize, one can simply call:

double Q = boost::louvain_clustering(
    g, cluster_map, weight_map, gen,
    boost::newman_and_girvan{},  // quality function (default)
    1e-7,                        // min_improvement_inner (per-pass convergence)
    0.0                          // min_improvement_outer (cross-level convergence)
);
// Q = 0.42, cluster_map = {0,0,0, 1,1,1}

As it happens often with heuristics, there is a large number of quality functions out there, and this is not because of a lack of consensus: in a 2002 paper, computer scientist Jon Kleinberg proved that no clustering quality function (Modularity, Goldberg density, Surprise…) can simultaneously be:

  1. scale-invariant (doubling all edges should not change the clusters),
  2. rich (all partitions should be achievable),
  3. consistent (shortening distances inside a cluster and expanding distances between clusters should lead to similar results).

In other words, there is no way to implement a single function hoping it would exhibit three basic properties we would genuinely expect. All we can do is to explore different trade-offs using different quality functions.

So I left some doors open to be able to inject an arbitrary quality function. If this function exposes a minimal, “naive” interface, the algorithm will statically use a slow but generic path, and iterate across all the edges of the graph to compute the quality. It is slow, yes, but it makes the study of qualities easier, as one does not have to figure out the local mathematical decomposition of the function to get started with coding:

struct my_quality {
    template <typename G, typename CMap, typename WMap>
    typename boost::property_traits<WMap>::value_type
    quality(const G& g, const CMap& c, const WMap& w) {
        // your custom partition quality function
    }
};

double Q = boost::louvain_clustering(g, cluster_map, weight_map, gen, my_quality{});

However, the Louvain algorithm is extremely popular because it is fast, as it is able to update the quality computational state for each vertex it tries to “insert” or “remove” from a neighboring putative community. This locality decomposition has to be figured out mathematically for each quality function, so it’s not trivial.

I defined a GraphPartitionQualityFunctionIncrementalConcept that refines the GraphPartitionQualityFunctionConcept : if the algorithm detects that the injected quality function exposes an interface for this incremental update, the fast path is taken. One thing I figured out is that the GraphPartitionQualityFunctionIncrementalConcept is for now too specific to the Modularity family. I am currently working on a proposal to increase its scope in future work.

The current PR has been carefully tested and benchmarked for correctness and performance, and validated by Jeremy to be merged on develop branch.

I wrote a paper to be submitted to the Journal of Open Source Software to publish the current results and benchmarks, as we are at least as fast as our competitors, and more generic. There is no equivalent I am aware of.

Making Community

Concurrently, I worked on summoning the Boost.Graph user base, and it quickly became clear a small local workshop would be a tremendous start: the Louvain algorithm community is based in Louvain (Belgium), its extension was formulated in Leiden (Netherlands) and my PhD graphs network is based in Paris (France) in what has been presented to me as “the Temple of the Stochastic Block Model” ! Quite a sign: life finds ways to run in (tight) circles.

So the goal of this workshop is to bring together a small group (10-15 people) of researchers, open-source implementers, and industrial users for a day of honest conversation on May 6th 2026. Three questions will anchor the discussions:

  1. What types of graphs and data structures do you use in practice?
  2. What performance, scalability, and interpretability requirements matter most to you?
  3. What algorithms are missing today that Boost.Graph could offer?

Ray and Collier from the C++ Alliance will also be there to record the lightning talks and document the process. It would also be the occasion to show off the python-based animations I put together for the French C++ User Group presentation on March 24th. Those had a nice success and received many compliments, as it pairs well with the visual and dynamic nature of graphs and their algorithms, and I hope it will contribute to the repopularization of Boost.Graph.

Graphliiings asseeeeemble !

All Posts by This Author