@inproceedings{38ea180d4a6940fe99a15099cab43180,
title = "Fast Approximate Temporal Butterfly Counting on Bipartite Graphs via Edge Sampling",
abstract = "Temporal bipartite graphs are widely used to represent time-evolving relationships between two disjoint sets of nodes, e.g., customer-product interactions in e-commerce and user-group memberships in social networks. Temporal butterflies, i.e., the complete bipartite subgraphs that occur between two nodes from each partition within a short period and in a prescribed order, are essential in modeling the structural and sequential patterns of such graphs. Counting the number of temporal butterflies is a fundamental task in temporal bipartite graph analysis. However, existing methods for butterfly counting on static bipartite graphs and motif counting on temporal unipartite graphs are inefficient for this purpose. Since exact counting can be time-consuming on large graphs, in this paper, we propose an edge sampling-based approach to approximating temporal butterfly counts accurately and efficiently. We provide an analytical bound on the number of edges to be sampled to obtain estimates with small relative errors and high probability. Finally, we evaluate our algorithm on six real-world temporal bipartite graphs to show its superior accuracy and efficiency compared to baselines.",
keywords = "Bipartite graph, Butterfly counting, Temporal motif",
author = "Jiaxi Pu and Yanhao Wang and Yuchen Li and Xuan Zhou",
note = "Publisher Copyright: {\textcopyright} The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd. 2025.; 10th International Workshop on Big Data Management and Service, BDMS 2024, 9th International Workshop on Big Data Quality Management, BDQM 2024, DASFAA 2024 Workshop on Emerging Results in Data Science and Engineering, ERDSE 2024 and 8th International Workshop on Graph Data Management and Analysis, GDMA 2024 held in conjunction with 29th International Conference on Database Systems for Advanced Applications, DASFAA 2024 ; Conference date: 02-07-2024 Through 05-07-2024",
year = "2025",
doi = "10.1007/978-981-96-0914-7\_4",
language = "英语",
isbn = "9789819609130",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Science and Business Media Deutschland GmbH",
pages = "42--57",
editor = "Atsuyuki Morishima and Guoliang Li and Yoshiharu Ishikawa and Sihem Amer-Yahia and H.V. Jagadish and Kejing Lu",
booktitle = "Database Systems for Advanced Applications. DASFAA 2024 International Workshops - BDMS, GDMA, BDQM and ERDSE, 2024, Proceedings",
address = "德国",
}