k_components#

k_components(G, flow_func=None)[源代码]#

返回图G的k分量结构。

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

参数
G网络X图表
flow_func功能

函数来执行基础流计算。缺省值 edmonds_karp() 。此函数在具有右尾度分布的稀疏图中执行得更好。 shortest_augmenting_path() 将在更密集的图形中执行得更好。

返回
k_componentsDICT

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

加薪
NetworkXNotImplemented

如果输入图是定向的。

参见

node_connectivity
all_node_cuts
biconnected_components

k=2时此函数的特殊情况

k_edge_components

类似于此函数，但使用边缘连接而不是节点连接

笔记

穆迪和怀特 [1] (附录A)提供了一种识别图中k-分量的算法，该算法基于Kanevsky的算法 [2] 用于查找图的所有最小大小的节点割集(在 all_node_cuts() 函数)：

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

  2. 使用Kanevsky的算法识别当前连接级别的所有k-cutset。

  3. 基于删除这些切割集生成新的图形组件。切割集中的节点属于诱导切割的两侧。

  4. 如果图既不完整也不琐碎，返回1；否则结束。

此实现还使用了一些试探法(请参见 [3] 有关详细信息)以加速计算。

工具书类

1

Moody，J.和D.White（2003年）。社会凝聚力与嵌入性：社会群体的等级观念。美国社会学评论68（1），103-28.http://ww2.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

实例

>>> # Petersen graph has 10 nodes and it is triconnected, thus all
>>> # nodes are in a single component on all three connectivity levels
>>> G = nx.petersen_graph()
>>> k_components = nx.k_components(G)