Butterfly-Based Higher-Order Clustering on Bipartite Networks

Higher-order clustering is a hot research topic which searches higher-order organization of networks at the level of small subgraphs (motifs). However, in bipartite networks, there are no higher-order structures such as triangles, quadrangles or cliques. In this paper, we study the problem of identifying clusters with motif of dense butterflies in bipartite networks. First, we propose a framework of higher-order clustering algorithm by optimizing motif conductance. Then, we prove that the problem can be transformed to computing the conductance of a weight graph constructed by butterflies, so it can be solved by eigenvalue decomposition techniques. Next, we analyse the computational complexity of the proposed algorithms and find that it is indeed efficient to cluster motif of butterflies in bipartite networks. Finally, numerous experiments prove the effectiveness, efficiency and scalability of the proposed algorithm.