Parallel clique-like subgraph counting and listing

Yi Yang, Da Yan, Shuigeng Zhou, Guimu Guo

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

2 Scopus citations


Cliques and clique-like subgraphs (e.g., quasi-cliques) are important dense structures whose counting or listing are essential in applications like complex network analysis and community detection. These problems are usually solved by divide and conquer, where a task over a big graph can be recursively divided into subtasks over smaller subgraphs whose search spaces are disjoint. This divisible algorithmic paradigm brings enormous potential for parallelism, since different subtasks can run concurrently to drastically reduce the overall running time. In this paper, we explore this potential by proposing a unified framework for counting and listing clique-like subgraphs. We study how to divide and distribute the counting and listing tasks, and meanwhile, to balance the assigned workloads of each thread dynamically. Four applications are studied under our parallel framework, i.e., triangle counting, clique counting, maximal clique listing and quasi-clique listing. Extensive experiments are conducted which demonstrate that our solution achieves an ideal speedup on various real graph datasets.

Original languageEnglish (US)
Title of host publicationConceptual Modeling - 38th International Conference, ER 2019, Proceedings
EditorsAlberto H.F. Laender, Barbara Pernici, Ee-Peng Lim, José Palazzo M. de Oliveira
PublisherSpringer Science and Business Media Deutschland GmbH
Number of pages14
ISBN (Print)9783030332228
StatePublished - 2019
Externally publishedYes
Event38th International Conference on Conceptual Modeling, ER 2019 - Salvador, Brazil
Duration: Nov 4 2019Nov 7 2019

Publication series

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


Conference38th International Conference on Conceptual Modeling, ER 2019

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Parallel clique-like subgraph counting and listing'. Together they form a unique fingerprint.

Cite this