Extracting all the k-cores using networkx

Question

Using networkx library of python, it is possible to extract a k-core from a graph G. But is it possible to extract all the k-cores for a certain k? I want to do graph clustering and my idea is to extract k-cores for large values of k and define clusters like this.

Answer 1

The definition of k-core used in NetworkX does not require the k-core to be connected. http://networkx.lanl.gov/reference/generated/networkx.algorithms.core.k_core.html

So you will get all of the (possibly disconnected) k-cores in the graph.

Here is a simple example of a graph of 2 disjoint 3-node complete graphs:

In [1]: import networkx as nx

In [2]: G = nx.Graph([(1,2),(1,3),(2,3)])

In [3]: G.add_edges_from([(10,20),(10,30),(20,30)])

In [4]: nx.k_core(G,k=2).edges()
Out[4]: [(1, 2), (1, 3), (2, 3), (10, 20), (10, 30), (20, 30)]

If you want them as separate subgraphs you can find the connected components:

In [5]: graphs = nx.connected_component_subgraphs(nx.k_core(G,k=2))

In [6]: for g in graphs:
   ...:     print g.edges()
   ...:        
[(1, 2), (1, 3), (2, 3)]
[(10, 20), (10, 30), (20, 30)]