Shared-Memory Parallel Maximal Biclique Enumeration
Shared-Memory Parallel Maximal Biclique Enumeration
复制标题
DOI：
10.1109/hipc.2019.00016
复制
发表时间：
2018-12
期刊：
影响因子：
--
通讯作者：
A. Das;Srikanta Tirthapura
中科院分区：
文献类型：
--
作者：
A. Das;Srikanta Tirthapura
We present shared memory parallel algorithms for maximal biclique enumeration (MBE), the task of enumerating all complete dense subgraphs (maximal bicliques) from a bipartite graph, which is widely used in the analysis of social, biological, and transactional networks. Since MBE is computationally expensive, it is necessary to use parallel computing to scale to large graphs. Our parallel algorithm ParMBE efficiently uses the power of multiple cores that share memory. From a theoretical view, ParMBE is work-efficient with respect to a state-of-the-art sequential algorithm. Our experimental evaluation shows that ParMBE scales well up to 64 cores, and is significantly faster than current parallel algorithms. Since ParMBE was yielding a super-linear speedup compared to the sequential algorithm on which it was based (MineLMBC), we develop an improved sequential algorithm FMBE, through "sequentializing" ParMBE
