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

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 signif...

Full description

Saved in:
Bibliographic Details
Published in:Journal of scientific computing 2024-05, Vol.99 (2), p.41, Article 41
Main Authors: Guidotti, Nicolas L., Acebrón, Juan A., Monteiro, José
Format: Article
Language:English
Subjects:
Algorithms
Computational Mathematics and Numerical Analysis
Graph theory
Linear algebra
Mathematical and Computational Engineering
Mathematical and Computational Physics
Mathematics
Mathematics and Statistics
Methods
Monte Carlo simulation
Power series
Series expansion
Theoretical
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0885-7474
1573-7691
DOI:10.1007/s10915-024-02500-w