Clustering Coefficient

Measures the density of triangles around a vertex. For vertex v, it is the fraction of pairs of v’s neighbors that are also connected to each other. A high value means v’s neighborhood is tightly knit.

Defined in: <boost/graph/clustering_coefficient.hpp>

Example

#include <boost/graph/adjacency_matrix.hpp>
#include <boost/graph/clustering_coefficient.hpp>
#include <iostream>
#include <vector>

// clustering_coefficient requires AdjacencyMatrix concept (lookup_edge),
// so we use adjacency_matrix instead of adjacency_list.
using Graph = boost::adjacency_matrix<boost::undirectedS>;
using Vertex = boost::graph_traits<Graph>::vertex_descriptor;

int main() {
    Graph g{5};
    boost::add_edge(0, 1, g);
    boost::add_edge(0, 2, g);
    boost::add_edge(1, 2, g); // triangle on {0,1,2}
    boost::add_edge(2, 3, g);
    boost::add_edge(3, 4, g);

    for (auto v : boost::make_iterator_range(vertices(g))) {
        double cc = boost::clustering_coefficient(g, v);
        std::cout << "vertex " << v << ": clustering coeff = " << cc << "\n";
    }
}

vertex 0: clustering coeff = 1
vertex 1: clustering coeff = 1
vertex 2: clustering coeff = 0.333333
vertex 3: clustering coeff = 0
vertex 4: clustering coeff = 0

(1) clustering_coefficient (default double result)

template <typename Graph, typename Vertex>
double clustering_coefficient(const Graph& g, Vertex v);

(2) clustering_coefficient with explicit result type

template <typename T, typename Graph, typename Vertex>
T clustering_coefficient(const Graph& g, Vertex v);

For each ordered pair (u, w) of neighbors of v, counts whether edge (u, w) is present. Returns num_triangles_on_vertex(g, v) / num_paths_through_vertex(g, v) (or zero if the denominator is zero).

(3) all_clustering_coefficients

template <typename Graph, typename ClusteringMap>
typename property_traits<ClusteringMap>::value_type
all_clustering_coefficients(const Graph& g, ClusteringMap cm);

Writes the clustering coefficient of each vertex to cm and returns the mean (sum / num_vertices(g)).

(4) mean_clustering_coefficient

template <typename Graph, typename ClusteringMap>
typename property_traits<ClusteringMap>::value_type
mean_clustering_coefficient(const Graph& g, ClusteringMap cm);

Given an already-populated cm, returns the mean of the values without recomputing them. ClusteringMap is a ReadablePropertyMap in this overload.

(5) Helpers: num_paths_through_vertex / num_triangles_on_vertex

template <typename Graph, typename Vertex>
typename graph_traits<Graph>::degree_size_type
num_paths_through_vertex(const Graph& g, Vertex v);

template <typename Graph, typename Vertex>
typename graph_traits<Graph>::degree_size_type
num_triangles_on_vertex(const Graph& g, Vertex v);

num_paths_through_vertex counts ordered pairs of v’s neighbors (the denominator of the clustering coefficient). `num_triangles_on_vertex counts the actual edges between those neighbors (the numerator).

Parameters

Direction Parameter Description

Direction	Parameter	Description
IN	`const Graph& g`	Must model Adjacency Graph and Incidence Graph. The single-vertex overloads also require Adjacency Matrix (the `edge()` function).
IN	`Vertex v`	The vertex to compute the coefficient for (single-vertex overloads).
IN/OUT	`ClusteringMap cm`	WritablePropertyMap for overload (3); ReadablePropertyMap for overload (4). Key type is the graph’s vertex descriptor; value type is the coefficient’s numeric type.

const Graph& g

Must model Adjacency Graph and Incidence Graph. The single-vertex overloads also require Adjacency Matrix (the edge() function).

Vertex v

The vertex to compute the coefficient for (single-vertex overloads).

IN/OUT

ClusteringMap cm

WritablePropertyMap for overload (3); ReadablePropertyMap for overload (4). Key type is the graph’s vertex descriptor; value type is the coefficient’s numeric type.

Edit this Page