On parallel computation of indicators of centrality and its application to speeding up RDA. Issue 5 (2nd August 2019)

• Record Type: Journal Article
• Authors: García, Juan F.; Carriegos, M.V.
• Is Part Of: Computational and mathematical methods. Volume 1:Issue 5(2019)
• Page Start: n/a
• Page End: n/a
• Publication Date: 2019-08-02
• Subjects: centrality measures -- graph -- high‐performance computing -- parallel computation -- network; Mathematics -- Data processing -- Periodicals; Numerical analysis -- Periodicals; Numerical analysis; Mathematics -- Data processing; Periodicals; 004.0151
• DOI: 10.1002/cmm4.1056
• Languages: English
• ISSNs: 2577-7408

Abstract

Abstract : Random decentralized algorithm (RDA) dynamically extends networks, hiding their central structure so that they becomes less vulnerable to attacks. To assess the efficacy of RDA, we have to monitor the values for several indicators of centrality, which must follow a decremental pattern as the algorithm progresses. Although optimized algorithms exist for computing of most of these indicators, they are still time consuming and are even infeasible to apply to big enough graphs like the ones representing social networks or extensive enough computer networks, which limit the scope of application of RDA to small networks. In this paper, we present a threading‐based parallel implementation in C language of some optimal algorithms for computing the indicators of centrality used by RDA. We have tested our software in several platforms, including the Supercomputer Calendula, and our parallel version greatly reduces the execution time of their sequential (nonparallel) counterpart. Our application is multiplatform and portable, working on any machine with several logical processors, which is capable of compiling and running C language code. The speedup of our solution allows us to apply RDA algorithm to networks with thousand of nodes.