NetworkX -- Create new graph of all nodes that are a part of 4-node clique

Question

I have a network that I would like to bound by clique, but I haven't quite figured out how to do this correctly. I am able to do this same process using k-cores, but not sure what the right process for creating a graph with only cliques in it.

I was hoping if I show my process for find subgraphs using the k_core function, someone could help me alter my process to find subgraphs using the clique function.

To start, I create a graph, I'll use the karate club one:

In [1]: import networkx as nx

In [2]: g = nx.karate_club_graph()

Plot to graph in iPython:

In [3]: pylab inline
Populating the interactive namespace from numpy and matplotlib

In [4]: nx.draw(g)

Next, I find all edges that are within the 4-core (have 4 or more edges):

In [5]: g_4k_edges = nx.k_core(g, k=4).edges()

Add those edges to a new graph:

In [6]: g_4k = nx.Graph()
In [7]: g_4k.add_edges_from(g_4k_edges)

Plot the 4-core graph:

In [8]: nx.draw(g_4k)

Any idea on how to do this, but instead of using k-cores to bound the network, use cliques that have 4 or more vertices?

Answer 1

Here is one way to generate your subgraph using cliques.

import networkx as nx

g = nx.karate_club_graph()

Find all cliques of 4 or more nodes:

cliques = nx.find_cliques(g)
cliques4 = [clq for clq in cliques if len(clq) >= 4]

Create a subgraph of g from all sufficiently large cliques:

nodes = set(n for clq in cliques4 for n in clq)
h = g.subgraph(nodes)

Drop nodes of h which have degree less than 4:

deg = nx.degree(h)
nodes = [n for n in nodes if deg[n] >= 4]

The desired graph k is the subgraph of h with these nodes:

k = h.subgraph(nodes)

Here's an image of the desired graph:

nx.draw(k)