A Parallel Algorithm for Counting Subgraphs in Complex Networks

• Tipo: Artigo em Livro de Atas de Conferência Internacional
• Data: 2011

Autores

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

Ata de Conferência Internacional

Título: Communications in Computer and Information Science

Páginas: 380-393

3rd International Joint Conference on Biomedical Engineering Systems and Technologies

Valencia, SPAIN, JAN 20-23, 2010

Indexação

ISI Web of Knowledge - 3 Citações

Scopus - 5 Citações

Classificação Científica

FOS: Ciências da engenharia e tecnologias > Biotecnologia ambiental

Outras Informações

ID Authenticus: P-002-Y3R

DOI: 10.1007/978-3-642-18472-7_30

Abstract (EN): Many natural and artificial structures can be represented as complex networks. Computing the frequency of all subgraphs of a certain size can give a very comprehensive structural characterization of these networks. This is known as the subgraph census problem, and it is also important as an intermediate step in the computation of other features of the network, such as network motifs. The subgraph census problem is computationally hard and most associated algorithms for it are sequential. Here we present several increasingly efficient parallel strategies for, culminating in a scalable and adaptive parallel algorithm. We applied our strategies to a representative set of biological networks and achieved almost linear speedups up to 128 processors, paving the way for making it possible to compute the census for bigger networks and larger subgraph sizes.

Idioma: Inglês

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

Nº de páginas: 14