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
|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.|
|Appears in Collections:||CRACS - Articles in International Conferences|
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.