pgr_betweennessCentrality

pgr_betweennessCentrality - Calculates the relative betweeness centrality using Brandes Algorithm

Boost 图内部

可用性

• Version 3.7.0

  • 新的 实验 函数：

    • pgr_betweennessCentrality

描述

The Brandes Algorithm takes advantage of the sparse graphs for evaluating the betweenness centrality score of all vertices.

Betweenness centrality measures the extent to which a vertex lies on the shortest paths between all other pairs of vertices. Vertices with a high betweenness centrality score may have considerable influence in a network by the virtue of their control over the shortest paths passing between them.

The removal of these vertices will affect the network by disrupting the it, as most of the shortest paths between vertices pass through them.

This implementation work for both directed and undirected graphs.

• Running time: \(\Theta(VE)\)

• Running space: \(\Theta(VE)\)

• Throws when there are no edges in the graph

签名

总结

pgr_betweennessCentrality(Edges SQL, [directed])

Returns set of (vid, centrality)

示例:

For a directed graph with edges \(\{1, 2, 3, 4\}\).

SELECT * FROM pgr_betweennessCentrality(
'SELECT id, source, target, cost, reverse_cost
FROM edges where id < 5'
) ORDER BY vid;
 vid | centrality
-----+------------
   5 |          0
   6 |        0.5
   7 |          0
  10 |       0.25
  15 |          0
(5 rows)

Explanation

• The betweenness centrality are between parenthesis.

• The leaf vertices have betweenness centrality \(0\).

• Betweenness centrality of vertex \(6\) is higher than of vertex \(10\).

  • Removing vertex \(6\) will create three graph components.

  • Removing vertex \(10\) will create two graph components.

参数

参数	类型	默认	描述
Edges SQL	TEXT		Edges SQL 如下所述。

可选参数

列	类型	默认	描述
directed	BOOLEAN	true	当 true 时，该图被视为有 有向 如果为 false ，则该图被视为 无向。

内部查询

Edges SQL

列	类型	默认	描述
source	ANY-INTEGER		边的第一个端点顶点的标识符。
target	ANY-INTEGER		边的第二个端点顶点的标识符。
cost	ANY-NUMERICAL		边(source, target)的权重
reverse_cost	ANY-NUMERICAL	-1	边(target, source)的权重 当为负时：边（ target, source ）不存在，因此它不是图的一部分。

其中：

ANY-INTEGER:

SMALLINT, INTEGER, BIGINT

ANY-NUMERICAL:

SMALLINT, INTEGER, BIGINT, REAL, FLOAT

结果列

列	类型	描述
vid	BIGINT	顶点的标识符。
centrality	FLOAT	Relative betweenness centrality score of the vertex (will be in range [0,1])

另请参阅

• Boost's betweenness_centrality

• 查询使用 示例数据 网络。

索引和表格

• Index

• Search Page