# Detecting patterns in a graph network

If we create a random graph

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


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]})}]


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:

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

Hopefully to see if there is any frequent structures

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

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]

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
]


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).

• Thanks! I get an error creating rmotifs , rg appears not to be defined. Could this be because I am not using mma12? Apr 14, 2021 at 19:34
• Also struggling to find the 11.0 version for Labellingsize Apr 14, 2021 at 19:37
• 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) Apr 15, 2021 at 22:58