incremental_closeness_centrality#

incremental_closeness_centrality(G, edge, prev_cc=None, insertion=True, wf_improved=True)[source]#

节点增量的紧密中心性。

使用基于层次的工作过滤来计算节点的紧密中心性，如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] 是 V 中顶点 s 的紧密中心性，cc’[s] 是添加了 (u, v) 边后 V 中顶点 s 的紧密中心性。

— 我们使用定理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 是图中的节点数量。

注意，紧密中心性的值越高表示中心性越高。

Parameters:

G图: 一个 NetworkX 图
edge元组: 图中的修改边 (u, v)。
prev_cc字典: 图中所有节点的先前紧密中心性。
insertion布尔值, 可选: 如果为 True（默认），则边被插入，否则从图中删除。
wf_improved布尔值, 可选 (默认=True): 如果为 True，则按可达节点的比例进行缩放。这给出了 Wasserman 和 Faust 改进的公式。对于单个连通分量的图，它与原始公式相同。

Returns:

nodes字典: 节点字典，值为紧密中心性。