Common neighbours

Two vertices are more likely to be connected if they are connected to the same set of other vertices. (Newman 2001) used this method in the study of collaboration networks, showing positive relation between number of common neighbours and probability of collaborating in the future.

s_xy = |Γ(x) ∩ Γ(y)|

or in a matrix form

s_xy = (A²)_xy.

Salton Index (cosine similarity)

Due to Salton and McGill (1986) . It measures the cosine of the angle between columns of the adjacency matrix, corresponding to given vertices. This measure is commonly used in information retrieval.

$$ s_{xy}=\frac{|\Gamma(x)\cap\Gamma(y)|}{\sqrt{k_x\times k_y}}. $$

Jaccard Index

Jaccard Index (Jaccard 1912) measures the proportion of common neighbours in the total number of neighbors. It reaches its maximum if Γ(x) = Γ(y), namely all neighbours are common to both vertices.

$$ s_{xy}=\frac{|\Gamma(x)\cap\Gamma(y)|}{|\Gamma(x)\cup\Gamma(y)|}. $$

Sørensen Index

Due to (Sørensen 1948). This method is similar to the Jaccard Index as it measures the relative size of an intersection of neighbours’ sets.

$$ s_{xy}=\frac{2|\Gamma(x)\cap\Gamma(y)|}{k_x+k_y}. $$

Hub Promoted Index

Due to (Ravasz et al. 2002). This measure assigns higher scores to links adjacent to hubs (high-degree vertices), as the denominator depends on the minimum of the degrees of the vertices of interest.

$$ s_{xy}=\frac{|\Gamma(x)\cap\Gamma(y)|}{\min\{k_x,k_y\}}. $$

Hub Depressed Index

Due to (Ravasz et al. 2002). This measure, in contrast to Hub Promoted Index, assigns lower scores to links adjacent to hubs. It penalises large neighbourhoods.

$$ s_{xy}=\frac{|\Gamma(x)\cap\Gamma(y)|}{\max\{k_x,k_y\}}. $$

Leicht-Holme-Newman Index

Due to Leicht, Holme, and Newman (2006). It is a variant of Common Neighbours, similar to Salton Index.

$$ s_{xy}=\frac{|\Gamma(x) \cap \Gamma(y)|}{k_x \cdot k_y}. $$

Preferential Attachment

Preferential Attachment was developed as a model of the growth of network in a sense of new nodes emerging (Barabási and Albert 1999).

s_xy = k_x ⋅ k_y.

Adamic–Adar Index

This measure develops simple counting of common neighbours by assigning weights to nodes inversely proportional to their degrees (Adamic and Adar 2001). That means that a common neighbour, which is unique for a few nodes only, is more important than a hub.

$$ s_{xy}=\sum_{z\in \Gamma(x)\cap\Gamma(y)}\frac{1}{\log k_z}. $$

Note that this index is well defined, because when vertex z is a common neighbour of x and y, than its degree is at least 2.

Resource Allocation Index

Proposed by Zhou, Lü, and Zhang (2009). This measure is motivated by a resource allocation process. It measures how much resource is transmitted between x and y.

$$ s_{xy}=\sum_{z\in \Gamma(x)\cap\Gamma(y)}\frac{1}{k_z}. $$

Katz Index

(Katz 1953) counts all the paths between given pair of nodes, with shorter paths counting more heavily. $$ s_{xy}=\sum_{l=1}^{\infty}\beta^l|paths_{xy}^{<l>}|, $$

where β is a free parameter. The sum converges when β is lower than the reciprocal of the largest eigenvalue of adjacency matrix. If this condition is satisfied Katz Index could be expressed in matrix form as

S = (I − βA)⁻¹ − I.

Leicht-Holme-Newman Index

The global version (Leicht, Holme, and Newman 2006) is a variant of Katz Index, based on the concept that two nodes are similar if they neighbours are similar. It counts all paths between two nodes, but weights them by the expected number of such paths in a random graph with the same degree distribution. In matrix form, without constant factor:

$$ S = D^{-1}\left(I-\frac{\phi A}{\lambda_1}\right)^{-1}D^{-1}, $$

where λ₁ is the largest eigenvalue of adjacency matrix A and ϕ is a free parameter.

Average Commute Time

$$ s_{xy}=\frac{1}{n(x,y)}=\frac{1}{m(x,y)+m(y,x)}, $$

where m(x, y) is the average number of steps required by a random walker starting from x to reach y. Sum of two directional commute times is taken to achieve symmetrical measure. Hence two nodes are similar if they are closer to each other and have smaller commute time, reciprocal is needed. Average Commute Time could be computed by solving collection of the linear equations, taken from Markov Chain analysis, but it is more straightforward to compute it in terms of the pseudoinverse of the Laplacian matrix, L⁺. Namely: n_xy = 2M(l_xx⁺ + l_yy⁺ − 2l_xy⁺), where l_xy⁺ = [L⁺]_xy and M is the number of edges. Thanks to the special form of the Laplacian matrix, its pseudoinverse L⁺ could be computed using formula (Fouss et al. 2007): $$ L^{+}=\left(L-\frac{ee^T}{n}\right)^{-1}+\frac{ee^T}{n}, $$ where e is a column vector made of 1’s.

Normalized Average Commute Time

This is a variant of ACT, which takes into account node degrees, as for high–degree node (hub) y, m(x, y) is usually small regardless of x. $$ s_{xy}=\frac{1}{(m(x,y)\pi_y+m(y,x)\pi_x)}, $$ where π is a stationary distribution of a Markov chain describing random walker on the graph. It is easily shown that on a connected graph $$ \pi(x) = \frac{k_x}{\sum_y k_y}. $$

Cosine based on L⁺

(Fouss et al. 2007)

$$ s_{xy}=\frac{l_{xy}^{+}}{\sqrt{l_{xx}^{+}l_{yy}^{+}}} $$ It measures the cosine of the angle between node vectors in a space spanned by columns of L⁺.

Random Walk with Restart (RWR)

It is an adaptation of PageRank algorithm (Brin and Page 1998). Consider random walker starting from node x and periodically, with probability α, returning to x. Let q_x be a stationary distribution of Markov chain describing this walker. From definition of stationary distribution: q_x = (1 − α)P^Tq_x + αe_x, where e_x is a unit vector with 1 on position corresponding to node x, and P is a transition matrix describing ordinary random walker, P_xy = 1/k_x if A_xy = 1 and 0 otherwise. The solution for all nodes simultaneously is q = [q₁|q₂|…|q_n] = α(I − (1 − α)P^T)⁻¹. In order to achieve symmetry the RWR index is defined as s_xy = q_xy + q_yx.

L⁺ directly

(Fouss et al. 2007)

S = L⁺. L⁺ provides a direct measure of similarity, as its elements are the inner products of vectors from an Euclidean space, which preserves Average Commute Time between nodes, see (Fouss et al. 2007) for details.

Matrix Forest Index

(Chebotarev P. Yu. 1997)

S = (I + L)⁻¹. Matrix Forest Index can be understood as the ratio of the number of spanning rooted forest such that nodes x and y belong to the same tree rooted at x to all spanning rooted forests of the network, see (Chebotarev P. Yu. 1997).

Shortest Paths (Graph distance)

where {p_xy} = min {l : path_xy^< l> exists} is the length of the shortest path connecting x and y.

Local Path Index

(Zhou, Lü, and Zhang 2009)

S = A² + ϵA³, where ϵ is a free parameter. This measure benefits from more information than simple common neighbours, as it looks on neighbours of second order, but at the same time is still fairly inexpensive to compute.