← Back to branch summary

~ubuntu-branches/debian/sid/boost1.49/sid

« back to all changes in this revision

Viewing changes to libs/graph/doc/betweenness_centrality.html

  • Committer: Package Import Robot
  • Author(s): Steve M. Robbins
  • Date: 2012-02-26 00:31:44 UTC
  • Revision ID: package-import@ubuntu.com-20120226003144-eaytp12cbf6ubpms
Tags: upstream-1.49.0
Import upstream version 1.49.0

Show diffs side-by-side

added added

removed removed

Lines of Context:
libs/graph/doc/betweenness_centrality.html
 
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>
 
22
template&lt;typename Graph, typename Param, typename Tag, typename Rest&gt;
 
23
void 
 
24
brandes_betweenness_centrality(const Graph&amp; g,
 
25
                               const bgl_named_params&lt;Param,Tag,Rest&gt;&amp; params);
 
26
 
 
27
template&lt;typename Graph, typename CentralityMap&gt;
 
28
void 
 
29
brandes_betweenness_centrality(const Graph&amp; g, CentralityMap centrality_map);
 
30
 
 
31
template&lt;typename Graph, typename CentralityMap, typename EdgeCentralityMap&gt;
 
32
void 
 
33
brandes_betweenness_centrality(const Graph&amp; g, CentralityMap centrality_map,
 
34
                               EdgeCentralityMap edge_centrality);
 
35
 
 
36
<em>// non-named parameter versions</em>
 
37
template&lt;typename Graph, typename CentralityMap, typename EdgeCentralityMap,
 
38
         typename IncomingMap, typename DistanceMap, typename DependencyMap, 
 
39
         typename PathCountMap, typename VertexIndexMap&gt;
 
40
void 
 
41
brandes_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
 
 
48
template&lt;typename Graph, typename CentralityMap, typename EdgeCentralityMap,
 
49
         typename IncomingMap, typename DistanceMap, typename DependencyMap, 
 
50
         typename PathCountMap, typename VertexIndexMap, typename WeightMap&gt;    
 
51
void 
 
52
brandes_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>
 
61
template&lt;typename Graph, typename CentralityMap&gt;
 
62
void 
 
63
relative_betweenness_centrality(const Graph&amp; g, CentralityMap centrality_map);
 
64
 
 
65
template&lt;typename Graph, typename CentralityMap&gt;
 
66
typename property_traits&lt;CentralityMap&gt;::value_type
 
67
central_point_dominance(const Graph&amp; g, CentralityMap centrality_map);
 
68
    </pre>
 
69
 
 
70
<p>This algorithm&nbsp;[<a href="bibliography.html#brandes01">54</a>]
 
71
computes the <em>betweenness centrality</em>&nbsp;[<a
 
72
href="bibliography.html#freeman77">55</a>,<a
 
73
href="bibliography.html#anthonisse71">56</a>] of each vertex or each
 
74
edge in the graph. The betweenness centrality of a vertex <em>v</em>
 
75
is 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
 
80
vertex <em>s</em> to vertex <em>t</em> and <img src="figs/sigma_stv.gif">
 
81
is 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
 
87
betweenness centrality that was contributed to the target(s) of the
 
88
edge (plural for undirected graphs). Similar to (vertex) betweenness
 
89
centrality, edge betweenness centrality can be used to determine the
 
90
edges through which most shortest paths must pass. A single invocation
 
91
of this algorithm can compute either the vertex or edge centrality (or
 
92
both).</p>
 
93
 
 
94
<p>This algorithm can operate either on weighted graphs (if a suitable
 
95
edge weight map is supplied) or unweighted graphs (if no edge weight
 
96
map is supplied). The result is the absolute betweenness centrality;
 
97
to convert to the relative betweenness centrality, which scales each
 
98
absolute 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
 
101
betweenness centrality, one can compute the <em>central point
 
102
dominance</em>&nbsp;[<a href="bibliography.html#freeman77">55</a>], which is a measure of the maximum "betweenness" of any
 
103
point in the graph: it will be 0 for complete graphs and
 
104
1 for "wheel" graphs (in which there is a central vertex that all
 
105
paths 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>
 
129
IN: <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
    
 
141
UTIL: <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&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
 
 
158
UTIL: <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
 
 
181
UTIL: <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
 
 
201
UTIL: <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>
 
223
OUT/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
 
 
240
OUT/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
 
 
257
IN: <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>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
 
 
274
IN: <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> 
 
290
The 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
 
292
is <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="http://www.boost.org/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>,
 
301
Indiana University (<A
 
302
HREF="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>