RWE: A Random Walk Based Graph Entropy for the Structural Complexity of Directed Networks

This paper studies a graph entropy measure to characterize the structural complexity of directed networks. Since the von Neumann entropy (VNE) has found applications in many tasks by networked data, but suffers from a high computational complexity in computing the Laplacian spectrum, we aim to propose a simple yet effective alternative method. Considering that local nodal interactions collectively induce the information flow of the entire graph, we are motivated to use the probability flow of random walks as the proxy of information flow in real-world digraphs, and correspondingly propose a random walk based entropy (RWE) to measure the average information that the random walker reaches each node. Inspired by the close relation between Laplacian spectrum and the Perron vector, we prove that RWE serves as a good approximation for the VNE in digraphs with a guaranteed entropy gap. This approximation is further applied to a digraph similarity measure based on the Jensen-Shannon divergence. Therefore, RWE exhibits interpretability, scalability and capability of well capturing the structural complexity of digraphs as empirically verified. We further extend RWE to two dimensions by incorporating community structures, which characterizes information flow both between and within communities. By proving that the difference between the one-dimensional and two-dimensional RWE reflects the extent to which the community structure is preserved, we convert the community detection problem into the minimization of two-dimensional RWE, and design a greedy algorithm. Various experiments confirm the superiority of our approach over the baselines.