local_node_connectivity

local_node_connectivity(G, source, target, cutoff=None)

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

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

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

Parameters:

GNetworkX图

source节点

节点连通性的起始节点

target节点

节点连通性的结束节点

cutoff整数

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

Returns:

k: 整数

成对节点连通性

See also

all_pairs_node_connectivity

node_connectivity

Notes

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

请注意，作者提出了一种进一步的细化方法，牺牲了准确性但提高了速度，目前尚未实现。

References

[1]

White, Douglas R., and Mark Newman. 2001 A Fast Algorithm for Node-Independent Paths. Santa Fe Institute Working Paper #01-07-035 http://eclectic.ss.uci.edu/~drwhite/working.pdf

Examples

>>> # 柏拉图正八面体图的节点连通性为4
>>> # 对于每个不相邻的节点对
>>> from networkx.algorithms import approximation as approx
>>> G = nx.octahedral_graph()
>>> approx.local_node_connectivity(G, 0, 5)
4