Vertex distinction with subgraph centrality: a proof of Estrada’s conjecture and some generalizations. (English) Zbl 1459.05310
Summary: Centrality measures are used in network science to identify the most important vertices for transmission of information and dynamics on a graph. One of these measures, introduced by E. Estrada and J. A. Rodríguez-Velázquez [“Subgraph centrality in complex networks”, Phys. Rev. E 71, Article ID 056103, 9 p. (2005; doi:10.1103/PhysRevE.71.056103)], is the \(\beta\)-subgraph centrality, which is based on the exponential of the matrix \(\beta A\), where \(A\) is the adjacency matrix of the graph and \(\beta\) is a real parameter (“inverse temperature”). We prove that for algebraic \(\beta\), two vertices with equal \(\beta\)-subgraph centrality are necessarily cospectral. We further show that two such vertices must have the same degree and eigenvector centralities. Our results settle a conjecture of Estrada and a generalization of it due to K. Kloster et al. [Linear Algebra Appl. 546, 115–121 (2018; Zbl 1391.05169)]. We also discuss possible extensions of our results.
MSC:
| 05C82 | Small world graphs, complex networks (graph-theoretic aspects) |
| 05C09 | Graphical indices (Wiener index, Zagreb index, Randić index, etc.) |
| 15A16 | Matrix exponential and similar functions of matrices |
| 11J72 | Irrationality; linear independence over a field |
Keywords:
subgraph centrality; walk-regular graph; cospectral vertices; Lindemann-Weierstrass theoremCitations:
Zbl 1391.05169References:
| [1] | Baker, A., Transcendental Number Theory, 1-8 (1990), Cambridge University Press · Zbl 0715.11032 |
| [2] | Benzi, M., A note on walk entropies in graphs, Linear Algebra Appl., 445, 395-399 (2014) · Zbl 1285.05162 |
| [3] | Benzi, M.; Klymko, C., On the limiting behavior of parameter-dependent network centrality measures, SIAM J. Matrix Anal. Appl., 36, 2, 686-706 (2015) · Zbl 1314.05113 |
| [4] | Brezinski, C., History of Continued Fractions and Padé Approximants, vol. 12, 141-259 (2012), Springer Science & Business Media |
| [5] | Godsil, C.; Smith, J., Strongly cospectral vertices, preprint · Zbl 1530.05090 |
| [6] | Chudnovsky, G. V., (Nathanson, M. B., Number Theory, Carbondale 1979: Proceedings of the Southern Illinois Number Theory Conference, vol. 751 (2006), Springer), 45-69 · Zbl 0418.10031 |
| [7] | Estrada, E., About the discriminant power of the subgraph centrality and other centrality measures, preprint |
| [8] | Estrada, E.; de la Peña, J. A., Maximum walk entropy implies walk regularity, Linear Algebra Appl., 458, 542-547 (2014) · Zbl 1296.05122 |
| [9] | Estrada, E.; de la Peña, J. A.; Hatano, N., Walk entropies in graphs, Linear Algebra Appl., 443C, 235-244 (2014) · Zbl 1282.05111 |
| [10] | Estrada, E.; Hatano, N., Statistical-mechanical approach to subgraph centrality in complex networks, Chem. Phys. Lett., 439, 247-251 (2007) |
| [11] | Estrada, E.; Hatano, N., Communicability in complex networks, Phys. Rev., 77, Article 036111 pp. (2008) |
| [12] | Estrada, E.; Hatano, N.; Benzi, M., The physics of communicability in complex networks, Phys. Rep., 514, 89-119 (2012) |
| [13] | Estrada, E.; Higham, D. J., Network properties revealed through matrix functions, SIAM Rev., 52, 4, 696-714 (2010) · Zbl 1214.05077 |
| [14] | Estrada, E.; Rodríguez-Velázquez, J. A., Subgraph centrality in complex networks, Phys. Rev., 71, 5 (2005) |
| [15] | Horn, R. A.; Johnson, C. R., Matrix Analysis, 517-537 (2013), Cambridge University Press · Zbl 1267.15001 |
| [16] | Horton, E.; Kloster, K.; Sullivan, B. D., Subgraph centrality and walk-regularity, Linear Algebra Appl., 570, 225-244 (2019) · Zbl 1411.05241 |
| [17] | Kloster, K.; Král, D.; Sullivan, B. D., Walk entropy and walk-regularity, Linear Algebra Appl., 546, 115-121 (2018) · Zbl 1391.05169 |
| [18] | Rombach, M. P.; Porter, M. A., Discriminating power of centrality measures, preprint |
| [19] | Schwenk, A. J., Almost all trees are cospectral, (New Directions in the Theory of Graphs, Proc. Third Ann Arbor Conf.. New Directions in the Theory of Graphs, Proc. Third Ann Arbor Conf., Univ. Michigan, Ann Arbor, Mich., 1971 (1973), Academic Press: Academic Press New York), 275-307 · Zbl 0261.05102 |
| [20] | Siegel, C. L., Transcendental Numbers, 1-30 (1950), Princeton University Press |
| [21] | Stevanović, D., Comment on “Subgraph centrality in complex networks”, Phys. Rev. E, 88, Article 026801 pp. (2013) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
