Please use this identifier to cite or link to this item:
Author(s): Pedro Ribeiro
Silva, F
Lopes, L
Title: Efficient Parallel Subgraph Counting Using G-Tries
Issue Date: 2010
Abstract: 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. (c) 2010 IEEE.
Subject: Ciência de computadores, Ciências da computação e da informação
Computer science, Computer and information sciences
Scientific areas: Ciências exactas e naturais::Ciências da computação e da informação
Natural sciences::Computer and information sciences
Source: Proceedings of the 2010 IEEE International Conference on Cluster Computing, Heraklion, Crete, Greece, 20-24 September, 2010
Document Type: Artigo em Livro de Atas de Conferência Internacional
Rights: restrictedAccess
Appears in Collections:FCUP - Artigo em Livro de Atas de Conferência Internacional

Files in This Item:
File Description SizeFormat 
  Restricted Access
Artigo457.16 kBAdobe PDF    Request a copy from the Author(s)

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.