Artigo em revista científica Q1
A distributed Monte Carlo based linear algebra solver applied to the analysis of large complex networks
Filipe Magalhães (Magalhães, F.); Jose Monteiro (Monteiro, J.); Juan Torres (Acebron, J. A.); Jose R. Herrero (Herrero, J. R.);
Título Revista
Future Generation Computer Systems
Ano (publicação definitiva)
2022
Língua
Inglês
País
Países Baixos (Holanda)
Mais Informação
Web of Science®

N.º de citações: 4

(Última verificação: 2024-11-02 00:40)

Ver o registo na Web of Science®


: 0.3
Scopus

N.º de citações: 4

(Última verificação: 2024-10-30 14:40)

Ver o registo na Scopus


: 0.2
Google Scholar

N.º de citações: 8

(Última verificação: 2024-11-01 17:02)

Ver o registo no Google Scholar

Abstract/Resumo
Methods based on Monte Carlo for solving linear systems have some interesting properties which make them, in many instances, preferable to classic methods. Namely, these statistical methods allow the computation of individual entries of the output, hence being able to handle problems where the size of the resulting matrix would be too large. In this paper, we propose a distributed linear algebra solver based on Monte Carlo. The proposed method is based on an algorithm that uses random walks over the system’s matrix to calculate powers of this matrix, which can then be used to compute a given matrix function. Distributing the matrix over several nodes enables the handling of even larger problem instances, however it entails a communication penalty as walks may need to jump between computational nodes. We have studied different buffering strategies and provide a solution that minimizes this overhead and maximizes performance. We used our method to compute metrics of complex networks, such as node centrality and resolvent Estrada index. We present results that demonstrate the excellent scalability of our distributed implementation on very large networks, effectively providing a solution to previously unreachable problem instances.
Agradecimentos/Acknowledgements
--
Palavras-chave
Matrix inverse,Monte Carlo,Distributed computation,Network metrics
  • Ciências da Computação e da Informação - Ciências Naturais
Registos de financiamentos
Referência de financiamento Entidade Financiadora
UIDB/50021/2020 Fundação para a Ciência e a Tecnologia
PID2019-107255GB Generalitat de Catalunya
PID2019-107255GB Spanish Ministry of Science and Technology

Com o objetivo de aumentar a investigação direcionada para o cumprimento dos Objetivos do Desenvolvimento Sustentável para 2030 das Nações Unidas, é disponibilizada no Ciência-IUL a possibilidade de associação, quando aplicável, dos artigos científicos aos Objetivos do Desenvolvimento Sustentável. Estes são os Objetivos do Desenvolvimento Sustentável identificados pelo(s) autor(es) para esta publicação. Para uma informação detalhada dos Objetivos do Desenvolvimento Sustentável, clique aqui.