A Matrix-Based Measure of Inter-Node Walk Relatedness in a Network

For a pair of nodes in a network, a measure of walk relatedness is introduced. The measure is based on the total weight (number) of $k$-step walks connecting the pair, i.e., the corresponding entry of the $k$th power of the network matrix as $k\to\infty$. The damping factor $r^{-k}$ is used, where $r$ is the largest eigenvalue of the network matrix. The measure turns out to be equal to the product of the pair's coreness values, i.e., the nodes' coordinates in the network matrix's right and left eigenvectors corresponding to $r$. The walk relatedness reduction in a network caused by the removal of a node or link is investigated, namely, the reduction dependence on the structural position (coreness) of the removed element. It is revealed that the “damage” can be measured by the drop in the value of $r$ after the removal; to find this drop, the perturbation method is used. Some possible applications are indicated, and a numerical example with a large real network of 197 nodes and 780 links is considered.