NetMODE: network motif detection without nauty

Xin Li, Douglas Stuart Stones, Haidong Wang, Hualiang Deng, Xiaoguang Liu, Gang Wang

Research output: Contribution to journalArticleResearchpeer-review

28 Citations (Scopus)

Abstract

A motif in a network is a connected graph that occurs significantly more frequently as an induced subgraph than would be expected in a similar randomized network. By virtue of being atypical, it is thought that motifs might play a more important role than arbitrary subgraphs. Recently, a flurry of advances in the study of network motifs has created demand for faster computational means for identifying motifs in increasingly larger networks. Motif detection is typically performed by enumerating subgraphs in an input network and in an ensemble of comparison networks; this poses a significant computational problem. Classifying the subgraphs encountered, for instance, is typically performed using a graph canonical labeling package, such as Nauty, and will typically be called billions of times. In this article, we describe an implementation of a network motif detection package, which we call NetMODE. NetMODE can only perform motif detection for k-node subgraphs when k≤6, but does so without the use of Nauty. To avoid using Nauty, NetMODE has an initial pretreatment phase, where k-node graph data is stored in memory (k≤5). For k=6 we take a novel approach, which relates to the Reconstruction Conjecture for directed graphs. We find that NetMODE can perform up to around 30 times faster than its predecessors when k≤5 and up to around 20 times faster when k=6 (the exact improvement varies considerably). NetMODE also (a) includes a method for generating comparison graphs uniformly at random, (b) can interface with external packages (e.g. R), and (c) can utilize multi-core architectures. NetMODE is available from netmode.sf.net.
Original languageEnglish
Article numbere50093
Number of pages9
JournalPLoS ONE
Volume7
Issue number12
DOIs
Publication statusPublished - 2012

Cite this