Please use this identifier to cite or link to this item:
Title: A Scalable Parallel Approach for Subgraph Census Computation
Authors: David Oliveira Aparício
Pedro Reis Paredes
Pedro Manuel Ribeiro
Issue Date: 2014
Abstract: Counting the occurrences of small subgraphs in large networks is a fundamental graph mining metric with several possible applications. Computing frequencies of those subgraphs is also known as the subgraph census problem, which is a computationally hard task. In this paper we provide a parallel multicore algorithm for this purpose. At its core we use FaSE, an efficient network-centric sequential subgraph census algorithm, which is able to substantially decrease the number of isomorphism tests needed when compared to past approaches. We use one thread per core and employ a dynamic load balancing scheme capable of dealing with the highly unbalanced search tree induced by FaSE and effectively redistributing work during execution. We assessed the scalability of our algorithm on a varied set of representative networks and achieved near linear speedup up to 32 cores while obtaining a high efficiency for the total 64 cores of our machine.
metadata.dc.type: conferenceObject
Appears in Collections:CRACS - Articles in International Conferences

Files in This Item:
File Description SizeFormat 
P-00A-8W0.pdf230.62 kBAdobe PDFThumbnail

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