Parallel discovery of network motifs

• Type: Article in International Scientific Journal
• Date: 2012

Authors

Pedro Ribeiro (Author) FCUP; Fernando Silva (Author) FCUP; Luis Lopes (Author) FCUP

Journal

Title: Journal of Parallel and Distributed Computing

Vol. 72

Pages: 144-154

ISSN: 0743-7315

Publisher: Elsevier

Indexing

ISI Web of Knowledge - 28 Citations

Scopus - 32 Citations

Scientific classification

FOS: Natural sciences > Computer and information sciences

Other information

Authenticus ID: P-002-DPT

DOI: 10.1016/j.jpdc.2011.08.007

Abstract (EN): 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.

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 11