Betweenness Centrality

// 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);

Brandes_betweenness_centrality()функция вычисляет центральность между вершинами и краями в графе. Способ вычисления между ними центральности вO(V)пространства обусловлен Брандесом[Brandes01]. Алгоритм сам по себе является модификацией алгоритма Брандеса.[Эдмондс09].

Contents

Where Defined

<boost/graph/distributed/betweenness_centrality.hpp>

Также доступны из

<boost/graph/betweenness_centrality.hpp>

Parameters

IN: const Graph& g

The graph type must be a model of Distributed Graph. The graph type must also model the Incidence Graph concept. 0-weighted edges in g will result in undefined behavior.

IN: CentralityMap centrality

A centrality map may be supplied to the algorithm, if not supplied a dummy_property_map will be used and no vertex centrality information will be recorded. The CentralityMap type must be a Distributed Property Map. The key type must be the graph's vertex descriptor type.

Default: A dummy_property_map.

IN: EdgeCentralityMap edge_centrality_map

An edge centrality map may be supplied to the algorithm, if not supplied a dummy_property_map will be used and no edge centrality information will be recorded. The EdgeCentralityMap type must be a Distributed Property Map. The key type must be the graph's vertex descriptor type.

Default: A dummy_property_map.

IN: IncomingMap incoming

The incoming map contains the incoming edges to a vertex that are part of shortest paths to that vertex. The IncomingMap type must be a Distributed Property Map. Its key type and value type must both be the graph's vertex descriptor type.

Default: An iterator_property_map created from a: std::vector of std::vector of the graph's vertex descriptor type.

IN: DistanceMap distance

The distance map records the distance to vertices during the shortest paths portion of the algorithm. The DistanceMap type must be a Distributed Property Map. Its key type must be the graph's vertex descriptor type.

Default: An iterator_property_map created from a: std::vector of the value type of the CentralityMap.

IN: DependencyMap dependency

The dependency map records the dependency of each vertex during the centrality calculation portion of the algorithm. The DependencyMap type must be a Distributed Property Map. Its key type must be the graph's vertex descriptor type.

Default: An iterator_property_map created from a: std::vector of the value type of the CentralityMap.

В:Карта маршрутаПуть_счет

Карта подсчета маршрутов записывает количество кратчайших маршрутов, по которым проходит каждая вершина во время расчетной части алгоритма.Карта маршрутадолжна бытьРаспределенная карта собственности. Его ключевым типом должен быть тип дескриптора вершины графа.

Default: An iterator_property_map created from a

std::vector of the graph's degree size type.

IN: VertexIndexMap vertex_index

A model of Readable Property Map whose key type is the vertex descriptor type of the graph g and whose value type is an integral type. The property map should map from vertices to their (local) indices in the range [0, num_vertices(g)).

Default: get(vertex_index, g)

IN: WeightMap weight_map

A model of Readable Property Map whose key type is the edge descriptor type of the graph g. If not supplied the betweenness centrality calculation will be unweighted.

IN: Buffer sources

A model of Buffer containing the starting vertices for the algorithm. If sources is empty a complete betweenness centrality calculation using all vertices in g will be performed. The value type of the Buffer must be the graph's vertex descriptor type.

Default: An empty boost::queue of int.

Complexity

Вычисление кратчайших путей, их подсчет и вычисление вклада в карту централизации составляетO(V log V). Вычисление точной центральной точки между вершинами требует подсчета кратчайших путей из всех вершин вг, таким образом, точная центральная точка между вершинами составляетO(V^2 log V).

Algorithm Description

Для вершин висточниках(или всех вершин вг, когдаисточниковпуст) алгоритм сначала вызывает настраиваемую реализациюdelta_stepping_shortest_paths, которая поддерживает дерево кратчайших путей с использованием.Входящая карта.Входящая картасодержит источник всех входящих краев на кратчайших путях.

IncomingMapопределяет кратчайший путь DAG у цели краев в дереве кратчайших путей. В двунаправленном случае краевые флаги могут использоваться для перевода информации о кратчайших путях к источнику краев. Установка краевых флагов во время вычисления кратчайшего пути вместо использованияВходящая картаприведет к добавлению фактораO(V)во внутреннюю петлю вычисления кратчайших путей, чтобы учесть необходимость очистки краевых флагов при обнаружении нового кратчайшего пути. Это увеличит сложность алгоритма. Асимптотически текущая реализация лучше, однако использование краевых флагов в двунаправленном случае уменьшит количество супершагов, требуемых глубиной кратчайших путей DAG для каждой вершины. В настоящее времяисходящаякарта явно построена путем простого изменения краев на входящей карте. После того, как карта, исходящая, построена, она проходит в порядке зависимости от источника вычисления кратчайших путей для вычисления числа путей. После вычисления числа путей самые короткие пути DAG снова проходят в порядке зависимости от источника, чтобы вычислить зависимость и центральность каждой вершины.

Алгоритм завершается, когда центральность вычисляется из всех вершин вг.

Bibliography

[Brandes01]

Ульрик Брандес. Быстрый алгоритм централизации. В Журнале математической социологии, том 25, номер 2, страницы 163-177, 2001.

[Edmonds09]

Ник Эдмондс, Торстен Хефлер и Эндрю Ламсдейн. Космически эффективный параллельный алгоритм для вычисления межпространственной центральности в разрозненных сетях. Технический отчет Университета Индианы. 2009.

Авторы: Ник Эдмондс и Эндрю Ламсдейн

Статья Parallel BGL Betweenness Centrality раздела может быть полезна для разработчиков на c++ и boost.

Parallel BGL Betweenness Centrality