Papers › Role Similarity Metric Based on Spanning Rooted Forest

Role Similarity Metric Based on Spanning Rooted Forest

15 Oct 2021arXiv:2110.07872archive 2025-07-28

Qi Bao, Zhongzhi Zhang, Haibin Kan

As a fundamental issue in network analysis, structural node similarity has received much attention in academia and is adopted in a wide range of applications. Among these proposed structural node similarity measures, role similarity stands out because of satisfying several axiomatic properties including automorphism conformation. Existing role similarity metrics cannot handle top-k queries on large real-world networks due to the high time and space cost. In this paper, we propose a new role similarity metric, namely ForestSim. We prove that ForestSim is an admissible role similarity metric and devise the corresponding top-k similarity search algorithm, namely ForestSimSearch, which is able to process a top-k query in O(k) time once the precomputation is finished. Moreover, we speed up the precomputation by using a fast approximate algorithm to compute the diagonal entries of the forest matrix, which reduces the time and space complexity of the precomputation to O(ϵ⁻²mlog⁵nlog1/ϵ) and O(mlog³n), respectively. Finally, we conduct extensive experiments on 26 real-world networks. The results show that ForestSim works efficiently on million-scale networks and achieves comparable performance to the state-of-art methods.

PaperPDFCode

Syntology This paper's arXiv id is not in Syntology's Atlas id list (549,449 ids, as this build read them; the read time is in the build record), so this page links to no Syntology page for it. The list is not the whole graph; Syntology's feed shows papers as they enter the graph.

Code

accelerator950113/forestsim officialmentioned in paperSyntology: not harvested report

Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.

Code Syntology ran Syntology

Not run by Syntology. Nothing on this page verifies that the listed code works.

Results from the paper archive 2025-07-28

No leaderboard rows for this paper in the archive.

Methods

SPEED

Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections