local_node_connectivity

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

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

两个不同节点和非相邻节点之间的成对或本地节点连接是断开它们时必须删除的节点的最小数目（最小分离切割集）。根据Menger定理，这等于独立于节点的路径数（除了源和目标之外不共享任何节点的路径）。这就是我们在这个函数中计算的。

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

参数

G网络X图表

source结点

用于节点连接的起始节点

target结点

用于节点连接的结束节点

cutoff整数

要考虑的最大节点连接性。如果没有，则使用源或目标的最小程度作为分界点。缺省值为无。

返回

K：整数

成对节点连通性

参见

all_pairs_node_connectivity

node_connectivity

笔记

该算法 [1] 通过使用BFS计算两个节点之间的最短路径，将找到的路径中的节点标记为已用，然后搜索除标记为已用的节点之外的其他最短路径，直到不再存在路径，从而查找两个节点之间的独立于节点的路径。这并不准确，因为最短路径可以使用节点，如果路径较长，则这些节点可能属于两个不同的节点独立路径。因此，它只保证节点连通性的严格下限。

值得注意的是，作者提出了一个进一步的细化，失去了准确性和获得速度，但尚未实现。

工具书类

1(1,2)

怀特、道格拉斯·R.和马克·纽曼。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