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:

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