Core-biased random walks in networks. (23rd January 2018) - Mondragón, Raúl J
Abstract: A simple strategy to explore a network is to use a random-walk where the walker jumps from one node to an adjacent node at random. It is known that biasing the random jump, the walker can explore every walk of the same length with equal probability, this is known as a maximal entropy random walk (MERW). To construct a MERW requires the knowledge of the largest eigenvalue $λ_1$ and corresponding eigenvector $\overline{v}^{(1)}$ of the adjacency matrix ${\bf A} = \{a_{ij}\}$, that is global knowledge of the network. When this global information is not available, it is possible to construct a biased random walk which approximates the MERW using only the degree of the nodes, a local property. Here, we show that it is also possible to construct a good approximation to a MERW by biasing the random walk via the properties of the network's core. We present some examples based on real and artificial networks showing that the core-biased random walk outperforms the degree-biased random walks.