顶点和边的介数中心性

顶点和边的介数（大致）由通过顶点或边的测地线（最短路径）的数量定义。

用法

betweenness(
  graph,
  v = V(graph),
  directed = TRUE,
  weights = NULL,
  normalized = FALSE,
  cutoff = -1
)

edge_betweenness(
  graph,
  e = E(graph),
  directed = TRUE,
  weights = NULL,
  cutoff = -1
)

参数

graph

要分析的图。

v

将要计算顶点介数的顶点。

directed

逻辑值，指示在确定最短路径时是否应考虑有向路径。

weights

用于计算加权介数的可选正权重向量。如果图具有 weight 边属性，则默认情况下使用此属性。权重用于计算加权最短路径，因此它们被解释为距离。

normalized

逻辑标量，指示是否要标准化介数分数。如果为 TRUE，则结果分别按有向和无向图中的有序或无序顶点对的数量进行标准化。在无向图中，$$B^n=\frac{2B}{(n-1)(n-2)},$$ 其中 \(B^n\) 是标准化的介数，\(B\) 是原始介数，\(n\) 是图中的顶点数。请注意，即使在设置 cutoff 以限制考虑的最短路径长度时，也使用相同的标准化因子，即使彼此可达的顶点对的数量可能小于 \((n-1)(n-2)/2\)。

cutoff

计算介数时要考虑的最大最短路径长度。如果为负数，则没有此类限制。

e

将要计算边介数的边。

值

对于 betweenness()，这是一个数值向量，包含 v 中每个顶点的介数分数。

对于 edge_betweenness()，这是一个数值向量，包含 e 中每个边的边介数分数。

详细信息

顶点 v 的顶点介数定义为

$$\sum_{i\ne j, i\ne v, j\ne v} g_{ivj}/g_{ij}$$

边 e 的边介数定义为

$$\sum_{i\ne j} g_{iej}/g_{ij}.$$

betweenness() 计算顶点介数，edge_betweenness() 计算边介数。

这里 \(g_{ij}\) 是顶点 \(i\) 和 \(j\) 之间的最短路径的总数，而 \(g_{ivj}\) 是通过顶点 \(v\) 的那些最短路径的数量。

这两个函数都允许您仅考虑长度为 cutoff 或更小的路径；这可以在更大的图上运行，因为运行时间不是二次的（如果 cutoff 很小）。如果 cutoff 为负数（默认值），则该函数计算精确的介数分数。从 igraph 1.6.0 开始，cutoff 值为零将被字面意义地处理，即长度大于零的路径将被忽略。

对于介数的计算，使用了 Brandes 提出的类似算法（参见参考文献）。

注意

edge_betweenness() 可能会为具有多重边的图给出错误的值。

参考文献

Freeman, L.C. (1979). Centrality in Social Networks I: Conceptual Clarification. Social Networks, 1, 215-239. doi:10.1016/0378-8733(78)90021-7

Ulrik Brandes, A Faster Algorithm for Betweenness Centrality. Journal of Mathematical Sociology 25(2):163-177, 2001. doi:10.1080/0022250X.2001.9990249

参见

closeness(), degree(), harmonic_centrality()

中心性度量 alpha_centrality(), authority_score(), closeness(), diversity(), eigen_centrality(), harmonic_centrality(), hits_scores(), page_rank(), power_centrality(), spectrum(), strength(), subgraph_centrality()

作者

Gabor Csardi csardi.gabor@gmail.com

示例

g <- sample_gnp(10, 3 / 10)
betweenness(g)
#>  [1] 13 10  0  0  6  1  0  6  0  0
edge_betweenness(g)
#> [1] 15  5  9  4  2  3 12  7  7