Ask Your Question

motifs and subgraphs

asked 2013-05-27 02:02:15 +0200

gvdr gravatar image

updated 2013-05-27 02:03:00 +0200

I'm counting the number of motifs (3-nodes isophormic class of connected subgraphs) in a random directed network. There are 13 of this. One is, for example S1={1 -> 2, 2 -> 3} and another one S2={1 -> 2, 2 -> 3, 1 -> 3}. They are two distinct motifs, and I wouldn't count a S1 when I actually find S2. The problem is that S1 is in S2, hence subgraph_search() finds a S1 in each S2 and all related functions inherit the problem (wrong counting, wrong iterator...).

Any idea how to resolve this issue? Similar things would happen for 4-nodes motifs and so on...

The code I used goes like:

import numpy
M1 = DiGraph(numpy.array([[0,1,0],[0,0,1],[0,0,0]])) #first motif
M5 = DiGraph(numpy.array([[0,1,1],[0,0,1],[0,0,0]])) #second motif
g = digraphs.RandomDirectedGNP(20,0.1) #a random network
l1 = []
for p in g.subgraph_search_iterator(M1): #search first motif
  l1.append(p) #make a list of its occurences
l5 = []
for p in g.subgraph_search_iterator(M5): #the same for the second motif
edit retag flag offensive close merge delete

1 Answer

Sort by ยป oldest newest most voted

answered 2013-05-27 02:37:07 +0200

vdelecroix gravatar image

First of all, you do not need numpy to initialize a graph. Simply write

M1 = DiGraph(matrix([[0,1,0],[0,0,1],[0,0,0]])) #first motif
M5 = DiGraph(matrix([[0,1,1],[0,0,1],[0,0,0]])) #second motif

Your question is documented in subgraph_search, subgraph_search_iterator and subgraph_search_count. You can access the documentation through

sage: G = DiGraph()
sage: G.subgraph_search?

There is an option induced which allows you to search only for induced subgraph and which is False by default.

sage: M5.subgraph_search_count(M1)
sage: M5.subgraph_search_count(M1,induced=True)
edit flag offensive delete link more


And be extra careful when you *COUNT* these patterns, for subgraph_search will return the same set of vertices several times ! For example : digraphs.Circuit(3).subgraph_search_count(digraphs.Circuit(3)) returns 3, and not one ! If you only want to count the number of copies of a graph H in G which have a different vertex set, then you should divide the result by H.automorphism_group().cardinality().

Nathann gravatar imageNathann ( 2013-05-27 05:40:01 +0200 )edit

(and you can also create your graphs like that : DiGraph([ (1,2), (2,3) ])

Nathann gravatar imageNathann ( 2013-05-27 05:40:46 +0200 )edit

Thanks, I use numpy as I have to do some matrices manipulation on the starting graph. But thanks for the reminder!

gvdr gravatar imagegvdr ( 2013-05-27 15:26:29 +0200 )edit

Yep, the induce option works! I overview that part (but take into account the automorphism group cardinality...). Thanks twice.

gvdr gravatar imagegvdr ( 2013-05-27 15:35:26 +0200 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools


Asked: 2013-05-27 02:02:15 +0200

Seen: 719 times

Last updated: May 27 '13