On the Efficient Discovery of Maximum $k$-Defective Biclique
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908413290610688 |
|---|---|
| author | Cui, Donghang Li, Ronghua Dai, Qiangqiang Qin, Hongchao Wang, Guoren |
| author_facet | Cui, Donghang Li, Ronghua Dai, Qiangqiang Qin, Hongchao Wang, Guoren |
| contents | The problem of identifying the maximum edge biclique in bipartite graphs has attracted considerable attention in bipartite graph analysis, with numerous real-world applications such as fraud detection, community detection, and online recommendation systems. However, real-world graphs may contain noise or incomplete information, leading to overly restrictive conditions when employing the biclique model. To mitigate this, we focus on a new relaxed subgraph model, called the $k$-defective biclique, which allows for up to $k$ missing edges compared to the biclique model. We investigate the problem of finding the maximum edge $k$-defective biclique in a bipartite graph, and prove that the problem is NP-hard. To tackle this computation challenge, we propose a novel algorithm based on a new branch-and-bound framework, which achieves a worst-case time complexity of $O(mα_k^n)$, where $α_k < 2$. We further enhance this framework by incorporating a novel pivoting technique, reducing the worst-case time complexity to $O(mβ_k^n)$, where $β_k < α_k$. To improve the efficiency, we develop a series of optimization techniques, including graph reduction methods, novel upper bounds, and a heuristic approach. Extensive experiments on 10 large real-world datasets validate the efficiency and effectiveness of the proposed approaches. The results indicate that our algorithms consistently outperform state-of-the-art algorithms, offering up to $1000\times$ speedups across various parameter settings. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_16121 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On the Efficient Discovery of Maximum $k$-Defective Biclique Cui, Donghang Li, Ronghua Dai, Qiangqiang Qin, Hongchao Wang, Guoren Data Structures and Algorithms The problem of identifying the maximum edge biclique in bipartite graphs has attracted considerable attention in bipartite graph analysis, with numerous real-world applications such as fraud detection, community detection, and online recommendation systems. However, real-world graphs may contain noise or incomplete information, leading to overly restrictive conditions when employing the biclique model. To mitigate this, we focus on a new relaxed subgraph model, called the $k$-defective biclique, which allows for up to $k$ missing edges compared to the biclique model. We investigate the problem of finding the maximum edge $k$-defective biclique in a bipartite graph, and prove that the problem is NP-hard. To tackle this computation challenge, we propose a novel algorithm based on a new branch-and-bound framework, which achieves a worst-case time complexity of $O(mα_k^n)$, where $α_k < 2$. We further enhance this framework by incorporating a novel pivoting technique, reducing the worst-case time complexity to $O(mβ_k^n)$, where $β_k < α_k$. To improve the efficiency, we develop a series of optimization techniques, including graph reduction methods, novel upper bounds, and a heuristic approach. Extensive experiments on 10 large real-world datasets validate the efficiency and effectiveness of the proposed approaches. The results indicate that our algorithms consistently outperform state-of-the-art algorithms, offering up to $1000\times$ speedups across various parameter settings. |
| title | On the Efficient Discovery of Maximum $k$-Defective Biclique |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2506.16121 |