Efficient Temporal Butterfly Counting and Enumeration on Temporal Bipartite Graphs
Proceedings of the VLDB Endowment · 2023-12 · 17 (4) · 657-670
DOI: 10.14778/3636218.3636223 ↗Kurz gefasst
Fachartikel in der Zeitschrift Proceedings of the VLDB Endowment, online erschienen am 05.03.2024. Verfasst von Xinwei Cai und 6 weiteren Autor:innen. Die Arbeit wurde bisher 27-mal zitiert (Crossref) und nennt 66 Literaturangaben.
Abstract (Originalsprache)
Bipartite graphs characterize relationships between two different sets of entities, like actor-movie, user-item, and author-paper. The butterfly, a 4-vertices 4-edges (2,2)-biclique, is the simplest cohesive motif in a bipartite graph and is the fundamental component of higher-order substructures. Counting and enumerating the butterflies offer significant benefits across various applications, including fraud detection, graph embedding, and community search. While the corresponding motif, the triangle, in the unipartite graphs has been widely studied in both static and temporal settings, the extension of butterfly to temporal bipartite graphs remains unexplored. In this paper, we investigate the temporal butterfly counting and enumeration problem: count and enumerate the butterflies whose edges establish following a certain order within a given duration. Towards efficient computation, we devise a non-trivial baseline rooted in the state-of-the-art butterfly counting algorithm on static graphs, further, explore the intrinsic property of the temporal butterfly, and develop a new optimization framework with a compact data structure and effective priority strategy. The time complexity is proved to be significantly reduced without compromising on space efficiency. In addition, we generalize our algorithms to practical streaming settings and multi-core computing architectures. Our extensive experiments on 11 large-scale real-world datasets demonstrate the efficiency and scalability of our solutions.
Zitieren
APA
Cai, X., Ke, X., Wang, K., Chen, L., Zhang, T., Liu, Q., & Gao, Y. (2023). Efficient Temporal Butterfly Counting and Enumeration on Temporal Bipartite Graphs. Proceedings of the VLDB Endowment, 17(4), 657-670. https://doi.org/10.14778/3636218.3636223
Vancouver
Cai X, Ke X, Wang K, Chen L, Zhang T, Liu Q, et al. Efficient Temporal Butterfly Counting and Enumeration on Temporal Bipartite Graphs. Proceedings of the VLDB Endowment. 2023;17(4):657-670. doi:10.14778/3636218.3636223
BibTeX
@article{Cai2023,
author = {Cai, Xinwei and Ke, Xiangyu and Wang, Kai and Chen, Lu and Zhang, Tianming and Liu, Qing and Gao, Yunjun},
title = {Efficient Temporal Butterfly Counting and Enumeration on Temporal Bipartite Graphs},
journal = {Proceedings of the VLDB Endowment},
year = {2023},
volume = {17},
number = {4},
pages = {657--670},
doi = {10.14778/3636218.3636223}
}
EUVIMED