Efficient Bitruss Decomposition without Butterfly Enumeration

Mining cohesive subgraphs in bipartite graphs is of great importance to various real-world applications such as recommendation in e-commercial systems and fraud detections in social networks. In this paper, we study the problem of Bitruss Decomposition of a given bipartite graph G. The goal is to compute, for each edge e, the largest value of k such that e is still contained in a k-bitruss. Here, a k-bitruss is a maximal subgraph of G such that every edge of it is contained in at least k butterflies (i.e(2,2)-cliques) in the subgraph. All the previous state-of-the-art solutions are based on the well-known Peeling Process framework and have to ''touch'' every butterfly in the graph G for at least once, causing a O(⧖G) cost, where ⧖G is the number of butterflies in G. In the worst case, ⧖G can be as large as O(m2), where m is the number of edges in G. We propose the first algorithm called BiT-DT, whose running time is bounded by O(m^1.5 log m), significantly improving the state-of-the-art bound by roughly a factor of O(√m). The crucial idea of our algorithm is an efficient approach to identify the edges to be peeled next in the Peeling Process without maintaining a precise butterfly support for each edge. To further enhance the practical performance of our BiT-DT algorithm, we propose a heuristic to peel the edges in batch. Extensive experimental results on ten real-world datasets show that our proposed algorithm outperforms the state-of-the-art baselines by up to an order of magnitude in terms of running time.