local_node_connectivity#

local_node_connectivity(G, source, target, cutoff=None)[来源]#

计算源节点和目标节点之间的节点连通性。

两个不同且不相邻节点之间的成对或局部节点连通性是必须移除以使它们断开连接的最小节点数（最小分离割集）。根据 Menger 定理，这等于节点独立路径（除了源节点和目标节点之外不共享任何节点的路径）的数量。这正是我们在本函数中计算的内容。

该算法是一种快速近似方法，它给出了两个节点之间实际节点独立路径数的严格下界 [1]。它适用于有向图和无向图。

参数：
GNetworkX 图
source节点

节点连通性的起始节点

target节点

节点连通性的结束节点

cutoff整数

考虑的最大节点连通性。如果为 None，则使用源节点或目标节点的最小度数作为截止值。默认值为 None。

返回：
k: 整数

成对节点连通性

另请参阅

all_pairs_node_connectivity
node_connectivity

注意

该算法 [1] 通过使用 BFS 计算最短路径，将找到的路径上的节点标记为“已使用”，然后搜索排除已标记为已使用节点的其他最短路径，直到不再存在路径，从而找到两个节点之间的节点独立路径。它不精确，因为最短路径可能使用那些如果路径更长则可能属于两个不同节点独立路径的节点。因此，它仅保证节点连通性的严格下界。

请注意，作者提出了进一步的改进，以牺牲精度为代价换取速度提升，但这尚未实现。

参考文献

[1] (1,2)

White, Douglas R., and Mark Newman. 2001 节点独立路径的快速算法。圣达菲研究所工作论文 #01-07-035 http://eclectic.ss.uci.edu/~drwhite/working.pdf

示例

>>> # Platonic octahedral graph has node connectivity 4
>>> # for each non adjacent node pair
>>> from networkx.algorithms import approximation as approx
>>> G = nx.octahedral_graph()
>>> approx.local_node_connectivity(G, 0, 5)
4
在本页上