Relating centralities in graphs and the principal eigenvector of its distance matrix

Authors

DOI:

https://doi.org/10.22199/issn.0717-6279-2021-01-0014

Keywords:

Centrality, Distance matrix, Principal eigenvector, Spectral closeness

Abstract

In this work a new centrality measure of graphs is presented, based on the principal eigenvector of the distance matrix: spectral closeness. Using spectral graph theory, we show some of its properties and we compare the results of this new centrality with closeness centrality. In particular, we prove that for threshold graphs these two centralities always coincide. In addition we construct an infinity family of graphs for which these centralities never coincide.

Author Biographies

Celso Marques da Silva Jr., Centro Federal de Educação Tecnológica Celso Suckow da Fonseca.

Dept. de Ensino Médio e Técnico.

Renata R. Del-Vecchio, Universidade Federal Fluminense.

Instituto de Matemática e Estatística.

References

A. Bavelas, “Communication patterns in task‐oriented groups”, The Journal of the Acoustical Society of America, vol. 22, no. 6, pp. 725–730, Nov. 1950, doi: 10.1121/1.1906679

P. Bonacich, “Factoring and weighting approaches to status scores and clique identification”, The journal of mathematical sociology, vol. 2, no. 1, pp. 113-120, 1972, doi: 10.1080/0022250X.1972.9989806

A. E. Brouwer and W. H. Haemers, Spectra of graphs. New York, NY: Springer, 2012, doi: 10.1007/978-1-4614-1939-6

G. Caporossi, M. Paiva, D. Vukičević, and M. Segatto, “Centrality and betweenness: vertex and edge decomposition of the Wiener index”, MATCH-communications in mathematical and computer chemistry, vol. 68, no. 1, pp. 293-302, 2012. [On line]. Available: https://bit.ly/3ids0Oh

Y. Chen, H. Lin, and J. Shu. “Sharp upper bounds on the distance spectral radius of a graph”, Linear algebra and its applications, vol. 439, no, 9, pp. 2659-2666, Nov. 2013, doi: 10.1016/j.laa.2013.07.023

V. Chvátal and P. L. Hammer, “Aggregation of inequalities in integer programming”, Annals of discrete mathematics, vol. 1, pp. 145-162, 1977, doi: 10.1016/S0167-5060(08)70731-3

R. Grassi, S. Stefani, and A. Torriero, “Extremal properties of graphs and eigencentrality in trees with a given degree sequence”, The journal of mathematical sociology, vol. 34, no. 2, pp. 115-135, Mar. 2010, doi: 10.1080/00222500903221563

R. Grassi, S. Stefani, and A. Torriero, “Some new results on the eigenvector centrality”, The journal of mathematical sociology, vol. 31, no. 3, pp. 237-248, Jun. 2007, doi: 10.1080/00222500701373251

O. Hein, M. Schwind, and M. Spiwoks, “Network centrality and stock market volatility: the impact of communication topologies on prices”, Journal of finance and investment analysis, vol. 1, no. 1, pp. 199-232, 2012. [On line]. Available: https://bit.ly/3iewt3x

R. A. Horn and C. R. Johnson, Matrix analysis, 2nd ed. Cambridge: Cambridge University Press, 2012.

H. Jeong, S. P. Mason, A.-L. Barabási, and Z. N. Oltvai, “Lethality and centrality in protein networks”, Nature, vol. 411, no. 6833, pp. 41–42, May 2001, doi: 10.1038/35075138

M. Krnc, Matjaz and R. Škrekovski. “Centralization of transmission in networks”, Discrete mathematics, vol. 338, no. 12, pp. 2412-2420, Dec. 2015, doi: 10.1016/j.disc.2015.06.011

X. Li, Y. Fan, and S. Zha, “A lower bound for the distance signless Laplacian spectral radius of graphs in terms of chromatic number”, Journal of mathematical research with applications, vol. 34, no. 3, pp. 289-294, May 2014, doi: 10.3770/j.issn:2095-2651.2014.03.004

X.-X. Li, Y.-Z. Fan, and Y. Wang. “Minimum distance spectral radius of graphs with given edge connectivity”, 2012, arXiv:1203.3112

B. D. McKay and A. Piperno, “Practical graph isomorphism, II”, Journal of symbolic computation, vol. 60, pp. 94-112, Jan. 2014, doi: 10.1016/j.jsc.2013.09.003

K. Okamoto, W. Chen, and X.-Y. Li, “Ranking of closeness centrality for large-scale social networks”, in Frontiers in algorithmics. FAW 2008, F. P. Preparata, X. Wu, and J. Yin, Eds. Berlin: Springer, 2008, pp. 186–195, doi: 10.1007/978-3-540-69311-6_21

A. Reggiani, S. Signoretti, P. Nijkamp, and A. Cento, “Network measures in civil air transport: a case study of Lufthansa”, in Networks, topology and dynamics, A. K. Naimzada, S. Stefani, and A. Torriero. Eds. Berlin: Springer, 2009, pp. 257-282, doi: 10.1007/978-3-540-68409-1_14

S. N. Ruzieh and D. L. Powers, “The distance spectrum of the path Pn and the first distance eigenvector of connected graphs”, Linear and multilinear algebra, vol. 28, no. 1-2, pp. 75-81, 1990, doi: 10.1080/03081089008818032

G. Sabidussi, “The centrality index of a graph”, Psychometrika, vol. 31, no. 4, pp. 581-603, Dec. 1966, doi: 10.1007/BF02289527

SageMath - Open Source Mathematics Software, Sage 7.4. 10-Oct-2016. [On line]. Available: http://old.files.sagemath.org/src-old/

M. E. Shaw, “Communication networks”, Advances in experimental social psychology, vol. 1, pp. 111-147, 1964, doi: 10.1016/S0065-2601(08)60050-7.

R. Xing and B. Zhou, “On the distance and distance signless Laplacian spectral radii of bicyclic graphs”, Linear algebra and its applications, vol. 439, no. 12, pp. 3955-3963, Dec. 2013, doi: 10.1016/j.laa.2013.10.005

Published

2021-01-16

How to Cite

[1]
C. M. da Silva Jr., R. R. Del-Vecchio, and B. B. Monteiro, “Relating centralities in graphs and the principal eigenvector of its distance matrix”, Proyecciones (Antofagasta, On line), vol. 40, no. 1, pp. 217-237, Jan. 2021.

Issue

Section

Artículos

Most read articles by the same author(s)