Efficient Historical Butterfly Counting in Large Temporal Bipartite Networks via Graph Structure-Aware Index
Proceedings of the VLDB Endowment · 2025-02 · 18 (6) · 1607-1620
DOI: 10.14778/3725688.3725693 ↗Kurz gefasst
Fachartikel in der Zeitschrift Proceedings of the VLDB Endowment, online erschienen am 29.08.2025. Verfasst von Qiuyang Mang und 8 weiteren Autor:innen. Die Arbeit wurde bisher 3-mal zitiert (Crossref) und nennt 57 Literaturangaben.
Abstract (Originalsprache)
Bipartite graphs are ubiquitous in many domains, e.g., e-commerce platforms, social networks, and academia, by modeling interactions between distinct entity sets. Within these graphs, the butterfly motif, a complete 2×2 biclique, represents the simplest yet significant subgraph structure, crucial for analyzing complex network patterns. Counting the butterflies offers significant benefits across various applications, including community analysis and recommender systems. Additionally, the temporal dimension of bipartite graphs, where edges activate within specific time frames, introduces the concept of historical butterfly counting, i.e., counting butterflies within a given time interval. This temporal analysis sheds light on the dynamics and evolution of network interactions, offering new insights into their mechanisms. Despite its importance, no existing algorithm can efficiently solve the historical butterfly counting task. To address this, we design two novel indices whose memory footprints are dependent on #butterflies and #wedges, respectively. Combining these indices, we propose a graph structure-aware indexing approach that significantly reduces memory usage while preserving exceptional query speed. To further reduce the index size and boost the query efficiency, we design an index compression strategy, enabling the fast, high-quality, and unbiased approximation of historical butterfly counts. We theoretically prove that our approach is particularly advantageous on power-law graphs, a common characteristic of real-world bipartite graphs, by surpassing traditional complexity barriers for general graphs. Extensive experiments reveal that our query algorithms outperform existing methods by up to five magnitudes, effectively balancing speed with manageable memory requirements.
Zitieren
APA
Mang, Q., Chen, J., Zhou, H., Gao, Y., Zhou, Y., Shi, Q., Peng, R., Fang, Y., & Ma, C. (2025). Efficient Historical Butterfly Counting in Large Temporal Bipartite Networks via Graph Structure-Aware Index. Proceedings of the VLDB Endowment, 18(6), 1607-1620. https://doi.org/10.14778/3725688.3725693
Vancouver
Mang Q, Chen J, Zhou H, Gao Y, Zhou Y, Shi Q, et al. Efficient Historical Butterfly Counting in Large Temporal Bipartite Networks via Graph Structure-Aware Index. Proceedings of the VLDB Endowment. 2025;18(6):1607-1620. doi:10.14778/3725688.3725693
BibTeX
@article{Mang2025,
author = {Mang, Qiuyang and Chen, Jingbang and Zhou, Hangrui and Gao, Yu and Zhou, Yingli and Shi, Qingyu and Peng, Richard and Fang, Yixiang and Ma, Chenhao},
title = {Efficient Historical Butterfly Counting in Large Temporal Bipartite Networks via Graph Structure-Aware Index},
journal = {Proceedings of the VLDB Endowment},
year = {2025},
volume = {18},
number = {6},
pages = {1607--1620},
doi = {10.14778/3725688.3725693}
}
EUVIMED