An Efficient Ranking of Nodes and Edges According to their Impact on Graph Von Neumann Entropy

Measuring the importance of edges (and subsequently nodes) is a central task in network science and complex systems, yet this pursuit has not been sufficiently explored from the perspective of information theory. To this end, we utilize the framework of von Neumann entropy (VNE) for networks and quantify the importance of edges by studying how their removals change the network’s VNE. We study a formulation for VNE that is based on the eigenspectra of a Laplacian matrix, which allows us to interpret VNE (and the rankings obtained therefrom) using the perspective of diffusion dynamics.

Specifically, there is intuition in our formulation which relates to heat diffusion of statistical thermodynamics. We study VNE-based rankings for synthetic and empirical networks based on the U.S. Senate, the London rail system (Fig. 1), and the human brain, exploring how the rankings change as we vary a time-scale parameter β > 0. For example, when studying networks drawn from a stochastic block model, we find that the edges between communities can either be the top-ranked edges or have intermediate ranks, depending on β.

As a practical consideration, these VNE-based rankings are too computationally expensive to directly apply to large networks, and we therefore introduce approximate rankings that utilize spectral perturba- tion theory to efficiently approximate how edge removals affect VNE.

Keywords: complex systems, network science, society, thermodynamics