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

作     者：Das, Apurba Sanei-Mehri, Seyed-Vahid Tirthapura, Srikanta 

作者机构：Iowa State Univ Ames IA 50011 USA 

出 版 物：《ACM TRANSACTIONS ON PARALLEL COMPUTING》 (ACM Trans. Parallel Comp.)

年 卷 期：2020年第7卷第1期

页      面：1–28页

核心收录：

基　　金：US National Science Foundation [1527541, 1725702] Direct For Computer & Info Scie & Enginr Div Of Information & Intelligent Systems Funding Source: National Science Foundation Division of Computing and Communication Foundations Direct For Computer & Info Scie & Enginr Funding Source: National Science Foundation 

主　　题：Parallel algorithm maximal clique enumeration dynamic graph batch parallel algorithm work depth analysis scalable graph processing 

摘      要：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.