123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307 |
- <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
- <html>
- <!--
- Copyright (c) 2004 Trustees of Indiana University
-
- Distributed under the Boost Software License, Version 1.0.
- (See accompanying file LICENSE_1_0.txt or copy at
- http://www.boost.org/LICENSE_1_0.txt)
- -->
- <head>
- <title>Boost Graph Library: Brandes' Betweenness Centrality</title>
- </head>
- <body>
- <IMG SRC="../../../boost.png"
- ALT="C++ Boost" width="277" height="86">
- <h1><img src="figs/python.gif" alt="(Python)"/><tt>brandes_betweenness_centrality</tt></h1>
- <p>
- <pre>
- <em>// named parameter versions</em>
- template<typename Graph, typename Param, typename Tag, typename Rest>
- void
- brandes_betweenness_centrality(const Graph& g,
- const bgl_named_params<Param,Tag,Rest>& params);
- template<typename Graph, typename CentralityMap>
- void
- brandes_betweenness_centrality(const Graph& g, CentralityMap centrality_map);
- template<typename Graph, typename CentralityMap, typename EdgeCentralityMap>
- void
- brandes_betweenness_centrality(const Graph& g, CentralityMap centrality_map,
- EdgeCentralityMap edge_centrality);
- <em>// non-named parameter versions</em>
- template<typename Graph, typename CentralityMap, typename EdgeCentralityMap,
- typename IncomingMap, typename DistanceMap, typename DependencyMap,
- typename PathCountMap, typename VertexIndexMap>
- void
- brandes_betweenness_centrality(const Graph& g, CentralityMap centrality_map,
- EdgeCentralityMap edge_centrality,
- IncomingMap incoming,
- DistanceMap distance, DependencyMap dependency,
- PathCountMap path_count,
- VertexIndexMap vertex_index);
- template<typename Graph, typename CentralityMap, typename EdgeCentralityMap,
- typename IncomingMap, typename DistanceMap, typename DependencyMap,
- typename PathCountMap, typename VertexIndexMap, typename WeightMap>
- void
- brandes_betweenness_centrality(const Graph& g, CentralityMap centrality_map,
- EdgeCentralityMap edge_centrality,
- IncomingMap incoming,
- DistanceMap distance, DependencyMap dependency,
- PathCountMap path_count,
- VertexIndexMap vertex_index,
- WeightMap weight_map);
- <em>// helper functions</em>
- template<typename Graph, typename CentralityMap>
- void
- relative_betweenness_centrality(const Graph& g, CentralityMap centrality_map);
- template<typename Graph, typename CentralityMap>
- typename property_traits<CentralityMap>::value_type
- central_point_dominance(const Graph& g, CentralityMap centrality_map);
- </pre>
- <p>This algorithm [<a href="bibliography.html#brandes01">54</a>]
- computes the <em>betweenness centrality</em> [<a
- href="bibliography.html#freeman77">55</a>,<a
- href="bibliography.html#anthonisse71">56</a>] of each vertex or each
- edge in the graph. The betweenness centrality of a vertex <em>v</em>
- is defined by
- <p><img src="figs/betweenness_centrality.gif">,
- <p>where <img src="figs/sigma_st.gif"> is the number of shortest paths from
- vertex <em>s</em> to vertex <em>t</em> and <img src="figs/sigma_stv.gif">
- is the number of shortest paths from vertex <em>s</em> to vertex
- <em>t</em> that pass through vertex <em>v</em>.
- <!-- \sum_{s \neq v \neq t}\frac{\sigma_{st}(v)}{\sigma_{st}} -->
- <p>The edge betweenness centrality indicates for each edge the
- betweenness centrality that was contributed to the target(s) of the
- edge (plural for undirected graphs). Similar to (vertex) betweenness
- centrality, edge betweenness centrality can be used to determine the
- edges through which most shortest paths must pass. A single invocation
- of this algorithm can compute either the vertex or edge centrality (or
- both).</p>
- <p>This algorithm can operate either on weighted graphs (if a suitable
- edge weight map is supplied) or unweighted graphs (if no edge weight
- map is supplied). The result is the absolute betweenness centrality;
- to convert to the relative betweenness centrality, which scales each
- absolute centrality by <img src="figs/rel_betweenness_centrality.gif">
- (where <em>n</em> is the number of vertices in the graph), use
- <tt>relative_betweenness_centrality</tt>. Given the relative
- betweenness centrality, one can compute the <em>central point
- dominance</em> [<a href="bibliography.html#freeman77">55</a>], which is a measure of the maximum "betweenness" of any
- point in the graph: it will be 0 for complete graphs and
- 1 for "wheel" graphs (in which there is a central vertex that all
- 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:
- <p><img src="figs/central_point_dominance.gif">
- <!-- C_B' = \frac{\sum_{v \in V} C_B(v^*) - C_B'(v)}{n-1} -->
- <p><a name="Fig1">
- <table border="1">
- <thead>
- <tr>
- <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>
- </tr>
- </thead>
- <tbody>
- <tr>
- <td align="center"><img src="figs/wheel_graph.gif"></td>
- </tr>
- </tbody>
- </table>
- <h3>Where Defined</h3>
- <a href="../../../boost/graph/betweenness_centrality.hpp"><tt>boost/graph/betweenness_centrality.hpp</tt></a>
- <h3>Parameters</h3>
- IN: <tt>const Graph& g</tt>
- <blockquote>
- The graph object on which the algorithm will be applied. The type
- <tt>Graph</tt> must be a model of <a
- href="VertexListGraph.html">Vertex List Graph</a> and <a
- href="IncidenceGraph.html">Incidence Graph</a>. When an edge
- centrality map is supplied, it must also model <a
- href="EdgeListGraph.html">Edge List Graph</a>.<br>
- <b>Python</b>: The parameter is named <tt>graph</tt>.
- </blockquote>
-
- UTIL: <tt>IncomingMap incoming</tt>
- <blockquote>
- 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
- href="../../property_map/doc/LvaluePropertyMap.html">Lvalue Property
- Map</a> whose key type is the same as the vertex descriptor type of
- the graph and whose value type is a Sequence (e.g., an
- <tt>std::vector</tt>) containing edge descriptors.<br>
- <b>Default:</b> <a
- href="../../property_map/doc/iterator_property_map.html">
- <tt>iterator_property_map</tt></a> created from a
- <tt>std::vector</tt> of <tt>std::vector<Edge></tt>, where
- <tt>Edge</tt> is the edge descriptor type of the graph.<br>
- <b>Python</b>: Unsupported parameter.
- </blockquote>
- UTIL: <tt>DistanceMap distance_map</tt>
- <blockquote>
- The shortest path weight from each source vertex <tt>s</tt> to each
- vertex in the graph <tt>g</tt> is recorded in this property map, but
- the result is only used internally. The type <tt>DistanceMap</tt>
- must be a model of <a
- href="../../property_map/doc/ReadWritePropertyMap.html">Read/Write
- Property Map</a>. The vertex descriptor type of the graph needs to
- be usable as the key type of the distance map. The value type of the
- distance map is the element type of a <a
- href="./Monoid.html">Monoid</a>.<br>
- <b>Default:</b> <a
- href="../../property_map/doc/iterator_property_map.html">
- <tt>iterator_property_map</tt></a> created from a
- <tt>std::vector</tt> of the <tt>WeightMap</tt>'s value type (or the
- <tt>vertices_size_type</tt> of the graph when no weight map exists)
- of size <tt>num_vertices(g)</tt> and using the <tt>vertex_index</tt> for
- the index map.<br>
- <b>Python</b>: Unsupported parameter.
- </blockquote>
- UTIL: <tt>DependencyMap dependency</tt>
- <blockquote>
- Property map used internally to accumulate partial betweenness
- centrality results. The type <tt>DependencyMap</tt> must be a model
- of <a href="../../property_map/doc/ReadWritePropertyMap.html">Read/Write
- Property Map</a>. The vertex descriptor type of the graph needs to
- be usable as the key type of the dependency map. The value type of
- the dependency map must be compatible with the value type of the
- centrality map.<br>
- <b>Default:</b> <a
- href="../../property_map/doc/iterator_property_map.html">
- <tt>iterator_property_map</tt></a> created from a
- <tt>std::vector</tt> of the <tt>CentralityMap</tt>'s value type of
- size <tt>num_vertices(g)</tt> and using the <tt>vertex_index</tt>
- for the index map.<br>
- <b>Python</b>: Unsupported parameter.
- </blockquote>
- UTIL: <tt>PathCountMap path_count</tt>
- <blockquote>
- Property map used internally to accumulate the number of paths that
- pass through each particular vertex. The type <tt>PathCountMap</tt>
- must be a model of <a
- href="../../property_map/doc/ReadWritePropertyMap.html">Read/Write
- Property Map</a>. The vertex descriptor type of the graph needs to
- be usable as the key type of the dependency map. The value type of
- the dependency map must be an integral type large enough to store
- the number of paths in the graph.<br>
- <b>Default:</b> <a
- href="../../property_map/doc/iterator_property_map.html">
- <tt>iterator_property_map</tt></a> created from a
- <tt>std::vector</tt> of the <tt>degree_size_type</tt> of the graph of
- size <tt>num_vertices(g)</tt> and using the <tt>vertex_index</tt>
- for the index map.<br>
- <b>Python</b>: Unsupported parameter.
- </blockquote>
- <h3>Named parameters</h3>
- OUT/UTIL: <tt>CentralityMap centrality_map</tt>
- <blockquote>
- This property map is used to accumulate the betweenness centrality
- of each vertex, and is the primary output of the algorithm. The type
- <tt>CentralityMap</tt> must be a model of <a
- href="../../property_map/doc/ReadWritePropertyMap.html">Read/Write
- Property Map</a>, with the graph's vertex descriptor type as its key
- type. The value type of this property map should be a floating-point
- or rational type.<br>
- <b>Default:</b> a <tt>dummy_property_map</tt>, which requires no
- work to compute and returns no answer.<br>
- <b>Python</b>: The color map must be a <tt>vertex_double_map</tt> for
- the graph.<br>
- <b>Python default</b>: <tt>graph.get_vertex_double_map("centrality")</tt>
- </blockquote>
- OUT/UTIL: <tt>EdgeCentralityMap edge_centrality_map</tt>
- <blockquote>
- This property map is used to accumulate the betweenness centrality
- of each edge, and is a secondary form of output for the
- algorithm. The type <tt>EdgeCentralityMap</tt> must be a model of <a
- href="../../property_map/doc/ReadWritePropertyMap.html">Read/Write
- Property Map</a>, with the graph's edge descriptor type as its key
- type. The value type of this property map should be the same as the
- value type of the <tt>CentralityMap</tt> property map.<br>
- <b>Default:</b> a <tt>dummy_property_map</tt>, which requires no
- work to compute and returns no answer.<br>
- <b>Python</b>: The color map must be a <tt>edge_double_map</tt> for
- the graph.<br>
- <b>Python default</b>: <tt>graph.get_edge_double_map("centrality")</tt>
- </blockquote>
- IN: <tt>vertex_index_map(VertexIndexMap vertex_index)</tt>
- <blockquote>
- This maps each vertex to an integer in the range <tt>[0,
- num_vertices(g))</tt>. This is necessary for efficient updates of the
- heap data structure when an edge is relaxed. The type
- <tt>VertexIndexMap</tt> must be a model of
- <a href="../../property_map/doc/ReadablePropertyMap.html">Readable Property Map</a>. The value type of the map must be an
- integer type. The vertex descriptor type of the graph needs to be
- usable as the key type of the map.<br>
- <b>Default:</b> <tt>get(vertex_index, g)</tt>.
- Note: if you use this default, make sure your graph has
- an internal <tt>vertex_index</tt> property. For example,
- <tt>adjacency_list</tt> with <tt>VertexList=listS</tt> does
- not have an internal <tt>vertex_index</tt> property.<br>
- <b>Python</b>: Unsupported parameter.
- </blockquote>
- IN: <tt>weight_map(WeightMap w_map)</tt>
- <blockquote>
- The weight or ``length'' of each edge in the graph. The weights
- must all be non-negative, and the algorithm will throw a
- <a href="./exception.html#negative_edge"><tt>negative_edge</tt></a>
- exception is one of the edges is negative.
- The type <tt>WeightMap</tt> must be a model of
- <a href="../../property_map/doc/ReadablePropertyMap.html">Readable Property Map</a>. The edge descriptor type of
- the graph needs to be usable as the key type for the weight
- map. The value type for this map must be
- the same as the value type of the distance map.<br>
- <b>Default:</b> All edge weights are assumed to be equivalent.
- <b>Python</b>: If supplied, must be an <tt>edge_double_map</tt> for the graph.
- </blockquote>
- <h3>Complexity</h3>
- The time complexity is <em>O(VE)</em> for unweighted graphs and
- <em>O(VE + V(V+E) log V)</em> for weighted graphs. The space complexity
- is <em>O(VE)</em>.
- <hr>
- <TABLE>
- <TR valign=top>
- <TD nowrap>Copyright © 2004</TD><TD>
- <A HREF="http://www.boost.org/people/doug_gregor.html">Douglas Gregor</A>, Indiana University (dgregor@cs.indiana.edu</A>)<br>
- <A HREF="https://homes.cs.washington.edu/~al75">Andrew Lumsdaine</A>,
- Indiana University (<A
- HREF="mailto:lums@osl.iu.edu">lums@osl.iu.edu</A>)
- </TD></TR></TABLE>
- <!-- Created: Fri Jun 4 16:42:50 EST 2004 -->
- <!-- hhmts start -->Last modified: Tue Mar 1 14:14:51 EST 2005 <!-- hhmts end -->
- </body>
- </html>
|