Butterfly Counting In Bipartite Networks

Authors:
Seyed-Vahid Sanei-Mehri Iowa State University
Ahmet Erdem Sariyuce University at Buffalo
Srikanta Tirthapura Iowa State University

Introduction:

This paper considers the problem of counting motifs in bipartite affiliation networks. main contribution is a suite of randomized algorithms that can quickly approximate the number of butterflies in a graph with a provable guarantee on accuracy.

Abstract:

We consider the problem of counting motifs in bipartite affiliation networks, such as author-paper, user-product, and actor-movie relations. We focus on counting the number of occurrences of a “butterfly”, a complete 2x2 biclique, the simplest cohesive higher-order structure in a bipartite graph. Our main contribution is a suite of randomized algorithms that can quickly approximate the number of butterflies in a graph with a provable guarantee on accuracy. An experimental evaluation on large real-world networks shows that our algorithms return accurate estimates within a few seconds, even for networks with trillions of butterflies and hundreds of millions of edges.

You may want to know: