收藏切换
Fast Algorithm for Approximate Motif Counting in Temporal Graph Streams
收藏切换
Jingjing Wang1, Yanhao Wang2, Wenjun Jiang3, Yifu Zeng1, Tuanfei Zhu1
Journal of Computer Research and Development | 2025, 62(3) : 709 - 719
Less
收藏切换
Journal of Computer Research and Development | 2025, 62(3): 709-719
• Artificial Intelligence •
Fast Algorithm for Approximate Motif Counting in Temporal Graph Streams
Full
Jingjing Wang1, Yanhao Wang2, Wenjun Jiang3, Yifu Zeng1, Tuanfei Zhu1
Affiliations
  • 1College of Computer Science and Engineering, Changsha University, Changsha 410022
  • 2School of Data Science and Engineering, East China Normal University, Shanghai 200062
  • 3College of Computer Science and Electronic Engineering, Hunan University, Changsha 410082
  • born in 1991. PhD, lecturer. Member of CCF. Her main research interests include graph data mining and social network analysis

    born in 1990. PhD, associate professor, PhD supervisor. Member of CCF. His main research interests include algorithm design and analysis, graph data mining, and responsible data management. ()

    born in 1982. PhD, professor, PhD supervisor. Senior member of CCF. Her main research interests include social network analysis and recommendation system, smart education, and learning optimization

    born in 1990. PhD, master supervisor. Member of CCF. His main research interests include data management, network of data center

    born in 1987. PhD, associate professor, master supervisor. Member of CCF. His main research interests include ensemble learning and imbalanced data learning

About Author:

born in 1991. PhD, lecturer. Member of CCF. Her main research interests include graph data mining and social network analysis

born in 1990. PhD, associate professor, PhD supervisor. Member of CCF. His main research interests include algorithm design and analysis, graph data mining, and responsible data management. ()

born in 1982. PhD, professor, PhD supervisor. Senior member of CCF. Her main research interests include social network analysis and recommendation system, smart education, and learning optimization

born in 1990. PhD, master supervisor. Member of CCF. His main research interests include data management, network of data center

born in 1987. PhD, associate professor, master supervisor. Member of CCF. His main research interests include ensemble learning and imbalanced data learning

Published: 2025-03-01 doi: 10.7544/issn1000-1239.202330788
Outline
收藏切换

Graphs often have rich temporal information and evolve dynamically over time, which can be modeled as temporal graph streams. A temporal graph stream consists of a set of vertices and a series of timestamped and directed edges, where new vertices and edges arrive continuously over time. Temporal motifs are generalizations of subgraph patterns in static graphs which take into account edge orderings and durations in addition to topologies. Counting the number of occurrences of temporal motifs is a fundamental problem for temporal graph analysis. However, traditional streaming subgraph counting methods cannot support temporal matching, and are only suitable for simple graphs that do not contain temporal information. In addition, existing temporal motifs counting methods suffer from poor performance in temporal graph streams. We thus study approximate temporal motif counting via random sampling in temporal graph streams. We propose a generic streaming edge sampling (SES) algorithm to estimate the number of instances of any temporal motif in a given temporal graph stream. We then provide comprehensive analyses of the theoretical bounds and time complexities of SES. Finally, we perform extensive experimental evaluations for SES on four real world datasets. The results show that SES achieves up to three orders of magnitude speedups over the state-of-the-art sampling methods while having comparable estimation errors for temporal motif counting in the streaming setting.

temporal motif  /  motif counting  /  temporal graph streams  /  random sampling  /  graph algorithm
王晶晶, 王延昊, 姜文君, 曾一夫, 祝团飞. 时序图流上的快速子图近似计数算法. 计算机研究与发展, 2025 , 62 (3) : 709 -719 . DOI: 10.7544/issn1000-1239.202330788
Jingjing Wang, Yanhao Wang, Wenjun Jiang, Yifu Zeng, Tuanfei Zhu. Fast Algorithm for Approximate Motif Counting in Temporal Graph Streams[J]. Journal of Computer Research and Development, 2025 , 62 (3) : 709 -719 . DOI: 10.7544/issn1000-1239.202330788
Year 2025 volume 62 Issue 3
104
47
Cite this Article
BibTeX
Article Info
doi: 10.7544/issn1000-1239.202330788
  • Receive Date:2023-10-10
  • Online Date:2026-11-10
  • Published:2025-03-01
Article Data
Affiliations
History
  • Received:2023-10-10
  • Revised:2024-02-06
Affiliations
    1College of Computer Science and Engineering, Changsha University, Changsha 410022
    2School of Data Science and Engineering, East China Normal University, Shanghai 200062
    3College of Computer Science and Electronic Engineering, Hunan University, Changsha 410082
References
Share
https://castjournals.cast.org.cn/joweb/jsjyjyfz/EN/10.7544/issn1000-1239.202330788
Share to
QR

Scan QR to access full text

Cite this article
BibTeX
Citations
表12种不同金属材料的力学参数
科
Family
属数
Number of
genus
种数
Number of
species
占总种数比例
Percentage of
total species (%)
属
Genus
种数
Number of
species
占总种数比例
Percentage of total
species (%)
鹅膏菌科Amanitaceae 2 11 5.26 鹅膏菌属 Amanita 10 4.78
小菇科 Mycenaceae 2 12 5.74 丝盖伞属 Inocybe 5 2.39
多孔菌科 Polyporaceae 8 14 6.70 蜡蘑属 Laccaria 5 2.39
红菇科 Russulaceae 3 23 11.00 小皮伞属 Marasmius 6 2.87
小菇属 Mycena 11 5.26
光柄菇属 Pluteus 5 2.39
红菇属 Russula 17 8.13
栓菌属 Trametes 5 2.39
关闭全屏
  • BibTeX
  • EndNote
  • RefWorks
  • TxT