RAGE - A Rapid Graphlet Enumerator for Large Networks
Counting network graphlets (and motifs) was shown to have an important role in studying a wide range of complex networks. However, when the network size is large, as in the case of the Internet topology and WWW graphs, counting the number of graphlets becomes prohibitive for graphlets of size 4 and above. Devising efficient graphlet counting algorithms thus becomes an important goal. In this paper, the authors present efficient counting algorithms for 4-node graphlets. They show how to efficiently count the total number of each type of graphlet, and the number of graphlets adjacent to a node. They further present a new algorithm for node position-aware graphlet counting, namely partitioning the graphlet count by the node position in the graphlet.