Planet
navi homePPSaboutscreenshotsdownloaddevelopmentforum

source: downloads/boost_1_34_1/libs/graph/doc/betweenness_centrality.html @ 29

Last change on this file since 29 was 29, checked in by landauf, 17 years ago

updated boost from 1_33_1 to 1_34_1
File size: 13.4 KB
Line 
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&lt;typename Graph, typename Param, typename Tag, typename Rest&gt;
23void
24brandes_betweenness_centrality(const Graph&amp; g,
25                               const bgl_named_params&lt;Param,Tag,Rest&gt;&amp; params);
26
27template&lt;typename Graph, typename CentralityMap&gt;
28void
29brandes_betweenness_centrality(const Graph&amp; g, CentralityMap centrality_map);
30
31template&lt;typename Graph, typename CentralityMap, typename EdgeCentralityMap&gt;
32void
33brandes_betweenness_centrality(const Graph&amp; g, CentralityMap centrality_map,
34                               EdgeCentralityMap edge_centrality);
35
36<em>// non-named parameter versions</em>
37template&lt;typename Graph, typename CentralityMap, typename EdgeCentralityMap,
38         typename IncomingMap, typename DistanceMap, typename DependencyMap,
39         typename PathCountMap, typename VertexIndexMap&gt;
40void
41brandes_betweenness_centrality(const Graph&amp; 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&lt;typename Graph, typename CentralityMap, typename EdgeCentralityMap,
49         typename IncomingMap, typename DistanceMap, typename DependencyMap,
50         typename PathCountMap, typename VertexIndexMap, typename WeightMap&gt;   
51void
52brandes_betweenness_centrality(const Graph&amp; 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&lt;typename Graph, typename CentralityMap&gt;
62void
63relative_betweenness_centrality(const Graph&amp; g, CentralityMap centrality_map);
64
65template&lt;typename Graph, typename CentralityMap&gt;
66typename property_traits&lt;CentralityMap&gt;::value_type
67central_point_dominance(const Graph&amp; g, CentralityMap centrality_map);
68    </pre>
69
70<p>This algorithm&nbsp;[<a href="bibliography.html#brandes01">54</a>]
71computes the <em>betweenness centrality</em>&nbsp;[<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>&nbsp;[<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&amp; 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/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/iterator_property_map.html">
151  <tt>iterator_property_map</tt></a> created from a
152  <tt>std::vector</tt> of <tt>std::vector&lt;Edge&gt;</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/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/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/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/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/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/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/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/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/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>adjacenty_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/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 &copy 2004</TD><TD>
299<A HREF="../../../people/doug_gregor.html">Douglas Gregor</A>, Indiana University (dgregor@cs.indiana.edu</A>)<br>
300<A HREF=http://www.osl.iu.edu/~lums>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>
Note: See TracBrowser for help on using the repository browser.