A Fast Monte Carlo algorithm for evaluating matrix functions with application in complex networks

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.

Published in the Journal of Scientific Computing

References in corpus (13)

• The structure and function of complex networks
• Error and attack tolerance of complex networks
• Lethality and centrality in protein networks
• Subgraph Centrality in Complex Networks
• The Physics of Communicability in Complex Networks
• Complex Networks as Hypergraphs
• Virtual Identification of Essential Proteins Within the Protein Interaction Network of Yeast
• Statistical-mechanical approach to subgraph centrality in complex networks
• On the limiting behavior of parameter-dependent network centrality measures
• Community Structure in Large Networks: Natural Cluster Sizes and the Absence of Large Well-Defined Clusters
• Randomized Numerical Linear Algebra : A Perspective on the Field With an Eye to Software
• Limited-memory polynomial methods for large-scale matrix functions
• Fast & Accurate Randomized Algorithms for Linear Systems and Eigenvalue Problems