{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,6]],"date-time":"2026-03-06T22:16:23Z","timestamp":1772835383625,"version":"3.50.1"},"reference-count":42,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2021,8,11]],"date-time":"2021-08-11T00:00:00Z","timestamp":1628640000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,8,11]],"date-time":"2021-08-11T00:00:00Z","timestamp":1628640000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["NSFC61972203"],"award-info":[{"award-number":["NSFC61972203"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004608","name":"Natural Science Foundation of Jiangsu Province","doi-asserted-by":"publisher","award":["BK20190442"],"award-info":[{"award-number":["BK20190442"]}],"id":[{"id":"10.13039\/501100004608","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["World Wide Web"],"published-print":{"date-parts":[[2022,3]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>RoleSim and SimRank are among the popular graph-theoretic similarity measures with many applications in, <jats:italic>e.g.,<\/jats:italic> 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 (<jats:italic>i.e.,<\/jats:italic> 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.<\/jats:p>","DOI":"10.1007\/s11280-021-00925-z","type":"journal-article","created":{"date-parts":[[2021,8,11]],"date-time":"2021-08-11T15:02:47Z","timestamp":1628694167000},"page":"785-829","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["RoleSim*: Scaling axiomatic role-based similarity ranking on large graphs"],"prefix":"10.1007","volume":"25","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1082-9475","authenticated-orcid":false,"given":"Weiren","family":"Yu","sequence":"first","affiliation":[]},{"given":"Sima","family":"Iranmanesh","sequence":"additional","affiliation":[]},{"given":"Aparajita","family":"Haldar","sequence":"additional","affiliation":[]},{"given":"Maoyin","family":"Zhang","sequence":"additional","affiliation":[]},{"given":"Hakan","family":"Ferhatosmanoglu","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,8,11]]},"reference":[{"key":"925_CR1","doi-asserted-by":"crossref","unstructured":"Antonellis, I., Garcia-Molina, H., Chang, C.-C.: SimRank++: Query rewriting through link analysis of the click graph. PVLDB, 1(1) (2008)","DOI":"10.14778\/1453856.1453903"},{"issue":"1","key":"925_CR2","doi-asserted-by":"publisher","first-page":"443","DOI":"10.1007\/s10479-010-0757-3","volume":"181","author":"J Bijsterbosch","year":"2010","unstructured":"Bijsterbosch, J., Volgenant, A.: Solving the rectangular assignment problem and applications. Ann. Oper. Res. 181(1), 443\u2013462 (2010)","journal-title":"Ann. Oper. Res."},{"issue":"2","key":"925_CR3","doi-asserted-by":"publisher","first-page":"15:1","DOI":"10.1145\/2776894","volume":"10","author":"H Chen","year":"2015","unstructured":"Chen, H., Giles, C.L.: ASCOS++: an asymmetric similarity measure for weighted networks to address the problem of simrank. ACM Trans. Knowl. Discov. Data 10(2), 15:1\u201315:26 (2015)","journal-title":"ACM Trans. Knowl. Discov. Data"},{"key":"925_CR4","doi-asserted-by":"crossref","unstructured":"Fujiwara, Y., Nakatsuji, M., Shiokawa, H., Onizuka, M.: Efficient search algorithm for SimRank. In: ICDE, pp 589\u2013600 (2013)","DOI":"10.1109\/ICDE.2013.6544858"},{"key":"925_CR5","doi-asserted-by":"crossref","unstructured":"He, G., Feng, H., Li, C., Chen, H.: Parallel SimRank computation on large graphs with iterative aggregation. In: KDD (2010)","DOI":"10.1145\/1835804.1835874"},{"key":"925_CR6","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1016\/j.is.2013.12.008","volume":"42","author":"J He","year":"2014","unstructured":"He, J., Liu, H., Yu, J.X., Li, P., He, W., Du, X.: Assessing single-pair similarity over graphs by aggregating first-meeting probabilities. Inf. Syst. 42, 107\u2013122 (2014)","journal-title":"Inf. Syst."},{"key":"925_CR7","doi-asserted-by":"crossref","unstructured":"Jeh, G., Widom, J.: SimRank: A measure of structural-context similarity. In: KDD, pp 538\u2013543 (2002)","DOI":"10.1145\/775047.775126"},{"issue":"9","key":"925_CR8","first-page":"937","volume":"10","author":"M Jiang","year":"2017","unstructured":"Jiang, M., Fu, A.W., Wong, R.C., Wang, K.: READS: A random walk approach for efficient and accurate dynamic simrank. PVLDB 10(9), 937\u2013948 (2017)","journal-title":"PVLDB"},{"key":"925_CR9","doi-asserted-by":"crossref","unstructured":"Jin, R., Lee, V.E., Hong, H.: Axiomatic ranking of network role similarity. In: Apt\u00e9, C., Ghosh, J., Smyth, P. (eds.) Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Diego, CA, USA, August 21-24, 2011, pp 922\u2013930. ACM (2011)","DOI":"10.1145\/2020408.2020561"},{"issue":"1","key":"925_CR10","doi-asserted-by":"publisher","first-page":"3:1","DOI":"10.1145\/2518176","volume":"8","author":"R Jin","year":"2014","unstructured":"Jin, R., Lee, V.E., Li, L.: Scalable and axiomatic ranking of network role similarity. TKDD 8(1), 3:1\u20133:37 (2014)","journal-title":"TKDD"},{"issue":"1","key":"925_CR11","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1137\/S1064827595287997","volume":"20","author":"G Karypis","year":"1998","unstructured":"Karypis, G., Kumar, V.: A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM J. Scientif. Comput. 20(1), 359\u2013392 (1998)","journal-title":"SIAM J. Scientif. Comput."},{"key":"925_CR12","doi-asserted-by":"crossref","unstructured":"Kusumoto, M., Maehara, T., Kawarabayashi, K.: Scalable Similarity Search for SimRank. In: SIGMOD, pp 325\u2013336 (2014)","DOI":"10.1145\/2588555.2610526"},{"key":"925_CR13","doi-asserted-by":"crossref","unstructured":"Li, C., Han, J., He, G., Jin, X., Sun, Y., Yu, Y., Wu, T.: Fast Computation of SimRank for Static and Dynamic Information Networks. In: EDBT (2010)","DOI":"10.1145\/1739041.1739098"},{"key":"925_CR14","doi-asserted-by":"crossref","unstructured":"Li, L., Qian, L., Lee, V.E., Leng, M., Chen, M., Chen, X.: Fast and accurate computation of role similarity via vertex centrality. In: Li, J., Sun, Y. (eds.) WAI, volume 9098 of Lecture Notes in Computer Science, pp 123\u2013134. Springer (2015)","DOI":"10.1007\/978-3-319-21042-1_10"},{"key":"925_CR15","doi-asserted-by":"crossref","unstructured":"Li, P., Liu, H., Yu, J.X., He, J., Du, X.: Fast single-pair simrank computation. In: Proceedings of the SIAM International Conference on Data Mining, SDM 2010, April 29 - May 1, 2010, Columbus, Ohio, USA, pp 571\u2013582. SIAM (2010)","DOI":"10.1137\/1.9781611972801.50"},{"issue":"1","key":"925_CR16","first-page":"24","volume":"9","author":"Z Li","year":"2015","unstructured":"Li, Z., Fang, Y., Liu, Q., Cheng, J., Cheng, R., Lui, J.C.S.: Walking in the cloud: Parallel SimRank at scale. PVLDB 9(1), 24\u201335 (2015)","journal-title":"PVLDB"},{"issue":"1","key":"925_CR17","doi-asserted-by":"publisher","first-page":"4:1","DOI":"10.1145\/1326561.1326565","volume":"2","author":"Y Lin","year":"2008","unstructured":"Lin, Y., Sundaram, H., Chi, Y., Tatemura, J., Tseng, B.L.: Detecting splogs via temporal dynamics using self-similarity analysis. TWEB 2(1), 4:1\u20134:35 (2008)","journal-title":"TWEB"},{"issue":"1","key":"925_CR18","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1007\/s10115-011-0427-z","volume":"32","author":"Z Lin","year":"2012","unstructured":"Lin, Z., Lyu, M.R., King, I.: Matchsim: a novel similarity measure based on maximum neighborhood matching. Knowl. Inf. Syst. 32(1), 141\u2013166 (2012)","journal-title":"Knowl. Inf. Syst."},{"issue":"1","key":"925_CR19","first-page":"14","volume":"11","author":"Y Liu","year":"2017","unstructured":"Liu, Y., Zheng, B., He, X., Wei, Z., Xiao, X., Zheng, K., Lu, J.: ProbeSim: Scalable single-source and top-k simrank computations on dynamic graphs. PVLDB 11(1), 14\u201326 (2017)","journal-title":"PVLDB"},{"key":"925_CR20","doi-asserted-by":"crossref","unstructured":"Lizorkin, D., Velikhov, P., Grinev, M.N., Turdakov, D.: Accuracy estimate and optimization techniques for SimRank computation. VLDB J. 19(1) (2010)","DOI":"10.1007\/s00778-009-0168-8"},{"key":"925_CR21","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.ins.2020.12.046","volume":"556","author":"J Lu","year":"2021","unstructured":"Lu, J., Gong, Z., Yang, Y.: A matrix sampling approach for efficient SimRank computation. Inf. Sci. 556, 1\u201326 (2021)","journal-title":"Inf. Sci."},{"key":"925_CR22","doi-asserted-by":"crossref","unstructured":"Maehara, T., Kusumoto, M., Kawarabayashi, K.: Scalable Simrank Join Algorithm. In: ICDE, pp 603\u2013614 (2015)","DOI":"10.1109\/ICDE.2015.7113318"},{"key":"925_CR23","doi-asserted-by":"crossref","unstructured":"Rothe, S., Sch\u00fctze, H.: CoSimRank: A Flexible & Efficient Graph-Theoretic Similarity Measure. In: ACL, pages 1392\u20131402. The Association for Computer Linguistics (2014)","DOI":"10.3115\/v1\/P14-1131"},{"issue":"8","key":"925_CR24","first-page":"838","volume":"8","author":"Y Shao","year":"2015","unstructured":"Shao, Y., Cui, B., Chen, L., Liu, M., Xie, X.: An efficient similarity search framework for SimRank over large dynamic graphs. PVLDB 8(8), 838\u2013849 (2015)","journal-title":"PVLDB"},{"issue":"1","key":"925_CR25","doi-asserted-by":"publisher","first-page":"76","DOI":"10.1007\/s41019-019-0086-8","volume":"4","author":"Y Shao","year":"2019","unstructured":"Shao, Y., Liu, J., Shi, S., Zhang, Y., Cui, B.: Fast de-anonymization of social networks with structural information. Data Sci. Eng. 4(1), 76\u201392 (2019)","journal-title":"Data Sci. Eng."},{"key":"925_CR26","doi-asserted-by":"crossref","unstructured":"Tian, B., Xiao, X.: SLING: A Near-Optimal Index Structure for SimRank. In: SIGMOD, pp 1859\u20131874 (2016)","DOI":"10.1145\/2882903.2915243"},{"key":"925_CR27","doi-asserted-by":"crossref","unstructured":"Wang, H., Wei, Z., Yuan, Y., Du, X., Wen, J.: Exact single-source SimRank computation on large graphs. In: Maier, D., Pottinger, R., Doan, A., Tan, W., Alawini, A., Ngo, H.Q. (eds.) 653\u2013663. ACM (2020)","DOI":"10.1145\/3318464.3389781"},{"key":"925_CR28","doi-asserted-by":"crossref","unstructured":"Wang, Y., Lian, X., Chen, L., 545\u2013556: Efficient Simrank Tracking in Dynamic Graphs. In: ICDE (2018)","DOI":"10.1109\/ICDE.2018.00056"},{"key":"925_CR29","doi-asserted-by":"crossref","unstructured":"Wei, Z., He, X., Xiao, X., Wang, S., Liu, Y., Du, X., Wen, J.: PRSim: Sublinear time simrank computation on large power-law graphs. In: Boncz, P.A., Manegold, S., Ailamaki, A., Deshpande, A., Kraska, T. (eds.) SIGMOD, pp 1042\u20131059. ACM (2019)","DOI":"10.1145\/3299869.3319873"},{"key":"925_CR30","doi-asserted-by":"crossref","unstructured":"Xi, W., Fox, E.A., Fan, W., Zhang, B., Chen, Z., Yan, J., Zhuang, D.: Simfusion: Measuring Similarity Using Unified Relationship Matrix. In: SIGIR (2005)","DOI":"10.1145\/1076034.1076059"},{"key":"925_CR31","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1016\/j.ins.2015.07.036","volume":"326","author":"S Yoon","year":"2016","unstructured":"Yoon, S., Kim, S., Park, S.: C-rank: A link-based similarity measure for scientific literature databases. Inf. Sci. 326, 25\u201340 (2016)","journal-title":"Inf. Sci."},{"key":"925_CR32","unstructured":"Youngmann, B., Milo, T., Somech, A.: Boosting SimRank with Semantics. In: EDBT, pp 37\u201348 (2019)"},{"key":"925_CR33","doi-asserted-by":"crossref","unstructured":"Yu, W., Iranmanesh, S., Haldar, A., Zhang, M., Ferhatosmanoglu, H.: An Axiomatic Role Similarity Measure Based on Graph Topology. In: Software Foundations for Data Interoperability and Large Scale Graph Data Analytics, pp 33\u201348. Springer International Publishing (2020)","DOI":"10.1007\/978-3-030-61133-0_3"},{"key":"925_CR34","unstructured":"Yu, W., Lin, X., Zhang, W.: Towards Efficient SimRank Computation on Large Networks. In: ICDE, pp 601\u2013612 (2013)"},{"issue":"7","key":"925_CR35","doi-asserted-by":"publisher","first-page":"1810","DOI":"10.1109\/TKDE.2014.2339828","volume":"27","author":"W Yu","year":"2015","unstructured":"Yu, W., Lin, X., Zhang, W., McCann. J.A.: Fast all-pairs SimRank assessment on large graphs and bipartite domains. IEEE Trans. Knowl. Data Eng. 27 (7), 1810\u20131823 (2015)","journal-title":"IEEE Trans. Knowl. Data Eng."},{"issue":"1","key":"925_CR36","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1007\/s00778-017-0488-z","volume":"27","author":"W Yu","year":"2018","unstructured":"Yu, W., Lin, X., Zhang, W., McCann, J.A.: Dynamical SimRank search on time-varying networks. VLDB J. 27(1), 79\u2013104 (2018)","journal-title":"VLDB J."},{"issue":"3","key":"925_CR37","doi-asserted-by":"publisher","first-page":"401","DOI":"10.1007\/s00778-018-0536-3","volume":"28","author":"W Yu","year":"2019","unstructured":"Yu, W., Lin, X., Zhang, W., Pei, J., McCann, J.A.: SimRank*: Effective and scalable pairwise similarity search based on graph topology. VLDB J. 28(3), 401\u2013426 (2019)","journal-title":"VLDB J."},{"key":"925_CR38","doi-asserted-by":"crossref","unstructured":"Yu, W., Lin, X., Zhang, W., Zhang, Y., Le, J.: Simfusion+: Extending SimFusion Towards Efficient Estimation on Large and Dynamic Networks. In: SIGIR, pp 365\u2013374 (2012)","DOI":"10.1145\/2348283.2348334"},{"issue":"5","key":"925_CR39","first-page":"569","volume":"8","author":"W Yu","year":"2015","unstructured":"Yu, W., McCann, J.A.: Efficient partial-pairs SimRank search for large networks. PVLDB 8(5), 569\u2013580 (2015)","journal-title":"PVLDB"},{"key":"925_CR40","doi-asserted-by":"crossref","unstructured":"Yu, W., Wang, F.: Fast Exact CoSimRank Search on Evolving and Static Graphs. In: WWW, pp 599\u2013608 (2018)","DOI":"10.1145\/3178876.3186126"},{"key":"925_CR41","doi-asserted-by":"crossref","unstructured":"Zhao, P., Han, J., Sun, Y.: P-Rank: A Comprehensive Structural Similarity Measure over Information Networks. In: CIKM (2009)","DOI":"10.1145\/1645953.1646025"},{"key":"925_CR42","doi-asserted-by":"crossref","unstructured":"Zhu, R., Zou, Z., Li, J.: Simrank Computation on Uncertain Graphs. In: ICDE, pp 565\u2013576 (2016)","DOI":"10.1109\/ICDE.2016.7498271"}],"container-title":["World Wide Web"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11280-021-00925-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11280-021-00925-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11280-021-00925-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,3,1]],"date-time":"2022-03-01T11:19:41Z","timestamp":1646133581000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11280-021-00925-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,8,11]]},"references-count":42,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,3]]}},"alternative-id":["925"],"URL":"https:\/\/doi.org\/10.1007\/s11280-021-00925-z","relation":{},"ISSN":["1386-145X","1573-1413"],"issn-type":[{"value":"1386-145X","type":"print"},{"value":"1573-1413","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,8,11]]},"assertion":[{"value":"4 February 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 May 2021","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 July 2021","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 August 2021","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}