5
$\begingroup$

There is a function IGMotifs in package of IGraph/M. I have read it some times but fail to understand it.

SeedRandom[1]
g = RandomGraph[{5, 7}]

Mathematica graphics

IGMotifs[g, 3]

{Indeterminate,Indeterminate,5,3}

Or a disconnected graph

SeedRandom[2]
g = RandomGraph[{8, 7}]

Mathematica graphics

As the documentation, the IGTriadCensus serve this case.

To count non-connected size-3 subgraphs, use IGTriadCensus.

Then I get a result like

Mathematica graphics

Well,I have lose my directory totally..

$\endgroup$
2
$\begingroup$

The purpose of IGMotifs is to find graph motifs. Currently size-3 and size-4 motifs are supported, both directed and undirected. Usually, this function is used with directed graphs.

What are motifs?

Let us look at size-3 directed graphs. There are 16 of these if we do not count isomorphisms. They can be shown using

<<IGraphM`

Grid[Partition[IGData[{"AllDirectedGraphs", 3}], 4], Frame -> All]

The connectivity pattern of any 3 nodes in a directed graph will fall into one of these 16 categories. I.e., the subgraph induced by those three nodes will be isomorphic with one of the 16 3-vertex graphs above.

IGMotifs[g, 3] simply counts how many times each of these 16 patterns appear in a graph.

For example,

g = ExampleData[{"NetworkGraph", "MetabolicNetworkAeropyrumPernix"}];

DirectedGraphQ[g]
(* True *)

IGMotifs[g, 3]
(* {Indeterminate, Indeterminate, 3221, Indeterminate, 7399, 200, 3538, 0, 0, 219, 6, 0, 0, 0, 0, 0} *)

The counts are returned in the same order as the graphs in IGData[{"AllDirectedGraphs", 3}].

What are those Indeterminates there? The algorithm (RAND-ESU) used by igraph can only count weakly connected subgraphs. Notice that above subgraphs no. 1, 2 and 4 are not connected. Counts are not returned for these. Thus the 1st, 2nd and 4th elements will always be Indeterminate when counting directed 3-motifs.

In hindsight, using Missing[] would have been better than Indeterminate, but I do not think I will change this now to preserve compatibility.

If we want to count all 16 possible subgraphs, we can use IGTriadCensus.

IGTriadCensus[g]
(* <|"003" -> 18942639, "012" -> 524169, "102" -> 6889, 
 "021D" -> 3538, "021U" -> 3221, "021C" -> 7399, "111D" -> 200, 
 "111U" -> 219, "030T" -> 0, "030C" -> 0, "201" -> 6, "120D" -> 0, 
 "120U" -> 0, "120C" -> 0, "210" -> 0, "300" -> 0|> *)

This returns an association with same strange looking keys. These are "MAN labels" where MAN stands for Mutual, Asymmetric, None, i.e. bidirectional connection, unidirectional connection or no connection. 012 means that there are no bidirectional connections, 1 unidirectional one, and two unconnected pairs, i.e. this:

Mathematica graphics

This type of notation for size-3 directed graphs is sometimes used in sociology. I have no personal need for this notation. I am simply mirroring the approach of the original igraph in IGraph/M.

You can find out what label corresponds to what 3-vertex directed graph using

IGData["MANTriadLabels"]

enter image description here

You can get size-3 induced subgraph counts in the same format as IGMotifs returns them, but with the missing entries filled in, using:

Lookup[IGTriadCensus[g], Keys@IGData["MANTriadLabels"]]
(* {18942639, 524169, 3221, 6889, 7399, 200, 3538, 0, 0, 219, 6, 0, 0, 0, 0, 0} *)

The triad counts will sum up to the total number of triplets in the graph:

Total[%]
(* 19488280 *)

Binomial[VertexCount[g], 3]
(* 19488280 *)

If you want to learn more about the applications of motifs, take a look at Uri Alon's website, Milo et. al and check the example in the IGraph/M documentation.

People typically look at subgraphs that occur much more frequently in some type of network than they would in a random network with the same degree sequence. For example, in our network g the following size-4 subgraphs occur more than 3 times as often as expected:

pos = Position[
  N@IGMotifs[g, 4]/IGMotifs[IGRewire[g, 1000000], 4],
  x_?NumericQ /; x > 3
  ]
(* {{20}, {67}, {129}, {147}} *)

Extract[IGData[{"AllDirectedGraphs", 4}], pos]

Mathematica graphics

$\endgroup$
1
  • $\begingroup$ Thanks,I understand it eventually.. $\endgroup$ – yode Apr 30 '17 at 15:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.