k_components¶

k_components
(G, flow_func=None)[source]¶ Returns the kcomponent structure of a graph G.
A \(k\)component is a maximal subgraph of a graph G that has, at least, node connectivity \(k\): we need to remove at least \(k\) nodes to break it into more components. \(k\)components have an inherent hierarchical structure because they are nested in terms of connectivity: a connected graph can contain several 2components, each of which can contain one or more 3components, and so forth.
Parameters:  G (NetworkX graph) –
 flow_func (function) – Function to perform the underlying flow computations. Default value
edmonds_karp()
. This function performs better in sparse graphs with right tailed degree distributions.shortest_augmenting_path()
will perform better in denser graphs.
Returns: k_components – Dictionary with all connectivity levels \(k\) in the input Graph as keys and a list of sets of nodes that form a kcomponent of level \(k\) as values.
Return type: Raises: NetworkXNotImplemented: – If the input graph is directed.
Examples
>>> # 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)
Notes
Moody and White [1] (appendix A) provide an algorithm for identifying kcomponents in a graph, which is based on Kanevsky’s algorithm [2] for finding all minimumsize node cutsets of a graph (implemented in
all_node_cuts()
function): Compute node connectivity, k, of the input graph G.
 Identify all kcutsets at the current level of connectivity using Kanevsky’s algorithm.
 Generate new graph components based on the removal of these cutsets. Nodes in a cutset belong to both sides of the induced cut.
 If the graph is neither complete nor trivial, return to 1; else end.
This implementation also uses some heuristics (see [3] for details) to speed up the computation.
See also
node_connectivity()
,all_node_cuts()
References
[1] Moody, J. and D. White (2003). Social cohesion and embeddedness: A hierarchical conception of social groups. American Sociological Review 68(1), 103–28. http://www2.asanet.org/journals/ASRFeb03MoodyWhite.pdf [2] Kanevsky, A. (1993). Finding all minimumsize separating vertex sets in a graph. Networks 23(6), 533–541. http://onlinelibrary.wiley.com/doi/10.1002/net.3230230604/abstract [3] Torrents, J. and F. Ferraro (2015). Structural Cohesion: Visualization and Heuristics for Fast Computation. http://arxiv.org/pdf/1503.04476v1