Further Results on Betweenness Centrality of Graphs

Document Type : Research Paper


Ferdowsi University of Mashhad, I R Iran


Betweenness centrality is a distance-based invariant of graphs. In this paper, we use
lexicographic product to compute betweenness centrality of some important classes of
graphs. Finally, we pose some open problems related to this topic.


Main Subjects

1. T. Akutsu and H. Nagamochi, Comparison and Enumeration of Chemical
Graphs, Comput. Struct. Biotech. J. 5 (2013) 1−9.
2. A. R. Ashrafi, A. Hamzeh and S. Hossein-Zadeh, Calculation of some
topological indices of splice and links of graphs, J. Appl. Math. &
Informatics 29 (2011) 327−335.
3. A. Bavelas, A mathematical model for group structure, Human
Organizations 7 (1948) 16−30.
4. J. A. Bondy and U. S. R. Murty, Graph Theory, Springer−Verlag, New
York, 2008.
5. T. Došlić, Splices, links, and their degree-weighted Wiener polynomials,
Graph Theory Notes New York 48 (2005) 47−55.
6. E. Estrada, Virtual identification of essential proteins within the protein
interaction network of yeast, Proteomics 6 (2006) 35−40.
7. L. Freeman, A set of measures of centrality based on betweenness,
Sociometry 40 (1977) 35−41.
8. L. C. Freeman, Centrality in social networks conceptual clarification,
Social Networks 1 (1979) 215−239.
9. A. M. M. Gonzalez, B. Dalsgaard and J. M. Olesen, Centrality measures
and the importance of generalist species in pollination networks, Ecol.
Complex. 7 (2010) 36−43.
10. R. Hammack, W. Imrich and S. Klavžar, Handbook of Product Graphs, 2rd
ed., Taylor & Francis Group, 2011.
11. S. Kumar and K. Balakrishnan, Betweenness centrality of Cartesian
product of graphs, arXiv:1603.04258.
12. D. Koschutzki and F. Schreiber, Centrality analysis methods for biological
networks and their application to gene regulatory networks, Gene Regul.
Syst. Bio. 2008 (2008) 193−201.
13. V. Latora and M. Marchiori, A measure of centrality based on network
efficiency, New J. Phys. 9 (2007) article188.
14. M. E. J. Newman, Scientific collaboration networks. II. shortest paths,
weighted networks, and centrality, Phys. Rev. E 64 (2001) 1−7.
15. E. Otte and R. Rousseau, Social network analysis: a powerful strategy, also
for the information sciences, J. Inf. Sci. 28 (2002) 441−453.
16. K. Park and A. Yilmaz, A social network an analysis approach to analyze
road networks, in Proceedings of the ASPRS Annual Conference, San
Diego, Calif, USA, 2010.
17. M. Rubinov and O. Sporns, Complex network measures of brain
connectivity: uses and interpretations, Neuro Image 52 (2010) 1059−1069.
18. M. Tavakoli and F. Rahbarnia, Note on properties of first Zagreb index of
graphs, Iranian J. Math. Chem. 3 (2012) s1−s5.
19. M. Tavakoli, F. Rahbarnia and A. R. Ashrafi, Note on strong product of
graphs, Kragujevac J. Math. 37 (2013) 187−193.
20. S. K. R. Unnithan, B. Kannan and M. Jathavedan, Betweenness centrality
in some classes of graphs, Int. J. Combin. 2014 (2014), Article ID 241723,
12 pages.