A Scalable Parallel Approach for Subgraph Census Computation

• Type: Article in International Conference Proceedings Book
• Date: 2014

Authors

Aparicio, D (Author) Other; Paredes, P (Author) Other; Pedro Ribeiro (Author) FCUP

Conference proceedings International

Title: EURO-PAR 2014: PARALLEL PROCESSING WORKSHOPS, PT II

Pages: 194-205

20th Euro-Par International Workshops

Porto, PORTUGAL, AUG 25-26, 2014

Indexing

ISI Web of Knowledge - 6 Citations

Scopus - 5 Citations

Other information

Authenticus ID: P-00A-8W0

DOI: 10.1007/978-3-319-14313-2_17

Abstract (EN): 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.

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 12