International Journal of Computer Applications |
Foundation of Computer Science (FCS), NY, USA |
Volume 181 - Number 23 |
Year of Publication: 2018 |
Authors: Noor Mohammad Zahid, Badrun Nahar Khan |
10.5120/ijca2018917973 |
Noor Mohammad Zahid, Badrun Nahar Khan . Parallel Algorithms for Evaluating Centrality for Weighted Graphs. International Journal of Computer Applications. 181, 23 ( Oct 2018), 1-4. DOI=10.5120/ijca2018917973
This paper discusses fast parallel algorithms for evaluating betweenness centrality in complex network analysis for weighted graphs. The previous studies on this topic mainly focused on unweighted graphs. Moreover, we will try to implement a shortest path algorithm which is the input of the parallel algorithm. These algorithms have been optimized to exploit properties typically observed in real-world large scale networks. The algorithm are implemented on real datasets such as the web graph, protein-interaction networks, movie-actor and citation networks, and report impressive parallel performance for evaluation of the computationally intensive centrality metrics on high-end shared memory symmetric multiprocessor and multithreaded architectures. For instance, we compute the exact betweenness centrality value for each vertex in a large US patent citation network (3 mil- lion patents, 16 million citations) in 42 minutes on 16 processors, utilizing 20GB RAM of the IBM p5 570. Current SNA packages on the other hand cannot handle graphs with more than hundred thousand edges.