So, finding motifs (patterns) in the network has some basic steps to get through:
1. Check for isomorphic in two different given graphs.
2. Count the number of small graphlets in a given large graph. (Find the pattern that occurred frequently)
3. Build a user-friendly system for it.
The first part
There is nauty (No AUTomorphisms, Yes?) that allows us to test graphs for isomorphism. There is Traces that somehow is the same as nauty but it can not work for some cases. And there is this dreadnaut program that can read graphs and execute the nauty or Traces.
With the tools above we could do the first step! We just need to create 2 sets of graphs and compare them together! I tried to take show you the work here by images and other stuff. 🙂
The second part
So, now it is time to start finding motifs (graphlets) in graphs. But, before that, I need to mention that traces is not able to handle directed graphs, so since for motifs we need directed graphs then we will go with nauty. Moreover, there are two nauty types; one sparse nauty and the other is dense nauty!
A dense graph is a graph in which the number of edges is close to the maximal number of edges.
A Sparse graph is a graph in which the number of edges is close to the minimal number of edges.
Furthermore, this is the part that the system starts searching and counting the patterns (motifs) in the given graph.
We will use two different methods for it. One that finds graphlets the other finds motifs.
GraphletLift: The Random Walk Monte Carlo is a very good method that we are using here for searching in networks for counting different graphlets.
Kavosh: This method focuses on finding k-size network motifs that is more memory efficient and less time-consuming.
The Third part
In this section, I build a website for users to go into and upload their .csv file of dataset and then click on the search bottom to see the result of the search in less than a secound.