Core-biased random walks in networks. (23rd January 2018)

• Record Type: Journal Article
• Authors: Mondragón, Raúl J
• Editors: Perc, Matjaz
• Is Part Of: Journal of complex networks. Volume 6:Number 6(2018)
• Page Start: 877
• Page End: 886
• Publication Date: 2018-01-23
• Subjects: networks -- entropy rate random walks -- biased random walk -- spectral bound; Numerical analysis -- Periodicals; Computer networks -- Periodicals; Social networks -- Periodicals; 518.05
• DOI: 10.1093/comnet/cny001
• Languages: English
• ISSNs: 2051-1310

Abstract

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 $\lambda_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.