k_components#

k_components(G, min_density=0.95)[source]#

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

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

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

参数：
GNetworkX 图

无向图

min_density浮点数

密度松弛阈值。默认值 0.95

返回：
k_componentsdict

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

抛出：
NetworkXNotImplemented

如果 G 是有向图。

另请参阅

k_components

注意

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

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

参考文献

[1] (1,2)

Torrents, J. and F. Ferraro (2015) Structural Cohesion: Visualization and Heuristics for Fast Computation. https://arxiv.org/pdf/1503.04476v1

[2] (1,2)

White, Douglas R., and Mark Newman (2001) A Fast Algorithm for Node-Independent Paths. Santa Fe Institute Working Paper #01-07-035 https://www.santafe.edu/research/results/working-papers/fast-approximation-algorithms-for-finding-node-ind

[3]

Moody, J. and D. White (2003). Social cohesion and embeddedness: A hierarchical conception of social groups. American Sociological Review 68(1), 103–28. https://doi.org/10.2307/3088904

示例

>>> # Petersen graph has 10 nodes and it is triconnected, thus all
>>> # nodes are in a single component on all three connectivity levels
>>> from networkx.algorithms import approximation as apxa
>>> G = nx.petersen_graph()
>>> k_components = apxa.k_components(G)
在本页