TY - JOUR

T1 - NetMODE: network motif detection without nauty

AU - Li, Xin

AU - Stones, Douglas Stuart

AU - Wang, Haidong

AU - Deng, Hualiang

AU - Liu, Xiaoguang

AU - Wang, Gang

PY - 2012

Y1 - 2012

N2 - 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.

AB - 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.

U2 - 10.1371/journal.pone.0050093

DO - 10.1371/journal.pone.0050093

M3 - Article

VL - 7

JO - PLoS ONE

JF - PLoS ONE

SN - 1932-6203

IS - 12

M1 - e50093

ER -