5
$\begingroup$

If we create a random graph

Chop[LowerTriangularize[RandomReal[{-1, 1}, {10, 10}], -1], 0.6] /.0 -> \[Infinity] // MatrixForm
WeightedAdjacencyGraph[%]

enter image description here

How can we detect repeating patterns in larger graphs?

Particularly, patterns including a negative or positive parameter:

SetProperty[%, 
 EdgeStyle -> {x_ :> (PropertyValue[{%, x}, 
       EdgeWeight] /. {a_?Positive -> 
        Directive[Thickness[Abs@a/400000] , Opacity[.5], Green], 
       b_?Negative -> 
        Directive[Thickness[Abs@b/400000] , Opacity[.5], Red]})}]

enter image description here

The only thing that comes to mind is using the graph as an image and trying some pattern detection that way

Edit:

I'd like to find Patterns of an arbitrary amount of nodes, for example n = 3 nodes, such as:

enter image description here

and how many times it occurs in a large network such as:

enter image description here

Hopefully to see if there is any frequent structures

$\endgroup$
2
  • 3
    $\begingroup$ I do not understand what you mean by "pattern". Can you expand the question and explain it? $\endgroup$
    – Szabolcs
    Apr 14, 2021 at 14:41
  • $\begingroup$ Oops, sorry. Thanks @Szabolcs , I've updated the post to hopefully explain better $\endgroup$
    – Teabelly
    Apr 14, 2021 at 16:56

1 Answer 1

6
$\begingroup$

I'd like to find Patterns of an arbitrary amount of nodes, for example n = 3 nodes, such as:

These are called networks motifs. The usual reference is Milo et al, Network Motifs: Simple Building Blocks of Complex Networks.

IGraph/M has functionality for counting motifs.

Example:

Needs["IGraphM`"]

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

Count 3-motifs in g:

motifs = AssociationThread[
   IGData[{"AllDirectedGraphs", 3}],
   IGMotifs[g, 3]
   ];

Also count in a random graph with the same vertex and edge counts, and compare:

rg = RandomGraph[{VertexCount[g], EdgeCount[g]}, 
  DirectedEdges -> True]

rmotifs = AssociationThread[
   IGData[{"AllDirectedGraphs", 3}],
   IGMotifs[rg, 3]
   ];

(Note: if you are serious about this, you would want to use IGRewire on the original graph to create a randomized version with the same degrees. I just took a shortcut here.)

How many more times does each motif appear in the empirical network than the random one?

BarChart[
 Quiet@N[motifs/rmotifs],
 ChartLabels -> Automatic,
 LabelingSize -> 29, ImageSize -> 600, AspectRatio -> 1/2
 ]

enter image description here


If you also want to take the colour into account, there is no special functionality in IGraph/M yet (but could be implemented based on the underlying igraph library).

You can use IGVF2FindSubisomorphisms, which supports coloured graphs, to find edge-coloured patterns. Note that IGVF2FindSubisomorphisms looks for all subgraphs, not merely induced ones. You would have to filter induced ones yourself. IGLADFindSubisomorphisms can filter induced subgraphs efficiently, but it does not support edge colours (only vertex colours).

Please see the documentation for more information on all these functions.

$\endgroup$
3
  • $\begingroup$ Thanks! I get an error creating rmotifs , rg appears not to be defined. Could this be because I am not using mma12? $\endgroup$
    – Teabelly
    Apr 14, 2021 at 19:34
  • $\begingroup$ Also struggling to find the 11.0 version for Labellingsize $\endgroup$
    – Teabelly
    Apr 14, 2021 at 19:37
  • $\begingroup$ I'm struggling a little trying to implement IGVF2FindSubisomorphisms[]. It has parameters subgraph and graph. Do I test a predefined subgraph ~ motif on a large graph. Maybe I'm not navigating the documentation well, it seems a little thin. I get a result, if I use a random n=3 graph, of numbers. If you've any advice? (Thanks so much for all your help) $\endgroup$
    – Teabelly
    Apr 15, 2021 at 22:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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