×

Gaussianization of the spectra of graphs and networks. Theory and applications. (English) Zbl 1401.05178

Summary: Matrix functions of the adjacency matrix are very useful for understanding important structural properties of graphs and networks, such as communicability, node centrality, bipartivity, and many more. They are also intimately related to the solution of differential equations describing dynamical processes on graphs and networks. Here, we propose a new matrix function based on the Gaussianization of the adjacency matrix of a graph. This function gives more weight to a selected reference eigenvalue \(\lambda_{\mathrm{ref}}\), which may be located in any region of the graph spectra. We show here that this matrix function can be derived from physical models that consider the interactions between nearest and next-nearest neighbors in the graph. We first obtain a few mathematical results for the trace of this matrix function when \(\lambda_{\mathrm{ref}} = - 1\) (\(H_{- 1}\)) for simple graphs as well as for random graphs. We also provide a combinatorial interpretation of this index in terms of subgraphs in the graph, and in terms of the competition pressure among agents in a complex system. Finally, we apply this index to the study of magnetic properties of molecules emerging due to spin interactions as well as to studying the temporal evolution of the international trade network in the period 1992-2002. In both cases we give a clear phenomenological interpretation of the processes described.

MSC:

05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
05C82 Small world graphs, complex networks (graph-theoretic aspects)

Software:

mftoolbox
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Abramovich, M.; Stegun, I., Handbook of mathematical functions with formulas, graphs and mathematical tables, National Bureau of Standards, Appl. Math. Series, vol. 55, (1964) · Zbl 0171.38503
[2] Arrigo, F.; Benzi, M., Updating and downdating techniques for optimizing network communicability, SIAM J. Sci. Comput., 38, B25-B49, (2016) · Zbl 1328.05174
[3] Ball, P., Elusive triangulene created by moving atoms one at a time, Nature, 542, 284-285, (2017)
[4] Barabási, A.-L.; Albert, R., Emergence of scaling in random networks, Science, 286, 509-512, (1999) · Zbl 1226.05223
[5] Benzi, M.; Klymko, C., On the limiting behavior of parameter-dependent network centrality measures, SIAM J. Matrix Anal. Appl., 36, 686-706, (2015) · Zbl 1314.05113
[6] Benzi, M.; Estrada, E.; Klymko, C., Ranking hubs and authorities using matrix functions, Linear Algebra Appl., 438, 2447-2474, (2013) · Zbl 1258.05067
[7] Blackwell, P.; Edmondson-Jones, M.; Jordan, J., Spectra of adjacency matrices of random geometric graphs, (2007), University of Sheffield, Department of Probability and Statistics
[8] Brouwer, A. E.; Haemers, W. H., Spectra of graphs, (2011), Springer Science & Business Media
[9] Cámara, M.; Haemers, W. H., Spectral characterizations of almost complete graphs, Discrete Appl. Math., 176, 19-23, (2014) · Zbl 1298.05233
[10] Canadell, E.; Doublet, M.-L.; Iung, Ch., Orbital approach to the electronic structure of solids, (2012), Oxford University Press Oxford
[11] Canning, A.; Wang, L. W.; Williamson, A.; Zunger, A., Parallel empirical pseudopotential electronic structure calculations for million atom systems, J. Comput. Phys., 160, 29-41, (2000) · Zbl 0963.65110
[12] Chen, G.; Wang, X.; Li, X., Fundamentals of complex networks: models, structures and dynamics, (2014), John Wiley & Sons
[13] Collatz, L.; Sinogowitz, U., Spektren endlicher grafen, Abh. Math. Semin. Univ. Hambg., 21, 63-77, (1957) · Zbl 0077.36704
[14] Corboz, P.; Jordan, J.; Vidal, G., Simulation of fermionic lattice models in two dimensions with projected entangled-pair states: next-nearest neighbor Hamiltonians, Phys. Rev. B, 82, (2010)
[15] Costa, L. F.; Oliveira, O. N.; Travieso, G.; Rodrigues, F. A.; Villas Boas, P. R.; Antiqueira, L.; Viana, M. P.; Correa Rocha, L. E., Analyzing and modeling real-world phenomena with complex networks: a survey of applications, Adv. Phys., 60, 329-412, (2011)
[16] Cvetković, D., Applications of graph spectra: an introduction to the literature, (Cvetković, D.; Gutman, I., Applications of Graph Spectra, (2009), Math. Inst. Belgrade), 123-140
[17] Cvetković, D. M.; Doob, M.; Sachs, H., Spectra of graphs: theory and application, (1980), Academic Press · Zbl 0458.05042
[18] Deng, H.; Radenković, S.; Gutman, I., The estrada index, (Cvetković, D.; Gutman, I., Applications of Graph Spectra, (2009), Math. Inst. Belgrade), 123-140 · Zbl 1224.05296
[19] Ejov, V.; Filar, J. A.; Lucas, S. K.; Zograf, P., Clustering of spectra and fractals of regular graphs, J. Math. Anal. Appl., 333, 236-246, (2007) · Zbl 1118.05062
[20] Ejov, V.; Friedlan, S.; Nguyen, G. T., A note on the Graph’s resolvent and the multifilar structure, Linear Algebra Appl., 431, 1367-1379, (2009) · Zbl 1203.05091
[21] Erdős, P.; Rényi, A., On random graphs, I, Publ. Math., 6, 290-297, (1959) · Zbl 0092.15705
[22] Esser, F.; Harary, F., On the spectrum of a complete multipartite graph, European J. Combin., 1, 211-218, (1980) · Zbl 0454.05045
[23] Estrada, E., Characterization of the folding degree of proteins, Bioinformatics, 18, 697-704, (2002)
[24] Estrada, E., Spectral scaling and good expansion properties in complex networks, Europhys. Lett., 73, 649, (2006)
[25] Estrada, E., Topological structural classes of complex networks, Phys. Rev. E, 75, (2007)
[26] Estrada, E., Generalized walks-based centrality measures for complex biological networks, J. Theoret. Biol., 263, 556-565, (2010)
[27] Estrada, E., The structure of complex networks. theory and applications, (2011), Oxford University Press
[28] Estrada, E., The electron density function of the Hückel (tight-binding) model, Proc. R. Soc. A, 474, (2018) · Zbl 1402.92445
[29] Estrada, E.; Benzi, M., What is the meaning of the graph energy after all?, Discrete Appl. Math., 230, 71-77, (2017) · Zbl 1368.05094
[30] Estrada, E.; Gómez-Gardeñes, J., Network bipartivity and the transportation efficiency of European passenger airlines, Phys. D, 323-324, 57-63, (2016) · Zbl 1364.90041
[31] Estrada, E.; Hatano, N., Statistical-mechanical approach to subgraph centrality in complex networks, Chem. Phys. Lett., 439, 247-251, (2007)
[32] Estrada, E.; Hatano, N., Communicability in complex networks, Phys. Rev. E, 77, (2008)
[33] Estrada, E.; Higham, D. J., Network properties revealed through matrix functions, SIAM Rev., 52, 96-714, (2010) · Zbl 1214.05077
[34] Estrada, E.; Rodríguez-Velázquez, J. A., Subgraph centrality in complex networks, Phys. Rev. E, 71, (2005)
[35] Estrada, E.; Rodríguez-Velázquez, J. A., Spectral measures of bipartivity in complex networks, Phys. Rev. E, 72, (2005)
[36] Estrada, E.; Silver, G., Accounting for the role of long walks on networks via a new matrix function, J. Math. Anal. Appl., 449, 1581-1600, (2017) · Zbl 1355.05233
[37] Estrada, E.; Hatano, N.; Benzi, M., The physics of communicability in complex networks, Phys. Rep., 514, 89-119, (2012)
[38] Estrada, E.; Alhomaidhi, A. A.; Al-Thukair, F., Exploring the “middle earth” of network spectra via a Gaussian matrix function, Chaos, 27, (2017) · Zbl 1390.05126
[39] Farkas, I. J.; Derényi, I.; Barabási, A.-L.; Vicsek, T., Spectra of “real-world” graphs: beyond the semicircle law, Phys. Rev. E, 64, (2001)
[40] Garlaschelli, D.; Loffredo, M. I., Structure and evolution of the world trade network, Phys. A, 355, 138-144, (2005)
[41] Gutman, I.; Deng, H.; Radenković, S., The estrada index: an updated survey, (Cvetković, D.; Gutman, I., Selected Topics on Applications of Graph Spectra, (2011), Math. Inst. Beograd), 155-174 · Zbl 1289.05288
[42] Higham, N. J., Functions of matrices: theory and computation, (2008), Society for Industrial and Applied Mathematics Philadelphia, PA · Zbl 1167.15001
[43] Hückel, E., Zur quantentheorie der doppelbindung, Z. Phys., 60, 423-456, (1930) · JFM 56.1315.01
[44] Hückel, E., Quantentheoretische beiträge zum benzolproblem, Z. Phys., 70, 204-286, (1931) · Zbl 0002.09601
[45] Jiang, Y. S.; Chen, G. Y., On subspectral problem - benzenoid hydrocarbons with common eigenvalues ±1, Theor. Chim. Acta, 76, 437-450, (1990)
[46] Kadirko, V.; Ziegler, K.; Kogan, E., Next-nearest-neighbor tight-binding model of plasmons in graphene, (2 Nov. 2011), arXiv preprint
[47] Katz, L., A new index derived from sociometric data analysis, Psychometrika, 18, 39-43, (1953) · Zbl 0053.27606
[48] Ketzmerick, R.; Petschel, G.; Geisel, T., Slow decay of temporal correlations in quantum systems with Cantor spectra, Phys. Rev. Lett., 69, 695, (1992)
[49] Krivelevich, M.; Sudakov, B., The largest eigenvalue of sparse random graphs, Combin. Probab. Comput., 12, 61-72, (2003) · Zbl 1012.05109
[50] Ma, Z.; Cheng, L. K., The effects of financial crises on international trade, (International Trade in East Asia, NBER-East Asia Seminar on Economics, vol. 14, (1 Aug. 2005), University of Chicago Press), 253-286
[51] Mitsuhashi, R.; Suzuki, Y.; Yamanari, Y.; Mitamura, H.; Kambe, T.; Ikeda, N.; Okamoto, H.; Fujiwara, A.; Yamaji, M.; Kawasaki, N.; Maniwa, Y., Superconductivity in alkali-metal-doped picene, Nature, 464, 76, (2010)
[52] Morita, Y.; Suzuki, S.; Sato, K.; Takui, T., Synthetic organic spin chemistry for structurally well-defined open-shell graphene fragments, Nat. Chem., 3, 197, (2011)
[53] de la Peña, J. A.; Gutman, I.; Rada, J., Estimating the estrada index, Linear Algebra Appl., 427, 70-76, (2007) · Zbl 1184.05082
[54] Powell, B. J., An introduction to effective low-energy Hamiltonians in condensed matter physics and chemistry, (9 Jun. 2009), arXiv preprint
[55] Romero, F. D.; Pitcher, M. J.; Hiley, C. I.; Whitehead, G. F.; Kar, S.; Ganin, A. Y.; Antypov, D.; Collins, C.; Dyer, M. S.; Klupp, G.; Colman, R. H., Redox-controlled potassium intercalation into two polyaromatic hydrocarbon solids, Nat. Chem., 9, 644, (2017)
[56] Rowlinson, P., On multiple eigenvalues of trees, Linear Algebra Appl., 432, 3007-3011, (2010) · Zbl 1195.05044
[57] Shang, Y., Lower bounds for Gaussian estrada index of graphs, Symmetry, 10, 325, (2018)
[58] Smith, J. H., Some properties of the spectrum of a graph, (Guy, R.; Hanani, H.; Sauer, N.; Schönheim, J., Combinatorial Structures and Their Application, (1970), Gordon and Breach, Science Publ., Inc. New York, London, Paris), 403-406
[59] Squartini, T.; Fagiolo, G.; Garlaschelli, D., Randomizing world trade. I. A binary network analysis, Phys. Rev. E, 84, (2011)
[60] Takabayashi, Y.; Menelaou, M.; Tamura, H.; Takemori, N.; Koretsune, T.; Štefančič, A.; Klupp, G.; Buurma, A. J.; Nomura, Y.; Arita, R.; Arčon, D., π-electron \(\operatorname{S} = 1 / 2\) quantum spin-liquid state in an ionic polyaromatic hydrocarbon, Nat. Chem., 9, 635, (2017)
[61] Van Mieghem, P., Graph spectra for complex networks, (2010), Cambridge University Press
[62] Wang, L. W.; Zunger, A., Solving schroedinger’s equation around a desired energy: application to silicon quantum dots, J. Chem. Phys., 100, 2394, (1994)
[63] Wigner, E., Characteristic vectors of bordered matrices with infinite dimensions, Ann. Math., 62, 548-564, (1955) · Zbl 0067.08403
[64] Xue, M.; Cao, T.; Wang, D.; Wu, Y.; Yang, H.; Dong, X.; He, J.; Li, F.; Chen, G. F., Superconductivity above 30 K in alkali-metal-doped hydrocarbon, Sci. Rep., 30, (2012)
[65] Yates, K., Hückel molecular orbital theory, (2012), Elsevier
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.