]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | <?xml version="1.0" encoding="utf-8" ?> |
2 | <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> | |
3 | <html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en"> | |
4 | <head> | |
5 | <meta http-equiv="Content-Type" content="text/html; charset=utf-8" /> | |
6 | <meta name="generator" content="Docutils 0.6: http://docutils.sourceforge.net/" /> | |
7 | <title>Parallel BGL Betweenness Centrality</title> | |
8 | <link rel="stylesheet" href="../../../../rst.css" type="text/css" /> | |
9 | </head> | |
10 | <body> | |
11 | <div class="document" id="logo-betweenness-centrality"> | |
12 | <h1 class="title"><a class="reference external" href="http://www.osl.iu.edu/research/pbgl"><img align="middle" alt="Parallel BGL" class="align-middle" src="pbgl-logo.png" /></a> Betweenness Centrality</h1> | |
13 | ||
14 | <!-- Copyright (C) 2004-2009 The Trustees of Indiana University. | |
15 | Use, modification and distribution is subject to the Boost Software | |
16 | License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at | |
17 | http://www.boost.org/LICENSE_1_0.txt) --> | |
18 | <pre class="literal-block"> | |
19 | // named parameter versions | |
20 | template<typename Graph, typename Param, typename Tag, typename Rest> | |
21 | void | |
22 | brandes_betweenness_centrality(const Graph& g, | |
23 | const bgl_named_params<Param,Tag,Rest>& params); | |
24 | ||
25 | template<typename Graph, typename CentralityMap> | |
26 | void | |
27 | brandes_betweenness_centrality(const Graph& g, CentralityMap centrality); | |
28 | ||
29 | template<typename Graph, typename CentralityMap, typename EdgeCentralityMap> | |
30 | void | |
31 | brandes_betweenness_centrality(const Graph& g, CentralityMap centrality, | |
32 | EdgeCentralityMap edge_centrality_map); | |
33 | ||
34 | // non-named parameter versions | |
35 | template<typename Graph, typename CentralityMap, typename EdgeCentralityMap, | |
36 | typename IncomingMap, typename DistanceMap, typename DependencyMap, | |
37 | typename PathCountMap, typename VertexIndexMap, typename Buffer> | |
38 | void | |
39 | brandes_betweenness_centrality(const Graph& g, | |
40 | CentralityMap centrality, | |
41 | EdgeCentralityMap edge_centrality_map, | |
42 | IncomingMap incoming, | |
43 | DistanceMap distance, | |
44 | DependencyMap dependency, | |
45 | PathCountMap path_count, | |
46 | VertexIndexMap vertex_index, | |
47 | Buffer sources, | |
48 | typename property_traits<DistanceMap>::value_type delta); | |
49 | ||
50 | template<typename Graph, typename CentralityMap, typename EdgeCentralityMap, | |
51 | typename IncomingMap, typename DistanceMap, typename DependencyMap, | |
52 | typename PathCountMap, typename VertexIndexMap, typename WeightMap, | |
53 | typename Buffer> | |
54 | void | |
55 | brandes_betweenness_centrality(const Graph& g, | |
56 | CentralityMap centrality, | |
57 | EdgeCentralityMap edge_centrality_map, | |
58 | IncomingMap incoming, | |
59 | DistanceMap distance, | |
60 | DependencyMap dependency, | |
61 | PathCountMap path_count, | |
62 | VertexIndexMap vertex_index, | |
63 | Buffer sources, | |
64 | typename property_traits<WeightMap>::value_type delta, | |
65 | WeightMap weight_map); | |
66 | ||
67 | // helper functions | |
68 | template<typename Graph, typename CentralityMap> | |
69 | typename property_traits<CentralityMap>::value_type | |
70 | central_point_dominance(const Graph& g, CentralityMap centrality); | |
71 | </pre> | |
72 | <p>The <tt class="docutils literal"><span class="pre">brandes_betweenness_centrality()</span></tt> function computes the | |
73 | betweenness centrality of the vertices and edges in a graph. The | |
74 | method of calculating betweenness centrality in <em>O(V)</em> space is due to | |
75 | Brandes <a class="citation-reference" href="#brandes01" id="id1">[Brandes01]</a>. The algorithm itself is a modification of | |
76 | Brandes algorithm by Edmonds <a class="citation-reference" href="#edmonds09" id="id2">[Edmonds09]</a>.</p> | |
77 | <div class="contents topic" id="contents"> | |
78 | <p class="topic-title first">Contents</p> | |
79 | <ul class="simple"> | |
80 | <li><a class="reference internal" href="#where-defined" id="id3">Where Defined</a></li> | |
81 | <li><a class="reference internal" href="#parameters" id="id4">Parameters</a></li> | |
82 | <li><a class="reference internal" href="#complexity" id="id5">Complexity</a></li> | |
83 | <li><a class="reference internal" href="#algorithm-description" id="id6">Algorithm Description</a></li> | |
84 | <li><a class="reference internal" href="#bibliography" id="id7">Bibliography</a></li> | |
85 | </ul> | |
86 | </div> | |
87 | <div class="section" id="where-defined"> | |
88 | <h1><a class="toc-backref" href="#id3">Where Defined</a></h1> | |
89 | <p><<tt class="docutils literal"><span class="pre">boost/graph/distributed/betweenness_centrality.hpp</span></tt>></p> | |
90 | <p>also accessible from</p> | |
91 | <p><<tt class="docutils literal"><span class="pre">boost/graph/betweenness_centrality.hpp</span></tt>></p> | |
92 | </div> | |
93 | <div class="section" id="parameters"> | |
94 | <h1><a class="toc-backref" href="#id4">Parameters</a></h1> | |
95 | <dl class="docutils"> | |
96 | <dt>IN: <tt class="docutils literal"><span class="pre">const</span> <span class="pre">Graph&</span> <span class="pre">g</span></tt></dt> | |
97 | <dd>The graph type must be a model of <a class="reference external" href="DistributedGraph.html">Distributed Graph</a>. The graph | |
98 | type must also model the <a class="reference external" href="http://www.boost.org/libs/graph/doc/IncidenceGraph.html">Incidence Graph</a> concept. 0-weighted | |
99 | edges in <tt class="docutils literal"><span class="pre">g</span></tt> will result in undefined behavior.</dd> | |
100 | <dt>IN: <tt class="docutils literal"><span class="pre">CentralityMap</span> <span class="pre">centrality</span></tt></dt> | |
101 | <dd><p class="first">A centrality map may be supplied to the algorithm, if not supplied a | |
102 | <tt class="docutils literal"><span class="pre">dummy_property_map</span></tt> will be used and no vertex centrality | |
103 | information will be recorded. The <tt class="docutils literal"><span class="pre">CentralityMap</span></tt> type must be a | |
104 | <a class="reference external" href="distributed_property_map.html">Distributed Property Map</a>. The key type must be the graph's | |
105 | vertex descriptor type.</p> | |
106 | <p class="last"><strong>Default</strong>: A <tt class="docutils literal"><span class="pre">dummy_property_map</span></tt>.</p> | |
107 | </dd> | |
108 | <dt>IN: <tt class="docutils literal"><span class="pre">EdgeCentralityMap</span> <span class="pre">edge_centrality_map</span></tt></dt> | |
109 | <dd><p class="first">An edge centrality map may be supplied to the algorithm, if not | |
110 | supplied a <tt class="docutils literal"><span class="pre">dummy_property_map</span></tt> will be used and no edge | |
111 | centrality information will be recorded. The <tt class="docutils literal"><span class="pre">EdgeCentralityMap</span></tt> | |
112 | type must be a <a class="reference external" href="distributed_property_map.html">Distributed Property Map</a>. The key type must be | |
113 | the graph's vertex descriptor type.</p> | |
114 | <p class="last"><strong>Default</strong>: A <tt class="docutils literal"><span class="pre">dummy_property_map</span></tt>.</p> | |
115 | </dd> | |
116 | <dt>IN: <tt class="docutils literal"><span class="pre">IncomingMap</span> <span class="pre">incoming</span></tt></dt> | |
117 | <dd><p class="first">The incoming map contains the incoming edges to a vertex that are | |
118 | part of shortest paths to that vertex. The <tt class="docutils literal"><span class="pre">IncomingMap</span></tt> type | |
119 | must be a <a class="reference external" href="distributed_property_map.html">Distributed Property Map</a>. Its key type and value type | |
120 | must both be the graph's vertex descriptor type.</p> | |
121 | <dl class="last docutils"> | |
122 | <dt><strong>Default</strong>: An <tt class="docutils literal"><span class="pre">iterator_property_map</span></tt> created from a</dt> | |
123 | <dd><tt class="docutils literal"><span class="pre">std::vector</span></tt> of <tt class="docutils literal"><span class="pre">std::vector</span></tt> of the graph's vertex | |
124 | descriptor type.</dd> | |
125 | </dl> | |
126 | </dd> | |
127 | <dt>IN: <tt class="docutils literal"><span class="pre">DistanceMap</span> <span class="pre">distance</span></tt></dt> | |
128 | <dd><p class="first">The distance map records the distance to vertices during the | |
129 | shortest paths portion of the algorithm. The <tt class="docutils literal"><span class="pre">DistanceMap</span></tt> type | |
130 | must be a <a class="reference external" href="distributed_property_map.html">Distributed Property Map</a>. Its key type must be the | |
131 | graph's vertex descriptor type.</p> | |
132 | <dl class="last docutils"> | |
133 | <dt><strong>Default</strong>: An <tt class="docutils literal"><span class="pre">iterator_property_map</span></tt> created from a</dt> | |
134 | <dd><tt class="docutils literal"><span class="pre">std::vector</span></tt> of the value type of the <tt class="docutils literal"><span class="pre">CentralityMap</span></tt>.</dd> | |
135 | </dl> | |
136 | </dd> | |
137 | <dt>IN: <tt class="docutils literal"><span class="pre">DependencyMap</span> <span class="pre">dependency</span></tt></dt> | |
138 | <dd><p class="first">The dependency map records the dependency of each vertex during the | |
139 | centrality calculation portion of the algorithm. The | |
140 | <tt class="docutils literal"><span class="pre">DependencyMap</span></tt> type must be a <a class="reference external" href="distributed_property_map.html">Distributed Property Map</a>. Its | |
141 | key type must be the graph's vertex descriptor type.</p> | |
142 | <dl class="last docutils"> | |
143 | <dt><strong>Default</strong>: An <tt class="docutils literal"><span class="pre">iterator_property_map</span></tt> created from a</dt> | |
144 | <dd><tt class="docutils literal"><span class="pre">std::vector</span></tt> of the value type of the <tt class="docutils literal"><span class="pre">CentralityMap</span></tt>.</dd> | |
145 | </dl> | |
146 | </dd> | |
147 | </dl> | |
148 | <p>IN: <tt class="docutils literal"><span class="pre">PathCountMap</span> <span class="pre">path_count</span></tt></p> | |
149 | <blockquote> | |
150 | <p>The path count map records the number of shortest paths each vertex | |
151 | is on during the centrality calculation portion of the algorithm. | |
152 | The <tt class="docutils literal"><span class="pre">PathCountMap</span></tt> type must be a <a class="reference external" href="distributed_property_map.html">Distributed Property Map</a>. | |
153 | Its key type must be the graph's vertex descriptor type.</p> | |
154 | <dl class="docutils"> | |
155 | <dt><strong>Default</strong>: An <tt class="docutils literal"><span class="pre">iterator_property_map</span></tt> created from a</dt> | |
156 | <dd><tt class="docutils literal"><span class="pre">std::vector</span></tt> of the graph's degree size type.</dd> | |
157 | </dl> | |
158 | </blockquote> | |
159 | <dl class="docutils"> | |
160 | <dt>IN: <tt class="docutils literal"><span class="pre">VertexIndexMap</span> <span class="pre">vertex_index</span></tt></dt> | |
161 | <dd><p class="first">A model of <a class="reference external" href="http://www.boost.org/libs/property_map/ReadablePropertyMap.html">Readable Property Map</a> whose key type is the vertex | |
162 | descriptor type of the graph <tt class="docutils literal"><span class="pre">g</span></tt> and whose value type is an | |
163 | integral type. The property map should map from vertices to their | |
164 | (local) indices in the range <em>[0, num_vertices(g))</em>.</p> | |
165 | <p class="last"><strong>Default</strong>: <tt class="docutils literal"><span class="pre">get(vertex_index,</span> <span class="pre">g)</span></tt></p> | |
166 | </dd> | |
167 | <dt>IN: <tt class="docutils literal"><span class="pre">WeightMap</span> <span class="pre">weight_map</span></tt></dt> | |
168 | <dd>A model of <a class="reference external" href="http://www.boost.org/libs/property_map/ReadablePropertyMap.html">Readable Property Map</a> whose key type is the edge | |
169 | descriptor type of the graph <tt class="docutils literal"><span class="pre">g</span></tt>. If not supplied the betweenness | |
170 | centrality calculation will be unweighted.</dd> | |
171 | <dt>IN: <tt class="docutils literal"><span class="pre">Buffer</span> <span class="pre">sources</span></tt></dt> | |
172 | <dd><p class="first">A model of <a class="reference external" href="http://www.boost.org/libs/graph/doc/Buffer.html">Buffer</a> containing the starting vertices for the | |
173 | algorithm. If <tt class="docutils literal"><span class="pre">sources</span></tt> is empty a complete betweenness | |
174 | centrality calculation using all vertices in <tt class="docutils literal"><span class="pre">g</span></tt> will be | |
175 | performed. The value type of the Buffer must be the graph's vertex | |
176 | descriptor type.</p> | |
177 | <p class="last"><strong>Default</strong>: An empty <tt class="docutils literal"><span class="pre">boost::queue</span></tt> of int.</p> | |
178 | </dd> | |
179 | </dl> | |
180 | </div> | |
181 | <div class="section" id="complexity"> | |
182 | <h1><a class="toc-backref" href="#id5">Complexity</a></h1> | |
183 | <p>Computing the shortest paths, counting them, and computing the | |
184 | contribution to the centrality map is <em>O(V log V)</em>. Calculating exact | |
185 | betweenness centrality requires counting the shortest paths from all | |
186 | vertices in <tt class="docutils literal"><span class="pre">g</span></tt>, thus exact betweenness centrality is <em>O(V^2 log | |
187 | V)</em>.</p> | |
188 | </div> | |
189 | <div class="section" id="algorithm-description"> | |
190 | <h1><a class="toc-backref" href="#id6">Algorithm Description</a></h1> | |
191 | <p>For the vertices in <tt class="docutils literal"><span class="pre">sources</span></tt> (or all vertices in <tt class="docutils literal"><span class="pre">g</span></tt> when | |
192 | <tt class="docutils literal"><span class="pre">sources</span></tt> is empty) the algorithm first calls a customized | |
193 | implementation of <a class="reference external" href="dijkstra_shortest_paths.html">delta_stepping_shortest_paths</a> which maintains a | |
194 | shortest path tree using an <tt class="docutils literal"><span class="pre">IncomingMap</span></tt>. The <tt class="docutils literal"><span class="pre">IncomingMap</span></tt> | |
195 | contains the source of all incoming edges on shortest paths.</p> | |
196 | <p>The <tt class="docutils literal"><span class="pre">IncomingMap</span></tt> defines the shortest path DAG at the target of the | |
197 | edges in the shortest paths tree. In the bidirectional case edge | |
198 | flags could be used to translate the shortest paths information to the | |
199 | source of the edges. Setting edge flags during the shortest path | |
200 | computation rather than using an <tt class="docutils literal"><span class="pre">IncomingMap</span></tt> would result in | |
201 | adding an <em>O(V)</em> factor to the inner loop of the shortest paths | |
202 | computation to account for having to clear edge flags when a new | |
203 | shortest path is found. This would increase the complexity of the | |
204 | algorithm. Asymptotically, the current implementation is better, | |
205 | however using edge flags in the bidirectional case would reduce the | |
206 | number of supersteps required by the depth of the shortest paths DAG | |
207 | for each vertex. Currently an <tt class="docutils literal"><span class="pre">outgoing</span></tt> map is explicitly | |
208 | constructed by simply reversing the edges in the incoming map. Once | |
209 | the <tt class="docutils literal"><span class="pre">outgoing</span></tt> map is constructed it is traversed in dependency | |
210 | order from the source of the shortest paths calculation in order to | |
211 | compute path counts. Once path counts are computed the shortest paths | |
212 | DAG is again traversed in dependency order from the source to | |
213 | calculate the dependency and centrality of each vertex.</p> | |
214 | <p>The algorithm is complete when the centrality has been computed from | |
215 | all vertices in <tt class="docutils literal"><span class="pre">g</span></tt>.</p> | |
216 | </div> | |
217 | <div class="section" id="bibliography"> | |
218 | <h1><a class="toc-backref" href="#id7">Bibliography</a></h1> | |
219 | <table class="docutils citation" frame="void" id="brandes01" rules="none"> | |
220 | <colgroup><col class="label" /><col /></colgroup> | |
221 | <tbody valign="top"> | |
222 | <tr><td class="label"><a class="fn-backref" href="#id1">[Brandes01]</a></td><td>Ulrik Brandes. A Faster Algorithm for Betweenness | |
223 | Centrality. In the Journal of Mathematical Sociology, volume 25 | |
224 | number 2, pages 163--177, 2001.</td></tr> | |
225 | </tbody> | |
226 | </table> | |
227 | <table class="docutils citation" frame="void" id="edmonds09" rules="none"> | |
228 | <colgroup><col class="label" /><col /></colgroup> | |
229 | <tbody valign="top"> | |
230 | <tr><td class="label"><a class="fn-backref" href="#id2">[Edmonds09]</a></td><td>Nick Edmonds, Torsten Hoefler, and Andrew Lumsdaine. | |
231 | A Space-Efficient Parallel Algorithm for Computing Betweenness | |
232 | Centrality in Sparse Networks. Indiana University tech report. | |
233 | 2009.</td></tr> | |
234 | </tbody> | |
235 | </table> | |
236 | <hr class="docutils" /> | |
237 | <p>Copyright (C) 2009 The Trustees of Indiana University.</p> | |
238 | <p>Authors: Nick Edmonds and Andrew Lumsdaine</p> | |
239 | </div> | |
240 | </div> | |
241 | <div class="footer"> | |
242 | <hr class="footer" /> | |
243 | Generated on: 2009-05-31 00:21 UTC. | |
244 | Generated by <a class="reference external" href="http://docutils.sourceforge.net/">Docutils</a> from <a class="reference external" href="http://docutils.sourceforge.net/rst.html">reStructuredText</a> source. | |
245 | ||
246 | </div> | |
247 | </body> | |
248 | </html> |