Shared-memory Parallel Maximal Clique Enumeration from Static and Dynamic Graphs

Thumbnail Image
Date
2020-03-16
Authors
Das, Apurba
Sanei-Mehri, Seyed-Vahid
Major Professor
Advisor
Committee Member
Journal Title
Journal ISSN
Volume Title
Publisher
Association for Computing Machinery
Authors
Research Projects
Organizational Units
Journal Issue
Is Version Of
Versions
Series
Department
Electrical and Computer Engineering
Abstract
Maximal Clique Enumeration (MCE) is a fundamental graph mining problem and is useful as a primitive in identifying dense structures in a graph. Due to the high computational cost of MCE, parallel methods are imperative for dealing with large graphs. We present shared-memory parallel algorithms for MCE, with the following properties: (1) the parallel algorithms are provably work-efficient relative to a state-of-the-art sequential algorithm, (2) the algorithms have a provably small parallel depth, showing they can scale to a large number of processors, and (3) our implementations on a multicore machine show good speedup and scaling behavior with increasing number of cores and are substantially faster than prior shared-memory parallel algorithms for MCE; for instance, on certain input graphs, while prior works either ran out of memory or did not complete in five hours, our implementation finished within a minute using 32 cores. We also present work-efficient parallel algorithms for maintaining the set of all maximal cliques in a dynamic graph that is changing through the addition of edges.
Comments
This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published as Das, Apurba, Seyed-Vahid Sanei-Mehri, and Srikanta Tirthapura. "Shared-memory parallel maximal clique enumeration from static and dynamic graphs." ACM Transactions on Parallel Computing (TOPC) 7, no. 1 (2020): 1-28. DOI: 10.1145/3380936. Copyright 2020 Association for Computing Machinery. Posted with permission.
Description
Keywords
Citation
DOI
Copyright
Collections