Maximal-entropy random walk unifies centrality measures

This paper compares a number of centrality measures and several (dis-)similarity matrices with which they can be defined. These matrices, which are used among others in community detection methods, represent quantities connected to enumeration of paths on a graph and to random walks. Relationships between some of these matrices are derived in the paper. These relationships are inherited by the centrality measures. They include measures 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. As the random walk defining the centrality measure can be arbitrarily chosen, we pay particular attention to the maximal-entropy random walk, which serves as a very distinct alternative to the ordinary (diffusive) 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 with varying mixing parameter and are grouped with the use of the agglomerative clustering technique. It is shown that centrality measures defined with the two different random walks cluster into two separate groups. In particular, the group of centrality measures defined by the maximal-entropy random walk does not cluster with any other measures on change of graphs’ parameters, and members of this group produce mutually closer results than members of the group defined by the ordinary random walk.

Figure 1

The stationary probability distribution of MERW and GRW as a function of the averaged rows of MFPT matrix (average MFPT of reaching a vertex $f$ from any initial vertex) for a sample graph with $N=1000$ vertices. Solid lines have best fit slopes $-1.027\pm 0.001$ (MERW) and $-1.070\pm 0.005$ (GRW). The correlation for GRW is weaker, since the degrees of the graph take values 10–50 and accordingly the stationary state is quantized. ${\pi }_f$ for GRW is multiplied by 10 for clarity.

Figure 2

The dendrograms correspond to benchmark graphs with the mixing parameter $\mu =0.1,0.3,0.6$. The labels 1, 2, and 3 represent MERW's stationary state, MFPT, and ${\mathbf{P}}^t$ (orange cluster). 6, 7, and 8 are GRW's analogs (blue cluster). 4 denotes weighted paths’ and 5 shortest paths’ centrality. 9, 10 are closeness and betweenness. In 3 and 8, the maximal power of $\mathbf{P}$ is $T=5$. In 4 and 5 $\mu =\ln {\lambda }_0$ and $T$ equals the diameter of the graph.