The Library
RoleSim* : scaling axiomatic role-based similarity ranking on large graphs
Tools
Tools
Tools
Yu, Weiren, Iranmanesh, Sima, Haldar, Aparajita, Zhang, Maoyin and Ferhatosmanoglu, Hakan (2022) RoleSim* : scaling axiomatic role-based similarity ranking on large graphs. World Wide Web, 25 (2). pp. 785-829. doi:10.1007/s11280-021-00925-z ISSN 1573-1413.
|
PDF
11280_2021_Article_925.pdf - Published Version - Requires a PDF viewer. Available under License Creative Commons Attribution 4.0. Download (3621Kb) | Preview |
Official URL: https://doi.org/10.1007/s11280-021-00925-z
Abstract
RoleSim and SimRank are among the popular graph-theoretic similarity measures with many applications in, e.g., web search, collaborative filtering, and sociometry. While RoleSim addresses the automorphic (role) equivalence of pairwise similarity which SimRank lacks, it ignores the neighboring similarity information out of the automorphically equivalent set. Consequently, two pairs of nodes, which are not automorphically equivalent by nature, cannot be well distinguished by RoleSim if the averages of their neighboring similarities over the automorphically equivalent set are the same. To alleviate this problem: 1) We propose a novel similarity model, namely RoleSim*, which accurately evaluates pairwise role similarities in a more comprehensive manner. RoleSim* not only guarantees the automorphic equivalence that SimRank lacks, but also takes into account the neighboring similarity information outside the automorphically equivalent sets that are overlooked by RoleSim. 2) We prove the existence and uniqueness of the RoleSim* solution, and show its three axiomatic properties (i.e., symmetry, boundedness, and non-increasing monotonicity). 3) We provide a concise bound for iteratively computing RoleSim* formula, and estimate the number of iterations required to attain a desired accuracy. 4) We induce a distance metric based on RoleSim* similarity, and show that the RoleSim* metric fulfills the triangular inequality, which implies the sum-transitivity of its similarity scores. 5) We present a threshold-based RoleSim* model that reduces the computational time further with provable accuracy guarantee. 6) We propose a single-source RoleSim* model, which scales well for sizable graphs. 7) We also devise methods to scale RoleSim* based search by incorporating its triangular inequality property with partitioning techniques. Our experimental results on real datasets demonstrate that RoleSim* achieves higher accuracy than its competitors while scaling well on sizable graphs with billions of edges.
| Item Type: | Journal Article | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software T Technology > TK Electrical engineering. Electronics Nuclear engineering |
|||||||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | |||||||||
| SWORD Depositor: | Library Publications Router | |||||||||
| Library of Congress Subject Headings (LCSH): | Computer networks, Graph algorithms, Data structures (Computer science), Web search engines | |||||||||
| Journal or Publication Title: | World Wide Web | |||||||||
| Publisher: | Springer | |||||||||
| ISSN: | 1573-1413 | |||||||||
| Official Date: | March 2022 | |||||||||
| Dates: |
|
|||||||||
| Volume: | 25 | |||||||||
| Number: | 2 | |||||||||
| Page Range: | pp. 785-829 | |||||||||
| DOI: | 10.1007/s11280-021-00925-z | |||||||||
| Status: | Peer Reviewed | |||||||||
| Publication Status: | Published | |||||||||
| Access rights to Published version: | Open Access (Creative Commons) | |||||||||
| Date of first compliant deposit: | 27 February 2023 | |||||||||
| Date of first compliant Open Access: | 28 February 2023 | |||||||||
| RIOXX Funder/Project Grant: |
|
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
