收藏切换
Random-Walk Probability Computation on Dynamic Weighted Graphs
收藏切换
Hanzhi Wang1, Lu Yi2, Zhewei Wei2, 3, 6, 7, *, Junhao Gan4, Ye Yuan5, Jirong Wen1, 2, 6, Xiaoyong Du1, 7
Journal of Computer Research and Development | 2024, 61(8) : 1865 - 1881
Less
收藏切换
Journal of Computer Research and Development | 2024, 61(8): 1865-1881
• Special Issue on Graph Machine Learning •
Random-Walk Probability Computation on Dynamic Weighted Graphs
Full
Hanzhi Wang1, Lu Yi2, Zhewei Wei2, 3, 6, 7, *, Junhao Gan4, Ye Yuan5, Jirong Wen1, 2, 6, Xiaoyong Du1, 7
Affiliations
  • 1School of Information, Renmin University of China, Beijing 100872
  • 2Gaoling School of Artificial Intelligence, Renmin University of China, Beijing 100872
  • 3Pazhou Laboratory (Huangpu), Guangzhou 510555
  • 4University of Melbourne, Melbourne, Australia, VIC3010
  • 5School of Computer Science and Technology, Beijing Institute of Technology, Beijing 100081
  • 6Beijing Key Laboratory of Big Data Management and Analysis Methods (Gaoling School of Artificial Intelligence, Renmin University of China), Beijing 100872
  • 7Key Laboratory of Data Engineering and Knowledge Engineering (Renmin University of China), Ministry of Education, Beijing 100872
  • born in 1997. PhD candidate. Her main research interest includes graph analysis and learning on large graphs

    born in 2000. PhD student. Her main research interests include graph analysis and learning, dynamic graph neural network,data removal for graph neural network

    born in 1986. PhD, professor. His main research interests include big data and machine learning algorithms, graph analysis and learning, and streaming algorithms

    born in 1988. PhD, senior lecturer. His main research interests include practical algorithms with non-trivial theoretical guarantees for solving problems on massive data

    born in 1981. PhD, professor. His main research interests include big data management and analysis, artificial intelligence, and distributed computing

    born in 1972. PhD, professor. His main research interests include information retrieval, data mining, and machine learning

    born in 1963. PhD, professor. His main research interests include database system, and big data management and analysis

About Author:

born in 1997. PhD candidate. Her main research interest includes graph analysis and learning on large graphs

born in 2000. PhD student. Her main research interests include graph analysis and learning, dynamic graph neural network,data removal for graph neural network

born in 1986. PhD, professor. His main research interests include big data and machine learning algorithms, graph analysis and learning, and streaming algorithms

born in 1988. PhD, senior lecturer. His main research interests include practical algorithms with non-trivial theoretical guarantees for solving problems on massive data

born in 1981. PhD, professor. His main research interests include big data management and analysis, artificial intelligence, and distributed computing

born in 1972. PhD, professor. His main research interests include information retrieval, data mining, and machine learning

born in 1963. PhD, professor. His main research interests include database system, and big data management and analysis

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

Computing random-walk probabilities on graphs is the subject of extensive research in both graph theory and data mining research. However, existing work mainly focuses on static graphs, and cannot efficiently support dynamic weighted graphs, which are ubiquitous in real-world applications. We study the problem of computing random-walk probabilities on dynamic weighted graphs. We propose to use a sampling schema called coin flip sampling, rather than the more commonly adopted weighted sampling schema, for simulating random walks in dynamic weighted graphs. We demonstrate that simulations based on coin-flip sampling maintain the unbiasedness of the resulting random-walk probability approximations. Moreover, this approach allows us to simultaneously achieve a near-optimal query time complexity and an optimal $ O\left(1\right) $ update time overhead per edge insertion or deletion. This is a significant improvement over existing methods, which typically incur substantial sampling costs or rely on intricate auxiliary structures that are hard to maintain in a dynamic setting. We present both theoretical analysis and empirical evaluations to substantiate the superiority of our method on dynamic weighted graphs.

random-walk probability computation  /  dynamic weighted graphs  /  coin-flip sampling  /  real-time update  /  large-scale graphs
王涵之, 易璐, 魏哲巍, 甘骏豪, 袁野, 文继荣, 杜小勇. 动态有权图上的随机游走概率计算. 计算机研究与发展, 2024 , 61 (8) : 1865 -1881 . DOI: 10.7544/issn1000-1239.202440148
Hanzhi Wang, Lu Yi, Zhewei Wei, Junhao Gan, Ye Yuan, Jirong Wen, Xiaoyong Du. Random-Walk Probability Computation on Dynamic Weighted Graphs[J]. Journal of Computer Research and Development, 2024 , 61 (8) : 1865 -1881 . DOI: 10.7544/issn1000-1239.202440148
Year 2024 volume 61 Issue 8
67
30
Cite this Article
BibTeX
Article Info
doi: 10.7544/issn1000-1239.202440148
  • Receive Date:2024-03-02
  • Online Date:2026-11-17
  • Published:2024-08-01
Article Data
Affiliations
History
  • Received:2024-03-02
  • Revised:2024-04-25
Affiliations
    1School of Information, Renmin University of China, Beijing 100872
    2Gaoling School of Artificial Intelligence, Renmin University of China, Beijing 100872
    3Pazhou Laboratory (Huangpu), Guangzhou 510555
    4University of Melbourne, Melbourne, Australia, VIC3010
    5School of Computer Science and Technology, Beijing Institute of Technology, Beijing 100081
    6Beijing Key Laboratory of Big Data Management and Analysis Methods (Gaoling School of Artificial Intelligence, Renmin University of China), Beijing 100872
    7Key Laboratory of Data Engineering and Knowledge Engineering (Renmin University of China), Ministry of Education, Beijing 100872
References
Share
https://castjournals.cast.org.cn/joweb/jsjyjyfz/EN/10.7544/issn1000-1239.202440148
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