A matrix-based measure of inter-node walk relatedness in a network (Q1033899)

Consider a network with \(n\) nodes and directed arcs with positive weights. Let \(A\) be the adjacency matrix. We assume that the network is strongly connected, so \(A\) is irreducible and has a dominant eigenvalue \(r\), say. Let \(c_{out}\) and \(c_{in}\) be the right and left eigenvectors of \(A\) for the eigenvalue \(r\), normalized so that \((c_{out},c_{in})=(c_{out},c_{out})=1.\) The \(i\)th coordinates of \(c_{out}\) and \(c_{in}\) are referred to as the ``out-coreness'' and ``in-coreness'' of the \(i\)th vertex, respectively. The authors note that two nodes \(i,j\) are closely related (in some sense) when the \((i,j)\)th entry \(A^{(k)}(i,j)\) of \(A^{k}\) is large, and they define the ``strength of relatedness'' to be \(\lim_{k\rightarrow\infty}r^{-k}A^{(k)}(i,j)\). The latter equals \(c_{out}(i)c_{in}(j)\) by the Perron-Frobenius theorem. To compare the ``walk relatedness'' of two networks with equal numbers of vertices, the authors propose comparing the \(1\)-norms of the corresponding \(A^{k}\) as \(k\) becomes large. They note that with this measure the effect of removing the link \((i,j)\) in a network is related to the drop in the size of the dominant eigenvalue and is asymptotically dependent on \(c_{out}(i)c_{in}(j)\). Some examples are given.