Maximum Butterfly Generators Search in Bipartite Networks

Bipartite graphs are widely used for modelling various real-world scenarios characterized with binary relations, such as, scholarly articles recommendation with author-paper relations, and product recommendation with user-product relations. Particularly, maximum butterfly as a special cohesive subgraph of bipartite graphs, is playing an critical role in many promising application such as recommendation systems and research groups detection. Enumerating maximal butterfly has been proved to be a NP-hard and suffers time and space complexity. To conquer this challenge, this paper pioneers a novel problem called maximal butterfly generators search (MBGS) for facilitating the detection of maximal butterflies. The MBGS problem is to find a subgraph B of G such that maximize the number of butterflies in B and it is mathematically proved to NP-Hard. To address this problem, an equivalence relation theorem between maximum butterfly generator and maximum butterfly concept is presented. Furthermore, an effective MBGS search algorithm is proposed. Extensive experiments on real-world networks with ground-truth communities and interesting case studies validated the effectiveness and efficiency of our MBGS model and algorithm.