Blink Proximity       


Blink Proximity - overview


Humans have intuitions for graph proximity. Given a graph, certain pairs of nodes are perceived to have stronger relation strength than others. We know that a larger number of shorter paths indicate greater proximity, yet a precise mathematical formulation of such perception is elusive. This project is an attempt to design this formulation.

This project proposes a new measure of graph proximity, i.e., a new definition of relation strength between nodes in a graph. We demonstrate that this new measure is more consistent with human intuition than existing proximity measures, including PageRank, effective conductance, Katz and many others, and empirically quantify its advantage on link prediction benchmarks.

The following is an informal description of the basic form of this new measure. Please refer to the publications for rigorous definitions, discussions and generalizations. Consider a given graph as a graph that blinks: edges and nodes exist with certain probabilities. The proposed proximity measure is, for two nodes A and B:

s(A,B) = -log( 1 - P[at least one path exists from A to B] )



These are two temporal link prediction benchmarks. Documentation can be downloaded here.

  • Predicting new relations in coauthorship social networks: a replication of the experiments in the following paper. Data and code can be downloaded here.
    • D. Liben-Nowell and J. Kleinberg. The link-prediction problem for social networks. Journal of the American Society for Information Science and Technology, 58(7):1019-1031, 2007.
  • Predicting additions of inter-wikipage citations in Wikipedia from April 2014 to March 2015. Data and code can be downloaded here.