Efficient Parallel Subgraph Counting Using G-Tries

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

Autores

Pedro Ribeiro (Autor) Outra; Silva, F (Autor) FCUP; Lopes, L (Autor) FCUP

Ata de Conferência Internacional

Título: Proceedings of the 2010 IEEE International Conference on Cluster Computing, Heraklion, Crete, Greece, 20-24 September, 2010

Páginas: 217-226

Indexação

Scopus - 20 Citações

COMPENDEX

Classificação Científica

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

CORDIS: Ciências Físicas > Ciência de computadores

Outras Informações

ID Authenticus: P-007-WCE

DOI: 10.1109/CLUSTER.2010.27

Abstract (EN): Finding and counting the occurrences of a collection of subgraphs within another larger network is a computationally hard problem, closely related to graph isomorphism. The subgraph count is by itself a very powerful characterization of a network and it is crucial for other important network measurements. G-tries are a specialized data-structure designed to store and search for subgraphs. By taking advantage of subgraph common substructure, g-tries can provide considerable speedups over previously used methods. In this paper we present a parallel algorithm based precisely on gtries that is able to efficiently find and count subgraphs. The algorithm relies on randomized receiver-initiated dynamic load balancing and is able to stop its computation at any given time, efficiently store its search position, divide what is left to compute in two halfs, and resume from where it left. We apply our algorithm to several representative real complex networks from various domains and examine its scalability. We obtain an almost linear speedup up to 128 processors, thus allowing us to reach previously unfeasible limits. We showcase the multidisciplinary potential of the algorithm by also applying it to network motif discovery. © 2010 IEEE.

Idioma: Inglês

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

Notas: ISBN-13: 978-1-4244-8373-0; Publisher: IEEE Computer Society; Subjects: graph theory, parallel algorithms, resource allocation, tree data structures.

Nº de páginas: 10