Maximal-entropy random walk unifies centrality measures

Abstract

In this paper analogies between different (dis)similarity matrices are derived. These matrices, which are connected to path enumeration and random walks, are used in community detection methods or in computation of centrality measures for complex networks. The focus is on a number of known centrality measures, which inherit the connections established for similarity matrices. These measures are based on the principal eigenvector of the adjacency matrix, path enumeration, as well as on the stationary state, stochastic matrix or mean first-passage times of a random walk. Particular attention is paid to the maximal-entropy random walk, which serves as a very distinct alternative to the ordinary random walk used in network analysis. The various importance measures, defined both with the use of ordinary random walk and the maximal-entropy random walk, are compared numerically on a set of benchmark graphs. It is shown that groups of centrality measures defined with the two random walks cluster into two separate families. In particular, the group of centralities for the maximal-entropy random walk, connected to the eigenvector centrality and path enumeration, is strongly distinct from all the other measures and produces largely equivalent results.

7 pages, 2 figures

References in corpus (9)

• Benchmark graphs for testing community detection algorithms
• Communicability in complex networks
• The Shannon and the Von Neumann entropy of random networks with heterogeneous expected degree
• Maximal-entropy random walks in complex networks with limited information
• Communicability Graph and Community Structures in Complex Networks
• Topologically biased random walk with application for community finding in networks
• Exact Solution for Statics and Dynamics of Maximal Entropy Random Walk on Cayley Trees
• Random elastic networks : strong disorder renormalization approach
• Maximal Entropy Random Walk: solvable cases of dynamics

Cited by in corpus (7)

• Analyzing complex networks through correlations in centrality measurements
• Mean first-passage time for maximal-entropy random walks in complex networks
• Maximal entropy random walk in community finding
• Maximal entropy random walk improves efficiency of trapping in dendrimers
• Scoring Anomalous Vertices Through Quantum Walks
• Maximal dispersion of adaptive random walks
• Stationary Schrödinger Equation and Darwin Term from Maximal Entropy Random Walk