1.. Copyright (C) 2004-2009 The Trustees of Indiana University. 2 Use, modification and distribution is subject to the Boost Software 3 License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at 4 http://www.boost.org/LICENSE_1_0.txt) 5 6============================= 7|Logo| Betweenness Centrality 8============================= 9 10:: 11 12 // named parameter versions 13 template<typename Graph, typename Param, typename Tag, typename Rest> 14 void 15 brandes_betweenness_centrality(const Graph& g, 16 const bgl_named_params<Param,Tag,Rest>& params); 17 18 template<typename Graph, typename CentralityMap> 19 void 20 brandes_betweenness_centrality(const Graph& g, CentralityMap centrality); 21 22 template<typename Graph, typename CentralityMap, typename EdgeCentralityMap> 23 void 24 brandes_betweenness_centrality(const Graph& g, CentralityMap centrality, 25 EdgeCentralityMap edge_centrality_map); 26 27 // non-named parameter versions 28 template<typename Graph, typename CentralityMap, typename EdgeCentralityMap, 29 typename IncomingMap, typename DistanceMap, typename DependencyMap, 30 typename PathCountMap, typename VertexIndexMap, typename Buffer> 31 void 32 brandes_betweenness_centrality(const Graph& g, 33 CentralityMap centrality, 34 EdgeCentralityMap edge_centrality_map, 35 IncomingMap incoming, 36 DistanceMap distance, 37 DependencyMap dependency, 38 PathCountMap path_count, 39 VertexIndexMap vertex_index, 40 Buffer sources, 41 typename property_traits<DistanceMap>::value_type delta); 42 43 template<typename Graph, typename CentralityMap, typename EdgeCentralityMap, 44 typename IncomingMap, typename DistanceMap, typename DependencyMap, 45 typename PathCountMap, typename VertexIndexMap, typename WeightMap, 46 typename Buffer> 47 void 48 brandes_betweenness_centrality(const Graph& g, 49 CentralityMap centrality, 50 EdgeCentralityMap edge_centrality_map, 51 IncomingMap incoming, 52 DistanceMap distance, 53 DependencyMap dependency, 54 PathCountMap path_count, 55 VertexIndexMap vertex_index, 56 Buffer sources, 57 typename property_traits<WeightMap>::value_type delta, 58 WeightMap weight_map); 59 60 // helper functions 61 template<typename Graph, typename CentralityMap> 62 typename property_traits<CentralityMap>::value_type 63 central_point_dominance(const Graph& g, CentralityMap centrality); 64 65The ``brandes_betweenness_centrality()`` function computes the 66betweenness centrality of the vertices and edges in a graph. The 67method of calculating betweenness centrality in *O(V)* space is due to 68Brandes [Brandes01]_. The algorithm itself is a modification of 69Brandes algorithm by Edmonds [Edmonds09]_. 70 71.. contents:: 72 73Where Defined 74------------- 75<``boost/graph/distributed/betweenness_centrality.hpp``> 76 77also accessible from 78 79<``boost/graph/betweenness_centrality.hpp``> 80 81Parameters 82---------- 83 84IN: ``const Graph& g`` 85 The graph type must be a model of `Distributed Graph`_. The graph 86 type must also model the `Incidence Graph`_ concept. 0-weighted 87 edges in ``g`` will result in undefined behavior. 88 89IN: ``CentralityMap centrality`` 90 A centrality map may be supplied to the algorithm, if not supplied a 91 ``dummy_property_map`` will be used and no vertex centrality 92 information will be recorded. The ``CentralityMap`` type must be a 93 `Distributed Property Map`_. The key type must be the graph's 94 vertex descriptor type. 95 96 **Default**: A ``dummy_property_map``. 97 98IN: ``EdgeCentralityMap edge_centrality_map`` 99 An edge centrality map may be supplied to the algorithm, if not 100 supplied a ``dummy_property_map`` will be used and no edge 101 centrality information will be recorded. The ``EdgeCentralityMap`` 102 type must be a `Distributed Property Map`_. The key type must be 103 the graph's vertex descriptor type. 104 105 **Default**: A ``dummy_property_map``. 106 107IN: ``IncomingMap incoming`` 108 The incoming map contains the incoming edges to a vertex that are 109 part of shortest paths to that vertex. The ``IncomingMap`` type 110 must be a `Distributed Property Map`_. Its key type and value type 111 must both be the graph's vertex descriptor type. 112 113 **Default**: An ``iterator_property_map`` created from a 114 ``std::vector`` of ``std::vector`` of the graph's vertex 115 descriptor type. 116 117IN: ``DistanceMap distance`` 118 The distance map records the distance to vertices during the 119 shortest paths portion of the algorithm. The ``DistanceMap`` type 120 must be a `Distributed Property Map`_. Its key type must be the 121 graph's vertex descriptor type. 122 123 **Default**: An ``iterator_property_map`` created from a 124 ``std::vector`` of the value type of the ``CentralityMap``. 125 126IN: ``DependencyMap dependency`` 127 The dependency map records the dependency of each vertex during the 128 centrality calculation portion of the algorithm. The 129 ``DependencyMap`` type must be a `Distributed Property Map`_. Its 130 key type must be the graph's vertex descriptor type. 131 132 **Default**: An ``iterator_property_map`` created from a 133 ``std::vector`` of the value type of the ``CentralityMap``. 134 135IN: ``PathCountMap path_count`` 136 137 The path count map records the number of shortest paths each vertex 138 is on during the centrality calculation portion of the algorithm. 139 The ``PathCountMap`` type must be a `Distributed Property Map`_. 140 Its key type must be the graph's vertex descriptor type. 141 142 **Default**: An ``iterator_property_map`` created from a 143 ``std::vector`` of the graph's degree size type. 144 145IN: ``VertexIndexMap vertex_index`` 146 A model of `Readable Property Map`_ whose key type is the vertex 147 descriptor type of the graph ``g`` and whose value type is an 148 integral type. The property map should map from vertices to their 149 (local) indices in the range *[0, num_vertices(g))*. 150 151 **Default**: ``get(vertex_index, g)`` 152 153IN: ``WeightMap weight_map`` 154 A model of `Readable Property Map`_ whose key type is the edge 155 descriptor type of the graph ``g``. If not supplied the betweenness 156 centrality calculation will be unweighted. 157 158IN: ``Buffer sources`` 159 A model of Buffer_ containing the starting vertices for the 160 algorithm. If ``sources`` is empty a complete betweenness 161 centrality calculation using all vertices in ``g`` will be 162 performed. The value type of the Buffer must be the graph's vertex 163 descriptor type. 164 165 **Default**: An empty ``boost::queue`` of int. 166 167Complexity 168---------- 169 170Computing the shortest paths, counting them, and computing the 171contribution to the centrality map is *O(V log V)*. Calculating exact 172betweenness centrality requires counting the shortest paths from all 173vertices in ``g``, thus exact betweenness centrality is *O(V^2 log 174V)*. 175 176Algorithm Description 177--------------------- 178 179For the vertices in ``sources`` (or all vertices in ``g`` when 180``sources`` is empty) the algorithm first calls a customized 181implementation of delta_stepping_shortest_paths_ which maintains a 182shortest path tree using an ``IncomingMap``. The ``IncomingMap`` 183contains the source of all incoming edges on shortest paths. 184 185The ``IncomingMap`` defines the shortest path DAG at the target of the 186edges in the shortest paths tree. In the bidirectional case edge 187flags could be used to translate the shortest paths information to the 188source of the edges. Setting edge flags during the shortest path 189computation rather than using an ``IncomingMap`` would result in 190adding an *O(V)* factor to the inner loop of the shortest paths 191computation to account for having to clear edge flags when a new 192shortest path is found. This would increase the complexity of the 193algorithm. Asymptotically, the current implementation is better, 194however using edge flags in the bidirectional case would reduce the 195number of supersteps required by the depth of the shortest paths DAG 196for each vertex. Currently an ``outgoing`` map is explicitly 197constructed by simply reversing the edges in the incoming map. Once 198the ``outgoing`` map is constructed it is traversed in dependency 199order from the source of the shortest paths calculation in order to 200compute path counts. Once path counts are computed the shortest paths 201DAG is again traversed in dependency order from the source to 202calculate the dependency and centrality of each vertex. 203 204The algorithm is complete when the centrality has been computed from 205all vertices in ``g``. 206 207Bibliography 208------------ 209 210.. [Brandes01] Ulrik Brandes. A Faster Algorithm for Betweenness 211 Centrality. In the Journal of Mathematical Sociology, volume 25 212 number 2, pages 163--177, 2001. 213 214.. [Edmonds09] Nick Edmonds, Torsten Hoefler, and Andrew Lumsdaine. 215 A Space-Efficient Parallel Algorithm for Computing Betweenness 216 Centrality in Sparse Networks. Indiana University tech report. 217 2009. 218 219----------------------------------------------------------------------------- 220 221Copyright (C) 2009 The Trustees of Indiana University. 222 223Authors: Nick Edmonds and Andrew Lumsdaine 224 225.. |Logo| image:: pbgl-logo.png 226 :align: middle 227 :alt: Parallel BGL 228 :target: http://www.osl.iu.edu/research/pbgl 229 230.. _delta_stepping_shortest_paths: dijkstra_shortest_paths.html 231.. _Distributed Graph: DistributedGraph.html 232.. _Incidence Graph: http://www.boost.org/libs/graph/doc/IncidenceGraph.html 233.. _Readable Property Map: http://www.boost.org/libs/property_map/ReadablePropertyMap.html 234.. _Buffer: http://www.boost.org/libs/graph/doc/Buffer.html 235.. _Process Group: process_group.html 236.. _Distributed Property Map: distributed_property_map.html 237
