Please use this identifier to cite or link to this item:
http://hdl.handle.net/10071/27154
Author(s): | Magalhães, F. Monteiro, J. Acebron, J. A. Herrero, J. R. |
Date: | 2022 |
Title: | A distributed Monte Carlo based linear algebra solver applied to the analysis of large complex networks |
Journal title: | Future Generation Computer Systems |
Volume: | 127 |
Pages: | 220 - 230 |
Reference: | Magalhães, F., Monteiro, J., Acebron, J. A., & Herrero, J. R. (2022). A distributed Monte Carlo based linear algebra solver applied to the analysis of large complex networks. Future Generation Computer Systems, 127, 220-230. http://dx.doi.org/10.1016/j.future.2021.09.014 |
ISSN: | 0167-739X |
DOI (Digital Object Identifier): | 10.1016/j.future.2021.09.014 |
Keywords: | Matrix inverse Monte Carlo Distributed computation Network metrics |
Abstract: | 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. |
Peerreviewed: | yes |
Access type: | Open Access |
Appears in Collections: | CTI-RI - Artigos em revistas científicas internacionais com arbitragem científica |
Files in This Item:
File | Size | Format | |
---|---|---|---|
article_83360.pdf | 585,67 kB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.