2011 AxiomaticRankingofNetworkRoleSi
- (Jin et al., 2011) ⇒ Ruoming Jin, Victor E. Lee, and Hui Hong. (2011). “Axiomatic Ranking of Network Role Similarity.” In: Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2011) Journal. ISBN:978-1-4503-0813-7 doi:10.1145/2020408.2020561
Subject Headings:
Notes
Cited By
- http://scholar.google.com/scholar?q=%222011%22+Axiomatic+Ranking+of+Network+Role+Similarity
- http://dl.acm.org/citation.cfm?id=2020408.2020561&preflayout=flat#citedby
Quotes
Author Keywords
- Algorithms; automorphic equivalence; complex network; data mining; experimentation; measurement; ranking; role similarity; social network; theory; vertex similarity
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, [ince 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 similarity 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
;
Author | volume | Date Value | title | type | journal | titleUrl | doi | note | year | |
---|---|---|---|---|---|---|---|---|---|---|
2011 AxiomaticRankingofNetworkRoleSi | Ruoming Jin Victor E. Lee Hui Hong | Axiomatic Ranking of Network Role Similarity | 10.1145/2020408.2020561 | 2011 |