How can I extract all possible induced subgraphs from a given graph with networkx

Question

I am wondering whether can I use networkx to extract all possible induced subgraphs (graphlets) with specific number of nodes in the subgraphs from an input large graph, or is there another package that can do the job? For example, if I have a large graph, which is illustrated in networkx adjacency list format,

graph G:

1 2 3 7
2 1 4
3 1 4 6 5
4 2 3 5
5 3 4 6
6 3 5 7
7 1 6

which will be look like

if I want to extract graphlet with 3 nodes the algorithm should return me

subgraph1:

1 2 3
2 1
3 1

[(1,2),(1,3)] subgraph2:

1 3 7
3 1
7 1

[(1,3),(1,7)] subgraph3:

3 4 5
4 3 5
5 3 4

[(3,4),(3,5),(4,5)]

subgraph4,subgraph5,subgraph6...

The following is the code of the question suggested by @Hooked. Let's say n=3

import itertools
target = nx.complete_graph(3)
for sub_nodes in itertools.combinations(g.nodes(),len(target.nodes())):
    subg = g.subgraph(sub_nodes)
    if nx.is_connected(subg):
        print subg.edges()

the the output will look like

[(1, 2), (1, 3)]
[(1, 2), (2, 4)]
[(1, 2), (1, 7)]
[(1, 3), (3, 4)]
[(1, 3), (3, 5)]
[(1, 3), (3, 6)]
[(1, 3), (1, 7)]
[(1, 7), (6, 7)]
[(2, 4), (3, 4)]
[(2, 4), (4, 5)]
[(3, 4), (3, 5), (4, 5)]
[(3, 4), (3, 6)]
[(3, 5), (3, 6), (5, 6)]
[(3, 6), (6, 7)]
[(4, 5), (5, 6)]
[(5, 6), (6, 7)]

Answer 1

This assumes you want all matching subgraphs of a given target which you'll have to define. The native way is to loop over all combinations of nodes, find those connected then check for an isomorphism. It's unclear if you want a network motif or a graphlet. In a graphlet all edges present in the original graph must be there - this would exclude 3-4-5 from your target. This method finds graphlets, to find motifs you'll have to check for each combination if there is an induced subgraph (and how many!).

import networkx as nx

g = nx.Graph()
g.add_edge(1,2);g.add_edge(1,3)
g.add_edge(1,7);g.add_edge(2,4)
g.add_edge(3,4);g.add_edge(3,5)
g.add_edge(3,6);g.add_edge(4,5)
g.add_edge(5,6);g.add_edge(6,7)

import itertools

target = nx.Graph()
target.add_edge(1,2)
target.add_edge(2,3)

for sub_nodes in itertools.combinations(g.nodes(),len(target.nodes())):
    subg = g.subgraph(sub_nodes)
    if nx.is_connected(subg) and nx.is_isomorphic(subg, target):
        print subg.edges()

For me, this gives the edge set matches of:

[(1, 2), (1, 3)]
[(1, 2), (2, 4)]
[(1, 2), (1, 7)]
[(1, 3), (3, 4)]
[(1, 3), (3, 5)]
[(1, 3), (3, 6)]
[(1, 3), (1, 7)]
[(1, 7), (6, 7)]
[(2, 4), (3, 4)]
[(2, 4), (4, 5)]
[(3, 4), (3, 6)]
[(3, 6), (6, 7)]
[(4, 5), (5, 6)]
[(5, 6), (6, 7)]

Your examples are listed in here.