Axiomatic Ranking of Network Role Similarity

1. INTRODUCTION

• Roles characterize nodes by their interaction patterns and can help predict functionality across social, biological, trade, and software networks.For example, proteins with similar roles tend to serve similar metabolic functions.Source: §1 · p. 1
• Role analysis complements clustering, which can overlook distinct node roles within a cluster and roles in networks without modular structure.Nodes with similar roles need not be directly connected.Source: §1 · p. 1
• Automorphically equivalent nodes should receive maximal similarity, but strict equivalence is often rare and fragile to network noise.Strict equivalence schemes provide only binary scores, while real-valued scores can rank degrees of similarity.Source: §1 · pp. 1–2
• SimRank can assign less than maximal similarity to automorphically equivalent nodes, whereas RoleSim uses optimal neighbor matching to satisfy automorphic equivalence and the triangle inequality.The paper presents RoleSim as the first real-valued measure to solve this problem.Source: §1 · p. 2

2. ROLE EQUIVALENCE

• The four role-equivalence definitions, in decreasing strictness, are structural, automorphic, equitable-partition, and regular equivalence.They can generate different roles from the same network.Source: §2 · p. 2
• Structural equivalence requires identical interaction partners, so the children in each family form classes while the parents do not.Mathematically, u and v are structurally equivalent exactly when N(u) = N(v).Source: §2 · p. 2
• Automorphic equivalence permits coordinated node swaps that preserve edges; it groups Smith and Jones counterparts but distinguishes the Lee family’s parents.Automorphic equivalence also preserves equivalent indirect relations.Source: §2 · p. 2
• Exact coloration groups nodes with equal counts of neighbors by color, while regular equivalence matches varieties of role classes regardless of neighbor counts.Under regular equivalence, all three families are equivalent.Source: §2 · pp. 2–3

3. AXIOMATIC ROLE SIMILARITY

• A role-similarity measure should satisfy range, symmetry, automorphism confirmation, transitive similarity, and triangle inequality.The triangle inequality implies consistent cross-similarities among equivalent nodes, and distance is defined as 1 − sim.Source: §3 · p. 3

3.1 Binary-Valued Role Similarity Measures

• An equivalence relation satisfying automorphism confirmation yields an admissible binary metric, but binary scores provide no ranking between distinct classes.The paper therefore seeks a real-valued measure of cross-class role similarity.Source: §3.1 · pp. 3–4

3.2 SimRank is NOT Admissible

• SimRank is not admissible because it can assign 0.667 or even 0 to automorphically equivalent nodes in the paper’s examples.The examples violate automorphism confirmation, a required property of role similarity.Source: §3.2 · p. 4

ADMISSIBLE ROLE SIMILARITY

• RoleSim starts from an admissible measure and refines it through neighbor similarities to address the difficulty of encoding automorphic equivalence in a real-valued ranking.The paper also notes that existing real-valued measures have difficulty with structural equivalence.Source: ADMISSIBLE ROLE SIMILARITY · p. 4

4.1 RoleSim Definition

• RoleSim scores two nodes by matching their neighbors using recursive similarity values, with a decay factor β that damps recursion and guarantees a minimum score of β.A matching uses at most min(Nu, Nv) pairs, selecting one cell per row and column in the neighbor grid.Source: §4.1 · p. 4, Figure 3 · p. 4

4.1.1 Relation to Jaccard Coefficient

• RoleSim generalizes the Jaccard coefficient by matching similar, not necessarily identical, members of the two neighborhoods.Its neighborhood component is the maximum generalized Jaccard coefficient over possible matchings.Source: §4.1.1 · p. 5

4.1.2 Relation to Weighted Matching

• Theorem 4 equates RoleSim’s update with a maximal weighted matching, allowing each iteration to use existing maximal-matching algorithms.Matching-edge weights are the RoleSim values of the paired neighbors.Source: §4.1.2 · p. 5

4.2 RoleSim Computation

• RoleSim iteratively updates pair scores from the previous iteration, and the computation converges for any admissible initial scores.The convergent score can depend on initialization, which the authors identify as a way to use prior knowledge of network structure.Source: §4.2 · p. 5

4.3 Admissibility of RoleSim

• Theorem 7 establishes that admissible initialization and invariant updates yield an admissible converged RoleSim measure.The proof treats range, symmetry, automorphic equivalence, transitive similarity, and the triangle inequality as the relevant properties.Source: §4.3 · pp. 5–6

4.4 Initialization

• ALL-1, Degree-Binary, and Degree-Ratio are admissible initial measures; ALL-1 and Degree-Binary are also admissible metrics.ALL-1 and Degree-Ratio produce the same final results, with Degree-Ratio one iteration faster; ALL-1 scores are non-increasing, while Degree-Binary lacks the stated monotone-convergence property.Source: §4.4 · pp. 6–7

4.5 Computational Complexity

• With greedy neighbor matching, RoleSim has time complexity O(kn^2d′) and space complexity O(n^2), where k is the iteration count and d′ averages matching costs.The greedy matching is a 1/2-approximation and finds an equivalence matching when one exists.Source: §4.5 · p. 7

5. ICEBERG ROLESIM COMPUTATION

• For n nodes, maintaining all O(n^2) pair scores can require about 40 GB at 100,000 nodes, motivating a method for finding high-similarity pairs without computing every score.The cited memory estimate assumes 8 bytes per value.Source: §5 · p. 7
• Iceberg RoleSim seeks every pair with RoleSim at least θ, pruning pairs whose scores must fall below θ before iterating on the remaining candidates.The candidate computation uses upper and lower bounds for non-candidate neighbor pairs needed during updates.Source: §5 · p. 7
• The algorithm sorts nodes and neighbor lists by degree, applies degree and matching-weight pruning, then iterates only over retained pairs in a hash table.For non-candidate neighbor pairs, it applies an estimate based on bounds; the paper evaluates α’s effect on estimation accuracy.Source: §5 · pp. 7–8

6.1 Comparing Initialization

• Degree-Binary initialization yields virtually identical rankings to ALL-1 and takes 20%–68% less time to converge.The authors adopt Degree-Binary for the remaining experiments.Source: §6.1 · p. 8, Table 2 · p. 8

6.2 General Role Detection

• On probabilistic block-model graphs, RoleSim outperforms SimRank, SimRank++, and PSimRank across all tested conditions.None scores perfectly because of edge-distribution variance; standard RoleSim is about twice as slow as SimRank.Source: §6.2 · p. 9, Figure 4 · p. 9

6.3 Real Dataset: Co-author Network

• For top 0.01% coauthor pairs, RoleSim and P-SimRank show about 20 points of G-index rank difference, versus 33 for random pairs.As the selection expands to 10%, RoleSim continues identifying authors with similar authorship performance while P-SimRank approaches random scoring; RoleSim also scores same-decile pairs 55%–60% on average and declines as decile gaps widen.Source: §6.3 · p. 9, Figure 5 · p. 9, Figure 6 · p. 9

6.4 Real Dataset: Internet Network

• Across K-shells, RoleSim’s within-shell similarity values are consistently high, averaging 70%, and its similarity approaches zero as shell difference approaches the maximum.K-shells 1–3 contain 92% of all nodes; P-SimRank is nearly random for these shells and shows almost no correlation with shell difference.Source: §6.4 · p. 10
• Across the experiments, node pairs with similar roles rank higher than dissimilar pairs, and high RoleSim rankings indicate similar roles.P-SimRank scores do not correlate with network role similarity.Source: §6.4 · p. 10

6.5 Performance of Iceberg RoleSim

• Iceberg RoleSim runs an order of magnitude faster, with ranking correlations of 0.823 at θ = 0.8 and 0.880 at θ = 0.9.Its hash tables use 0.15%–3.5% of the full similarity matrices in the tested scale-free graphs.Source: §6.5 · p. 10, Figure 8 · p. 10, Table 3 · p. 10

7. RELATED WORK

• Link similarity covers applications such as co-citation, recommender systems, and Web search, while role similarity is a distinct special case.Clustering groups nodes into components but does not provide individual node-pair similarities.Source: §7 · p. 10
• SimRank recursively scores nodes by the average similarity of their neighbor pairs, extending the idea that objects linked to similar objects are similar.The paper describes SimRank as having a random-walk interpretation.Source: §7 · p. 11
• The authors distinguish RoleSim from MatchSim by its guarantees of automorphic equivalence and the triangle inequality, making RoleSim a true metric.They also characterize their framework as theoretical rather than intuition-based.Source: §7 · p. 11

8. CONCLUSION

• RoleSim is presented as the first real-valued role similarity measure that confirms automorphic equivalence.The authors also present axioms for assessing future measures and metrics.Source: §8 · p. 11
• The authors report that experiments demonstrate RoleSim’s correctness and usefulness on real-world data.The conclusion says this opens possibilities for scientific and business applications.Source: §8 · p. 11
• The conclusion says other well-known measures can be suitable for other tasks but not for role similarity.It also suggests the axiomatic approach may help develop and validate solutions to related tasks.Source: §8 · p. 11

A. PROOFS OF THEOREMS AND LEM-MAS

• The convergence proof seeks to show that the maximum change in RoleSim scores across node pairs decreases from one iteration to the next.It defines Dk as the maximum absolute score difference at iteration k.Source: A. PROOFS OF THEOREMS AND LEM-MAS · p. 13
• The triangle-inequality proof constructs matchings between neighborhood pairs and considers cases based on the relative neighborhood sizes.The text states the invariant using distance dk(a,b) = 1 − RoleSimk(a,b).Source: A. PROOFS OF THEOREMS AND LEM-MAS · p. 13

B.1 Non-iterative Predecessors of SimRank

• Bibliographic coupling and co-citation count shared references or citing works, with normalization by distinct works; related measures include Jaccard, cosine, and TF-IDF weighting.Cosine is presented as a convenient similarity for weighted feature vectors, while TF-IDF weights terms by frequency and inverse document frequency.Source: §B.1 · p. 14

B.2 SimRank and Simple Generalizations

• SimRank recursively defines similarity through related objects, initializes its similarity matrix to the identity, and can combine in-neighbor and out-neighbor effects.Its iterative form uses a decay constant, and the supplied passage says pairs with no neighbors receive zero similarity.Source: §B.2 · pp. 14–15

B.3 Improving the SimRank’s Computational Performance

• Computing even one SimRank pair requires considering the entire graph, increasing computational requirements by a factor of n^2k for k iterations.The cited passage notes work to reduce SimRank’s computational and memory requirements.Source: §B.3 · p. 15

B.4 Meaningful Extensions and Alternative to SimRank

• SimRank can score a pair with all neighbors in common lower as their shared degree rises, despite the expected stronger tie.The passage describes this as a structural flaw of the original formula.Source: §B.4 · p. 15

B.4.1 SimRank++

• SimRank++ adds an evidence factor that increases with the number of common neighbors, but its narrow [0.5, 1] range leaves scores unbounded by 1 or a graph-independent constant.The authors also describe an extension for edge-weighted graphs.Source: §B.4.1 · p. 15

B.4.2 PSimRank

• PSimRank replaces independent random walks with coupled walks, separating events such as both walks stepping to the same vertex and weighting neighbor-similarity cases by their probabilities.The direct-similarity case is described as the Jaccard coefficient.Source: §B.4.2 · p. 15

B.4.3 MatchSim

• MatchSim replaces random walks with the average similarity of a maximal matching between neighbors.The supplied discussion describes the matching size as the smaller of the two neighbor-set sizes.Source: §B.4.3 · pp. 15–16

B.4.4 PageSim

• PageSim propagates distinct self-features over paths and sums their contributions, then compares the resulting feature vectors.An expanded version modifies the similarity formula to more closely resemble the Jaccard coefficient.Source: §B.4.4 · p. 16

B.4.5 Vertex Similarity in Networks

• VertexSim addresses SimRank’s equal-length-path limitation, but its motivating maxim assumes that being neighbors implies similarity.The authors derive a closed form and an iterative version; they report that the latter can converge within 100 iterations or fewer.Source: §B.4.5 · p. 16

• Table 4 summarizes the structural similarity measures discussed in the preceding text.Source: §B.5 · p. 16, Table 4 · p. 17