A Proximity Measure using Blink Model

Haifeng Qian, Hui Wan, Mark N. Wegman, Luis A. Lastras, Ruchir PuriarXiv 2016 · arXiv

Abstract

Graph proximity measures are fundamental to network analysis, yet traditional metrics like Personalized PageRank (PPR) often fail to capture complex structural dependencies. This paper introduces the Blink Model, a proximity measure derived from network reliability. By treating edges and nodes as probabilistic entities that "blink" in and out of existence, the model accounts for path redundancy and bottlenecks—factors that align more closely with human intuition. Evaluated on arXiv and Wikipedia networks, the Blink Model demonstrates a 14–35% improvement in link prediction accuracy over existing standards.

Introduction: The Proximity Problem

In network science, "proximity" quantifies the strength of the relationship between two nodes. While common metrics like shortest paths or PageRank are widely used, they often struggle with structural nuances. For example, human intuition suggests that two nodes connected by multiple independent paths are "closer" than those connected by a single path. However, if those multiple paths share a common "bottleneck" edge, the reliability of the connection is compromised.

Illustration of path redundancy and bottlenecks. The presence of a bridging edge in the second graph changes the perceived proximity compared to the first.

Existing measures frequently over-count redundant paths or fail to distinguish between these structural variations. The Blink Model aims to provide a mathematically rigorous framework that reflects these "human-like" assessments of network strength.

The Blink Model defines proximity based on the probability of path existence in a stochastic graph.

Conceptual Framework

Imagine a graph where every edge $e$ has a weight $w_E(e)$ representing its existence probability. Nodes and edges "blink" independently. Proximity is defined as: $$s(A, B) = -\log(1 - b(A, B))$$ where $b(A, B)$ is the probability that at least one path exists from A to B. This approach naturally handles mutual corroboration: disjoint paths increase proximity additively, while overlapping paths contribute less due to shared vulnerabilities.

Deterministic Approximation

Calculating $b(A, B)$ exactly is #P-complete. To make the model practical, the authors developed a deterministic approximation algorithm. Instead of relying on stochastic Monte Carlo simulations, which can be unstable, this algorithm identifies "minimal paths" and iteratively refines their contribution. This allows for high-accuracy rankings with significantly lower computational overhead than traditional sampling methods.

Key Insights: Beyond Linear Algebra

A primary critique of popular measures like PPR and Katz centrality is their reliance on matrix iterations. These methods are "local" and cannot easily distinguish between complex global structures.

Comparison of different path structures (i, ii, iii) used to evaluate how proximity measures handle series, parallel, and overlapping paths.

As shown in structural tests, the Blink Model excels where linear algebraic methods fail. By focusing on reliability, the model captures the "Aha!" moment of structural overlap. While network reliability was previously dismissed in proximity literature, this research shows that with superior approximation, it becomes a state-of-the-art tool.

Experimental Results

The authors validated the Blink Model using two significant real-world datasets:

  • arXiv Coauthorship: In predicting future scientific collaborations, the Blink Model outperformed the best-known predictors (the "oracle") by 14% to 35% across various sub-fields.
  • Wikipedia Citations: On the task of predicting new links between Wikipedia pages, the model significantly outperformed Adamic/Adar, PPR, and Katz, reaching target true positive rates with far fewer predictions.

Conclusion

The Blink Model provides a robust alternative to traditional graph proximity measures by incorporating structural reliability. While scaling to billion-node social networks remains a challenge due to computational complexity, its superior accuracy in link prediction benchmarks marks a significant advancement. Future work will explore more efficient path pruning techniques and seek to prove the underlying conjectures of the approximation algorithm.

Summary updated

Abstract

This paper proposes a new graph proximity measure. This measure is a derivative of network reliability. By analyzing its properties and comparing it against other proximity measures through graph examples, we demonstrate that it is more consistent with human intuition than competitors. A new deterministic algorithm is developed to approximate this measure with practical complexity. Empirical evaluation by two link prediction benchmarks, one in coauthorship networks and one in Wikipedia, shows promising results. For example, a single parameterization of this measure achieves accuracies that are 14-35% above the best accuracy for each graph of all predictors reported in the 2007 Liben-Nowell and Kleinberg survey.
BibTeX
@misc{qian2016proximity,
  author = {Haifeng Qian and Hui Wan and Mark N. Wegman and Luis A. Lastras and Ruchir Puri},
  title = {{A Proximity Measure using Blink Model}},
  year = {2016},
  eprint = {1612.07365},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1612.07365},
}
Figure