k_components

k_components(G, min_density=0.95)

返回图 G 的近似 k-连通分量结构。

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

此实现基于快速启发式算法来近似图的 k -连通分量结构 [1]。该算法又基于一种快速近似算法，用于找到两个节点之间节点独立路径数量的良好下界 [2]。

Parameters:

GNetworkX 图

无向图

min_density浮点数

密度松弛阈值。默认值为 0.95

Returns:

k_components字典

以连通性级别 k 为键，值为形成 k -连通分量的节点集合列表的字典。

Raises:

NetworkXNotImplemented

如果 G 是有向图。

See also

k_components

Notes

计算 k -连通分量结构的近似算法 [1] 的逻辑基于反复应用简单且快速的 k -核和双连通分量算法，以缩小我们必须计算 White 和 Newman 的节点独立路径近似算法的节点对数 [2]。更正式地说，该算法基于 Whitney 定理，该定理指出任何图 G 的节点连通性、边连通性和最小度之间存在包含关系。该定理意味着每个 k -连通分量都嵌套在一个 k -边连通分量中，而该 k -边连通分量又包含在一个 k -核中。因此，该算法在每个 k -核的每个双连通部分中的节点对之间计算节点独立路径，并从 3 到输入图中节点的最大核数重复此过程。

因为在实践中，双连通分量中级别 k 的核心的许多节点实际上是级别 k 的连通分量的一部分，算法所需的辅助图很可能是非常密集的。因此，我们使用补图数据结构（见 AntiGraph ）来节省内存。AntiGraph 仅存储实际辅助图中不存在的边的信息。当将算法应用于这种补图数据结构时，它的行为就像它是密集版本一样。

References

[1]

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

[2]

White, Douglas R., 和 Mark Newman (2001) 一种快速节点独立路径算法。 Santa Fe Institute 工作论文 #01-07-035 https://www.santafe.edu/research/results/working-papers/fast-approximation-algorithms-for-finding-node-ind

[3]

Moody, J. 和 D. White (2003)。社会凝聚力和嵌入性：社会群体的层次概念。 美国社会学评论 68(1), 103–28. https://doi.org/10.2307/3088904

Examples

>>> # Petersen 图有 10 个节点且是三连通的，因此所有节点在所有三个连通性级别上都在一个连通分量中
>>> from networkx.algorithms import approximation as apxa
>>> G = nx.petersen_graph()
>>> k_components = apxa.k_components(G)