`betweenness_centrality_clustering`

Graph clustering based on edge betweenness centrality.

Complexity: O(VE) per iteration (unweighted)
Defined in: <boost/graph/bc_clustering.hpp>

Example

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/bc_clustering.hpp>
#include <boost/graph/connected_components.hpp>
#include <iostream>
#include <vector>

using namespace boost;

// Bundled edge scratch field holds the centrality value that the algorithm
// writes on each iteration. Passing it explicitly removes the need for the
// `edge_index_t` / iterator_property_map round-trip.
struct Edge { double centrality; };

using Graph = adjacency_list<vecS, vecS, undirectedS, no_property, Edge>;

int main() {
    Graph g(6);
    add_edge(0, 1, g); add_edge(1, 2, g); add_edge(0, 2, g);  // cluster A
    add_edge(3, 4, g); add_edge(4, 5, g); add_edge(3, 5, g);  // cluster B
    add_edge(2, 3, g);                                         // bridge

    // 3-arg overload takes an explicit EdgeCentralityMap.
    betweenness_centrality_clustering(g,
        bc_clustering_threshold<double>(1.0, g, false),
        get(&Edge::centrality, g));

    std::vector<int> comp(num_vertices(g));
    int nc = connected_components(g, &comp[0]);
    std::cout << "Clusters: " << nc << "\n";
    for (std::size_t v = 0; v < comp.size(); ++v) {
        std::cout << "  vertex " << v << " -> cluster " << comp[v] << "\n";
    }
}

Clusters: 6
  vertex 0 -> cluster 0
  vertex 1 -> cluster 1
  vertex 2 -> cluster 2
  vertex 3 -> cluster 3
  vertex 4 -> cluster 4
  vertex 5 -> cluster 5

(1) Full version

template<typename MutableGraph, typename Done,
         typename EdgeCentralityMap, typename VertexIndexMap>
void betweenness_centrality_clustering(
    MutableGraph& g, Done done,
    EdgeCentralityMap edge_centrality,
    VertexIndexMap vertex_index);

Direction Parameter Description

Direction	Parameter	Description
IN	`MutableGraph& g`	The graph object on which the algorithm will be applied. The type `MutableGraph` must be a model of Vertex List Graph and Incidence Graph. When an edge centrality map is supplied, it must also model Edge List Graph and MutableGraph.
IN	`Done done`	The function object that indicates termination of the algorithm. It must be a ternary function object that accepts the maximum centrality, the descriptor of the edge that will be removed, and the graph `g`.
OUT/UTIL	`EdgeCentralityMap edge_centrality`	This property map is used to accumulate the betweenness centrality of each edge, and is a secondary form of output for the algorithm. The type `EdgeCentralityMap` must be a model of Read/Write Property Map, with the graph’s edge descriptor type as its key type. The value type of this property map should be the same as the value type of the `CentralityMap` property map.
IN	`VertexIndexMap vertex_index`	This maps each vertex to an integer in the range `[0, num_vertices(g))`. This is necessary for efficient updates of the heap data structure when an edge is relaxed. The type `VertexIndexMap` must be a model of Readable Property Map. The value type of the map must be an integer type. The vertex descriptor type of the graph needs to be usable as the key type of the map.

MutableGraph& g

The graph object on which the algorithm will be applied. The type MutableGraph must be a model of Vertex List Graph and Incidence Graph. When an edge centrality map is supplied, it must also model Edge List Graph and MutableGraph.

Done done

The function object that indicates termination of the algorithm. It must be a ternary function object that accepts the maximum centrality, the descriptor of the edge that will be removed, and the graph g.

OUT/UTIL

EdgeCentralityMap edge_centrality

This property map is used to accumulate the betweenness centrality of each edge, and is a secondary form of output for the algorithm. The type EdgeCentralityMap must be a model of Read/Write Property Map, with the graph’s edge descriptor type as its key type. The value type of this property map should be the same as the value type of the CentralityMap property map.

VertexIndexMap vertex_index

This maps each vertex to an integer in the range [0, num_vertices(g)). This is necessary for efficient updates of the heap data structure when an edge is relaxed. The type VertexIndexMap must be a model of Readable Property Map. The value type of the map must be an integer type. The vertex descriptor type of the graph needs to be usable as the key type of the map.

(2) Edge centrality version (default vertex index)

template<typename MutableGraph, typename Done,
         typename EdgeCentralityMap>
void betweenness_centrality_clustering(
    MutableGraph& g, Done done,
    EdgeCentralityMap edge_centrality);

Direction Parameter Description

Direction	Parameter	Description
IN	`MutableGraph& g`	See (1) `MutableGraph& g`.
IN	`Done done`	See (1) `Done done`.
OUT/UTIL	`EdgeCentralityMap edge_centrality`	See (1) `EdgeCentralityMap edge_centrality`.

MutableGraph& g

See (1) MutableGraph& g.

Done done

See (1) Done done.

OUT/UTIL

EdgeCentralityMap edge_centrality

See (1) EdgeCentralityMap edge_centrality.

The vertex index defaults to get(vertex_index, g). Note: if you use this default, make sure your graph has an internal vertex_index property. For example, adjacency_list with VertexList=listS does not have an internal vertex_index property.

(3) Minimal version (default edge centrality and vertex index)

template<typename MutableGraph, typename Done>
void betweenness_centrality_clustering(
    MutableGraph& g, Done done);

Direction Parameter Description

Direction	Parameter	Description
IN	`MutableGraph& g`	See (1) `MutableGraph& g`.
IN	`Done done`	See (1) `Done done`.

MutableGraph& g

See (1) MutableGraph& g.

Done done

See (1) Done done.

The edge centrality map defaults to a dummy_property_map, which requires no work to compute and returns no answer. The vertex index defaults to get(vertex_index, g).

Description

This algorithm implements graph clustering based on edge betweenness centrality. It is an iterative algorithm, where in each step it computes the edge betweenness centrality (via brandes_betweenness_centrality) and removes the edge with the maximum betweenness centrality. The done function object determines when the algorithm terminates (the edge found when the algorithm terminates will not be removed).

Edit this Page