{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,7]],"date-time":"2025-06-07T00:40:04Z","timestamp":1749256804482,"version":"3.41.0"},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2025,6,6]],"date-time":"2025-06-06T00:00:00Z","timestamp":1749168000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,6,6]],"date-time":"2025-06-06T00:00:00Z","timestamp":1749168000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["SN COMPUT. SCI."],"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>This study presents a novel algorithm, , for single-source role similarity search, designed to capture nuanced topological features within graphs more effectively than existing methods. Traditional role-based similarity algorithms like  are proficient at identifying automorphic equivalences but often fail to distinguish nodes with structural differences despite their automorphic similarities. By incorporating a technique that utilizes the top <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$\\Gamma$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>\u0393<\/mml:mi>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula> maximum similarity matching,  enhances the fidelity of role similarity evaluations by considering a broader range of adjacency relationships. This approach not only ensures the accurate identification of automorphic and structural equivalences but also adheres to key mathematical properties such as uniqueness, symmetry, boundedness, and triangular inequality. We also introduce an accelerated variant of , named _, which employs innovative computational strategies to improve efficiency, particularly in dynamic environments. Experimental validations on several real-world datasets demonstrate that  and _ outperform standard benchmarks in both accuracy and computational speed, offering substantial improvements for applications in diverse domains like social network analysis and complex network management. This work contributes significant theoretical and practical advancements to the field of graph-based similarity search, laying a foundation for future explorations into dynamic graph analytics.<\/jats:p>","DOI":"10.1007\/s42979-025-04038-6","type":"journal-article","created":{"date-parts":[[2025,6,6]],"date-time":"2025-06-06T12:12:03Z","timestamp":1749211923000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["FaRS: A Performance-Driven Approach to Role Similarity in Graphs"],"prefix":"10.1007","volume":"6","author":[{"given":"Fan","family":"Wang","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Weiren","family":"Yu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4192-5363","authenticated-orcid":false,"given":"Hai","family":"Wang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Victor","family":"Chang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,6,6]]},"reference":[{"key":"4038_CR1","unstructured":"Rao, PN, Devi T, Kaladhar D, Sridhar G, Rao AA. A probabilistic neural network approach for protein superfamily classification. J Theor Appl Inf Technol. 2009;101\u20135."},{"key":"4038_CR2","doi-asserted-by":"crossref","unstructured":"Shahabi C, Banaei-Kashani F, Chen YS, McLeod D. Yoda: an accurate and scalable web-based recommendation system. In: International conference on cooperative information systems, Springer, 2001. p. 418\u2013 32.","DOI":"10.1007\/3-540-44751-2_31"},{"key":"4038_CR3","doi-asserted-by":"crossref","unstructured":"Yang R. Efficient and effective similarity search over bipartite graphs. In: Proceedings of the ACM web conference; 2022. p. 308\u2013 318","DOI":"10.1145\/3485447.3511959"},{"key":"4038_CR4","doi-asserted-by":"crossref","unstructured":"Wang, Y., Lian, X., Chen, L. Efficient simrank tracking in dynamic graphs. In: 2018 IEEE 34th international conference on data engineering (ICDE). IEEE; 2018. p. 545\u2013 56.","DOI":"10.1109\/ICDE.2018.00056"},{"key":"4038_CR5","doi-asserted-by":"crossref","unstructured":"Li L, Qian L, Lee VE, Leng M, Chen M, Chen X. Fast and accurate computation of role similarity via vertex centrality. In: International conference on web-age information management. Springer; 2015. p. 123\u201334.","DOI":"10.1007\/978-3-319-21042-1_10"},{"issue":"4","key":"4038_CR6","doi-asserted-by":"publisher","first-page":"353","DOI":"10.1016\/0378-8733(85)90013-9","volume":"7","author":"MG Everett","year":"1985","unstructured":"Everett MG. Role similarity and complexity in social networks. Soc Netw. 1985;7(4):353\u20139.","journal-title":"Soc Netw"},{"key":"4038_CR7","doi-asserted-by":"crossref","unstructured":"Rothe S, Sch\u00fctze H. Cosimrank: a flexible & efficient graph-theoretic similarity measure. In: Proceedings of the 52nd annual meeting of the association for computational linguistics (Vol. 1: Long Papers); 2014. p. 1392\u2013402.","DOI":"10.3115\/v1\/P14-1131"},{"key":"4038_CR8","doi-asserted-by":"crossref","unstructured":"Diao L, Wang H, Alsarra S, Yen I-L, Bastani F. A smart role mapping recommendation system. In: 2019 IEEE 43rd annual computer software and applications conference (COMPSAC). IEEE. 2019; vol. 2. p. 135\u201340.","DOI":"10.1109\/COMPSAC.2019.10196"},{"key":"4038_CR9","doi-asserted-by":"publisher","unstructured":"Wang F, Yu W, Wang H, Chang V. FaRS: a high-performance automorphism-aware algorithm for graph similarity matching. In: Proceedings of the 9th international conference on complexity, future information systems and risk\u2014Volume 1: COMPLEXIS. 2024. p. 17\u201329. SciTePress. INSTICC. https:\/\/doi.org\/10.5220\/0012724000003708.","DOI":"10.5220\/0012724000003708"},{"issue":"1","key":"4038_CR10","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. 2019;4(1):76\u201392.","journal-title":"Data Sci Eng"},{"issue":"3","key":"4038_CR11","doi-asserted-by":"publisher","first-page":"471","DOI":"10.1007\/s00778-021-00654-9","volume":"30","author":"X Chen","year":"2021","unstructured":"Chen X, Lai L, Qin L, Lin X. Efficient structural node similarity computation on billion-scale graphs. VLDB J. 2021;30(3):471\u201393.","journal-title":"VLDB J"},{"key":"4038_CR12","doi-asserted-by":"crossref","unstructured":"Chen X, Lai L, Qin L, Lin X. Structsim: querying structural node similarity at billion scale. In: 2020 IEEE 36th international conference on data engineering (ICDE). IEEE; 2020. p. 1950\u2013953.","DOI":"10.1109\/ICDE48307.2020.00211"},{"issue":"13","key":"4038_CR13","doi-asserted-by":"publisher","first-page":"6811","DOI":"10.3390\/app12136811","volume":"12","author":"J Kim","year":"2022","unstructured":"Kim J, Jeong S, Lim S. Link pruning for community detection in social networks. Appl Sci. 2022;12(13):6811.","journal-title":"Appl Sci"},{"issue":"1","key":"4038_CR14","doi-asserted-by":"publisher","first-page":"0296185","DOI":"10.1371\/journal.pone.0296185","volume":"19","author":"V Carchiolo","year":"2024","unstructured":"Carchiolo V, Grassia M, Malgeri M, Mangioni G. Geometric deep learning sub-network extraction for maximum clique enumeration. PLoS ONE. 2024;19(1):0296185.","journal-title":"PLoS ONE"},{"key":"4038_CR15","doi-asserted-by":"crossref","unstructured":"Long Y, Liu C-H, Shuai D, Zhang F-G. Image segmentation of canola based on color similarity in color space. In: Proceedings of the 2nd international conference on computer science and application engineering; 2018. p. 1\u20136.","DOI":"10.1145\/3207677.3278078"},{"key":"4038_CR16","doi-asserted-by":"crossref","unstructured":"Zeng J, Hao Z, Tang X, Zhao C. Data forwarding at intersections in vehicular social networks. In: Proceedings of the 6th international conference on computer science and application engineering; 2022. p. 1\u2013 7","DOI":"10.1145\/3565387.3565435"},{"key":"4038_CR17","unstructured":"Ribeiro LF, Saverese PH, Figueiredo DR. struc2vec: learning node representations from structural identity. In: Proceedings of the 23rd ACM SIGKDD international conference on knowledge discovery and data mining; 2017. p. 385\u201394."},{"key":"4038_CR18","unstructured":"Bao Q, Zhang Z. Role similarity metric based on spanning rooted forest. arXiv preprint arXiv:2110.07872 (2021)."},{"issue":"5","key":"4038_CR19","doi-asserted-by":"publisher","first-page":"411","DOI":"10.1177\/0037549718776368","volume":"95","author":"Y Bouanan","year":"2019","unstructured":"Bouanan Y, Zacharewicz G, Ribault J, Vallespir B. Discrete event system specification-based framework for modeling and simulation of propagation phenomena in social networks: application to the information spreading in a multi-layer social network. Simulation. 2019;95(5):411\u201327.","journal-title":"Simulation"},{"issue":"3","key":"4038_CR20","doi-asserted-by":"publisher","first-page":"364","DOI":"10.1137\/0138030","volume":"38","author":"M Yannakakis","year":"1980","unstructured":"Yannakakis M, Gavril F. Edge dominating sets in graphs. SIAM J Appl Math. 1980;38(3):364\u201372.","journal-title":"SIAM J Appl Math"},{"issue":"2","key":"4038_CR21","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1006\/jagm.2001.1167","volume":"40","author":"HN Gabow","year":"2001","unstructured":"Gabow HN, Kaplan H, Tarjan RE. Unique maximum matching algorithms. J Algorithms. 2001;40(2):159\u201383.","journal-title":"J Algorithms"},{"issue":"3","key":"4038_CR22","doi-asserted-by":"publisher","first-page":"682","DOI":"10.1287\/opre.16.3.682","volume":"16","author":"KG Murty","year":"1968","unstructured":"Murty KG. An algorithm for ranking all the assignments in order of increasing cost. Oper Res. 1968;16(3):682\u20137.","journal-title":"Oper Res"},{"key":"4038_CR23","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: Proceedings of the 13th international conference on extending database technology; 2010. p. 465\u201376.","DOI":"10.1145\/1739041.1739098"},{"key":"4038_CR24","doi-asserted-by":"crossref","unstructured":"Yu W, Lin X, Zhang W. Fast incremental simrank on link-evolving graphs. In: 2014 IEEE 30th international conference on data engineering. IEEE; 2014. p. 304\u201315.","DOI":"10.1109\/ICDE.2014.6816660"},{"key":"4038_CR25","doi-asserted-by":"crossref","unstructured":"Yu W, Wang F. Fast exact cosimrank search on evolving and static graphs. In: Proceedings of the 2018 world wide web conference; 2018. p. 599\u2013608.","DOI":"10.1145\/3178876.3186126"},{"key":"4038_CR26","unstructured":"Lee VE. Rolesim and rolematch: role-based similarity and graph matching. Technical report, Kent State University (2012)"},{"key":"4038_CR27","unstructured":"Arthur D, Vassilvitskii S. k-means++: the advantages of careful seeding. Technical report, Stanford (2006)"},{"issue":"2","key":"4038_CR28","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1109\/TIT.1982.1056489","volume":"28","author":"S Lloyd","year":"1982","unstructured":"Lloyd S. Least squares quantization in PCM. IEEE Trans Inf Theory. 1982;28(2):129\u201337.","journal-title":"IEEE Trans Inf Theory"},{"key":"4038_CR29","doi-asserted-by":"crossref","unstructured":"Bock H-H. Clustering methods: a history of k-means algorithms. Selected contributions in data analysis and classification; 2007. p. 161\u201372.","DOI":"10.1007\/978-3-540-73560-1_15"},{"key":"4038_CR30","unstructured":"Wang, Y., Wang, L., Li, Y., He, D., Liu, T.-Y.: A theoretical analysis of NDCG type ranking measures. In: Conference on learning theory. PMLR; 2013. p. 25\u2013 54."}],"container-title":["SN Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s42979-025-04038-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s42979-025-04038-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s42979-025-04038-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,7]],"date-time":"2025-06-07T00:02:00Z","timestamp":1749254520000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s42979-025-04038-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,6]]},"references-count":30,"journal-issue":{"issue":"5","published-online":{"date-parts":[[2025,6]]}},"alternative-id":["4038"],"URL":"https:\/\/doi.org\/10.1007\/s42979-025-04038-6","relation":{},"ISSN":["2661-8907"],"issn-type":[{"value":"2661-8907","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,6,6]]},"assertion":[{"value":"11 November 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 May 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 June 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"There is not any Conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}},{"value":"Not applicable.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethical Approval"}}],"article-number":"524"}}