Motif Finding Algorithms: A Performance Comparison

Network motifs are subgraphs of a network that occur more frequently than expected, according to some reasonable null model. They represent building blocks of complex systems such as genetic interaction networks or social networks and may reveal intriguing typical but perhaps unexpected relationships between interacting entities. The identification of network motif is a time consuming task since it subsumes the subgraph matching problem. Several algorithms have been proposed in the literature. In this paper we aim to review the motif finding problem through a systematic comparison of state-of-the-art algorithms on both real and artificial networks of different sizes. We aim to provide readers a complete overview of the performance of the various tools. As far as we know, this is the most comprehensive experimental review of motif finding algorithms to date, with respect both to the number of compared tools and to the variety and size of networks used for the experiments.