networkx.algorithms.connectivity.kcomponents.k_components¶
-
k_components
(G, flow_func=None)[source]¶ Returns the k-component structure of a graph G.
A
k
-component is a maximal subgraph of a graph G that has, at least, node connectivityk
: we need to remove at leastk
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 2-components, each of which can contain one or more 3-components, 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 k-component of levelk
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 k-components in a graph, which is based on Kanevsky’s algorithm 2 for finding all minimum-size node cut-sets of a graph (implemented in
all_node_cuts()
function):Compute node connectivity, k, of the input graph G.
Identify all k-cutsets 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()
biconnected_components()
special case of this function when k=2
k_edge_components()
similar to this function, but uses edge-connectivity instead of node-connectivity
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 minimum-size 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. https://arxiv.org/pdf/1503.04476v1