GT-Scanner
This webpage hosts a software tool that uses the g-trie data structure to enumerate subgraphs on large networks. The tool can be used to evaluate which subgraphs are network motifs and to perform graphlet comparison. This tool includes parallel implementations of g-trie based algorithms gtrieScanner and FaSE.
If you want to learn more about g-tries and related algorithms, please consult the following references:
References
- Pedro Ribeiro and Fernando M. A. Silva. G-Tries: a data structure for storing and finding subgraphs. In Data Mining and Knowledge Discovery, Vol. 28(2), pp. 337-377, Springer, March, 2014.
- David Aparício, Pedro Ribeiro and Fernando M. A. Silva. Extending the Applicability of Graphlets to Directed Networks. In IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB) (to appear).
- David Aparício, Pedro Ribeiro and Fernando M. A. Silva. Parallel Subgraph Counting for Multicore Architectures. In Proceedings of the 12th IEEE International Symposium on Parallel and Distributed Processing with Architectures (ISPA), pp. 34-41, IEEE, Milan, Italy, August, 2014.
- David Aparício, Pedro Paredes and Pedro Ribeiro. A Scalable Parallel Approach for Subgraph Census Computation. In Proceedings of the 7th International Workshop on Multi-/Many-Core Computing Systems (MuCoCos), pp. 194-205, Springer LNCS Vol. 8806, Porto, Portugal, August, 2014.
Building and Running GT-Scanner
After you download GT-Scanner you need to extract .zip file and build the executable using make. You should have the following:
- GTScanner: executable. Please check the provided README file for the complete list of command line arguments and a few examples on how to run the tool.
- examples: example network files.
- gtries: pre-created g-trie files for undirected subgraphs (up to size 8) and directed subgraphs (up to size 5). G-Tries that also contain orbit information have a "or_" prefix.
Example usage: GTScanner -s 3 -g examples/jazz.txt -m gtrie gtries/undir3.gt