Motif Detection Algorithm On Network Graph

Network motif is an induced connected subgraph which occurs more frequently in the original network than in the randomized network. This property reflects that this kind of subgraph plays a more important role in the input network than in arbitrary network. As the research on motif is becomes more and more, a faster motif detection algorithm is needed. Traditional motif detection includes subgraph census on input network and randomized network which cost a lot of computing time. Furthermore, during the census we need to handle the graph isomorphism problem which makes it worse. Nearly all of the current programs tackle the graph isomorphism using some canonical labeling algorithm, such as NAUTY. In our research, we proposed a new motif detection algorithm targeted the condition when the size of motif is less or equal than6. To reduce the calling of NAUTY, we use a pretreatment phase to save all the subgraphs when the number of vertices is less or equal to5. When the number of vertices is6, we solve the problem using a graph reconstruction conjecture. We achieved a nearly30times speed-up on the less or equal to5case and nearly20times speed-up on the6vertices case. Moreover, we give a uniform random graph generating algorithm on motif detection, an interface to the external program and the paralleled algorithm on motif detection. All the versions of our parallel motif detection program NetMODE can be accessed from http://netmode.sf.net.