Scalable Interactive Dynamic Graph Clustering on Multicore CPUs

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaperJournal articleResearchpeer-review

  • Mai Thai Son
  • Sihem Amer-Yahia, Universite Grenoble Alpes
  • ,
  • Ira Assent
  • Mathias Birk, Univ of Arhus
  • ,
  • Martin Storgaard Dieu
  • ,
  • Jon Jacobsen
  • ,
  • Jesper Kristensen

The structural graph clustering algorithm SCAN is a fundamental technique for managing and analyzing graph data. However, its high runtime remains a computational bottleneck, which limits its applicability. In this paper, we propose a novel interactive approach for tackling this problem on multicore CPUs. Our algorithm, called anySCAN, iteratively processes vertices in blocks. The acquired results are merged into an underlying cluster structure consisting of the so-called super-nodes for building clusters. During its runtime, anySCAN can be suspended for examining intermediate results and resumed for finding better results at arbitrary time points, making it an anytime algorithm which is capable of handling very large graphs in an interactive way and under arbitrary time constraints. Moreover, its block processing scheme allows the design of a scalable parallel algorithm on shared memory architectures such as multicore CPUs for speeding up the algorithm further at each iteration. Consequently, anySCAN uniquely is a both interactive and work-efficient parallel algorithm. We further introduce danySCAN an efficient bulk update scheme for anySCAN on dynamic graphs in which the clusters are updated in bulks and in a parallel interactive scheme. Experiments are conducted on very large real graph datasets for demonstrating the performance of anySCAN. They show its ability to acquire very good approximate results early, leading to orders of magnitude speedup compared to SCAN and its variants. Moreover, it scales very well with the number of threads when dealing with both static and dynamic graphs.

Original languageEnglish
Article number8340880
JournalIEEE Transactions on Knowledge and Data Engineering
Volume31
Issue7
Pages (from-to)1239-1252
Number of pages14
ISSN1041-4347
DOIs
Publication statusPublished - Jul 2019

    Research areas

  • anytime clustering, Approximation algorithms, Clustering algorithms, dynamic graphs, Electronic mail, Heuristic algorithms, multicore CPUs, Multicore processing, parallel algorithm, Parallel algorithms, Runtime, SCAN, Structural graph clustering, ALGORITHM

See relations at Aarhus University Citationformats

ID: 127675488