Efficient Index Maintenance for Effective Resistance Computation on Evolving Graphs
Summary: Introduces an index for effective resistance on evolving graphs based on preserving samples of random walks and loop-erased walks instead of matrices. Edge updates map to landmark-node updates; two update algorithms (random-walk and loop-erased-walk) support cycle-decomposition to update samples in O(1) per edge, yielding up to 100x speedups on real data. (summarized by gpt-5-nano on Feb 09 2026)
Incoming Non-self Citations Over Time
Authors
- 1. Meihao Liao (Beijing Institute of Technology)
- 2. Cheng Li (Beijing Institute of Technology)
- 3. Rong-Hua Li (Beijing Institute of Technology)
- 4. Guoren Wang (Beijing Institute of Technology)
BibTeX Citation
@inproceedings{liao_sigmod25,
title = {{Efficient Index Maintenance for Effective Resistance Computation on Evolving Graphs}},
author = {Liao, Meihao and Li, Cheng and Li, Rong-Hua and Wang, Guoren},
series = {{SIGMOD} '25},
booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
publisher = {Association for Computing Machinery},
doi = {10.1145/3709686},
url = {https://dl.acm.org/doi/10.1145/3709686},
year = {2025}
}Incoming Citations (Sorted by Pagerank)
Showing 3 of 3 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 10,366 | Efficient Exact Resistance Distance Computation on Small-Treewidth Graphs: a Labelling Approach | 2026 | SIGMOD | 5.093636e-05 |
| 10,450 | Enabling Efficient Direct Update on Rule-Based Compressed Graph | 2026 | SIGMOD | 5.093636e-05 |
| 10,560 | Theoretically and Practically Efficient Resistance Distance Computation on Large Graphs | 2026 | VLDB | 5.093636e-05 |
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 11 of 11 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
Previous
Page 1 / 1
Next