ASKSAGE: Sage Q&A Forum - Individual question feedhttp://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Mon, 27 May 2013 08:35:26 -0500motifs and subgraphshttp://ask.sagemath.org/question/10157/motifs-and-subgraphs/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
l5.append(p)
Sun, 26 May 2013 19:02:15 -0500http://ask.sagemath.org/question/10157/motifs-and-subgraphs/Answer by vdelecroix for <p>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...).</p>
<p>Any idea how to resolve this issue? Similar things would happen for 4-nodes motifs and so on...</p>
<p>The code I used goes like:</p>
<pre><code>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
l5.append(p)
</code></pre>
http://ask.sagemath.org/question/10157/motifs-and-subgraphs/?answer=14976#post-id-14976First 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)
1
sage: M5.subgraph_search_count(M1,induced=True)
0Sun, 26 May 2013 19:37:07 -0500http://ask.sagemath.org/question/10157/motifs-and-subgraphs/?answer=14976#post-id-14976Comment by Nathann for <p>First of all, you do not need numpy to initialize a graph. Simply write</p>
<pre><code>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
</code></pre>
<p>Your question is documented in <code>subgraph_search</code>, <code>subgraph_search_iterator</code> and <code>subgraph_search_count</code>. You can access the documentation through</p>
<pre><code>sage: G = DiGraph()
sage: G.subgraph_search?
</code></pre>
<p>There is an option <code>induced</code> which allows you to search only for induced subgraph and which is <code>False</code> by default.</p>
<pre><code>sage: M5.subgraph_search_count(M1)
1
sage: M5.subgraph_search_count(M1,induced=True)
0
</code></pre>
http://ask.sagemath.org/question/10157/motifs-and-subgraphs/?comment=17640#post-id-17640And 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().Sun, 26 May 2013 22:40:01 -0500http://ask.sagemath.org/question/10157/motifs-and-subgraphs/?comment=17640#post-id-17640Comment by gvdr for <p>First of all, you do not need numpy to initialize a graph. Simply write</p>
<pre><code>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
</code></pre>
<p>Your question is documented in <code>subgraph_search</code>, <code>subgraph_search_iterator</code> and <code>subgraph_search_count</code>. You can access the documentation through</p>
<pre><code>sage: G = DiGraph()
sage: G.subgraph_search?
</code></pre>
<p>There is an option <code>induced</code> which allows you to search only for induced subgraph and which is <code>False</code> by default.</p>
<pre><code>sage: M5.subgraph_search_count(M1)
1
sage: M5.subgraph_search_count(M1,induced=True)
0
</code></pre>
http://ask.sagemath.org/question/10157/motifs-and-subgraphs/?comment=17636#post-id-17636Thanks, I use numpy as I have to do some matrices manipulation on the starting graph. But thanks for the reminder!Mon, 27 May 2013 08:26:29 -0500http://ask.sagemath.org/question/10157/motifs-and-subgraphs/?comment=17636#post-id-17636Comment by gvdr for <p>First of all, you do not need numpy to initialize a graph. Simply write</p>
<pre><code>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
</code></pre>
<p>Your question is documented in <code>subgraph_search</code>, <code>subgraph_search_iterator</code> and <code>subgraph_search_count</code>. You can access the documentation through</p>
<pre><code>sage: G = DiGraph()
sage: G.subgraph_search?
</code></pre>
<p>There is an option <code>induced</code> which allows you to search only for induced subgraph and which is <code>False</code> by default.</p>
<pre><code>sage: M5.subgraph_search_count(M1)
1
sage: M5.subgraph_search_count(M1,induced=True)
0
</code></pre>
http://ask.sagemath.org/question/10157/motifs-and-subgraphs/?comment=17635#post-id-17635Yep, the induce option works! I overview that part (but take into account the automorphism group cardinality...). Thanks twice.Mon, 27 May 2013 08:35:26 -0500http://ask.sagemath.org/question/10157/motifs-and-subgraphs/?comment=17635#post-id-17635Comment by Nathann for <p>First of all, you do not need numpy to initialize a graph. Simply write</p>
<pre><code>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
</code></pre>
<p>Your question is documented in <code>subgraph_search</code>, <code>subgraph_search_iterator</code> and <code>subgraph_search_count</code>. You can access the documentation through</p>
<pre><code>sage: G = DiGraph()
sage: G.subgraph_search?
</code></pre>
<p>There is an option <code>induced</code> which allows you to search only for induced subgraph and which is <code>False</code> by default.</p>
<pre><code>sage: M5.subgraph_search_count(M1)
1
sage: M5.subgraph_search_count(M1,induced=True)
0
</code></pre>
http://ask.sagemath.org/question/10157/motifs-and-subgraphs/?comment=17639#post-id-17639(and you can also create your graphs like that : DiGraph([ (1,2), (2,3) ])Sun, 26 May 2013 22:40:46 -0500http://ask.sagemath.org/question/10157/motifs-and-subgraphs/?comment=17639#post-id-17639