Parallel Discovery of Network Motifs

Pedro Ribeiro, Fernando Silva and Luís Lopes

2012

Abstract

Many natural structures can be naturally represented by complex networks. Discovering network motifs, which are overrepresented patterns of inter-connections, is a computationally hard task related to graph isomorphism. Sequential methods are hindered by an exponential execution time growth when we increase the size of motifs and networks. In this article we study the opportunities for parallelism in existing methods and propose new parallel strategies that adapt and extend one of the most efficient serial methods known from the Fanmod tool. We propose both a master–worker strategy and one with distributed control, in which we employ a randomized receiver initiated methodology capable of providing dynamic load balancing during the whole computation process. Our strategies are capable of dealing both with exact and approximate network motif discovery. We implement and apply our algorithms to a set of representative networks and examine their scalability up to 128 processing cores. We obtain almost linear speedups, showcasing the efficiency of our proposed approach and are able to reach motif sizes that were not previously achievable using conventional serial algorithms.

Keywords

Parallel algorithms; Complex networks; Graph mining; Network motifs

Reference (text)

Pedro Ribeiro, Fernando Silva and Luís Lopes. Parallel Discovery of Network Motifs. In Journal of Parallel and Distributed Computing, Vol. 72(2), pp. 144-154, Elsevier, February, 2012.

Bibtex

@article{ribeiro-JPDC2012,
  author = {Pedro Ribeiro and  Fernando Silva and Luís Lopes},
  title = {Parallel Discovery of Network Motifs},
  doi = {10.1016/j.jpdc.2011.08.007},
  journal = {Journal of Parallel and Distributed Computing},
  volume = {72},
  issue = {2},
  pages = {144-154},
  publisher = {Elsevier},
  month = {February},
  year = {2012}
}