A scalable parallel approach for subgraph census computation

David Aparicio, Pedro Paredes, Pedro Ribeiro

Research output: Chapter in Book/Report/Conference proceedingConference contribution

4 Scopus citations

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.

Original languageEnglish (US)
Title of host publicationEuro-Par 2014
Subtitle of host publicationParallel Processing Workshops - Euro-Par 2014 InternationalWorkshops, Revised Selected Papers
EditorsLuís Lopes
PublisherSpringer Verlag
Pages194-205
Number of pages12
ISBN (Electronic)9783319143125
DOIs
StatePublished - 2014
Externally publishedYes
EventInternational Workshop on Parallel Processing, Euro-Par 2014 - Porto, Portugal
Duration: Aug 25 2014Aug 26 2014

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume8806
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

ConferenceInternational Workshop on Parallel Processing, Euro-Par 2014
Country/TerritoryPortugal
CityPorto
Period8/25/148/26/14

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science

Keywords

  • Graph Mining
  • Multicores
  • Parallelism
  • Subgraph Census

Fingerprint

Dive into the research topics of 'A scalable parallel approach for subgraph census computation'. Together they form a unique fingerprint.

Cite this