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
Person
Research Projects
Organizational Units
Organizational Unit
Electrical and Computer Engineering

The Department of Electrical and Computer Engineering (ECpE) contains two focuses. The focus on Electrical Engineering teaches students in the fields of control systems, electromagnetics and non-destructive evaluation, microelectronics, electric power & energy systems, and the like. The Computer Engineering focus teaches in the fields of software systems, embedded systems, networking, information security, computer architecture, etc.

History
The Department of Electrical Engineering was formed in 1909 from the division of the Department of Physics and Electrical Engineering. In 1985 its name changed to Department of Electrical Engineering and Computer Engineering. In 1995 it became the Department of Electrical and Computer Engineering.

Dates of Existence
1909-present

Historical Names

  • Department of Electrical Engineering (1909-1985)
  • Department of Electrical Engineering and Computer Engineering (1985-1995)

Related Units

Journal Issue
Is Version Of
Versions
Series
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