k_components

k_components(G, min_density=0.95)

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

A k -组件是图G的最大子图，至少具有节点连通性。 k ：我们至少需要移除 k 将其分解为更多组件的节点。 k -组件具有固有的层次结构，因为它们是按连接嵌套的：一个连接的图可以包含几个2个组件，每个组件可以包含一个或多个3个组件，等等。

此实现基于快速启发式算法，以近似 k -图的分量结构 [1]. 其又基于用于寻找两个节点之间的节点独立路径的数目的良好下界的快速近似算法 [2].

参数

G网络X图表

无向图

min_density浮标

密度松弛阈值。默认值0.95

返回

k_componentsDICT

具有连接级别的词典 k 作为关键字和形成Level的k分量的节点集的列表 k 就像价值观一样。

加薪

NetworkXNotImplemented

如果G被指示。

参见

k_components

笔记

近似算法的逻辑用于计算 k -组件结构 [1] 是基于反复应用简单快速的算法 k -核心和双连接组件，以缩小我们必须在其上计算White和Newman的近似算法以寻找节点独立路径的结点对的数量 [2]. 更正式地说，该算法基于惠特尼定理，该定理陈述了任意图G的结点连通性、边连通性和最小度之间的包含关系。该定理意味着每个 k -组件嵌套在 k -edge-组件，而该组件又包含在 k -核心。因此，该算法计算每个双连接部分中的节点对之间的节点独立路径 k -core，并对每个 k 从3到输入图中节点的最大核数。

因为在实践中，很多节点都是层次的核心 k 在双成分中，实际上是k级分量的一部分，算法所需的辅助图可能非常密集。因此，我们使用补码图数据结构（参见 AntiGraph ）保存内存。反图形仅存储 not 出现在实际的辅助图中。当将算法应用于这个补码图数据结构时，它的行为就好像它是稠密的版本。

工具书类

1(1,2)

Torrents，J.和F.Ferraro（2015年），《结构凝聚力：快速计算的可视化和启发式方法》。https://arxiv.org/pdf/1503.04476v1

2(1,2)

White，Douglas R.和Mark Newman(2001)节点无关路径的快速算法。圣达菲研究所工作文件#01-07-035 https://www.santafe.edu/research/results/working-papers/fast-approximation-algorithms-for-finding-node-ind

3

穆迪，J.和D.怀特(2003)。社会凝聚力和嵌入性：社会群体的等级概念。《美国社会学评论》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)