Relating centralities in graphs and the principal eigenvector of its distance matrix
DOI:
https://doi.org/10.22199/issn.0717-6279-2021-01-0014Keywords:
Centrality, Distance matrix, Principal eigenvector, Spectral closenessAbstract
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.
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
How to Cite
Issue
Section
Copyright (c) 2021 Celso Marques da Silva Junior, Renata R. Del-Vecchio, Bruno B. Monteiro
This work is licensed under a Creative Commons Attribution 4.0 International License.
-
Attribution — You must give appropriate credit, provide a link to the license, and indicate if changes were made. You may do so in any reasonable manner, but not in any way that suggests the licensor endorses you or your use.
- No additional restrictions — You may not apply legal terms or technological measures that legally restrict others from doing anything the license permits.