A Fast Monte Carlo Algorithm for Evaluating Matrix Functions with Application in Complex Networks Articles uri icon

authors

  • GUIDOTTI, NICOLAS L.
  • ACEBRON DE TORRES, JUAN ANTONIO
  • MONTEIRO, JOSE

publication date

  • April 2024

start page

  • 1

end page

  • 26

issue

  • 41

volume

  • 99

International Standard Serial Number (ISSN)

  • 0885-7474

Electronic International Standard Serial Number (EISSN)

  • 1573-7691

abstract

  • We propose a novel stochastic algorithm that randomly samples entire rows and columns of the matrix as a way to approximate an arbitrary matrix function using the power series expansion. This contrasts with existing Monte Carlo methods, which only work with one entry at a time, resulting in a significantly better convergence rate than the original approach. To assess the applicability of our method, we compute the subgraph centrality and total communicability of several large networks. In all benchmarks analyzed so far, the performance of our method was significantly superior to the competition, being able to scale up to 64 CPU cores with remarkable efficiency.

subjects

  • Mathematics

keywords

  • monte carlo methods; randomized algorithms; matrix functions·; network analysis