收藏切换
Edge Hashing Distributed Sampling Algorithm for Triangle Counting in Large-scale Dynamic Graph Stream
收藏切换
Yulin He1, 2, *, Bo Wu2, Dingming Wu2, Zhexue Huang1, 2, Fournier-Viger Philippe2
Journal of Computer Research and Development | 2024, 61(8) : 1882 - 1903
Less
收藏切换
Journal of Computer Research and Development | 2024, 61(8): 1882-1903
• Special Issue on Graph Machine Learning •
Edge Hashing Distributed Sampling Algorithm for Triangle Counting in Large-scale Dynamic Graph Stream
Full
Yulin He1, 2, *, Bo Wu2, Dingming Wu2, Zhexue Huang1, 2, Fournier-Viger Philippe2
Affiliations
  • 1Guangdong Laboratory of Artificial Intelligence and Digital Economy (Shenzhen), Shenzhen, Guangdong 518107
  • 2College of Computer Science and Software Engineering, Shenzhen University, Shenzhen, Guangdong 518060
  • born in 1982. PhD, research fellow. Member of CCF. His main research interests include data mining and machine learning, big data processing and analysis, big data approximate computing technology, and multi-sample statistic analysis theory and method

    born in 2000. Master candidate. His main research interests include social network management and mining, big data system computing technologies, and machine learning algorithms and their applications

    born in 1982. PhD, associate professor. Her main research interest includes the management and mining for spatial text data, knowledge graph data, social network data

    born in 1959. PhD, professor, PhD supervisor. Member of CCF. His main research interests include data mining, machine learning, big data processing and analysis, and big data system computing technologies

    born in 1980. PhD, professor, PhD supervisor. Senior member of CCF. His main research interests include data mining, artificial intelligence, knowledge expression and inference, and cognitive model construction

About Author:

born in 1982. PhD, research fellow. Member of CCF. His main research interests include data mining and machine learning, big data processing and analysis, big data approximate computing technology, and multi-sample statistic analysis theory and method

born in 2000. Master candidate. His main research interests include social network management and mining, big data system computing technologies, and machine learning algorithms and their applications

born in 1982. PhD, associate professor. Her main research interest includes the management and mining for spatial text data, knowledge graph data, social network data

born in 1959. PhD, professor, PhD supervisor. Member of CCF. His main research interests include data mining, machine learning, big data processing and analysis, and big data system computing technologies

born in 1980. PhD, professor, PhD supervisor. Senior member of CCF. His main research interests include data mining, artificial intelligence, knowledge expression and inference, and cognitive model construction

Published: 2024-08-01 doi: 10.7544/issn1000-1239.202440120
Outline
收藏切换

Triangle counting is a classical problem in large-scale graph analysis and widely applied in areas such as social network analysis, anomaly detection, and graph mining. In dynamic graph data streams, the topological structure of graph is constantly changing, involving edge insertions and deletions. Recent researches mainly focus on static streaming graphs and the corresponding streaming graph sampling algorithms only deal with edge insertions. Only a few single-machine sampling algorithms with low accuracy can handle edge deletion operations. We propose the edge hashing assignment-based distributed sampling (EHADS) algorithm, which is a distributed streaming algorithm designed for estimating the number of triangles in dynamic graph data streams. EHADS algorithm can rapidly and accurately estimate the counts of global triangles and local triangles associated with each vertex in dynamic streaming graphs. EHADS algorithm processes the input graph stream only once and samples edges across multiple machines. Compared with state-of-the-art single-machine streaming algorithms, the experimental results reflect that EHADS algorithm has the following advantages: 1) with the same sample capacity, EHADS algorithm achieves smaller estimation errors with less runtime, reducing the average estimation error of global triangle count by 31.79% and local triangle count by 23.35%; 2) EHADS algorithm provides unbiased estimations of the triangle count in streaming graph, and mathematical proofs demonstrate that the above-mentioned unbiased estimation has smaller variance.

triangle counting  /  dynamic graph stream  /  edge sampling  /  distributed streaming algorithm  /  edge hashing assignment
何玉林, 吴波, 吴定明, 黄哲学, 菲律普弗尼尔-维格. 针对大规模动态图流三角形计数的边哈希分布式抽样算法. 计算机研究与发展, 2024 , 61 (8) : 1882 -1903 . DOI: 10.7544/issn1000-1239.202440120
Yulin He, Bo Wu, Dingming Wu, Zhexue Huang, Fournier-Viger Philippe. Edge Hashing Distributed Sampling Algorithm for Triangle Counting in Large-scale Dynamic Graph Stream[J]. Journal of Computer Research and Development, 2024 , 61 (8) : 1882 -1903 . DOI: 10.7544/issn1000-1239.202440120
Year 2024 volume 61 Issue 8
78
36
Cite this Article
BibTeX
Article Info
doi: 10.7544/issn1000-1239.202440120
  • Receive Date:2024-03-15
  • Online Date:2026-11-17
  • Published:2024-08-01
Article Data
Affiliations
History
  • Received:2024-03-15
  • Revised:2024-05-17
Affiliations
    1Guangdong Laboratory of Artificial Intelligence and Digital Economy (Shenzhen), Shenzhen, Guangdong 518107
    2College of Computer Science and Software Engineering, Shenzhen University, Shenzhen, Guangdong 518060
References
Share
https://castjournals.cast.org.cn/joweb/jsjyjyfz/EN/10.7544/issn1000-1239.202440120
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