I am going to use two different methods for this part: GraphletLift and Kavosh.
For more information, I found there is another method that workes for counting motifs in large sparse graphs. Although we are working with dense graphs, not the sparse graphs, I thought maybe it would be useful for other cases to be mentioned here. The link related to this release is on the reference page.
GRAPHLETLIFT METHOD
Here, we search and count graphlets in real-world networks using the Random Walk Monte Carlo Methods.
Now, we will use our package named GraphletLift as a box that gives the network and returns the number of graphlets it can find.
So, for the beginning I need to explain some notions.
First, there is a sample of different types of graphlet that might be found in the given large network. Starting from 2 vertices to 4 vertices and you can see that each of them called by different name.
Second, when we are looking for the graphlets up to 4 nodes then we will get outputs from H1,..6 (4) graphs if any exist.
Third, there are a lot of datasets that you can use. But here I will use a biology dataset. The dataset that I am going to use is a category of Sparse network contains 453 nodes and 2K edges. The vertex types are substrates and the edges type are based on metabolic reactions. The format is the undirected graph and unweighted edges.
The name of the dataset is Celegans.
Now, let’s run this program and get some outputs:
The output[5] represents the graphlets up to 3 within 5K samples in the network “as-caida”.
The output[6] represents the graphlets up to 4 within 8K samples in the network “as-caida”.
The output[7] represents the graphlets up to 4 within 8K samples in network “bio-celegansneural”. This belongs to one of the biological networks.
KAVOSH METHOD
There is another method for finding k-size network motifs that is more memory efficient and less time-consuming.
This algorithm based on finding all k-size sub-graphs of a given graph regardless of a digraph or undirected graph.
Below, you can see the result of testing it on one of the datasets that we have:
There were a lot of different degree counting but the important information are mostly at the beginning and the end of the output.
In the beginning, you can see that it starts by knowing that we are looking for motifs size 2 (k =2) and we know that there are 24 nodes.
In the end, it shows us the total number of edges (2135) and nodes (297), maximum degree (129), the total number of subgraphs (2097), number of non-isomorphic classes (1.00), time used for the main graph (0.000610), and the total time (0.068196).
This is just some extra information about the algorithm.
Graphlet Decomposition Method
This method has a fast parallel parameterized graphlet decomposition library for large graphs.
For building this package you might need to go to the Github page download and install the package and follow the README.md guidance file.
After installation, you are able to get two different result based on the global counts and motif counts for each edge.
For Macro Motif Counts you will see this result:
For Micro Motif Counts you will see the following result:
Now, go ahead and hit the NEXT button for the next step!