Density Decomposition of Bipartite Graphs

Mining dense subgraphs in a bipartite graph is a fundamental task in bipartite graph analysis, with numerous applications in community detection, fraud detection, and e-commerce recommendation. Existing dense subgraph models, such as biclique, 𝑘-biplex, 𝑘-bitruss, and (𝛼, 𝛽)-core, often face challenges due to their high computational complexity or limitations in effectively capturing the density of the graph. To overcome these issues, in this paper, we propose a new dense subgraph model for bipartite graphs, namely (𝛼, 𝛽)-dense subgraph, designed to capture the density structure inherent in bipartite graphs. We show that all (𝛼, 𝛽)-dense subgraphs are nested within each other, forming a hierarchical density decomposition of the bipartite graph. To efficiently compute the (𝛼, 𝛽)-dense subgraph, we develop a novel network flow algorithm with a carefullydesigned core pruning technique. The time complexity of our algorithm is 𝑂(|𝐸| + |𝐸(𝑅)| 1.5 ), where |𝐸| denotes the number of edges and |𝐸(𝑅)| is the number of edges of the pruned graph, often significantly smaller than |𝐸|. Armed with this algorithm, we also propose a novel and efficient divide-and-conquer algorithm to compute the entire density decomposition of the bipartite graph within 𝑂(𝑝 ⋅ log 𝑑 max ⋅ |𝐸| 1.5 ) time, where 𝑝 is typically a small constant in real-world bipartite graphs and 𝑑 max is the maximum degree. Extensive experiments and case studies on 11 real-world datasets demonstrate the effectiveness of our (𝛼, 𝛽)-dense subgraph model and the high efficiency and scalability of our proposed algorithms. CCS Concepts: • Theory of computation → Graph algorithms analysis.