E-Rank: Beyond the Synchronous Constraints of Structural Similarity

TL;DR

Researchers from Fudan University have proposed E-Rank, a structural similarity measure that solves two major flaws in the classic SimRank algorithm: the requirement for equal-length paths and the lack of edge weighting. By modeling similarity as the expected meeting probability of two random walkers who can move at different paces, and introducing an iterative Relationship Strength (RS) metric, E-Rank provides a more "human-intuitive" ranking for social network entities.

Background: The Limits of SimRank

In the world of Social Network Analysis (SNA), structural similarity posits that "two entities are similar if they relate to similar entities." While SimRank has been the gold standard, it operates on a rigid "random surfer-pairs" model. If User A reaches a common friend in 2 steps and User B reaches them in 3, SimRank sees zero similarity for that path. Additionally, SimRank ignores the volume of interaction—treating a one-off email the same as a daily correspondence.

Methodology: The E-Rank Philosophy

E-Rank breaks these barriers using two core innovations:

1. Arriving Probability (Flexible Meetings)

Instead of checking for meetings at a fixed step $k$, E-Rank calculates the Arriving Probability Matrix $A_l$, which integrates the probability of a node reaching another within any length up to $l$. This is defined as: $A_l={\sum }_{k=0}^{l}c(1-c{)}^k{P}^k$ where $c$ is the restart probability. The similarity $m_l(a,b)$ is then the sum of products of these probabilities across all possible meeting nodes $x$.

2. Relationship Strength (RS)

To address link importance, the authors propose an iterative weight adjustment. A link's strength $R(u,v)$ is penalized if the sender $u$ is "too active" (broadcast behavior) or the receiver $v$ is "too attractive" (e.g., a public support inbox), ensuring that unique, high-frequency relationships carry more weight.

In the figure above, E-Rank identifies node $u_7$ as similar to $u_2$ in an e-mail network, whereas SimRank misses it because the path lengths are unequal.

Experiments & Results

The authors tested E-Rank against SimRank and P-Rank on several real-world datasets:

• Enron E-mail Network: 10k nodes, 16k edges.
• Citation Network: 12k papers from High Energy Physics.
• DBLP Co-author Network: 8k authors.

Key Findings:

• Convergence: E-Rank stabilizes relative rankings within 7-10 iterations, making it computationally viable.
• MAP Scores: E-Rank consistently showed higher Mean Average Precision (MAP) as the path length $l$ increased, whereas SimRank hit a performance ceiling.
• Qualitative Success: In the DBLP dataset, E-Rank successfully ranked top co-authors and research collaborators for prominent figures like Jiawei Han, matching real-world academic relationships better than unweighted structural measures.

The MAP scores for E-Rank (highest lines) demonstrate a significant performance advantage over SimRank and Bibliographic Coupling as the search depth ($l$) increases.

Critical Insight: Why it Works

The "synchronicity" of SimRank is its greatest weakness in social contexts. Social influence and information flow don't happen in lockstep. By allowing for a "lag" in meeting times (asynchronous paths) and weighting the "noise" out of high-traffic nodes, E-Rank captures the latent manifold of social structures more effectively.

Conclusion & Future Work

E-Rank bridges the gap between simple graph topology and the nuanced reality of social interactions. Future iterations look toward Heterogeneous Networks, where different types of links (e.g., "follows," "likes," "buys") can be unified under a single E-Rank framework.

For developers building recommendation engines, the takeaway is clear: don't just count hops; count the probability of connection across all possible temporal scales.