An optimal algorithm for counting network motifs

Network motifs are small connected sub-graphs occurring at significantly higher frequencies in a given graph compared with random graphs of similar degree distribution. Recently, network motifs have attracted attention as a tool to study networks microscopic details. The commonly used algorithm for counting small-scale motifs is the one developed by Milo et al. This algorithm is extremely costly in CPU time and actually cannot work on large networks, consisting of more than 100,000 edges on current CPUs. We here present a new optimal algorithm, based on network decomposition for counting K-size network motifs with constant memory costs and a CPU cost linear with the number of counted motifs. Our algorithm performs better than previous full enumeration algorithms in terms of running time. Moreover, it uses a constant amount of memory. It also outperforms sampling algorithms. Our algorithm permits the counting of three and four motif for large networks that consists of more than 500,000 nodes and 5,000,000 links. For large networks, it performs more than a thousand times faster than current algorithms.