  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.
