The week's pick
Random Articles
Reseach Article
Parallel Algorithms for Evaluating Centrality for Weighted Graphs
| 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
Abstract
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.
References
- Segarra, S., & Ribeiro, A. (2015). Stability and continuity of centrality measures in weighted graphs. 2015 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP). doi:10.1109/icassp.2015.7178599
- Bader, D., & Madduri, K. (n.d.). Parallel Algorithms for Evaluating Centrality Indices in Real-world Networks. 2006 International Conference on Parallel Processing (ICPP06). doi:10.1109/icpp.2006.57
- S. Brin and L. Page. The anatomy of a large-scale hypertextual web search engine. Computer Networks and ISDN Systems, 30(1–7):107–117, 1998
- P. Doreian and L. Albert. Partitioning political actor networks: Some quantitative tools for analyzing qualitative networks. Quantitative Anthropology, 161:279–291, 1989.
- A. Bavelas. Communication patterns in task oriented groups. J. Acoustical Soc. of America, 22:271–282, 1950
- G. Sabidussi. The centrality index of a graph. Psychometrika, 31:581–603, 1966.
- U. J. Nieminen. On the centrality in a directed graph. Social Science Research, 2:371–378, 1973
- L. C. Freeman. A set of measures of centrality based on betweenness. Sociometry, 40(1):35–41, 1977.
- H. Jeong, S. Mason, A.-L. Barabasi, and Z. Oltvai. Lethality and centrality in protein networks. Nature, 411:41, 2001
- J. Pinney, G. McConkey, and D. Westhead. Decomposition of biological networks using betweenness centrality. In Proc. Poster Session of the 9th Ann. Int’l Conf. on Research in Computational Molecular Biology (RECOMB 2004), Cambridge, MA, May 2005.
- A. del Sol, H. Fujihashi, and P. O’Meara. Topology of small-world networks of protein-protein complex structures. Bioinformatics, 21(8):1311–1315, 2005
- F. Liljeros, C. R. Edling, L. A. N. Amaral, H. E. Stanley, and Y. Aberg. The web of human sexual contacts. Nature, 411:907, 2001
- U. Brandes. A faster algorithm for betweenness centrality. J. Mathematical Sociology, 25(2):163–177, 2001.
- F. Jamour, S. Skiadopoulos and P. Kalnis, "Parallel Algorithm for Incremental Betweenness Centrality on Large Graphs", IEEE Transactions on Parallel and Distributed Systems, vol. 29, no. 3, pp. 659-672, 2018.
Index Terms
Keywords