ceph/src/boost/libs/graph_parallel/doc/betweenness_centrality.rst

   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
  65 The ``brandes_betweenness_centrality()`` function computes the
  66 betweenness centrality of the vertices and edges in a graph.  The
  67 method of calculating betweenness centrality in *O(V)* space is due to
  68 Brandes [Brandes01]_.  The algorithm itself is a modification of
  69 Brandes algorithm by Edmonds [Edmonds09]_.
  70
  71 .. contents::
  72
  73 Where Defined
  74 -------------
  75 <``boost/graph/distributed/betweenness_centrality.hpp``>
  76
  77 also accessible from
  78
  79 <``boost/graph/betweenness_centrality.hpp``>
  80
  81 Parameters
  82 ----------
  83
  84 IN:  ``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
  89 IN: ``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
  98 IN:  ``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
 107 IN:  ``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
 117 IN:  ``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
 126 IN: ``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
 135 IN:  ``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
 145 IN:  ``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
 153 IN:  ``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
 158 IN: ``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
 167 Complexity
 168 ----------
 169
 170 Computing the shortest paths, counting them, and computing the
 171 contribution to the centrality map is *O(V log V)*.  Calculating exact
 172 betweenness centrality requires counting the shortest paths from all
 173 vertices in ``g``, thus exact betweenness centrality is *O(V^2 log
 174 V)*.
 175
 176 Algorithm Description
 177 ---------------------
 178
 179 For the vertices in ``sources`` (or all vertices in ``g`` when
 180 ``sources`` is empty) the algorithm first calls a customized
 181 implementation of delta_stepping_shortest_paths_ which maintains a
 182 shortest path tree using an ``IncomingMap``.  The ``IncomingMap``
 183 contains the source of all incoming edges on shortest paths.
 184
 185 The ``IncomingMap`` defines the shortest path DAG at the target of the
 186 edges in the shortest paths tree.  In the bidirectional case edge
 187 flags could be used to translate the shortest paths information to the
 188 source of the edges.  Setting edge flags during the shortest path
 189 computation rather than using an ``IncomingMap`` would result in
 190 adding an *O(V)* factor to the inner loop of the shortest paths
 191 computation to account for having to clear edge flags when a new
 192 shortest path is found.  This would increase the complexity of the
 193 algorithm.  Asymptotically, the current implementation is better,
 194 however using edge flags in the bidirectional case would reduce the
 195 number of supersteps required by the depth of the shortest paths DAG
 196 for each vertex.  Currently an ``outgoing`` map is explicitly
 197 constructed by simply reversing the edges in the incoming map.  Once
 198 the ``outgoing`` map is constructed it is traversed in dependency
 199 order from the source of the shortest paths calculation in order to
 200 compute path counts.  Once path counts are computed the shortest paths
 201 DAG is again traversed in dependency order from the source to
 202 calculate the dependency and centrality of each vertex.
 203
 204 The algorithm is complete when the centrality has been computed from
 205 all vertices in ``g``.
 206
 207 Bibliography
 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
 221 Copyright (C) 2009 The Trustees of Indiana University.
 222
 223 Authors: 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