Non-Backtracking Centrality Based Random Walk on Networks
arXiv:1803.03087
Abstract
Random walks are a fundamental tool for analyzing realistic complex networked systems and implementing randomized algorithms to solve diverse problems such as searching and sampling. For many real applications, their actual effect and convenience depend on the properties (e.g. stationary distribution and hitting time) of random walks, with biased random walks often outperforming traditional unbiased random walks (TURW). In this paper, we present a new class of biased random walks, non-backtracking centrality based random walks (NBCRW) on a network, where the walker prefers to jump to neighbors with high non-backtracking centrality that has some advantages over eigenvector centrality. We study some properties of the non-backtracking matrix of a network, on the basis of which we propose a theoretical framework for fast computation of the transition probabilities, stationary distribution, and hitting times for NBCRW on the network. Within the paradigm, we study NBCRW on some model and real networks and compare the results with those corresponding to TURW and maximal entropy random walks (MERW), with the latter being biased random walks based on eigenvector centrality. We show that the behaviors of stationary distribution and hitting times for NBCRW widely differ from those associated with TURW and MERW, especially for heterogeneous networks.
References in corpus (16)
- Emergence of scaling in random networks
- The structure and function of complex networks
- Finding community structure in networks using the eigenvectors of matrices
- The architecture of complex weighted networks
- Self-similar community structure in organisations
- Spectral redemption: clustering sparse networks
- First-passage times in complex scale-invariant media
- Localization and centrality in networks
- Percolation on sparse networks
- Localization of maximal entropy random walk
- Random walks on weighted networks
- A message-passing approach for recurrent-state epidemic models on networks
- Random walks in weighted networks with a perfect trap: An application of Laplacian spectra
- Estimating and Sampling Graphs with Multidimensional Random Walks
- Maximal entropy random walk improves efficiency of trapping in dendrimers
- Exact Solution for Statics and Dynamics of Maximal Entropy Random Walk on Cayley Trees