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

Author(s)

Guzman, Grover Enrique Castro ; Stadler, Peter Florian ; Fujita, Andre

• Document type: Journal article
• Source: NUMERICAL ALGORITHMS; v. N/A, p. 22-pg., 2025-01-20.

Abstract

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\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{M}$$\end{document} be the adjacency matrix of a weighted undirected graph. Then, the trace of matrix functions, tr(f(M))\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\varvec{{{\,\textrm{tr}\,}}}(\varvec{f}(\textbf{M}))$$\end{document}, provides insights into global network structural and dynamical properties. Although tr(f(M))\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\varvec{{{\,\textrm{tr}\,}}}(\varvec{f}(\textbf{M}))$$\end{document} 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))\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\varvec{{{\,\textrm{tr}\,}}}(\varvec{f}(\textbf{M}))$$\end{document} 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. (AU)

• FAPESP's process: 20/08343-8 - Graph/Hypergraph (spectral) analysis to compare metabolic networks of pathogenic Trypanosoma sp.
• Grantee: André Fujita
• Support Opportunities: Regular Research Grants
• FAPESP's process: 18/21934-5 - Network statistics: theory, methods, and applications
• Grantee: André Fujita
• Support Opportunities: Research Projects - Thematic Grants
• FAPESP's process: 13/07699-0 - Research, Innovation and Dissemination Center for Neuromathematics - NeuroMat
• Grantee: Oswaldo Baffa Filho
• Support Opportunities: Research Grants - Research, Innovation and Dissemination Centers - RIDC
• FAPESP's process: 19/22845-9 - Computational approaches with the objective to explore intra and cross-species interactions and their role in all domains of life
• Grantee: André Fujita
• Support Opportunities: Regular Research Grants