Efficient Bitruss Decomposition without Butterfly Enumeration

Abstract

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 l..