A novel context-sensitive random walk model for estimating node correspondence between two biological networks

In this work, we propose a novel context-sensitive random walk model to accurately estimate the node correspondence between two biological networks. We adopt a Markov random walk model that performs a simultaneous walk on two networks. At each step, the random walker examines its neighbors and performs a context-sensitive walk in the following step. More specifically, if there are similar node pairs among the neighbors, the random walker performs a simultaneous walk on both networks. Otherwise, it performs an individual walk on one of the networks. Based on this random walk model, we assume that random walker more frequently visits node pairs with higher correspondence in the long run. Then, we can estimate the node correspondence score by computing the steady state distribution that reflects the long-term behavior of the random walker. We show that the proposed method can accurately predict the correspondence between proteins in different protein-protein interaction (PPI) networks, which implies that our context-sensitive random walker can provide an effective framework for the comparative analysis of large-scale biological networks.