1<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"> 2<html> 3<!-- 4 Copyright (c) 2004 Trustees of Indiana University 5 6 Distributed under the Boost Software License, Version 1.0. 7 (See accompanying file LICENSE_1_0.txt or copy at 8 http://www.boost.org/LICENSE_1_0.txt) 9 --> 10 <head> 11 <title>Boost Graph Library: Brandes' Betweenness Centrality</title> 12 </head> 13 14 <body> 15 <IMG SRC="../../../boost.png" 16 ALT="C++ Boost" width="277" height="86"> 17<h1><img src="figs/python.gif" alt="(Python)"/><tt>brandes_betweenness_centrality</tt></h1> 18 19 <p> 20 <pre> 21<em>// named parameter versions</em> 22template<typename Graph, typename Param, typename Tag, typename Rest> 23void 24brandes_betweenness_centrality(const Graph& g, 25 const bgl_named_params<Param,Tag,Rest>& params); 26 27template<typename Graph, typename CentralityMap> 28void 29brandes_betweenness_centrality(const Graph& g, CentralityMap centrality_map); 30 31template<typename Graph, typename CentralityMap, typename EdgeCentralityMap> 32void 33brandes_betweenness_centrality(const Graph& g, CentralityMap centrality_map, 34 EdgeCentralityMap edge_centrality); 35 36<em>// non-named parameter versions</em> 37template<typename Graph, typename CentralityMap, typename EdgeCentralityMap, 38 typename IncomingMap, typename DistanceMap, typename DependencyMap, 39 typename PathCountMap, typename VertexIndexMap> 40void 41brandes_betweenness_centrality(const Graph& g, CentralityMap centrality_map, 42 EdgeCentralityMap edge_centrality, 43 IncomingMap incoming, 44 DistanceMap distance, DependencyMap dependency, 45 PathCountMap path_count, 46 VertexIndexMap vertex_index); 47 48template<typename Graph, typename CentralityMap, typename EdgeCentralityMap, 49 typename IncomingMap, typename DistanceMap, typename DependencyMap, 50 typename PathCountMap, typename VertexIndexMap, typename WeightMap> 51void 52brandes_betweenness_centrality(const Graph& g, CentralityMap centrality_map, 53 EdgeCentralityMap edge_centrality, 54 IncomingMap incoming, 55 DistanceMap distance, DependencyMap dependency, 56 PathCountMap path_count, 57 VertexIndexMap vertex_index, 58 WeightMap weight_map); 59 60<em>// helper functions</em> 61template<typename Graph, typename CentralityMap> 62void 63relative_betweenness_centrality(const Graph& g, CentralityMap centrality_map); 64 65template<typename Graph, typename CentralityMap> 66typename property_traits<CentralityMap>::value_type 67central_point_dominance(const Graph& g, CentralityMap centrality_map); 68 </pre> 69 70<p>This algorithm [<a href="bibliography.html#brandes01">54</a>] 71computes the <em>betweenness centrality</em> [<a 72href="bibliography.html#freeman77">55</a>,<a 73href="bibliography.html#anthonisse71">56</a>] of each vertex or each 74edge in the graph. The betweenness centrality of a vertex <em>v</em> 75is defined by 76 77<p><img src="figs/betweenness_centrality.gif">, 78 79<p>where <img src="figs/sigma_st.gif"> is the number of shortest paths from 80vertex <em>s</em> to vertex <em>t</em> and <img src="figs/sigma_stv.gif"> 81is the number of shortest paths from vertex <em>s</em> to vertex 82<em>t</em> that pass through vertex <em>v</em>. 83 84<!-- \sum_{s \neq v \neq t}\frac{\sigma_{st}(v)}{\sigma_{st}} --> 85 86<p>The edge betweenness centrality indicates for each edge the 87betweenness centrality that was contributed to the target(s) of the 88edge (plural for undirected graphs). Similar to (vertex) betweenness 89centrality, edge betweenness centrality can be used to determine the 90edges through which most shortest paths must pass. A single invocation 91of this algorithm can compute either the vertex or edge centrality (or 92both).</p> 93 94<p>This algorithm can operate either on weighted graphs (if a suitable 95edge weight map is supplied) or unweighted graphs (if no edge weight 96map is supplied). The result is the absolute betweenness centrality; 97to convert to the relative betweenness centrality, which scales each 98absolute centrality by <img src="figs/rel_betweenness_centrality.gif"> 99(where <em>n</em> is the number of vertices in the graph), use 100<tt>relative_betweenness_centrality</tt>. Given the relative 101betweenness centrality, one can compute the <em>central point 102dominance</em> [<a href="bibliography.html#freeman77">55</a>], which is a measure of the maximum "betweenness" of any 103point in the graph: it will be 0 for complete graphs and 1041 for "wheel" graphs (in which there is a central vertex that all 105paths include; see <a href="#Fig1">Fig. 1</a>). Let <img src="figs/v_star.gif"> be the vertex with the largest relative betweenness centrality; then, the central point dominance is defined as: 106 107<p><img src="figs/central_point_dominance.gif"> 108 109<!-- C_B' = \frac{\sum_{v \in V} C_B(v^*) - C_B'(v)}{n-1} --> 110 111<p><a name="Fig1"> 112 <table border="1"> 113 <thead> 114 <tr> 115 <th>Fig. 1: A wheel graph, where every path travels through the central node. <br>The central point dominance of this graph is 1.</td> 116 </tr> 117 </thead> 118 <tbody> 119 <tr> 120 <td align="center"><img src="figs/wheel_graph.gif"></td> 121 </tr> 122 </tbody> 123 </table> 124 125<h3>Where Defined</h3> 126<a href="../../../boost/graph/betweenness_centrality.hpp"><tt>boost/graph/betweenness_centrality.hpp</tt></a> 127 128<h3>Parameters</h3> 129IN: <tt>const Graph& g</tt> 130<blockquote> 131 The graph object on which the algorithm will be applied. The type 132 <tt>Graph</tt> must be a model of <a 133 href="VertexListGraph.html">Vertex List Graph</a> and <a 134 href="IncidenceGraph.html">Incidence Graph</a>. When an edge 135 centrality map is supplied, it must also model <a 136 href="EdgeListGraph.html">Edge List Graph</a>.<br> 137 138<b>Python</b>: The parameter is named <tt>graph</tt>. 139</blockquote> 140 141UTIL: <tt>IncomingMap incoming</tt> 142<blockquote> 143 This property map records the set of edges incoming to each vertex that comprise a shortest path from a particular source vertex through this vertex, and is used internally by the algorithm.The <tt>IncomingMap</tt> type must be a <a 144 href="../../property_map/doc/LvaluePropertyMap.html">Lvalue Property 145 Map</a> whose key type is the same as the vertex descriptor type of 146 the graph and whose value type is a Sequence (e.g., an 147 <tt>std::vector</tt>) containing edge descriptors.<br> 148 149 <b>Default:</b> <a 150 href="../../property_map/doc/iterator_property_map.html"> 151 <tt>iterator_property_map</tt></a> created from a 152 <tt>std::vector</tt> of <tt>std::vector<Edge></tt>, where 153 <tt>Edge</tt> is the edge descriptor type of the graph.<br> 154 155 <b>Python</b>: Unsupported parameter. 156</blockquote> 157 158UTIL: <tt>DistanceMap distance_map</tt> 159<blockquote> 160 The shortest path weight from each source vertex <tt>s</tt> to each 161 vertex in the graph <tt>g</tt> is recorded in this property map, but 162 the result is only used internally. The type <tt>DistanceMap</tt> 163 must be a model of <a 164 href="../../property_map/doc/ReadWritePropertyMap.html">Read/Write 165 Property Map</a>. The vertex descriptor type of the graph needs to 166 be usable as the key type of the distance map. The value type of the 167 distance map is the element type of a <a 168 href="./Monoid.html">Monoid</a>.<br> 169 170 <b>Default:</b> <a 171 href="../../property_map/doc/iterator_property_map.html"> 172 <tt>iterator_property_map</tt></a> created from a 173 <tt>std::vector</tt> of the <tt>WeightMap</tt>'s value type (or the 174 <tt>vertices_size_type</tt> of the graph when no weight map exists) 175 of size <tt>num_vertices(g)</tt> and using the <tt>vertex_index</tt> for 176 the index map.<br> 177 178 <b>Python</b>: Unsupported parameter. 179</blockquote> 180 181UTIL: <tt>DependencyMap dependency</tt> 182<blockquote> 183 Property map used internally to accumulate partial betweenness 184 centrality results. The type <tt>DependencyMap</tt> must be a model 185 of <a href="../../property_map/doc/ReadWritePropertyMap.html">Read/Write 186 Property Map</a>. The vertex descriptor type of the graph needs to 187 be usable as the key type of the dependency map. The value type of 188 the dependency map must be compatible with the value type of the 189 centrality map.<br> 190 191 <b>Default:</b> <a 192 href="../../property_map/doc/iterator_property_map.html"> 193 <tt>iterator_property_map</tt></a> created from a 194 <tt>std::vector</tt> of the <tt>CentralityMap</tt>'s value type of 195 size <tt>num_vertices(g)</tt> and using the <tt>vertex_index</tt> 196 for the index map.<br> 197 198 <b>Python</b>: Unsupported parameter. 199</blockquote> 200 201UTIL: <tt>PathCountMap path_count</tt> 202<blockquote> 203 Property map used internally to accumulate the number of paths that 204 pass through each particular vertex. The type <tt>PathCountMap</tt> 205 must be a model of <a 206 href="../../property_map/doc/ReadWritePropertyMap.html">Read/Write 207 Property Map</a>. The vertex descriptor type of the graph needs to 208 be usable as the key type of the dependency map. The value type of 209 the dependency map must be an integral type large enough to store 210 the number of paths in the graph.<br> 211 212 <b>Default:</b> <a 213 href="../../property_map/doc/iterator_property_map.html"> 214 <tt>iterator_property_map</tt></a> created from a 215 <tt>std::vector</tt> of the <tt>degree_size_type</tt> of the graph of 216 size <tt>num_vertices(g)</tt> and using the <tt>vertex_index</tt> 217 for the index map.<br> 218 219 <b>Python</b>: Unsupported parameter. 220</blockquote> 221 222<h3>Named parameters</h3> 223OUT/UTIL: <tt>CentralityMap centrality_map</tt> 224<blockquote> 225 This property map is used to accumulate the betweenness centrality 226 of each vertex, and is the primary output of the algorithm. The type 227 <tt>CentralityMap</tt> must be a model of <a 228 href="../../property_map/doc/ReadWritePropertyMap.html">Read/Write 229 Property Map</a>, with the graph's vertex descriptor type as its key 230 type. The value type of this property map should be a floating-point 231 or rational type.<br> 232 233 <b>Default:</b> a <tt>dummy_property_map</tt>, which requires no 234 work to compute and returns no answer.<br> 235 <b>Python</b>: The color map must be a <tt>vertex_double_map</tt> for 236 the graph.<br> 237 <b>Python default</b>: <tt>graph.get_vertex_double_map("centrality")</tt> 238</blockquote> 239 240OUT/UTIL: <tt>EdgeCentralityMap edge_centrality_map</tt> 241<blockquote> 242 This property map is used to accumulate the betweenness centrality 243 of each edge, and is a secondary form of output for the 244 algorithm. The type <tt>EdgeCentralityMap</tt> must be a model of <a 245 href="../../property_map/doc/ReadWritePropertyMap.html">Read/Write 246 Property Map</a>, with the graph's edge descriptor type as its key 247 type. The value type of this property map should be the same as the 248 value type of the <tt>CentralityMap</tt> property map.<br> 249 250 <b>Default:</b> a <tt>dummy_property_map</tt>, which requires no 251 work to compute and returns no answer.<br> 252 <b>Python</b>: The color map must be a <tt>edge_double_map</tt> for 253 the graph.<br> 254 <b>Python default</b>: <tt>graph.get_edge_double_map("centrality")</tt> 255</blockquote> 256 257IN: <tt>vertex_index_map(VertexIndexMap vertex_index)</tt> 258<blockquote> 259 This maps each vertex to an integer in the range <tt>[0, 260 num_vertices(g))</tt>. This is necessary for efficient updates of the 261 heap data structure when an edge is relaxed. The type 262 <tt>VertexIndexMap</tt> must be a model of 263 <a href="../../property_map/doc/ReadablePropertyMap.html">Readable Property Map</a>. The value type of the map must be an 264 integer type. The vertex descriptor type of the graph needs to be 265 usable as the key type of the map.<br> 266 <b>Default:</b> <tt>get(vertex_index, g)</tt>. 267 Note: if you use this default, make sure your graph has 268 an internal <tt>vertex_index</tt> property. For example, 269 <tt>adjacency_list</tt> with <tt>VertexList=listS</tt> does 270 not have an internal <tt>vertex_index</tt> property.<br> 271 <b>Python</b>: Unsupported parameter. 272</blockquote> 273 274IN: <tt>weight_map(WeightMap w_map)</tt> 275<blockquote> 276 The weight or ``length'' of each edge in the graph. The weights 277 must all be non-negative, and the algorithm will throw a 278 <a href="./exception.html#negative_edge"><tt>negative_edge</tt></a> 279 exception is one of the edges is negative. 280 The type <tt>WeightMap</tt> must be a model of 281 <a href="../../property_map/doc/ReadablePropertyMap.html">Readable Property Map</a>. The edge descriptor type of 282 the graph needs to be usable as the key type for the weight 283 map. The value type for this map must be 284 the same as the value type of the distance map.<br> 285 <b>Default:</b> All edge weights are assumed to be equivalent. 286 <b>Python</b>: If supplied, must be an <tt>edge_double_map</tt> for the graph. 287</blockquote> 288 289<h3>Complexity</h3> 290The time complexity is <em>O(VE)</em> for unweighted graphs and 291<em>O(VE + V(V+E) log V)</em> for weighted graphs. The space complexity 292is <em>O(VE)</em>. 293 294 <hr> 295 296<TABLE> 297<TR valign=top> 298<TD nowrap>Copyright © 2004</TD><TD> 299<A HREF="http://www.boost.org/people/doug_gregor.html">Douglas Gregor</A>, Indiana University (dgregor@cs.indiana.edu</A>)<br> 300<A HREF="https://homes.cs.washington.edu/~al75">Andrew Lumsdaine</A>, 301Indiana University (<A 302HREF="mailto:lums@osl.iu.edu">lums@osl.iu.edu</A>) 303</TD></TR></TABLE> 304<!-- Created: Fri Jun 4 16:42:50 EST 2004 --> 305<!-- hhmts start -->Last modified: Tue Mar 1 14:14:51 EST 2005 <!-- hhmts end --> 306 </body> 307</html> 308
