Top-k Butterfly Detection in Probabilistic Networks

In this paper, we study the problem of top- butterfly discovery in uncertain bipartite networks.Butterflies are important motifs on bipartite graphs, and their existence gives valuable information regarding the network's connectivity and robustness.We focus on uncertain (or probabilistic) graphs, where each edge is annotated with an existential probability.In addition to counting, the discovery of the top- most probable butterfly motifs in the top is an interesting and computationally expensive problem.Our approach serves as a foundation for future studies on uncertain bipartite networks, with possible extensions to the detection of other important network motifs beyond butterflies.Future work could focus on the adaptation of the algorithms to handle dynamic networks, the application to different types of graphs, the development of real-time analysis methods for continuous data streams and more.