Shared-Memory Parallel Maximal Biclique Enumeration

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.

I. Introduction

We study the problem of Maximal Biclique Enumeration (MBE) from a bipartite graph, which requires to enumerate all maximal bicliques (complete bipartite graphs). A biclique is a dense bipartite subgraph of the original bipartite graph where every vertex in is connected to every vertex in . MBE is a computationally hard problem since the number of maximal bicliques can be of exponential order [1]. However, the number of maximal bicliques in real world graphs is typically small and therefore we can hope for enumerating them all in reasonable amount of time. Sequential algorithm for solving the MBE problem has been studied for more than a decade. Eppstein [2] proposed a linear time sequential algorithm for enumerating all maximal biclique from a simple undirected graph with bounded arboricity using a technique called acyclic orientation. Alexe et al. [3] proposed an output sensitive algorithm based on consensus technique where large bicliques are constructed by combining small bicliques starting with stars. There are many other works on designing sequential algorithms for solving MBE on static graph [4]–[8]. Liu et al. [9] develop a output sensitive branch and bound algorithm MineLMBC for solving the same problem which is also efficient in practice compared to the other algorithms.