TY - GEN
T1 - Parallel clique-like subgraph counting and listing
AU - Yang, Yi
AU - Yan, Da
AU - Zhou, Shuigeng
AU - Guo, Guimu
N1 - Publisher Copyright:
© Springer Nature Switzerland AG 2019.
PY - 2019
Y1 - 2019
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85076156805&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85076156805&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-33223-5_40
DO - 10.1007/978-3-030-33223-5_40
M3 - Conference contribution
AN - SCOPUS:85076156805
SN - 9783030332228
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 484
EP - 497
BT - Conceptual Modeling - 38th International Conference, ER 2019, Proceedings
A2 - Laender, Alberto H.F.
A2 - Pernici, Barbara
A2 - Lim, Ee-Peng
A2 - de Oliveira, José Palazzo M.
PB - Springer Science and Business Media Deutschland GmbH
T2 - 38th International Conference on Conceptual Modeling, ER 2019
Y2 - 4 November 2019 through 7 November 2019
ER -