EUVIMEDEUVIMED entdecken
Crossref

Efficient Temporal Butterfly Counting and Enumeration on Temporal Bipartite Graphs

Xinwei Cai, Xiangyu Ke, Kai Wang, Lu Chen, Tianming Zhang, Qing Liu, Yunjun Gao

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →