增量接近中心性

incremental_closeness_centrality(G, edge, prev_cc=None, insertion=True, wf_improved=True)

节点的增量接近中心性。

使用基于级别的作业过滤计算节点的接近中心性，如 Sariyuce 等人的论文《增量算法用于接近中心性》中所述。

基于级别的作业过滤会检测对接近中心性不必要的更新并将其过滤掉。

— 摘自《增量算法用于接近中心性》

定理 1：设 \(G = (V, E)\) 是一个图，u 和 v 是 V 中的两个顶点，且 E 中不存在边 (u, v)。设 \(G' = (V, E \cup uv)\) 则 \(cc[s] = cc'[s]\) 当且仅当 \(\left|dG(s, u) - dG(s, v)\right| \leq 1\)。

其中 \(dG(u, v)\) 表示图 G 中两个顶点 u 和 v 之间最短路径的长度，cc[s] 是顶点 s 在图 G 中的接近中心性，cc'[s] 是添加边 (u, v) 后顶点 s 在图 G 中的接近中心性。—

我们使用定理 1 来过滤添加或删除边时不必要的更新。当添加边 (u, v) 时，我们在添加边之前计算所有其他节点到 u 和到 v 的最短路径长度。当删除边时，我们在删除边之后计算最短路径长度。然后我们应用定理 1，对满足 \(\left|dG(s, u) - dG(s, v)\right| \leq 1\) 的节点使用之前计算的接近中心性。这仅适用于无向、无权图；不支持距离参数。

节点 u 的接近中心性 [1] 是从 u 到所有其他 n-1 个节点的最短路径距离之和的倒数。由于距离之和取决于图中的节点数量，接近中心性通过最小可能距离之和 n-1 进行归一化。

\[C(u) = \frac{n - 1}{\sum_{v=1}^{n-1} d(v, u)},\]

其中 d(v, u) 是 v 和 u 之间的最短路径距离，而 n 是图中的节点数量。

请注意，更高的接近中心性值表示更高的中心性。

参数：

G图

一个 NetworkX 图

edge元组

图中修改的边 (u, v)。

prev_cc字典

图中所有节点先前的接近中心性。

insertion布尔值，可选

如果为 True（默认），则边已插入；否则，已从图中删除。

wf_improved布尔值，可选（默认=True）

如果为 True，则按可达节点的分数进行缩放。这给出了 Wasserman 和 Faust 改进的公式。对于单个连通分量图，它与原始公式相同。

返回值：

nodes字典

以接近中心性作为值的节点字典。

另请参阅

betweenness_centrality, load_centrality, eigenvector_centrality

degree_centrality, closeness_centrality

注意

接近中心性被归一化为 (n-1)/(|G|-1)，其中 n 是图中包含该节点的连通部分的节点数。如果图不是完全连通的，此算法会分别计算每个连通部分的接近中心性。

参考文献

[1]

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

[2]

Sariyuce, A.E. ; Kaya, K. ; Saule, E. ; Catalyiirek, U.V. Incremental Algorithms for Closeness Centrality. 2013 IEEE International Conference on Big Data http://sariyuce.com/papers/bigdata13.pdf