[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
10.1145/2020408.2020561acmconferencesArticle/Chapter ViewAbstractPublication PageskddConference Proceedingsconference-collections
poster

Axiomatic ranking of network role similarity

Published: 21 August 2011 Publication History

Abstract

A key task in analyzing social networks and other complex networks is role analysis: describing and categorizing nodes by how they interact with other nodes. Two nodes have the same role if they interact with equivalent sets of neighbors. The most fundamental role equivalence is automorphic equivalence. Unfortunately, the fastest algorithm known for graph automorphism is nonpolynomial. Moreover, since exact equivalence is rare, a more meaningful task is measuring the role similarity between any two nodes. This task is closely related to the link-based similarity problem that SimRank addresses. However, SimRank and other existing simliarity measures are not sufficient because they do not guarantee to recognize automorphically or structurally equivalent nodes. This paper makes two contributions. First, we present and justify several axiomatic properties necessary for a role similarity measure or metric. Second, we present RoleSim, a role similarity metric which satisfies these axioms and which can be computed with a simple iterative algorithm. We rigorously prove that RoleSim satisfies all the axiomatic properties and demonstrate its superior interpretative power on both synthetic and real datasets.

References

[1]
Ioannis Antonellis, Hector Garcia-Molina, and Chi-Chao Chang. Simrank: query rewriting through link analysis of the clickgraph (poster). In WWW'08, pages 1177--1178, 2008.
[2]
D. Avis. A survey of heuristics for the weighted matching problem. Network, 13:475--493, 1983.
[3]
Vladimir Batagelj, Patrick Doreian, and Anuska Ferligoj. An optimizational approach to regular equivalence. Social Networks, 14:121--135, 1992.
[4]
Stephen P. Borgatti and Martin G. Everett. Notions of position in social network analysis. Sociological Methodology, 22:1--35, 1992.
[5]
Stephen P. Borgatti and Martin G. Everett. Two algorithms for computing regular equivalence. Social Networks, 15:361--376, 1993.
[6]
Shai Carmi, Shlomo Havlin, Scott Kirkpatrick, Yuval Shavitt, and Eran Shir. A model of internet topology using k-shell decomposition. PNAS, 104(27):11150--11154, July 2007.
[7]
Dragos M. Cvetkovíc, Michael Doob, and Horst Sachs. Spectra of Graphs: Theory and Applications, 3rd Revised and Enlarged Edition. Wiley, 1998.
[8]
Natalia Dragan, Michael L. Collard, and Jonathan I. Maletic. Using method stereotype distribution as a signature descriptor for software systems. In ICSM, pages 567--570, 2009.
[9]
Martin G. Everett. Role similarity and complexity in social networks. Social Networks, 7:353--359, 1985.
[10]
Martin G. Everett and Stephen P. Borgatti. Exact colorations of graphs and digraphs. Social Networks, 18:319--331, 1996.
[11]
M.G. Everett and S. P. Borgatti. Regular equivalence: General theory. J. Mathematical Sociology, 19:29--52, 1994.
[12]
Dániel Fogaras and Balázs Rácz. Scaling link-based similarity search. In WWW'05, pages 641--650, 2005.
[13]
Scott Fortin. The graph isomorphism problem. Technical Report TR 96--20, Dept. Computer Science, Univ. of Alberta, Edmonton, Alberta, Canada, July 1996.
[14]
C. Godsil and G. Royle. Algebraic Graph Theory. Springer-Verlag, New York, 2001.
[15]
E.M. Hafner-Burton, M. Kahler, and A.H. Montgomery. Network analysis for international relations. International Organization, 63(03):559--592, 2009.
[16]
Taher H. Haveliwala. Topic-sensitive pagerank: A context-sensitive ranking algorithm for web search. IEEE Trans. on Knowl. and Data Eng., 15(4):784--796, 2003.
[17]
Petter Holme and Mikael Huss. Role-similarity based functional prediction in networked systems: application to the yeast proteome. J. R. Soc. Interface, 2(4):327--33, 2005.
[18]
Glen Jeh and Jennifer Widom. Simrank: a measure of structural-context similarity. In KDD'02, pages 538--543, 2002.
[19]
Ruoming Jin, Victor E. Lee, and Hui Hong. Axiomatic ranking of network role similarity. Technical Report arXiv:1102.3937, http://arXiv.org, 2011.
[20]
M. M. Kessler. Bibliographic coupling between scientific papers. American Documentation, 14(1):10--25, 1963.
[21]
E. A. Leicht, Petter Holme, and M. E. J. Newman. Vertex similarity in networks. Phys. Rev. E, 73:026120, 2005.
[22]
Pei Li, Yuanzhe Cai, Hongyan Liu, Jun He, and Xiaoyong Du. Exploiting the block structure of link graph for efficient similarity computation. In PAKDD'09, pages 389--400, 2009.
[23]
Zhenjiang Lin, Michael R. Lyu, and Irwin King. Matchsim: a novel neighbor-based similarity measure with maximum neighborhood matching. In CIKM'09, pages 1613--1616, 2009.
[24]
F. P. Lorrain and H. C. White. Structural equivalence of individuals in networks. J. Math. Sociology, 1:49--80, 1971.
[25]
Wangzhong Lu, Jeannette Janssen, Evangelos Milios, and Nathalie Japkowicz. Node similarity in networked information spaces. In CASCON'01, pages 11--25, 2001.
[26]
J. J. Luczkovich, S.P. Borgatti, J.C. Johnson, and M.G. Everett. Defining and measuring trophic role similarity in food webs using regular coloration. J. Theoretical Biology, 220:303--321, 2003.
[27]
Ben D. MacArthur, Rubén J. Sánchez-García, and James W. Anderson. Note: Symmetry in complex networks. Discrete Appl. Math., 156(18):3525--3531, 2008.
[28]
Maarten Marx and Michael Masuch. Regular equivalence and dynamic logic. Social Networks, 25(1):51--65, 2003.
[29]
B.D. McKay. Practical graph isomorphism. Congressus Numerantium, 30:45--87, 1981.
[30]
Guy Melançon and Arnaud Sallaberry. Edge metrics for visual graph analytics: A comparative study. In Proc. 12th Int'l Conf. Inform. Visual., pages 610--615, 2008.
[31]
Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry Winograd. The pagerank citation ranking: Bringing order to the web. Technical Report SIDL-WP-1999-0120, Stanford Univ., 1999.
[32]
Ronald Read and Derek Corneil. The graph isomorphism disease. J. Graph Theory, 1:339--363, 1977.
[33]
Lee Douglas Sailer. Structure equivalence: meaning and definition, computation and application. Social Networks, 1:73--80, 1978.
[34]
Henry Small. Co-citation in the scientific literature: A new measure of the relationship between two documents. J. Amer. Soc. Information Sci., 24:265--269, 1973.
[35]
Malcolm K. Sparrow. A linear algorithm for computing automorphic equivalence classes: the numerical signatures approach. Social Networks, 15(2):151--170, 1993.
[36]
Jie Tang, Jing Zhang, Limin Yao, and Juanzi Li. Extraction and mining of an academic social network. In WWW'08, pages 1193--1194, New York, 2008. ACM.
[37]
T. T. Tanimoto. An elementary mathematical theory of classification and prediction. IBM Taxonomy Application M. and A.6, 3, Nov. 1958.
[38]
Sudhir L. Tauro, Georgos Siganos, C. Palmer, and Michalis Faloutsos. A simple conceptual model for the internet topology. In Proc. IEEE Global Telecomm. Conf., pages 1667--1671, 2001.
[39]
Y.J. Wang and G.Y. Wong. Stochastic blockmodels for directed graphs. J. Amer.Stat. Assoc., 82(397):8--19, 1987.
[40]
Stanley Wasserman and Katherine Faust. Social network analysis: methods and applications. Cambridge University Press, 1994.
[41]
Douglas R. White and Karl P. Reitz. Graph and semigroup homomorphisms on networks of relations. Social Networks, 5:193--234, 1983.
[42]
Harrison White, Scott Boorman, and Ronald Breiger. Social structure from multiple networks. i: Blockmodels of roles and positions. Am. J. Sociology, 81:730--780, 1976.
[43]
Wensi Xi, Edward A. Fox, Weiguo Fan, Benyu Zhang, Zheng Chen, Jun Yan, and Dong Zhuang. Simfusion: measuring similarity using unified relationship matrix. In SIGIR'05, pages 130--137, 2005.
[44]
Xiaoxin Yin, Jiawei Han, and Philip S. Yu. Linkclus: efficient clustering via heterogeneous semantic links. In VLDB'06, pages 427--438, 2006.
[45]
Peixiang Zhao, Jiawei Han, and Yizhou Sun. P-rank: a comprehensive structural similarity measure over information networks. In CIKM'09, pages 553--562, 2009.

Cited By

View all
  • (2024)StructSim: Meta-Structure-Based Similarity Measure in Heterogeneous Information NetworksApplied Sciences10.3390/app1402093514:2(935)Online publication date: 22-Jan-2024
  • (2023)ClipSim: A GPU-friendly Parallel Framework for Single-Source SimRank with Accuracy GuaranteeProceedings of the ACM on Management of Data10.1145/35887071:1(1-26)Online publication date: 30-May-2023
  • (2023)Role Discovery-Guided Network Embedding Based on Autoencoder and Attention MechanismIEEE Transactions on Cybernetics10.1109/TCYB.2021.309489353:1(365-378)Online publication date: Jan-2023
  • Show More Cited By

Index Terms

  1. Axiomatic ranking of network role similarity

    Recommendations

    Comments

    Please enable JavaScript to view thecomments powered by Disqus.

    Information & Contributors

    Information

    Published In

    cover image ACM Conferences
    KDD '11: Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining
    August 2011
    1446 pages
    ISBN:9781450308137
    DOI:10.1145/2020408
    Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

    Sponsors

    Publisher

    Association for Computing Machinery

    New York, NY, United States

    Publication History

    Published: 21 August 2011

    Permissions

    Request permissions for this article.

    Check for updates

    Author Tags

    1. automorphic equivalence
    2. complex network
    3. ranking
    4. role similarity
    5. social network
    6. vertex similarity

    Qualifiers

    • Poster

    Conference

    KDD '11
    Sponsor:

    Acceptance Rates

    Overall Acceptance Rate 1,133 of 8,635 submissions, 13%

    Upcoming Conference

    KDD '25

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)18
    • Downloads (Last 6 weeks)5
    Reflects downloads up to 01 Jan 2025

    Other Metrics

    Citations

    Cited By

    View all
    • (2024)StructSim: Meta-Structure-Based Similarity Measure in Heterogeneous Information NetworksApplied Sciences10.3390/app1402093514:2(935)Online publication date: 22-Jan-2024
    • (2023)ClipSim: A GPU-friendly Parallel Framework for Single-Source SimRank with Accuracy GuaranteeProceedings of the ACM on Management of Data10.1145/35887071:1(1-26)Online publication date: 30-May-2023
    • (2023)Role Discovery-Guided Network Embedding Based on Autoencoder and Attention MechanismIEEE Transactions on Cybernetics10.1109/TCYB.2021.309489353:1(365-378)Online publication date: Jan-2023
    • (2023)Hierarchical All-Pairs SimRank CalculationDatabase Systems for Advanced Applications10.1007/978-3-031-30675-4_17(252-268)Online publication date: 15-Apr-2023
    • (2023)Integrating Higher-Order Features for Structural Role DiscoveryMobile Multimedia Communications10.1007/978-3-031-23902-1_19(244-258)Online publication date: 1-Feb-2023
    • (2022)Scaling High-Quality Pairwise Link-Based Similarity Retrieval on Billion-Edge GraphsACM Transactions on Information Systems10.1145/349520940:4(1-45)Online publication date: 11-Jan-2022
    • (2022)A Survey on Role-Oriented Network EmbeddingIEEE Transactions on Big Data10.1109/TBDATA.2021.31316108:4(933-952)Online publication date: 1-Aug-2022
    • (2022)Estimating Node Importance Values in Heterogeneous Information Networks2022 IEEE 38th International Conference on Data Engineering (ICDE)10.1109/ICDE53745.2022.00068(846-858)Online publication date: May-2022
    • (2022)Role-Oriented Dynamic Network Embedding2022 IEEE International Conference on Big Data (Big Data)10.1109/BigData55660.2022.10020276(1070-1079)Online publication date: 17-Dec-2022
    • (2022)Semantic enhanced Top-k similarity search on weighted HINNeural Computing and Applications10.1007/s00521-022-07339-634:19(16911-16927)Online publication date: 18-Jun-2022
    • Show More Cited By

    View Options

    Login options

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Media

    Figures

    Other

    Tables

    Share

    Share

    Share this Publication link

    Share on social media