
where \(N(u)\)  are the neighbors of \(u\) .
Shortest path based heuristics are generally more expensive to calculate than neighborhood similarity as they require global knowledge of the graph to compute exactly.
The Katz index takes into account multiple paths between two nodes. Each path is given a weight of \(\alpha ^d\) , where \(\alpha \)  is a hyperparameter attenuation factor and \(d\)  is the path length. Similarly Personalized PageRank (PPR) estimates landing probabilities of a random walker from a single source node. For a survey comparing 20 different LP heuristics see e.g. [1]}.
