On Efficient Large Maximal Biplex Discovery

Kaiqiang Yu, Cheng Long, Deepak P, Tanmoy Chakraborty

Research output: Contribution to journalArticlepeer-review

Abstract

Cohesive subgraph discovery is an important problem in bipartite graph mining. In this paper, we focus on one kind of cohesive structure, called k-biplex, where each vertex of one side is disconnected from at most k vertices of the other side. We consider the large maximal k-biplex enumeration problem which is to list all those maximal k-biplexes with the number of vertices at each side at least a non-negative integer . This formulation, we observe, has various applications and targets to find non-redundant results by excluding non-maximal ones. Existing approaches suffer from massive redundant computations and can only run on small and moderate datasets. Towards improving scalability, we propose an efficient tree-based algorithm with two advanced strategies and powerful pruning techniques. Experimental results on real and synthetic datasets show the superiority of our algorithm over existing approaches.
Original languageEnglish
JournalIEEE Transactions on Knowledge and Data Engineering
Early online date03 May 2021
DOIs
Publication statusEarly online date - 03 May 2021

Cite this