| <!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>adjacenty_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="http://www.osl.iu.edu/~lums">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> |