File(s) under permanent embargo
Efficient Maximal Biclique Enumeration for Large Sparse Bipartite Graphs
conference contribution
posted on 2023-02-02, 06:43 authored by L Chen, C Liu, R Zhou, J Xu, Jianxin LiJianxin LiMaximal bicliques are effective to reveal meaningful information hidden in bipartite graphs. Maximal biclique enumeration (MBE) is challenging since the number of the maximal bicliques grows exponentially w.r.t. the number of vertices in a bipartite graph in the worst case. However, a large bipartite graph is usually very sparse, which is against the worst case and may lead to fast MBE algorithms. The uncharted opportunity is taking advantage of the sparsity to substantially improve the MBE efficiency for large sparse bipartite graphs. We observe that for a large sparse bipartite graph, a vertex υ may converge to a few vertices in the same vertex set as υ via its neighbours, which reveals that the enumeration scope for a vertex could be very small. Based on this observation, we propose novel concepts: unilateral coreness for individual vertices, unilateral order for each vertex set and unilateral convergence (Ϛ) for a large sparse bipartite graph. Ϛ could be a few thousand for a large sparse bipartite graph with hundreds of million edges. Using the unilateral order, every vertex with τ unilateral coreness only needs to check at most 2τ combinations so that all maximal bicliques can be enumerated and τ is bounded by Ϛ, which leads to a novel MBE algorithm running in O∗ (2Ϛ ) . We then propose a batch-pivots technique to eliminate all enumerations resulting in non-maximal bicliques, which guarantees that every maximal biclique is reported in O (Ϛe)-delay, where e is the number of edges. We devise novel data structures that allow storing subgraphs at omissible space for further speeding up MBE. Extensive experiments are conducted on synthetic and real large datasets to justify that our proposed algorithm is faster and more scalable than the existing algorithms.
History
Volume
15Pagination
1559-1571Publisher DOI
ISSN
0271-4132eISSN
1098-3627Language
enTitle of proceedings
Contemporary MathematicsIssue
8Publisher
Association for Computing Machinery (ACM)Usage metrics
Categories
No categories selectedKeywords
Licence
Exports
RefWorks
BibTeX
Ref. manager
Endnote
DataCite
NLM
DC