123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236 |
- .. Copyright (C) 2004-2009 The Trustees of Indiana University.
- Use, modification and distribution is subject to the Boost Software
- License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
- http://www.boost.org/LICENSE_1_0.txt)
- =============================
- |Logo| Betweenness Centrality
- =============================
- ::
- // named parameter versions
- template<typename Graph, typename Param, typename Tag, typename Rest>
- void
- brandes_betweenness_centrality(const Graph& g,
- const bgl_named_params<Param,Tag,Rest>& params);
- template<typename Graph, typename CentralityMap>
- void
- brandes_betweenness_centrality(const Graph& g, CentralityMap centrality);
- template<typename Graph, typename CentralityMap, typename EdgeCentralityMap>
- void
- brandes_betweenness_centrality(const Graph& g, CentralityMap centrality,
- EdgeCentralityMap edge_centrality_map);
- // non-named parameter versions
- template<typename Graph, typename CentralityMap, typename EdgeCentralityMap,
- typename IncomingMap, typename DistanceMap, typename DependencyMap,
- typename PathCountMap, typename VertexIndexMap, typename Buffer>
- void
- brandes_betweenness_centrality(const Graph& g,
- CentralityMap centrality,
- EdgeCentralityMap edge_centrality_map,
- IncomingMap incoming,
- DistanceMap distance,
- DependencyMap dependency,
- PathCountMap path_count,
- VertexIndexMap vertex_index,
- Buffer sources,
- typename property_traits<DistanceMap>::value_type delta);
- template<typename Graph, typename CentralityMap, typename EdgeCentralityMap,
- typename IncomingMap, typename DistanceMap, typename DependencyMap,
- typename PathCountMap, typename VertexIndexMap, typename WeightMap,
- typename Buffer>
- void
- brandes_betweenness_centrality(const Graph& g,
- CentralityMap centrality,
- EdgeCentralityMap edge_centrality_map,
- IncomingMap incoming,
- DistanceMap distance,
- DependencyMap dependency,
- PathCountMap path_count,
- VertexIndexMap vertex_index,
- Buffer sources,
- typename property_traits<WeightMap>::value_type delta,
- WeightMap weight_map);
- // helper functions
- template<typename Graph, typename CentralityMap>
- typename property_traits<CentralityMap>::value_type
- central_point_dominance(const Graph& g, CentralityMap centrality);
- The ``brandes_betweenness_centrality()`` function computes the
- betweenness centrality of the vertices and edges in a graph. The
- method of calculating betweenness centrality in *O(V)* space is due to
- Brandes [Brandes01]_. The algorithm itself is a modification of
- Brandes algorithm by Edmonds [Edmonds09]_.
- .. contents::
- Where Defined
- -------------
- <``boost/graph/distributed/betweenness_centrality.hpp``>
- also accessible from
- <``boost/graph/betweenness_centrality.hpp``>
- Parameters
- ----------
- IN: ``const Graph& g``
- The graph type must be a model of `Distributed Graph`_. The graph
- type must also model the `Incidence Graph`_ concept. 0-weighted
- edges in ``g`` will result in undefined behavior.
- IN: ``CentralityMap centrality``
- A centrality map may be supplied to the algorithm, if not supplied a
- ``dummy_property_map`` will be used and no vertex centrality
- information will be recorded. The ``CentralityMap`` type must be a
- `Distributed Property Map`_. The key type must be the graph's
- vertex descriptor type.
- **Default**: A ``dummy_property_map``.
- IN: ``EdgeCentralityMap edge_centrality_map``
- An edge centrality map may be supplied to the algorithm, if not
- supplied a ``dummy_property_map`` will be used and no edge
- centrality information will be recorded. The ``EdgeCentralityMap``
- type must be a `Distributed Property Map`_. The key type must be
- the graph's vertex descriptor type.
- **Default**: A ``dummy_property_map``.
- IN: ``IncomingMap incoming``
- The incoming map contains the incoming edges to a vertex that are
- part of shortest paths to that vertex. The ``IncomingMap`` type
- must be a `Distributed Property Map`_. Its key type and value type
- must both be the graph's vertex descriptor type.
- **Default**: An ``iterator_property_map`` created from a
- ``std::vector`` of ``std::vector`` of the graph's vertex
- descriptor type.
- IN: ``DistanceMap distance``
- The distance map records the distance to vertices during the
- shortest paths portion of the algorithm. The ``DistanceMap`` type
- must be a `Distributed Property Map`_. Its key type must be the
- graph's vertex descriptor type.
- **Default**: An ``iterator_property_map`` created from a
- ``std::vector`` of the value type of the ``CentralityMap``.
- IN: ``DependencyMap dependency``
- The dependency map records the dependency of each vertex during the
- centrality calculation portion of the algorithm. The
- ``DependencyMap`` type must be a `Distributed Property Map`_. Its
- key type must be the graph's vertex descriptor type.
- **Default**: An ``iterator_property_map`` created from a
- ``std::vector`` of the value type of the ``CentralityMap``.
- IN: ``PathCountMap path_count``
- The path count map records the number of shortest paths each vertex
- is on during the centrality calculation portion of the algorithm.
- The ``PathCountMap`` type must be a `Distributed Property Map`_.
- Its key type must be the graph's vertex descriptor type.
- **Default**: An ``iterator_property_map`` created from a
- ``std::vector`` of the graph's degree size type.
- IN: ``VertexIndexMap vertex_index``
- A model of `Readable Property Map`_ whose key type is the vertex
- descriptor type of the graph ``g`` and whose value type is an
- integral type. The property map should map from vertices to their
- (local) indices in the range *[0, num_vertices(g))*.
- **Default**: ``get(vertex_index, g)``
- IN: ``WeightMap weight_map``
- A model of `Readable Property Map`_ whose key type is the edge
- descriptor type of the graph ``g``. If not supplied the betweenness
- centrality calculation will be unweighted.
- IN: ``Buffer sources``
- A model of Buffer_ containing the starting vertices for the
- algorithm. If ``sources`` is empty a complete betweenness
- centrality calculation using all vertices in ``g`` will be
- performed. The value type of the Buffer must be the graph's vertex
- descriptor type.
- **Default**: An empty ``boost::queue`` of int.
- Complexity
- ----------
- Computing the shortest paths, counting them, and computing the
- contribution to the centrality map is *O(V log V)*. Calculating exact
- betweenness centrality requires counting the shortest paths from all
- vertices in ``g``, thus exact betweenness centrality is *O(V^2 log
- V)*.
- Algorithm Description
- ---------------------
- For the vertices in ``sources`` (or all vertices in ``g`` when
- ``sources`` is empty) the algorithm first calls a customized
- implementation of delta_stepping_shortest_paths_ which maintains a
- shortest path tree using an ``IncomingMap``. The ``IncomingMap``
- contains the source of all incoming edges on shortest paths.
- The ``IncomingMap`` defines the shortest path DAG at the target of the
- edges in the shortest paths tree. In the bidirectional case edge
- flags could be used to translate the shortest paths information to the
- source of the edges. Setting edge flags during the shortest path
- computation rather than using an ``IncomingMap`` would result in
- adding an *O(V)* factor to the inner loop of the shortest paths
- computation to account for having to clear edge flags when a new
- shortest path is found. This would increase the complexity of the
- algorithm. Asymptotically, the current implementation is better,
- however using edge flags in the bidirectional case would reduce the
- number of supersteps required by the depth of the shortest paths DAG
- for each vertex. Currently an ``outgoing`` map is explicitly
- constructed by simply reversing the edges in the incoming map. Once
- the ``outgoing`` map is constructed it is traversed in dependency
- order from the source of the shortest paths calculation in order to
- compute path counts. Once path counts are computed the shortest paths
- DAG is again traversed in dependency order from the source to
- calculate the dependency and centrality of each vertex.
- The algorithm is complete when the centrality has been computed from
- all vertices in ``g``.
- Bibliography
- ------------
- .. [Brandes01] Ulrik Brandes. A Faster Algorithm for Betweenness
- Centrality. In the Journal of Mathematical Sociology, volume 25
- number 2, pages 163--177, 2001.
- .. [Edmonds09] Nick Edmonds, Torsten Hoefler, and Andrew Lumsdaine.
- A Space-Efficient Parallel Algorithm for Computing Betweenness
- Centrality in Sparse Networks. Indiana University tech report.
- 2009.
- -----------------------------------------------------------------------------
- Copyright (C) 2009 The Trustees of Indiana University.
- Authors: Nick Edmonds and Andrew Lumsdaine
- .. |Logo| image:: pbgl-logo.png
- :align: middle
- :alt: Parallel BGL
- :target: http://www.osl.iu.edu/research/pbgl
- .. _delta_stepping_shortest_paths: dijkstra_shortest_paths.html
- .. _Distributed Graph: DistributedGraph.html
- .. _Incidence Graph: http://www.boost.org/libs/graph/doc/IncidenceGraph.html
- .. _Readable Property Map: http://www.boost.org/libs/property_map/ReadablePropertyMap.html
- .. _Buffer: http://www.boost.org/libs/graph/doc/Buffer.html
- .. _Process Group: process_group.html
- .. _Distributed Property Map: distributed_property_map.html
|