Accelerated butterfly counting with vertex priority on bipartite graphs
Kai Wang, Xuemin Lin, Lu Qin, Wenjie Zhang, Ying Zhang
Abstract
Abstract Bipartite graphs are of great importance in many real-world applications. Butterfly, which is a complete $$2 \times 2$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mn>2</mml:mn><mml:mo>×</mml:mo><mml:mn>2</mml:mn></mml:mrow></mml:math> biclique, plays a key role in bipartite graphs. In this paper, we investigate the problem of efficient counting the number of butterflies. The most advanced techniques are based on enumerating wedges which is the dominant cost of counting butterflies. Nevertheless, the existing algorithms cannot efficiently handle large-scale bipartite graphs. This becomes a bottleneck in large-scale applications. In this paper, instead of the existing layer-priority-based techniques, we propose a vertex-priority-based paradigm $${\mathsf {BFC}}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>BFC</mml:mi></mml:math> - $${\mathsf {VP}}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>VP</mml:mi></mml:math> to enumerate much fewer wedges; this leads to a significant improvement of the time complexity of the state-of-the-art algorithms. In addition, we present cache-aware strategies to further improve the time efficiency while theoretically retaining the time complexity of $${\mathsf {BFC}}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>BFC</mml:mi></mml:math> - $${\mathsf {VP}}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>VP</mml:mi></mml:math> . We also show that our proposed techniques can work efficiently in external and parallel contexts. Moreover, we study the butterfly counting problem on batch-dynamic graphs. Specifically, given a bipartite graph G and a batch-update of edges B , we aim to maintain the number of butterflies in G . To tackle this problem, fast vertex-priority-based algorithms are proposed with optimizations for reducing the computation of existing wedges in G . Our extensive empirical studies demonstrate that the proposed techniques significantly outperform the baseline solutions on real datasets.