Counting the Number of Hop-Constrained Simple S-T Paths in Large Graphs
Bocheng Han, Zebin Chen, Yi Ding, Weizhang Jiang, Yizhe Zhang, John Shepherd, Dong Wen, Zhengyi Yang*
International Conference on Web Information Systems Engineering (WISE)
RAIDS Lab Authors
Details
Research Area
Tags
Resources
Abstract
Graphs are widely used to model complex relationships among entities in domains such as recommendation systems and social networks. A fundamental problem in these applications is quantifying the connectivity between two entities, often formulated as estimating the number of source-to-target paths under specific constraints. In this paper, we study the problem of hop-constrained s-t path counting, which aims to estimate the number of paths from a source vertex s to a target vertex t within a given hop bound k. We propose kPathAssess, an efficient path counting algorithm inspired by the recent PathAssess algorithm. kPathAssess balances estimation accuracy and computational complexity by leveraging locally computable lower bounds on path counts. Extensive experiments on real-world graphs demonstrate that kPathAssess achieves high estimation efficiency with significantly reduced computation time, particularly as the hop constraint increases.
Author Affiliations
BibTeX
@inproceedings{han2025counting,
title = {Counting the Number of Hop-Constrained Simple S-T Paths in Large Graphs},
author = {Han, Bocheng and Chen, Zebin and Ding, Yi and Jiang, Weizhang and Zhang, Yizhe and Shepherd, John and Wen, Dong and Yang, Zhengyi},
editor = {Awan, Irfan and Younas, Muhammad and Zhang, Yanchun and Barhamgi, Mahmoud and Wang, Hua},
booktitle = {Web Information Systems Engineering -- WISE 2025},
year = {2026},
publisher = {Springer Nature Singapore},
address = {Singapore},
pages = {375--387},
isbn = {978-981-95-7251-9}
}