acc-Motif: Accelerated Network Motif Detection

摘要

Network motif algorithms have been a topic of research mainly after the 2002-seminal paper from Milo et al. [1], which provided motifs as a way to uncover the basic building blocks of most networks. Motifs have been mainly applied in Bioinformatics, regarding gene regulation networks. Motif detection is based on induced subgraph counting. This paper proposes an algorithm to count subgraphs of size ${bf k+2}$ based on the set of induced subgraphs of size ${bf k}$ . The general technique was applied to detect 3, 4 and 5-sized motifs in directed graphs. Such algorithms have time complexity ${bf O(a(G)m)}$ , ${bf O(m^2)}$ and ${bf O(nm^2)}$ , respectively, where ${bf a(G)}$ is the arboricity of ${bf G(V,E)}$ . The computational experiments in public data sets show that the proposed technique was one order of magnitude faster than Kavosh an- FANMOD. When compared to ${bf hbox{NetMODE}}$ , ${bf hbox{acc-Motif}}$ had a slightly improved performance.