Strategies for Network Motifs Discovery

Pedro Ribeiro, Fernando Silva and Marcus Kaiser

2009

Abstract

Complex networks from domains like Biology or Sociology are present in many e-Science data sets. Dealing with networks can often form a workflow bottleneck as several related algorithms are computationally hard. One example is detecting characteristic patterns or "network motifs" - a problem involving subgraph mining and graph isomorphism. This paper provides a review and runtime comparison of current motif detection algorithms in the field. We present the strategies and the corresponding algorithms in pseudo-code yielding a framework for comparison. We categorize the algorithms outlining the main differences and advantages of each strategy. We finally implement all strategies in a common platform to allow a fair and objective efficiency comparison using a set of benchmark networks. We hope to inform the choice of strategy and critically discuss future improvements in motif detection.

Keywords

Network Motifs; Graph Mining; Algorithms; Complex Networks

Reference (text)

Pedro Ribeiro, Fernando Silva and Marcus Kaiser. Strategies for Network Motifs Discovery. Proceedings of the 5th IEEE International Conference on e-Science (ESCIENCE), pp. 80-87, IEEE CS Press, Oxford, UK, December, 2009.

Bibtex

@inproceedings{ribeiro-ESCIENCE2009,
  author = {Pedro Ribeiro and  Fernando Silva and Marcus Kaiser},
  title = {Strategies for Network Motifs Discovery},
  doi = {10.1109/e-Science.2009.20},
  booktitle = {5th IEEE International Conference on e-Science},
  pages = {80-87},
  publisher = {IEEE},
  month = {December},
  year = {2009}
}