Skip to main content
`Ctrl`+`K`

# k_components

k_components(G, flow_func=None)

  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 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 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 dict

      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 level `k` as values.

  Raises:
    NetworkXNotImplemented

      If the input graph is directed.

  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

  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):

  > 1. Compute node connectivity, k, of the input graph G.

  > 2. Identify all k-cutsets at the current level of connectivity using Kanevsky’s algorithm.

  > 3. Generate new graph components based on the removal of these cutsets. Nodes in a cutset belong to both sides of the induced cut.

  > 4. 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.

  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

  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)