{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,8]],"date-time":"2026-02-08T18:45:10Z","timestamp":1770576310845,"version":"3.49.0"},"reference-count":54,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2014,2,1]],"date-time":"2014-02-01T00:00:00Z","timestamp":1391212800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Knowl. Discov. Data"],"published-print":{"date-parts":[[2014,2]]},"abstract":"<jats:p>\n            A key task in analyzing social networks and other complex networks is role analysis: describing and categorizing nodes according to how they interact with other nodes. Two nodes have the same role if they interact with\n            <jats:italic>equivalent<\/jats:italic>\n            sets of neighbors. The most fundamental role equivalence is automorphic equivalence. Unfortunately, the fastest algorithms known for graph automorphism are nonpolynomial. Moreover, since exact equivalence is rare, a more meaningful task is measuring the role\n            <jats:italic>similarity<\/jats:italic>\n            between any two nodes. This task is closely related to the structural or link-based similarity problem that SimRank addresses. However, SimRank and other existing similarity measures are not sufficient because they do not guarantee to recognize automorphically or structurally equivalent nodes. This article makes two contributions. First, we present and justify several axiomatic properties necessary for a role similarity measure or metric. Second, we present RoleSim, a new similarity metric that satisfies these axioms and can be computed with a simple iterative algorithm. We rigorously prove that RoleSim satisfies all of these axiomatic properties. We also introduce Iceberg RoleSim, a scalable algorithm that discovers all pairs with RoleSim scores above a user-defined threshold \u03b8. We demonstrate the interpretative power of RoleSim on both both synthetic and real datasets.\n          <\/jats:p>","DOI":"10.1145\/2518176","type":"journal-article","created":{"date-parts":[[2014,3,11]],"date-time":"2014-03-11T12:10:30Z","timestamp":1394539830000},"page":"1-37","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":22,"title":["Scalable and axiomatic ranking of network role similarity"],"prefix":"10.1145","volume":"8","author":[{"given":"Ruoming","family":"Jin","sequence":"first","affiliation":[{"name":"Kent State University, Kent, OH"}]},{"given":"Victor E.","family":"Lee","sequence":"additional","affiliation":[{"name":"John Carroll University"}]},{"given":"Longjie","family":"Li","sequence":"additional","affiliation":[{"name":"Lanzhou University"}]}],"member":"320","published-online":{"date-parts":[[2014,2]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453903"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230130404"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/0378-8733(92)90016-Z"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.2307\/270991"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/0378-8733(93)90012-A"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2009.136"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0701175104"},{"key":"e_1_2_1_8_1","volume-title":"3rd Revised and Enlarged Edition","author":"Cvetkov\u00edc Dragos M.","unstructured":"Dragos M. Cvetkov\u00edc , Michael Doob , and Horst Sachs . 1998. Spectra of Graphs: Theory and Applications , 3rd Revised and Enlarged Edition . Wiley . Dragos M. Cvetkov\u00edc, Michael Doob, and Horst Sachs. 1998. Spectra of Graphs: Theory and Applications, 3rd Revised and Enlarged Edition. Wiley."},{"key":"e_1_2_1_9_1","doi-asserted-by":"crossref","unstructured":"Patrick Doreian Vladimir Batagelj and Anu\u0161ka Ferligoj. 2005. Generalized Blockmodeling. Vol. 25. Cambridge University Press.  Patrick Doreian Vladimir Batagelj and Anu\u0161ka Ferligoj. 2005. Generalized Blockmodeling. Vol. 25. Cambridge University Press.","DOI":"10.1017\/CBO9780511584176"},{"key":"e_1_2_1_10_1","volume-title":"IEEE Int. Conf. Software Maintenance (ICSM). IEEE, 567--570","author":"Dragan Natalia","unstructured":"Natalia Dragan , Michael L. Collard , and Jonathan I. Maletic . 2009. Using method stereotype distribution as a signature descriptor for software systems . In IEEE Int. Conf. Software Maintenance (ICSM). IEEE, 567--570 . Natalia Dragan, Michael L. Collard, and Jonathan I. Maletic. 2009. Using method stereotype distribution as a signature descriptor for software systems. In IEEE Int. Conf. Software Maintenance (ICSM). IEEE, 567--570."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/0378-8733(95)00286-3"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060745.1060839"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.2307\/3033543"},{"key":"e_1_2_1_15_1","volume-title":"Algebraic Graph Theory","author":"Godsil Chris","unstructured":"Chris Godsil and Gordon Royle . 2001. Algebraic Graph Theory . Springer-Verlag . Chris Godsil and Gordon Royle. 2001. Algebraic Graph Theory. Springer-Verlag."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0020818309090195"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1098\/rsif.2005.0046"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/775047.775126"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03348-3_19"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2020408.2020561"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1002\/asi.5090140103"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1002\/nav.3800020109"},{"key":"e_1_2_1_23_1","volume-title":"Managing and Mining Graph Data","author":"Lee Victor E.","unstructured":"Victor E. Lee , Ning Ruan , Ruoming Jin , and Charu Aggarwal . 2010. Managing and Mining Graph Data . Springer , Chapter 10: A survey of algorithms for dense subgraph discovery, 303--336. Victor E. Lee, Ning Ruan, Ruoming Jin, and Charu Aggarwal. 2010. Managing and Mining Graph Data. Springer, Chapter 10: A survey of algorithms for dense subgraph discovery, 303--336."},{"key":"e_1_2_1_24_1","first-page":"2","article-title":"Vertex similarity in networks","volume":"73","author":"Leicht E. A.","year":"2005","unstructured":"E. A. Leicht , Petter Holme , and Mark E. J. Newman . 2005 . Vertex similarity in networks . Phys. Rev. E 73 , 2 , 026120. E. A. Leicht, Petter Holme, and Mark E. J. Newman. 2005. Vertex similarity in networks. Phys. Rev. E 73, 2, 026120.","journal-title":"Phys. Rev. E"},{"key":"e_1_2_1_25_1","unstructured":"Michael Ley Marc Herbstritt Marcel R. Ackermann Oliver Hoffmann Michael Wagner Stefanie von Keutz Katharina Hostert and Doris Holztr\u00e4ger. 2012. The DBLP Computer Science Bibliography. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik. http:\/\/www.informatik.uni-trier.de\/&sim;ley\/db\/.  Michael Ley Marc Herbstritt Marcel R. Ackermann Oliver Hoffmann Michael Wagner Stefanie von Keutz Katharina Hostert and Doris Holztr\u00e4ger. 2012. The DBLP Computer Science Bibliography. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik. http:\/\/www.informatik.uni-trier.de\/&sim;ley\/db\/."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-01307-2_36"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/WI.2006.127"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/WI.2007.54"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1645953.1646185"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453904"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1080\/0022250X.1971.9989788"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1006\/jtbi.2003.3147"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2008.04.008"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0378-8733(02)00036-9"},{"key":"e_1_2_1_35_1","volume-title":"Congressus Numerantium 30","author":"McKay B. D.","year":"1981","unstructured":"B. D. McKay . 1981 . Practical graph isomorphism . Congressus Numerantium 30 , 45--87. B. D. McKay. 1981. Practical graph isomorphism. Congressus Numerantium 30, 45--87."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/IV.2008.10"},{"key":"e_1_2_1_37_1","unstructured":"Microsoft Research. 2012. Microsoft academic search. http:\/\/academic.research.microsoft.com\/RankList&quest; entitytype=2&topdomainid=2&subdomainid=7. (2012). Accessed August 2012.  Microsoft Research. 2012. Microsoft academic search. http:\/\/academic.research.microsoft.com\/RankList&quest; entitytype=2&topdomainid=2&subdomainid=7. (2012). Accessed August 2012."},{"key":"e_1_2_1_38_1","unstructured":"Mark Newman. 2006. Internet network. http:\/\/www-personal.umich.edu\/&sim;mejn\/netdata\/.  Mark Newman. 2006. Internet network. http:\/\/www-personal.umich.edu\/&sim;mejn\/netdata\/."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0307545100"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1177\/016555150202800601"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190010410"},{"key":"e_1_2_1_43_1","volume-title":"Proc. DARPA Broadcast News Workshop. Morgan Kaufmann, 189--192","author":"Schultz Michael","year":"1999","unstructured":"Michael Schultz and Mark Liberman . 1999 . Topic detection and tracking using idf-weighted cosine coefficient . In Proc. DARPA Broadcast News Workshop. Morgan Kaufmann, 189--192 . Michael Schultz and Mark Liberman. 1999. Topic detection and tracking using idf-weighted cosine coefficient. In Proc. DARPA Broadcast News Workshop. Morgan Kaufmann, 189--192."},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1002\/asi.4630240406"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1016\/0378-8733(93)90003-4"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/1367497.1367722"},{"key":"e_1_2_1_47_1","first-page":"3","article-title":"An elementary mathematical theory of classification and prediction","volume":"6","author":"Tanimoto T. T.","year":"1958","unstructured":"T. T. Tanimoto . 1958 . An elementary mathematical theory of classification and prediction . IBM Taxonomy Application M. A. 6 , 3 . T. T. Tanimoto. 1958. An elementary mathematical theory of classification and prediction. IBM Taxonomy Application M. A. 6, 3.","journal-title":"IBM Taxonomy Application M. A."},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/GLOCOM.2001.965863"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1987.10478385"},{"key":"e_1_2_1_50_1","volume-title":"Social Network Analysis: Methods and Applications","author":"Wasserman Stanley","unstructured":"Stanley Wasserman and Katherine Faust . 1994. Social Network Analysis: Methods and Applications . Cambridge University Press . Stanley Wasserman and Katherine Faust. 1994. Social Network Analysis: Methods and Applications. Cambridge University Press."},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1016\/0378-8733(83)90025-4"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1086\/226141"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/1076034.1076059"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1002\/asi.v60:10"},{"key":"e_1_2_1_55_1","volume-title":"Proc. 32nd Int. Conf. Very Large Data Bases (VLDB). VLDB Endowment, 427--438","author":"Yin Xiaoxin","unstructured":"Xiaoxin Yin , Jiawei Han , and Philip S. Yu . 2006. LinkClus: Efficient clustering via heterogeneous semantic links . In Proc. 32nd Int. Conf. Very Large Data Bases (VLDB). VLDB Endowment, 427--438 . Xiaoxin Yin, Jiawei Han, and Philip S. Yu. 2006. LinkClus: Efficient clustering via heterogeneous semantic links. In Proc. 32nd Int. Conf. Very Large Data Bases (VLDB). VLDB Endowment, 427--438."},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/1645953.1646025"}],"container-title":["ACM Transactions on Knowledge Discovery from Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2518176","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2518176","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:14:13Z","timestamp":1750277653000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2518176"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,2]]},"references-count":54,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2014,2]]}},"alternative-id":["10.1145\/2518176"],"URL":"https:\/\/doi.org\/10.1145\/2518176","relation":{},"ISSN":["1556-4681","1556-472X"],"issn-type":[{"value":"1556-4681","type":"print"},{"value":"1556-472X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,2]]},"assertion":[{"value":"2012-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-08-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-02-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}