Parallel subgraph counting for multicore architectures

David Aparício, Pedro Ribeiro and Fernando Silva

2014

Abstract

Computing the frequency of small subgraphs on a large network is a computationally hard task. This is, however, an important graph mining primitive, with several applications, and here we present a novel multicore parallel algorithm for this task. At the core of our methodology lies a state-of-the-art data structure, the g-trie, which represents a collection of subgraphs and allows for a very efficient sequential search. Our implementation was done using Pthreads and can run on any multicore personal computer. We employ a diagonal work sharing strategy to dynamically and effectively divide work among threads during the execution. We assess the performance of our Pthreads implementation on a set of representative networks from various domains and with diverse topological features. For most networks, we obtain a speedup of over 50 for 64 cores and an almost linear speedup up to 32 cores, showcasing the flexibility and scalability of our algorithm. This paves the way for the usage of such counting algorithms on larger subgraph and network sizes without the obligatory access to a cluster.

Keywords

Parallel Algorithms; Adaptive Load Balancing; Complex Networks; Graph Mining; G-Tries

Digital Object Identifier (DOI)

doi 10.1109/ISPA.2014.14

Publication in PDF format

pdf Download PDF

Software

software GT-Scanner

Journal/Conference/Book

12th IEEE International Symposium on Parallel and Distributed Processing with Applications

Reference (text)

David Aparício, Pedro Ribeiro and Fernando Silva. Parallel subgraph counting for multicore architectures. Proceedings of the 12th IEEE International Symposium on Parallel and Distributed Processing with Applications (ISPA), pp. 34-41, IEEE, Milan, Italy, August, 2014.

Bibtex

@inproceedings{ribeiro-ISPA2014,
  author = {David Aparício and  Pedro Ribeiro and Fernando Silva},
  title = {Parallel subgraph counting for multicore architectures},
  doi = {10.1109/ISPA.2014.14},
  booktitle = {12th IEEE International Symposium on Parallel and Distributed Processing with Applications},
  pages = {34-41},
  publisher = {IEEE},
  month = {August},
  year = {2014}
}