 |
A Scalable Parallel Approach for Subgraph Census ComputationDavid Aparício, Pedro Paredes and Pedro Ribeiro2014 |
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 ass essed 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.
Keywords
Graph Mining; Subgraph Census; Parallelism; Multicores
Digital Object Identifier (DOI)
doi 10.1007/978-3-319-14313-2_17
Publication in PDF format
Software
Journal/Conference/Book
7th International Workshop on Multi-/Many-Core Computing SystemsReference (text)
David Aparício, Pedro Paredes and Pedro Ribeiro. A Scalable Parallel Approach for Subgraph Census Computation. Proceedings of the 7th International Workshop on Multi-/Many-Core Computing Systems (MuCoCos), pp. 194-205, Springer LNCS Vol. 8806, Porto, Portugal, August, 2014.
Bibtex
@inproceedings{ribeiro-MUCOCOS2014,
author = {David Aparício and Pedro Paredes and Pedro Ribeiro},
title = {A Scalable Parallel Approach for Subgraph Census Computation},
doi = {10.1007/978-3-319-14313-2_17},
booktitle = {7th International Workshop on Multi-/Many-Core Computing Systems},
pages = {194-205},
publisher = {Springer},
month = {August},
year = {2014}
}