Louvain Quality Function Concepts

These concepts define the interface used by louvain_clustering() to evaluate and incrementally update partition quality. A quality function measures how well a given partition of the vertices splits the graph into communities.

Where Defined

boost/graph/louvain_quality_functions.hpp

Concept GraphPartitionQualityFunctionConcept

A type QF models this concept if it provides a member function that evaluates the quality of a vertex partition by traversing the graph.

Refinement of

Notation

Associated Types

Valid Expressions

Concept Checking Class

  template <class QualityFunction, class Graph,
            class CommunityMap, class WeightMap>
  struct GraphPartitionQualityFunctionConcept
  {
      void constraints()
      {
          QualityFunction f;
          weight_type q = f.quality(g, cmap, wmap);
          boost::ignore_unused(q);
      }
      Graph g;
      CommunityMap cmap;
      WeightMap wmap;
  };

Models

• newman_and_girvan

Concept GraphPartitionQualityFunctionIncrementalConcept

Refinement of

A quality function that also models this concept supports O(1) incremental updates when a single vertex is moved between communities. This avoids a full O(V+E) graph traversal for every candidate move during local optimization.

Additional Notation

Associated Types

Valid Expressions

In addition to the expressions required by GraphPartitionQualityFunctionConcept:

Name	Expression	Return Type	Description
Full evaluation with auxiliary maps	f.quality(g, c, w, k, in, tot, m)	weight_type	Evaluate partition quality by traversing the graph while populating the auxiliary maps k, in, tot, and m.
Fast evaluation from statistics	f.quality(in, tot, m, n)	weight_type	Compute quality from the incrementally maintained community-level statistics without traversing the graph.
Remove vertex	f.remove(in, tot, comm, k_v, k_v_in, w_self)	void	Update in and tot to reflect the removal of a vertex with weighted degree k_v from community comm.
Insert vertex	f.insert(in, tot, comm, k_v, k_v_in, w_self)	void	Update in and tot to reflect the insertion of a vertex into community comm.
Gain	f.gain(tot, m, comm, k_v_in, k_v)	weight_type	Compute the change in quality that would result from moving a vertex (already removed from its old community) into community comm.

Concept Checking Class

  template <class QualityFunction, class Graph,
            class CommunityMap, class WeightMap>
  struct GraphPartitionQualityFunctionIncrementalConcept
    : GraphPartitionQualityFunctionConcept<QualityFunction, Graph,
                                           CommunityMap, WeightMap>
  {
      void constraints()
      {
          GraphPartitionQualityFunctionConcept<
              QualityFunction, Graph, CommunityMap, WeightMap
          >::constraints();

          QualityFunction f;
          weight_type q2 = f.quality(g, cmap, wmap, k, in, tot, m);
          weight_type q3 = f.quality(in, tot, m, num_communities);
          f.remove(in, tot, comm, weight_val, weight_val, weight_val);
          f.insert(in, tot, comm, weight_val, weight_val, weight_val);
          weight_type gain = f.gain(tot, m, comm, weight_val, weight_val);
          boost::ignore_unused(q2, q3, gain);
      }
      Graph g;
      CommunityMap cmap;
      WeightMap wmap;
      vector_property_map<weight_type> k;
      associative_property_map<...> in, tot;
      weight_type m, weight_val;
      community_type comm;
      std::size_t num_communities;
  };

Models

• newman_and_girvan

Model: newman_and_girvan

The default quality function for louvain_clustering(). It implements Newman–Girvan modularity [1]:

Q = (1 / 2m) ∑_c [ Σ_in(c) − Σ_tot(c)² / 2m ]

where m is the total edge weight, Σ_in(c) is the sum of edge weights inside community c (counted twice, once per endpoint), and Σ_tot(c) is the sum of weighted degrees of all vertices in community c.

newman_and_girvan models both GraphPartitionQualityFunctionConcept and GraphPartitionQualityFunctionIncrementalConcept.

Writing a Custom Quality Function

To use a custom quality metric with louvain_clustering(), define a struct with the required member functions.

Minimal (non-incremental): Implement only quality(g, c, w). The algorithm will use full recomputation at each step, which is correct but slow.

struct my_quality
{
    template <typename Graph, typename CommunityMap, typename WeightMap>
    typename boost::property_traits<WeightMap>::value_type
    quality(const Graph& g, const CommunityMap& c, const WeightMap& w)
    {
        // compute and return your metric
    }
};

boost::louvain_clustering<my_quality>(g, components, weights, rng);

Full (incremental): Also implement the three quality overloads plus remove, insert, and gain as member functions. The algorithm will automatically detect this and use the fast path.

See Also

louvain_clustering, betweenness_centrality_clustering

References

[1] M. E. J. Newman and M. Girvan, “Finding and evaluating community structure in networks,” Physical Review E, vol. 69, no. 2, 026113, 2004. doi:10.1103/PhysRevE.69.026113

[2] R. Campigotto, P. C. Céspedes, and J. L. Guillaume, “A generalized and adaptive method for community detection,” 2014.