Accelerated Motif Detection Using Combinatorial Techniques

Abstract

Network motif algorithms have been a topic of research mainly after the 2002-seminal paper from Milo et al, that provided motifs as a way to uncover the basic building blocks of most networks. This article proposes new algorithms to exactly count isomorphic pattern motifs of size 3 and 4 in directed graphs. The algorithms are accelerated by combinatorial techniques. Let G(V, E) be a directed graph with m=|E|. We describe an O(m√m) time complexity algorithm to count isomorphic patterns of size 3. To counting isomorphic patterns of size 4, we propose an O(m <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> ) algorithm. The new algorithms were implemented and compared with Fanmod motif detection tool. The experiments show that our algorithms are expressively faster than Fanmod. We also let our tool to detect motifs, the ACC-MOTIF, available in the Internet.