RAGE - RApid Graphlet Enumeration

RAGE - graphlet enumeration algorithm

Introduction

The page describes a tool to enumerate graphlets in large undirected graphs. The tool outputs the results both in CSV and in WEKA's arff format. The algorithms for this tool are described in:

Dror Marcus and Yuval Shavitt.
RAGE - A Rapid Graphlet Enumerator for Large Networks.
Computer Networks (COMNET, Elsevier), to appear.
Dror Marcus and Yuval Shavitt.
Efficient Counting of Network Motifs.
The 2nd Annual Workshop on Simplifying Complex Networks for Practitioners (SIMPLEX 2010), Genoa, Italy, June 2010. (pdf)

Software and Usage

RAGE executable is available for download here. Currently only a Windows executable exist, work is done to create a unix executable. The source for this software is openly available on this web page, and should be easily converted for unix.

Running RAGE

To run RAGE from the command line use: RAGE [file-name]

where [file-name] is an input graph in the form of a text file containing the graphs edge-list (e.g. sample graph). The output will be located in the "Result" folder created after the run.

An additional optional file with known node classes can be added to the run graph by adding a file with the name "NodeTypesList.txt" to RAGE executable folder (e.g. sample known set). The file should be in the form of lines consisting of [NODE_ID] [long name (no space)] [classification_ID].
E.g:
1 tel_aviv_univ EDU
2 jerusalem_univ EDU
3 at&t LTP
...

RAGE's Output

The output of RAGE will appear under the folder "Results" and will come in the form of: *.CSV (comma seperated vector) and *.arff (WEKA)
Rage graphlets id's follow the same convention of Uri Alon's motif dictionary (pdf). Since the above convention does not contain reference to the node position, we modified to ids as follows:

ID: 78_0 Three node path, node with degree 1
ID: 78,1 Three node path, node with degree 2
ID: 238_0 Triangle
ID: 4698_0 Four node Path, node with degree 2
ID: 4698_1 Four node Path, node with degree 1
ID: 13260_0 Cycle
ID: 4958_0 Tailed Triangle, node with degree 3
ID: 4958_1 Tailed Triangle, node with degree 2
ID: 4958_2 Tailed Triangle, node with degree 1
ID: 13278_0 Chordal Cycle, node with degree 3 (node touching the chord).
ID: 13278_1 Chordal Cycle, node with degree 2 (node not touching the chord).
ID: 4382_0 Four Node Star (or Claw) node with degree 3
ID: 4382_1 Four Node Star (or Claw) node with degree 1
ID: 31710_0 Clique

Source Code

Source code is located here and is free under the the revised BSD license.

Other papers on Motifs and Graphlets

See link