A message-passing approach to obtain the trace of matrix functions with applications to network analysis

Graphs have become a commonly used model to study technological, biological, and social systems. Various methods have been proposed to measure graphs’ structural and dynamical properties, providing insights into the fundamental processes and interactions that govern the behavior of these systems. Matrix functions are powerful mathematical tools for assessing vertex centrality, communicability, and diffusion processes. Let M be the adjacency matrix of a weighted undirected graph. Then, the trace of matrix functions, tr(f(M)), provides insights into global network structural and dynamical properties. Although tr(f(M)) can be computed using the diagonalization method for graphs with a few thousand vertices, this approach is impractical for large-scale networks due to its computational complexity. Here, we present a message-passing method to approximate tr(f(M)) for graphs with short cycles that runs in linear time up to logarithmic terms. We compare our proposal with the state-of-the-art approach through simulations and real-world network applications, achieving comparable accuracy in less time.