k_components(G, min_density=0.95)
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.
This implementation is based on the fast heuristics to approximate the k-component structure of a graph . Which, in turn, it is based on a fast approximation algorithm for finding good lower bounds of the number of node independent paths between two nodes .
The logic of the approximation algorithm for computing the k-component structure is based on repeatedly applying simple and fast algorithms for k-cores and biconnected components in order to narrow down the number of pairs of nodes over which we have to compute White and Newman's approximation algorithm for finding node independent paths . More formally, this algorithm is based on Whitney's theorem, which states an inclusion relation among node connectivity, edge connectivity, and minimum degree for any graph G. This theorem implies that every k-component is nested inside a k-edge-component, which in turn, is contained in a k-core. Thus, this algorithm computes node independent paths among pairs of nodes in each biconnected part of each k-core, and repeats this procedure for each k from 3 to the maximal core number of a node in the input graph.
Because, in practice, many nodes of the core of level k inside a bicomponent actually are part of a component of level k, the auxiliary graph needed for the algorithm is likely to be very dense. Thus, we use a complement graph data structure (see :None:None:`AntiGraph`) to save memory. AntiGraph only stores information of the edges that are not present in the actual auxiliary graph. When applying algorithms to this complement graph data structure, it behaves as if it were the dense version.
Undirected graph
Density relaxation threshold. Default value 0.95
If G is directed.
Dictionary with connectivity level k as key and a list of sets of nodes that form a k-component of level k as values.
Returns the approximate k-component structure of a graph G.
>>> # Petersen graph has 10 nodes and it is triconnected, thus allSee :
... # 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)
The following pages refer to to this document either explicitly or contain code examples using this.
networkx.algorithms.approximation.kcomponents.k_components
Hover to see nodes names; edges to Self not shown, Caped at 50 nodes.
Using a canvas is more power efficient and can get hundred of nodes ; but does not allow hyperlinks; , arrows or text (beyond on hover)
SVG is more flexible but power hungry; and does not scale well to 50 + nodes.
All aboves nodes referred to, (or are referred from) current nodes; Edges from Self to other have been omitted (or all nodes would be connected to the central node "self" which is not useful). Nodes are colored by the library they belong to, and scaled with the number of references pointing them