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

Autor(es)

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

• Tipo de documento: Artigo Científico
• Fonte: NUMERICAL ALGORITHMS; v. N/A, p. 22-pg., 2025-01-20.

Resumo

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)

• Processo FAPESP: 20/08343-8 - Análise (espectral) de grafos/hipergrafos para comparar redes metabólicas do patógeno Trypanosoma sp.
• Beneficiário: André Fujita
• Modalidade de apoio: Auxílio à Pesquisa - Regular
• Processo FAPESP: 18/21934-5 - Estatística de redes: teoria, métodos e aplicações
• Beneficiário: André Fujita
• Modalidade de apoio: Auxílio à Pesquisa - Temático
• Processo FAPESP: 13/07699-0 - Centro de Pesquisa, Inovação e Difusão em Neuromatemática - NeuroMat
• Beneficiário: Oswaldo Baffa Filho
• Modalidade de apoio: Auxílio à Pesquisa - Centros de Pesquisa, Inovação e Difusão - CEPIDs
• Processo FAPESP: 19/22845-9 - Abordagens computacionais com o objetivo de explorar interações intra e inter espécies e seu papel em todos os domínios da vida
• Beneficiário: André Fujita
• Modalidade de apoio: Auxílio à Pesquisa - Regular