Publication Type
Conference Proceeding Article
Version
publishedVersion
Publication Date
10-2020
Abstract
A great variety of complex systems ranging from user interactions in communication networks to transactions in financial markets can be modeled as temporal graphs, which consist of a set of vertices and a series of timestamped and directed edges. Temporal motifs in temporal graphs are generalized from subgraph patterns in static graphs which take into account edge orderings and durations in addition to structures. Counting the number of occurrences of temporal motifs is a fundamental problem for temporal network analysis. However, existing methods either cannot support temporal motifs or suffer from performance issues. In this paper, we focus on approximate temporal motif counting via random sampling. We first propose a generic edge sampling (ES) algorithm for estimating the number of instances of any temporal motif. Furthermore, we devise an improved EWS algorithm that hybridizes edge sampling with wedge sampling for counting temporal motifs with 3 vertices and 3 edges. We provide comprehensive analyses of the theoretical bounds and complexities of our proposed algorithms. Finally, we conduct extensive experiments on several real-world datasets, and the results show that our ES and EWS algorithms have higher efficiency, better accuracy, and greater scalability than the state-of-the-art sampling method for temporal motif counting.
Keywords
Temporal networks, Motif counting, Random sampling
Discipline
Numerical Analysis and Scientific Computing | Theory and Algorithms
Publication
CIKM '20: Proceedings of the 29th ACM International Conference on Information and Knowledge Management, Virtual, October 19-23
First Page
1505
Last Page
1514
ISBN
9781450368599
Identifier
10.1145/3340531.3411862
Publisher
ACM
City or Country
New York
Embargo Period
5-13-2021
Citation
WANG, Jingjing; WANG, Yanhao; JIANG, Wenjun; LI, Yuchen; and TAN, Kian-Lee.
Efficient sampling algorithms for approximate temporal motif counting. (2020). CIKM '20: Proceedings of the 29th ACM International Conference on Information and Knowledge Management, Virtual, October 19-23. 1505-1514.
Available at: https://ink.library.smu.edu.sg/sis_research/5934
Copyright Owner and License
Publisher
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.
Additional URL
https://doi.org/10.1145/3340531.3411862