Parallel discovery of network motifs

• Tipo: Artigo em Revista Científica Internacional
• Data: 2012

Autores

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

Revista

Título: Journal of Parallel and Distributed Computing

Vol. 72

Páginas: 144-154

ISSN: 0743-7315

Editora: Elsevier

Indexação

ISI Web of Knowledge - 28 Citações

Scopus - 32 Citações

Classificação Científica

FOS: Ciências exactas e naturais > Ciências da computação e da informação

Outras Informações

ID Authenticus: 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.

Idioma: Inglês

Tipo (Avaliação Docente): Científica

Nº de páginas: 11