CFP last date
20 November 2024
Call for Paper
December Edition
IJCA solicits high quality original research papers for the upcoming December edition of the journal. The last date of research paper submission is 20 November 2024

Submit your paper
Know more
Reseach Article

Parallel Algorithms for Evaluating Centrality for Weighted Graphs

by Noor Mohammad Zahid, Badrun Nahar Khan
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

@article{ 10.5120/ijca2018917973,
author = { Noor Mohammad Zahid, Badrun Nahar Khan },
title = { Parallel Algorithms for Evaluating Centrality for Weighted Graphs },
journal = { International Journal of Computer Applications },
issue_date = { Oct 2018 },
volume = { 181 },
number = { 23 },
month = { Oct },
year = { 2018 },
issn = { 0975-8887 },
pages = { 1-4 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume181/number23/30022-2018917973/ },
doi = { 10.5120/ijca2018917973 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-07T01:06:46.228688+05:30
%A Noor Mohammad Zahid
%A Badrun Nahar Khan
%T Parallel Algorithms for Evaluating Centrality for Weighted Graphs
%J International Journal of Computer Applications
%@ 0975-8887
%V 181
%N 23
%P 1-4
%D 2018
%I Foundation of Computer Science (FCS), NY, USA
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
  1. 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
  2. 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
  3. 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
  4. P. Doreian and L. Albert. Partitioning political actor networks: Some quantitative tools for analyzing qualitative networks. Quantitative Anthropology, 161:279–291, 1989.
  5. A. Bavelas. Communication patterns in task oriented groups. J. Acoustical Soc. of America, 22:271–282, 1950
  6. G. Sabidussi. The centrality index of a graph. Psychometrika, 31:581–603, 1966.
  7. U. J. Nieminen. On the centrality in a directed graph. Social Science Research, 2:371–378, 1973
  8. L. C. Freeman. A set of measures of centrality based on betweenness. Sociometry, 40(1):35–41, 1977.
  9. H. Jeong, S. Mason, A.-L. Barabasi, and Z. Oltvai. Lethality and centrality in protein networks. Nature, 411:41, 2001
  10. 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.
  11. 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
  12. 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
  13. U. Brandes. A faster algorithm for betweenness centrality. J. Mathematical Sociology, 25(2):163–177, 2001.
  14. 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

Computer Science
Information Sciences

Keywords

Parallel algorithm weighted graph centrality betweenneess centrality etc