incremental_closeness_centrality

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，cc中两个顶点u，v之间最短路径的长度 [s] 是V中顶点s的闭中心性，cc‘ [s] 是V中顶点s加上(u，v)边的闭中心性。--

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

贴近中心性 [1] 一个节点的 u 是最短路径距离之和的倒数 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图表

网络X图表

edge元组

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

prev_cc词典

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

insertion布尔值，可选

如果为True(默认)，则插入边，否则将从图形中删除该边。

wf_improved布尔值，可选(默认值=True)

如果为True，则按可访问的节点分数进行缩放。这给了瓦瑟曼和浮士德改进的公式。对于单分量图，它与原始公式相同。

返回

nodes词典

以贴近中心度为值的节点字典。

参见

betweenness_centrality, load_centrality, eigenvector_centrality

degree_centrality, closeness_centrality

笔记

接近中心性归一化为 (n-1)/(|G|-1) 在哪里？ n 是包含节点的图的连接部分中的节点数。如果图不是完全连通的，则该算法分别计算每个连通部分的闭中心度。

工具书类

1

弗里曼，L.C.，1979。网络的中心性：一、概念上的澄清。社交网络1,215-239。Https://doi.org/10.1016/0378-8733(78)90021-7

2

Sariyuce，A.E.；Kaya，K.；Saule，E.；Catalyiirek，U.V.《闭中心度增量算法》。2013年ieee大数据国际会议http://sariyuce.com/papers/bigdata13.pdf