k_components#

k_components(G, flow_func=None)[source]#

返回图 G 的 k-分量结构。

一个 k -分量是图 G 的一个极大子图，它至少具有节点连通性 k ：我们需要移除至少 k 个节点才能将其分解为更多分量。 k -分量具有固有的层次结构，因为它们在连通性方面是嵌套的：一个连通图可以包含几个 2-分量，每个 2-分量可以包含一个或多个 3-分量，依此类推。

Parameters:
GNetworkX 图
flow_func函数

执行底层流计算的函数。默认值为 edmonds_karp() 。该函数在具有右尾度分布的稀疏图中表现更好。shortest_augmenting_path() 在更密集的图中表现更好。

Returns:
k_components字典

字典，包含输入图中的所有连通性级别 k 作为键，以及形成该级别 k 的 k-分量的节点集合列表作为值。

Raises:
NetworkXNotImplemented

如果输入图是有向图。

See also

node_connectivity
all_node_cuts
biconnected_components

当 k=2 时的特殊情况

k_edge_components

类似于该函数，但使用边连通性而非节点连通性

Notes

Moody 和 White [R3e8a19d61280-1]_（附录 A）提供了一种识别图中的 k-分量的算法，该算法基于 Kanevsky 的算法 [2] 用于找到图的所有最小尺寸节点割集（在 all_node_cuts() 函数中实现）：

  1. 计算输入图 G 的节点连通性，k。

  2. 使用 Kanevsky 的算法识别当前连通性级别上的所有 k-割集。

  3. 基于移除这些割集生成新的图分量。割集中的节点属于所诱导割的两边。

  4. 如果图既不是完全图也不是平凡图，返回步骤 1；否则结束。

此实现还使用了一些启发式方法（详见 [3]）来加速计算。

References

[1]

Moody, J. 和 D. White (2003). 社会凝聚力和嵌入性：社会群体的分层概念。 美国社会学评论 68(1), 103–28. http://www2.asanet.org/journals/ASRFeb03MoodyWhite.pdf

[2]

Kanevsky, A. (1993). 在图中找到所有最小尺寸的分离顶点集。 网络 23(6), 533–541. http://onlinelibrary.wiley.com/doi/10.1002/net.3230230604/abstract

[3]

Torrents, J. 和 F. Ferraro (2015). 结构凝聚力：可视化和快速计算的启发式方法。 https://arxiv.org/pdf/1503.04476v1

Examples

>>> # Petersen 图有 10 个节点且是三连通的，因此所有节点在所有三个连通性级别上都在一个分量中
>>> G = nx.petersen_graph()
>>> k_components = nx.k_components(G)
On this page