All similarity measures so far are local: they count the number of common neighbors, or number of paths of length two, between two nodes. However, two nodes might be similar in a more general way. First, two identical nodes are similar for sure. Moreover, the fact that two nodes are connected by an edge (a path on unitary length) is certainly an indication of similarity. Furthermore, similarity can also be deduced by longer paths of length larger than two. For instance, paths of length 3 between nodes $i$ and $j$ count the number of neighbors of $i$ and $j$ that are connected by an edge; paths of length 4 count the number of neighbors of $i$ and $j$ that have a common neighbor; paths of length 5 count the number of neighbors of $i$ and $j$ that have neighbors that are connected by an edge. Two nodes may have few or none neighbors in common, but they still may be similar in an indirect, global way. Paths between nodes, of any length, are hints of similarity; nevertheless, the shorter the path, the stronger the contribution to similarity.
The recursive thesis of global similarity is the following:
Two nodes are similar if one has a neighbor that is similar to the other.
Mathematically, the recursive thesis of global similarity can be written as follows: $$ \sigma_{i,j} = \alpha \sum_k A_{i,k} \sigma_{k,j} + \delta_{i,j} $$ where $\alpha > 0$ is a constant and $\delta_{i,j}$ is the Kronecker delta ($\delta_{i,j} = 1$ if $i=j$ and $\delta_{i,j} = 0$ if $i \neq j$). In matrix form we have: $$ \sigma = \alpha A \sigma + I $$ Evaluating the expression by iteration starting from $\sigma^{0} = 0$ we get: $$ \begin{array}{lcl} \sigma^{(1)} & = & I \\ \sigma^{(2)} & = & \alpha A + I \\ \sigma^{(3)} & = & \alpha^2 A^2 + \alpha A + I \\ & \ldots & \end{array} $$ Hence, $\sigma^{(k)}$ counts the contribution of paths of length less than $k$ and the contribution of a path of length $k$ is weighted by the attenuation factor $\alpha^k$, as soon as $\alpha < 1$. Notice that the contribution of the identity matrix $I$ is that each node is initially similar to itself; this is necessary to propagare similarity through network using the network topology represented by the adjacency matrix $A$. In the final solution, however, values of $\sigma_{i,i}$ are an indication of how dense the network is around the node $i$, and hence different nodes might have different self-similarities. If follows that the similarity matrix $\sigma$ is the following: $$ \sigma = \sum_{k = 0}^{\infty} (\alpha A)^k = (I - \alpha A)^{-1} $$ This solution is reminiscent of Katz centrality; indeed, Katz centrality of node $i$ is exactly the sum of similarities of $i$ with all other nodes. Hence, a node is central in Katz view if it is similar to many other vertices. As with Katz centrality, the parameter $\alpha$ must be chosen less then $1 / \rho(A)$, with $\rho(A)$ the spectral radius of $A$.
A useful variant is to consider cases where the last term $I$ in the defining equation is not simply diagonal, but includes off-diagonal terms too. Such a generalization would allow us to specify explicitly that particular pairs of vertices are similar, based on some other (exogenous, non-network) information that we have at our disposal.
An alternative global dissimilarity measure is resistance distance. We have seen that the resistance distance amont two nodes has the properties that it is low if there are many short paths connecting two nodes, and it is high if there are few long paths between two nodes.