Generate subgraphs of 'n' nodes

[Deepa]

Hi,
Is there any function in networkx to generate
all subgraphs with 'n'(integer) nodes from a large graph
thanx

[Deepa]

[Aric Hagberg]

There are probably going to be a lot of subgraphs. You can use
the subgraph() method to generate a single subgraph with a given set
of nodes. But you'll have to generate the node sets yourself.

Aric

[jason-n...@creativetrax.com]

You can use Sage (http://www.sagemath.org) to do this for networkx
graphs. One of the things that Sage does is wrap networkx graphs with
additional functionality. In fact, you can use Sage to filter the list
for only non-isomorphic subgraphs using NICE, an open-source
implementation of the algorithm in nauty.

You could do the following in Sage:

import networkx

# Get a networkx graph
g=networkx.random_lobster(10,0.3,0.05)

# Convert to a Sage graph
gg = Graph(g)

# Display the graph
show(gg)

# Count the number of combinations of 5 vertices out of the graph
Combinations(gg.vertices(), 5).count()

# Construct a subgraph dictionary. Each key is a canonical string label
for a subgraph.
# Each value is the subgraph. The set of values is the set of
non-isomorphic subgraphs
# with 5 vertices.
subgraphs = {}
for v in Combinations(gg.vertices(), 5):
s = gg.subgraph(v, inplace=False)
# Compute a canonical string for each subgraph
canonical_string = s.canonical_label().graph6_string()
subgraphs[canonical_string] = s

# Convert back to networkx graphs
networkx_subgraphs = [g.networkx_graph() for g in subgraphs.values()]

Thanks,

Jason

[Deepa Nair]

Hi,

Thanks so much I will try ur code
 

Deepa

[Pieter Swart]

Jason's code is the right approach, but generating the resulting
subgraphs as a list in the last line may kill you for a large graph.
Better would be to try and create an iterator that will spit out these
graphs.

I suggest creating a graph with integer nodes
(using the function convert_node_labels_to_integers(...) ),
and then adapt the Sage code using a generator expression in the last
line;
i.e. replacing the [ ... ] with ( ... ),
see http://www.python.org/dev/peps/pep-0289/

Once you have a long list of subgraphs, you can study
their statistics to identify which subgraphs are either extremely
unlikely or likely, given what you already know about them.
This forms the starting point of what is known as "network motif"
discovery in the bioinformatics literature, and there
has been much recent work.
Check out the work of Uri Alon
http://www.weizmann.ac.il/mcb/UriAlon/ as a starting point.

He wrote the reviews

http://www.weizmann.ac.il/mcb/UriAlon/Papers/Network_motifs_nature_genetics_review.pdf
http://www.weizmann.ac.il/mcb/UriAlon/Papers/networkMotifs/networkMotifs.pdf

This subject has now reached wikipedia maturity
http://en.wikipedia.org/wiki/Network_motif

WIth too many subgraphs you might want to perform sampling.

For exhaustive enumeration see

Journal of Computational Biology
Discovering Topological Motifs Using a Compact Notation
Laxmi Parida. Journal of Computational Biology.
April 1, 2007, 14(3): 300-323. doi:10.1089/cmb.2006.0142.

Amazing to see the patents filed under "network motif".


Pieter Swart

On May 5, 6:34 pm, "Deepa Nair" <deepanai...@gmail.com> wrote:
> Hi,
> Thanks so much I will try ur code
>
> Deepa
>

> On 5/6/08, jason-netwo...@creativetrax.com <jason-netwo...@creativetrax.com>

[Deepa Nair]

Hi,

Thanx Peter ..Iam currently going through the Uri Alon's web site..and you have identified my real problem ie I also try to find out motifs in undirected graphs..

 

Thanx again,

Deepa

 

[Deepa]

Hi,
I found out an efficient algorithm for enumerating subgraphs of
certain size (Ref: Sebastian Wernicke) and implemented it in python as
follows:


#### Function to enumerate subgraphs of size k for a graph g

def enumerate_subgraphs(g,k,realsub):
vext=[]
for i in g.nodes(): # For each vertex , make a list of its
neighbours
neib=g.neighbors(i)
for j in neib:
if j>i:
vext.append(j)
mytmp=[]
for v in vext:
mytmp.append(v)
while len(mytmp)>0: # For each node in the neighbor list call
extend_subgraph function
vext=[]
for v in mytmp:
vext.append(v)
extend_subgraph([i],vext,k,g,realsub)
if mytmp:
mytmp.pop(0)


#### Function to extend a subgraph

def extend_subgraph(vsub,vext1,k,g,realsub):
if len(vsub)==k-1:
for i in vext1:
lst=[]
for j in vsub:
lst.append(j)
lst.append(i)
realsub.append(lst)
return
while vext1:
ele=vext1.pop(0)
for n in g.neighbors(ele):
if nexclusive(g,n,vsub):
vext1.append(n)
vsub.append(ele)
extend_subgraph(vsub,vext1,k,g,realsub)

On May 7, 4:11 pm, Pieter Swart <pietersw...@comcast.net> wrote:
> Jason's code is the right approach, but generating the resulting
> subgraphs as a list in the last line may kill you for a large graph.
> Better would be to try and create an iterator that will spit out these
> graphs.
>
> I suggest creating a graph with integer nodes
> (using the function convert_node_labels_to_integers(...) ),
> and then adapt the Sage code using a generator expression in the last
> line;
> i.e. replacing the [ ... ] with ( ... ),

> seehttp://www.python.org/dev/peps/pep-0289/

>
> Once you have a long list of subgraphs, you can study
> their statistics to identify which subgraphs are either extremely
> unlikely or likely, given what you already know about them.
> This forms the starting point of what is known as "network motif"
> discovery in the bioinformatics literature, and there
> has been much recent work.

> Check out the work of Uri Alonhttp://www.weizmann.ac.il/mcb/UriAlon/as a starting point.
>
> He wrote the reviews
>
> http://www.weizmann.ac.il/mcb/UriAlon/Papers/Network_motifs_nature_ge...http://www.weizmann.ac.il/mcb/UriAlon/Papers/networkMotifs/networkMot...
>
> This subject has now reached wikipedia maturityhttp://en.wikipedia.org/wiki/Network_motif

>
> WIth too many subgraphs you might want to perform sampling.
>
> For exhaustive enumeration see
>
> Journal of Computational Biology
> Discovering Topological Motifs Using a Compact Notation
> Laxmi Parida. Journal of Computational Biology.
> April 1, 2007, 14(3): 300-323. doi:10.1089/cmb.2006.0142.
>
> Amazing to see the patents filed under "network motif".
>
> Pieter Swart
>

[Kanwal]

Hello

I want to generate all subgraphs of given size from a large network..

Can anybody help me

Thanks in advance

[Daniel Schult]

You could use itertools.combinations to get all the possible combinations of nodes of given size, then use NetworkX.Graph.subgraph() to get the "node induced" subgraph from those nodes.

import networkx as nx

import itertools

G=nx.complete_graph(8)

for SG in (G.subgraph(s) for s in itertools.combinations(G, 5)):

    print(SG.nodes(), SG.edges())

    # Other stuff...

--
You received this message because you are subscribed to the Google Groups "networkx-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to networkx-discuss+unsubscribe@googlegroups.com.
To post to this group, send email to networkx-discuss@googlegroups.com.
Visit this group at https://groups.google.com/group/networkx-discuss.
For more options, visit https://groups.google.com/d/optout.

[Attia Kanwal]

Many thanks for your reply..I need code in MATLAB..can you please help me in this regard??

[Mridul Seth]

Have a look at http://boguslawobara.blogspot.in/2015/05/python-and-networkx-in-matlab.html

To unsubscribe from this group and stop receiving emails from it, send an email to networkx-discu...@googlegroups.com.
To post to this group, send email to networkx...@googlegroups.com.

Visit this group at https://groups.google.com/group/networkx-discuss.
For more options, visit https://groups.google.com/d/optout.

--
You received this message because you are subscribed to the Google Groups "networkx-discuss" group.

To unsubscribe from this group and stop receiving emails from it, send an email to networkx-discu...@googlegroups.com.
To post to this group, send email to networkx...@googlegroups.com.

[Attia Kanwal]

Thanks for the email. But this code works on the properties of network..I want to extract subgraphs of given size from a large graph in MATLAB

To unsubscribe from this group and stop receiving emails from it, send an email to networkx-discuss+unsubscribe@googlegroups.com.
To post to this group, send email to networkx-discuss@googlegroups.com.

[Harshi]

Hello Deepa

Can you please clarify on the arguments given for both the functions? It would be really helpful. Thank you.