{"ID":2826286,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2512.19426","arxiv_id":"2512.19426","title":"A Computationally Efficient Framework for Overlapping Community Detection in Large Bipartite Graphs","abstract":"Community detection, which uncovers closely connected vertex groups in networks, is vital for applications in social networks, recommendation systems, and beyond. Real-world networks often have bipartite structures (vertices in two disjoint sets with inter-set connections), creating unique challenges on specialized community detection methods. Biclique percolation community (BCPC) is widely used to detect cohesive structures in bipartite graphs. A biclique is a complete bipartite subgraph, and a BCPC forms when maximal bicliques connect via adjacency (sharing an (alpha, beta)-biclique). Yet, existing methods for BCPC detection suffer from high time complexity due to the potentially massive maximal biclique adjacency graph (MBAG). To tackle this, we propose a novel partial-BCPC based solution, whose key idea is to use partial-BCPC to reduce the size of the MBAG. A partial-BCPC is a subset of BCPC. Maximal bicliques belonging to the same partial-BCPC must also belong to the same BCPC. Therefore, these maximal bicliques can be grouped as a single vertex in the MBAG, significantly reducing the size of the MBAG. Furthermore, we move beyond the limitations of MBAG and propose a novel BCPC detection approach based on (alpha, beta)-biclique enumeration. This approach detects BCPC by enumerating all (alpha, beta)-bicliques and connecting maximal bicliques sharing the same (alpha, beta)-biclique, which is the condition for maximal bicliques to be adjacent. It also leverages partial-BCPC to significantly prune the enumeration space of (alpha, beta)-biclique. Experiments show that our methods outperform existing methods by nearly three orders of magnitude.","short_abstract":"Community detection, which uncovers closely connected vertex groups in networks, is vital for applications in social networks, recommendation systems, and beyond. Real-world networks often have bipartite structures (vertices in two disjoint sets with inter-set connections), creating unique challenges on specialized com...","url_abs":"https://arxiv.org/abs/2512.19426","url_pdf":"https://arxiv.org/pdf/2512.19426v1","authors":"[\"Yue Zeng\",\"Rong-Hua Li\",\"Qiangqiang Dai\",\"Guoren Wang\"]","published":"2025-12-22T14:28:27Z","proceeding":"cs.SI","tasks":"[\"cs.SI\",\"cs.DB\"]","methods":"[]","has_code":false}