]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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 |