Please use this identifier to cite or link to this item:
https://hdl.handle.net/10216/97578
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 |
URI: | https://hdl.handle.net/10216/97578 |
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 | Size | Format | |
---|---|---|---|---|
48138.pdf Restricted Access | Artigo | 457.16 kB | Adobe PDF | Request a copy from the Author(s) |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.