249 lines
16 KiB
HTML
249 lines
16 KiB
HTML
<?xml version="1.0" encoding="utf-8" ?>
|
|
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
|
|
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en">
|
|
<head>
|
|
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
|
|
<meta name="generator" content="Docutils 0.6: http://docutils.sourceforge.net/" />
|
|
<title>Parallel BGL Betweenness Centrality</title>
|
|
<link rel="stylesheet" href="../../../../rst.css" type="text/css" />
|
|
</head>
|
|
<body>
|
|
<div class="document" id="logo-betweenness-centrality">
|
|
<h1 class="title"><a class="reference external" href="http://www.osl.iu.edu/research/pbgl"><img align="middle" alt="Parallel BGL" class="align-middle" src="pbgl-logo.png" /></a> Betweenness Centrality</h1>
|
|
|
|
<!-- Copyright (C) 2004-2009 The Trustees of Indiana University.
|
|
Use, modification and distribution is subject to 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) -->
|
|
<pre class="literal-block">
|
|
// named parameter versions
|
|
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);
|
|
|
|
template<typename Graph, typename CentralityMap, typename EdgeCentralityMap>
|
|
void
|
|
brandes_betweenness_centrality(const Graph& g, CentralityMap centrality,
|
|
EdgeCentralityMap edge_centrality_map);
|
|
|
|
// non-named parameter versions
|
|
template<typename Graph, typename CentralityMap, typename EdgeCentralityMap,
|
|
typename IncomingMap, typename DistanceMap, typename DependencyMap,
|
|
typename PathCountMap, typename VertexIndexMap, typename Buffer>
|
|
void
|
|
brandes_betweenness_centrality(const Graph& g,
|
|
CentralityMap centrality,
|
|
EdgeCentralityMap edge_centrality_map,
|
|
IncomingMap incoming,
|
|
DistanceMap distance,
|
|
DependencyMap dependency,
|
|
PathCountMap path_count,
|
|
VertexIndexMap vertex_index,
|
|
Buffer sources,
|
|
typename property_traits<DistanceMap>::value_type delta);
|
|
|
|
template<typename Graph, typename CentralityMap, typename EdgeCentralityMap,
|
|
typename IncomingMap, typename DistanceMap, typename DependencyMap,
|
|
typename PathCountMap, typename VertexIndexMap, typename WeightMap,
|
|
typename Buffer>
|
|
void
|
|
brandes_betweenness_centrality(const Graph& g,
|
|
CentralityMap centrality,
|
|
EdgeCentralityMap edge_centrality_map,
|
|
IncomingMap incoming,
|
|
DistanceMap distance,
|
|
DependencyMap dependency,
|
|
PathCountMap path_count,
|
|
VertexIndexMap vertex_index,
|
|
Buffer sources,
|
|
typename property_traits<WeightMap>::value_type delta,
|
|
WeightMap weight_map);
|
|
|
|
// helper functions
|
|
template<typename Graph, typename CentralityMap>
|
|
typename property_traits<CentralityMap>::value_type
|
|
central_point_dominance(const Graph& g, CentralityMap centrality);
|
|
</pre>
|
|
<p>The <tt class="docutils literal"><span class="pre">brandes_betweenness_centrality()</span></tt> function computes the
|
|
betweenness centrality of the vertices and edges in a graph. The
|
|
method of calculating betweenness centrality in <em>O(V)</em> space is due to
|
|
Brandes <a class="citation-reference" href="#brandes01" id="id1">[Brandes01]</a>. The algorithm itself is a modification of
|
|
Brandes algorithm by Edmonds <a class="citation-reference" href="#edmonds09" id="id2">[Edmonds09]</a>.</p>
|
|
<div class="contents topic" id="contents">
|
|
<p class="topic-title first">Contents</p>
|
|
<ul class="simple">
|
|
<li><a class="reference internal" href="#where-defined" id="id3">Where Defined</a></li>
|
|
<li><a class="reference internal" href="#parameters" id="id4">Parameters</a></li>
|
|
<li><a class="reference internal" href="#complexity" id="id5">Complexity</a></li>
|
|
<li><a class="reference internal" href="#algorithm-description" id="id6">Algorithm Description</a></li>
|
|
<li><a class="reference internal" href="#bibliography" id="id7">Bibliography</a></li>
|
|
</ul>
|
|
</div>
|
|
<div class="section" id="where-defined">
|
|
<h1><a class="toc-backref" href="#id3">Where Defined</a></h1>
|
|
<p><<tt class="docutils literal"><span class="pre">boost/graph/distributed/betweenness_centrality.hpp</span></tt>></p>
|
|
<p>also accessible from</p>
|
|
<p><<tt class="docutils literal"><span class="pre">boost/graph/betweenness_centrality.hpp</span></tt>></p>
|
|
</div>
|
|
<div class="section" id="parameters">
|
|
<h1><a class="toc-backref" href="#id4">Parameters</a></h1>
|
|
<dl class="docutils">
|
|
<dt>IN: <tt class="docutils literal"><span class="pre">const</span> <span class="pre">Graph&</span> <span class="pre">g</span></tt></dt>
|
|
<dd>The graph type must be a model of <a class="reference external" href="DistributedGraph.html">Distributed Graph</a>. The graph
|
|
type must also model the <a class="reference external" href="http://www.boost.org/libs/graph/doc/IncidenceGraph.html">Incidence Graph</a> concept. 0-weighted
|
|
edges in <tt class="docutils literal"><span class="pre">g</span></tt> will result in undefined behavior.</dd>
|
|
<dt>IN: <tt class="docutils literal"><span class="pre">CentralityMap</span> <span class="pre">centrality</span></tt></dt>
|
|
<dd><p class="first">A centrality map may be supplied to the algorithm, if not supplied a
|
|
<tt class="docutils literal"><span class="pre">dummy_property_map</span></tt> will be used and no vertex centrality
|
|
information will be recorded. The <tt class="docutils literal"><span class="pre">CentralityMap</span></tt> type must be a
|
|
<a class="reference external" href="distributed_property_map.html">Distributed Property Map</a>. The key type must be the graph's
|
|
vertex descriptor type.</p>
|
|
<p class="last"><strong>Default</strong>: A <tt class="docutils literal"><span class="pre">dummy_property_map</span></tt>.</p>
|
|
</dd>
|
|
<dt>IN: <tt class="docutils literal"><span class="pre">EdgeCentralityMap</span> <span class="pre">edge_centrality_map</span></tt></dt>
|
|
<dd><p class="first">An edge centrality map may be supplied to the algorithm, if not
|
|
supplied a <tt class="docutils literal"><span class="pre">dummy_property_map</span></tt> will be used and no edge
|
|
centrality information will be recorded. The <tt class="docutils literal"><span class="pre">EdgeCentralityMap</span></tt>
|
|
type must be a <a class="reference external" href="distributed_property_map.html">Distributed Property Map</a>. The key type must be
|
|
the graph's vertex descriptor type.</p>
|
|
<p class="last"><strong>Default</strong>: A <tt class="docutils literal"><span class="pre">dummy_property_map</span></tt>.</p>
|
|
</dd>
|
|
<dt>IN: <tt class="docutils literal"><span class="pre">IncomingMap</span> <span class="pre">incoming</span></tt></dt>
|
|
<dd><p class="first">The incoming map contains the incoming edges to a vertex that are
|
|
part of shortest paths to that vertex. The <tt class="docutils literal"><span class="pre">IncomingMap</span></tt> type
|
|
must be a <a class="reference external" href="distributed_property_map.html">Distributed Property Map</a>. Its key type and value type
|
|
must both be the graph's vertex descriptor type.</p>
|
|
<dl class="last docutils">
|
|
<dt><strong>Default</strong>: An <tt class="docutils literal"><span class="pre">iterator_property_map</span></tt> created from a</dt>
|
|
<dd><tt class="docutils literal"><span class="pre">std::vector</span></tt> of <tt class="docutils literal"><span class="pre">std::vector</span></tt> of the graph's vertex
|
|
descriptor type.</dd>
|
|
</dl>
|
|
</dd>
|
|
<dt>IN: <tt class="docutils literal"><span class="pre">DistanceMap</span> <span class="pre">distance</span></tt></dt>
|
|
<dd><p class="first">The distance map records the distance to vertices during the
|
|
shortest paths portion of the algorithm. The <tt class="docutils literal"><span class="pre">DistanceMap</span></tt> type
|
|
must be a <a class="reference external" href="distributed_property_map.html">Distributed Property Map</a>. Its key type must be the
|
|
graph's vertex descriptor type.</p>
|
|
<dl class="last docutils">
|
|
<dt><strong>Default</strong>: An <tt class="docutils literal"><span class="pre">iterator_property_map</span></tt> created from a</dt>
|
|
<dd><tt class="docutils literal"><span class="pre">std::vector</span></tt> of the value type of the <tt class="docutils literal"><span class="pre">CentralityMap</span></tt>.</dd>
|
|
</dl>
|
|
</dd>
|
|
<dt>IN: <tt class="docutils literal"><span class="pre">DependencyMap</span> <span class="pre">dependency</span></tt></dt>
|
|
<dd><p class="first">The dependency map records the dependency of each vertex during the
|
|
centrality calculation portion of the algorithm. The
|
|
<tt class="docutils literal"><span class="pre">DependencyMap</span></tt> type must be a <a class="reference external" href="distributed_property_map.html">Distributed Property Map</a>. Its
|
|
key type must be the graph's vertex descriptor type.</p>
|
|
<dl class="last docutils">
|
|
<dt><strong>Default</strong>: An <tt class="docutils literal"><span class="pre">iterator_property_map</span></tt> created from a</dt>
|
|
<dd><tt class="docutils literal"><span class="pre">std::vector</span></tt> of the value type of the <tt class="docutils literal"><span class="pre">CentralityMap</span></tt>.</dd>
|
|
</dl>
|
|
</dd>
|
|
</dl>
|
|
<p>IN: <tt class="docutils literal"><span class="pre">PathCountMap</span> <span class="pre">path_count</span></tt></p>
|
|
<blockquote>
|
|
<p>The path count map records the number of shortest paths each vertex
|
|
is on during the centrality calculation portion of the algorithm.
|
|
The <tt class="docutils literal"><span class="pre">PathCountMap</span></tt> type must be a <a class="reference external" href="distributed_property_map.html">Distributed Property Map</a>.
|
|
Its key type must be the graph's vertex descriptor type.</p>
|
|
<dl class="docutils">
|
|
<dt><strong>Default</strong>: An <tt class="docutils literal"><span class="pre">iterator_property_map</span></tt> created from a</dt>
|
|
<dd><tt class="docutils literal"><span class="pre">std::vector</span></tt> of the graph's degree size type.</dd>
|
|
</dl>
|
|
</blockquote>
|
|
<dl class="docutils">
|
|
<dt>IN: <tt class="docutils literal"><span class="pre">VertexIndexMap</span> <span class="pre">vertex_index</span></tt></dt>
|
|
<dd><p class="first">A model of <a class="reference external" href="http://www.boost.org/libs/property_map/ReadablePropertyMap.html">Readable Property Map</a> whose key type is the vertex
|
|
descriptor type of the graph <tt class="docutils literal"><span class="pre">g</span></tt> and whose value type is an
|
|
integral type. The property map should map from vertices to their
|
|
(local) indices in the range <em>[0, num_vertices(g))</em>.</p>
|
|
<p class="last"><strong>Default</strong>: <tt class="docutils literal"><span class="pre">get(vertex_index,</span> <span class="pre">g)</span></tt></p>
|
|
</dd>
|
|
<dt>IN: <tt class="docutils literal"><span class="pre">WeightMap</span> <span class="pre">weight_map</span></tt></dt>
|
|
<dd>A model of <a class="reference external" href="http://www.boost.org/libs/property_map/ReadablePropertyMap.html">Readable Property Map</a> whose key type is the edge
|
|
descriptor type of the graph <tt class="docutils literal"><span class="pre">g</span></tt>. If not supplied the betweenness
|
|
centrality calculation will be unweighted.</dd>
|
|
<dt>IN: <tt class="docutils literal"><span class="pre">Buffer</span> <span class="pre">sources</span></tt></dt>
|
|
<dd><p class="first">A model of <a class="reference external" href="http://www.boost.org/libs/graph/doc/Buffer.html">Buffer</a> containing the starting vertices for the
|
|
algorithm. If <tt class="docutils literal"><span class="pre">sources</span></tt> is empty a complete betweenness
|
|
centrality calculation using all vertices in <tt class="docutils literal"><span class="pre">g</span></tt> will be
|
|
performed. The value type of the Buffer must be the graph's vertex
|
|
descriptor type.</p>
|
|
<p class="last"><strong>Default</strong>: An empty <tt class="docutils literal"><span class="pre">boost::queue</span></tt> of int.</p>
|
|
</dd>
|
|
</dl>
|
|
</div>
|
|
<div class="section" id="complexity">
|
|
<h1><a class="toc-backref" href="#id5">Complexity</a></h1>
|
|
<p>Computing the shortest paths, counting them, and computing the
|
|
contribution to the centrality map is <em>O(V log V)</em>. Calculating exact
|
|
betweenness centrality requires counting the shortest paths from all
|
|
vertices in <tt class="docutils literal"><span class="pre">g</span></tt>, thus exact betweenness centrality is <em>O(V^2 log
|
|
V)</em>.</p>
|
|
</div>
|
|
<div class="section" id="algorithm-description">
|
|
<h1><a class="toc-backref" href="#id6">Algorithm Description</a></h1>
|
|
<p>For the vertices in <tt class="docutils literal"><span class="pre">sources</span></tt> (or all vertices in <tt class="docutils literal"><span class="pre">g</span></tt> when
|
|
<tt class="docutils literal"><span class="pre">sources</span></tt> is empty) the algorithm first calls a customized
|
|
implementation of <a class="reference external" href="dijkstra_shortest_paths.html">delta_stepping_shortest_paths</a> which maintains a
|
|
shortest path tree using an <tt class="docutils literal"><span class="pre">IncomingMap</span></tt>. The <tt class="docutils literal"><span class="pre">IncomingMap</span></tt>
|
|
contains the source of all incoming edges on shortest paths.</p>
|
|
<p>The <tt class="docutils literal"><span class="pre">IncomingMap</span></tt> defines the shortest path DAG at the target of the
|
|
edges in the shortest paths tree. In the bidirectional case edge
|
|
flags could be used to translate the shortest paths information to the
|
|
source of the edges. Setting edge flags during the shortest path
|
|
computation rather than using an <tt class="docutils literal"><span class="pre">IncomingMap</span></tt> would result in
|
|
adding an <em>O(V)</em> factor to the inner loop of the shortest paths
|
|
computation to account for having to clear edge flags when a new
|
|
shortest path is found. This would increase the complexity of the
|
|
algorithm. Asymptotically, the current implementation is better,
|
|
however using edge flags in the bidirectional case would reduce the
|
|
number of supersteps required by the depth of the shortest paths DAG
|
|
for each vertex. Currently an <tt class="docutils literal"><span class="pre">outgoing</span></tt> map is explicitly
|
|
constructed by simply reversing the edges in the incoming map. Once
|
|
the <tt class="docutils literal"><span class="pre">outgoing</span></tt> map is constructed it is traversed in dependency
|
|
order from the source of the shortest paths calculation in order to
|
|
compute path counts. Once path counts are computed the shortest paths
|
|
DAG is again traversed in dependency order from the source to
|
|
calculate the dependency and centrality of each vertex.</p>
|
|
<p>The algorithm is complete when the centrality has been computed from
|
|
all vertices in <tt class="docutils literal"><span class="pre">g</span></tt>.</p>
|
|
</div>
|
|
<div class="section" id="bibliography">
|
|
<h1><a class="toc-backref" href="#id7">Bibliography</a></h1>
|
|
<table class="docutils citation" frame="void" id="brandes01" rules="none">
|
|
<colgroup><col class="label" /><col /></colgroup>
|
|
<tbody valign="top">
|
|
<tr><td class="label"><a class="fn-backref" href="#id1">[Brandes01]</a></td><td>Ulrik Brandes. A Faster Algorithm for Betweenness
|
|
Centrality. In the Journal of Mathematical Sociology, volume 25
|
|
number 2, pages 163--177, 2001.</td></tr>
|
|
</tbody>
|
|
</table>
|
|
<table class="docutils citation" frame="void" id="edmonds09" rules="none">
|
|
<colgroup><col class="label" /><col /></colgroup>
|
|
<tbody valign="top">
|
|
<tr><td class="label"><a class="fn-backref" href="#id2">[Edmonds09]</a></td><td>Nick Edmonds, Torsten Hoefler, and Andrew Lumsdaine.
|
|
A Space-Efficient Parallel Algorithm for Computing Betweenness
|
|
Centrality in Sparse Networks. Indiana University tech report.
|
|
2009.</td></tr>
|
|
</tbody>
|
|
</table>
|
|
<hr class="docutils" />
|
|
<p>Copyright (C) 2009 The Trustees of Indiana University.</p>
|
|
<p>Authors: Nick Edmonds and Andrew Lumsdaine</p>
|
|
</div>
|
|
</div>
|
|
<div class="footer">
|
|
<hr class="footer" />
|
|
Generated on: 2009-05-31 00:21 UTC.
|
|
Generated by <a class="reference external" href="http://docutils.sourceforge.net/">Docutils</a> from <a class="reference external" href="http://docutils.sourceforge.net/rst.html">reStructuredText</a> source.
|
|
|
|
</div>
|
|
</body>
|
|
</html>
|