×

Spectral properties of unimodular lattice triangulations. (English) Zbl 1342.82039

Summary: Random unimodular lattice triangulations have been recently used as an embedded random graph model, which exhibit a crossover behavior between an ordered, large-world and a disordered, small-world behavior. Using the ergodic Pachner flips that transform such triangulations into another and an energy functional that corresponds to the degree distribution variance, Markov chain Monte Carlo simulations can be applied to study these graphs. Here, we consider the spectra of the adjacency and the Laplacian matrix as well as the algebraic connectivity and the spectral radius. Power law dependencies on the system size can clearly be identified and compared to analytical solutions for periodic ground states. For random triangulations we find a qualitative agreement of the spectral properties with well-known random graph models. In the microcanonical ensemble analytical approximations agree with numerical simulations. In the canonical ensemble a crossover behavior can be found for the algebraic connectivity and the spectral radius, thus combining large-world and small-world behavior in one model. The considered spectral properties can be applied to transport problems on triangulation graphs and the crossover behavior allows a tuning of important transport quantities.

MSC:

82B20 Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics
05C80 Random graphs (graph-theoretic aspects)

Software:

NetworkX
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Albert, R., Barabási, A.L.: Statistical mechanics of complex networks. Rev. Mod. Phys. 74, 47-97 (2002) · Zbl 1205.82086 · doi:10.1103/RevModPhys.74.47
[2] Almeida, G.M.A., Souza, A.M.C.: Quantum transport with coupled cavities on an Apollonian network. Phys. Rev. A 87, 033804 (2013) · doi:10.1103/PhysRevA.87.033804
[3] Almendral, J.A., Daz-Guilera, A.: Dynamical and spectral properties of complex networks. New J. Phys. 9(6), 187 (2007) · doi:10.1088/1367-2630/9/6/187
[4] Ambjørn, J., Loll, R.: Reconstructing the universe. Phys. Rev. D 72, 064014 (2005) · doi:10.1103/PhysRevD.72.064014
[5] Andrade, J.S., Herrmann, H.J., Andrade, R.F.S., da Silva, L.R.: Apollonian networks: simultaneously scale-free, small world, euclidean, space filling, and with matching graphs. Phys. Rev. Lett. 94, 018702 (2005) · doi:10.1103/PhysRevLett.94.018702
[6] Aste, T., Gramatica, R., Di Matteo, T.: Exploring complex networks via topological embedding on surfaces. Phys. Rev. E 86, 036109 (2012) · doi:10.1103/PhysRevE.86.036109
[7] Aste, T., Rivier, N.: Random cellular froths in spaces of any dimension and curvature. J. Phys. A 28(5), 1381 (1995) · Zbl 0853.60096 · doi:10.1088/0305-4470/28/5/023
[8] Aste, T., Sherrington, D.: Glass transition in self-organizing cellular patterns. J. Phys. A 32, 70497056 (1999) · Zbl 0962.82064 · doi:10.1088/0305-4470/32/41/301
[9] Banerjee, A., Jost, J.: Graph spectra as a systematic tool in computational biology. Discret. Appl. Math. 157(10), 2425-2431 (2009) · Zbl 1172.92001 · doi:10.1016/j.dam.2008.06.033
[10] Barabási, A.L., Albert, R.: Emergence of scaling in random networks. Science 286(5439), 509-512 (1999) · Zbl 1226.05223 · doi:10.1126/science.286.5439.509
[11] Bauer, M., Golinelli, O.: Random incidence matrices: moments of the spectral density. J. Stat. Phys. 103(1-2), 301-337 (2001) · Zbl 0999.82035 · doi:10.1023/A:1004879905284
[12] Biroli, G., Monasson, R.: A single defect approximation for localized states on random lattices. J. Phys. A 32(24), L255 (1999) · doi:10.1088/0305-4470/32/24/101
[13] Bray, A.J., Rodgers, G.J.: Diffusion in a sparsely connected space: a model for glassy relaxation. Phys. Rev. B 38, 11461-11470 (1988) · doi:10.1103/PhysRevB.38.11461
[14] Caputo, P., Martinelli, F., Sinclair, A., Stauffer, A.: Random lattice triangulations: structure and algorithms. Ann. Appl. Probab. 25(3), 1650-1685 (2015) · Zbl 1329.60328 · doi:10.1214/14-AAP1033
[15] Chung, F., Lu, L.: Complex Graphs and Networks. No. 107 in CBMS Regional Conference Series in Mathematics. American Mathematical Society (2006) · Zbl 1114.90071
[16] Costa, L.D.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. 30(3), 329-412 (2011) · doi:10.1080/00018732.2011.572452
[17] Cvetković, D.M., Rowlinson, P., Simić, S.: An Introduction to the Theory of Graph Spectra. Cambridge University Press, Camebridge (2010) · Zbl 1211.05002
[18] de Abreu, N.M.M.: Old and new results on algebraic connectivity of graphs. Linear Algebra Appl. 423(1), 53-73 (2007) · Zbl 1115.05056 · doi:10.1016/j.laa.2006.08.017
[19] De Loera, J.A., Rambau, J., Santos, F.: Triangulations. Structures for Algorithms and Applications. Springer, Berlin (2010) · Zbl 1207.52002
[20] Dean, D.S.: An approximation scheme for the density of states of the Laplacian on random graphs. J. Phys. A 35(12), L153 (2002) · Zbl 1038.82031 · doi:10.1088/0305-4470/35/12/101
[21] Ding, X., Jiang, T.: Spectral distributions of adjacency and Laplacian matrices of random graphs. Ann. Appl. Probab. 20(6), 20862117 (2010) · Zbl 1231.05236 · doi:10.1214/10-AAP677
[22] Du, Z., Liu, Z.: On the Estrada and Laplacian Estrada indices of graphs. Linear Algebra Appl. 435(8), 2065-2076 (2011) · Zbl 1221.05211 · doi:10.1016/j.laa.2011.03.057
[23] Dubertret, B., Rivier, N., Peshkin, M.A.: Long-range geometrical correlations in two-dimensional foams. J. Phys. A. 31(3), 879 (1998) · Zbl 0945.74005 · doi:10.1088/0305-4470/31/3/005
[24] Earl, D.J., Deem, M.W.: Parallel tempering: Theory, applications, and new perspectives. Phys. Chem. Chem. Phys. 7, 3910-3916 (2005) · doi:10.1039/b509983h
[25] Erdös, P., Rényi, A.: On random graphs. Publ. Math. Debrecen 6, 290-297 (1959) · Zbl 0092.15705
[26] Erdös, P., Rényi, A.: On the evolution of random graphs. In: Publication of the Mathematical Institute of the Hungarian Academy of Sciences, pp. 17-61 (1960) · Zbl 0103.16301
[27] Erdös, P., Rényi, A.: On the strength of connectedness of a random graph. Acta Math. Acad. Sci. H. 12(1-2), 261-267 (1964) · Zbl 0103.16302 · doi:10.1007/BF02066689
[28] Estrada, E.: Characterization of 3D molecular structure. Chem. Phys. Lett. 319(56), 713-718 (2000) · doi:10.1016/S0009-2614(00)00158-5
[29] Estrada, E., Rodríguez-Velázquez, J.A.: Spectral measures of bipartivity in complex networks. Phys. Rev. E 72, 046105 (2005) · doi:10.1103/PhysRevE.72.046105
[30] Evangelou, S.N.: Quantum percolation and the Anderson transition in dilute systems. Phys. Rev. B 27, 1397-1400 (1983) · doi:10.1103/PhysRevB.27.1397
[31] Evangelou, S.N.: A numerical study of sparse random matrices. J. Stat. Phys. 69(1-2), 361-383 (1992) · Zbl 0888.65046 · doi:10.1007/BF01053797
[32] Evangelou, S.N., Economou, E.N.: Spectral density singularities, level statistics, and localization in a sparse random matrix ensemble. Phys. Rev. Lett. 68, 361-364 (1992) · doi:10.1103/PhysRevLett.68.361
[33] Farkas, I., Derenyi, I., Palla, G., Vicsek, T.: Equilibrium statistical mechanics of network structures. In: E. Ben-Naim, H. Frauenfelder, Z. Toroczkai (eds.) Complex Networks, Lecture Notes in Physics, vol. 650, pp. 163-187. Springer (2004) · Zbl 1102.82005
[34] 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, 026704 (2001) · doi:10.1103/PhysRevE.64.026704
[35] Fiedler, M.: Algebraic connectivity of graphs. Czechoslovak Math. J. 23(2), 298-305 (1973) · Zbl 0265.05119
[36] Gervais, C., Wüst, T., Landau, D.P., Xu, Y.: Application of the Wang-Landau algorithm to the dimerization of glycophorin A. J. Chem. Phys 130(21), 215106 (2009) · doi:10.1063/1.3148186
[37] Grone, R.D.: Eigenvalues and the degree sequences of graphs. Linear Multilinear Algebra 39, 133-136 (1995) · Zbl 0831.05047 · doi:10.1080/03081089508818384
[38] Guhr, T., Müller-Groeling, A., Weidenmüller, H.A.: Random-matrix theories in quantum physics: common concepts. Phys. Rep. 299(46), 189-425 (1998) · doi:10.1016/S0370-1573(97)00088-4
[39] Hagberg, A.A., Schult, D.A., Swart, P.J.: Exploring network structure, dynamics, and function using NetworkX. In: Varoquaux, G., Vaught, T., Millman, J. (eds.) Proceedings of the 7th Python in Science Conference, pp. 11-15. Pasadena (2008)
[40] Juhász, F.: On the spectrum of a random graph. In: L. Lovasz, V.T. Sos (eds.) Algebraic Methods in Graph Theory, Colloquia Mathematica Societatis Janos Bolyai, vol. 25 (1981) · Zbl 0475.05060
[41] Juvan, M., Mohar, B.: Laplace eigenvalues and bandwidth-type invariants of graphs. J. Graph Theory 17(3), 393-407 (1993) · Zbl 0785.05077 · doi:10.1002/jgt.3190170313
[42] Kaibel, V., Ziegler, G.M.: Counting lattice triangulations. Lond. Math. Soc. Lect. Note Ser. 307, 277-308 (2003) · Zbl 1031.05011
[43] Kirchhoff, G.: Über die Auflösung der Gleichungen, auf welche man bei der Untersuchung der linearen Verteilung galvanischer Ströme geführt wird. Ann. Phys. Chem. 72, 497-508 (1847) · doi:10.1002/andp.18471481202
[44] Knauf, J.F., Krüger, B., Mecke, K.: Entropy of unimodular lattice triangulations. EPL (Europhys. Lett.) 109(4), 40011 (2015) · doi:10.1209/0295-5075/109/40011
[45] Kownacki, J.P.: Freezing of triangulations. Eur. Phys. J. B 38(3), 485-494 (2004) · doi:10.1140/epjb/e2004-00143-8
[46] Krüger, B., Schmidt, E.M., Mecke, K.: Unimodular lattice triangulations as small-world and scale-free random graphs. New J. Phys. 17(2), 023013 (2015) · Zbl 1452.05172 · doi:10.1088/1367-2630/17/2/023013
[47] Kumar, S.: Random matrix ensembles: Wang-Landau algorithm for spectral densities. EPL (Europhys. Lett.) 101(2), 20002 (2013) · doi:10.1209/0295-5075/101/20002
[48] Lawson, C.L.: Transforming triangulations. Discret. Math. 3(4), 365-372 (1972) · Zbl 0253.05116 · doi:10.1016/0012-365X(72)90093-3
[49] Lee, J.: New Monte Carlo algorithm: entropic sampling. Phys. Rev. Lett. 71, 211-214 (1993) · doi:10.1103/PhysRevLett.71.211
[50] Metropolis, N., Rosenbluth, A.W., Rosenbluth, M.N., Teller, A.H., Teller, E.: Equation of state calculations by fast computing machines. J. Chem. Phys. 21, 1087 (1953) · Zbl 1431.65006 · doi:10.1063/1.1699114
[51] Mirlin, A.D., Fyodorov, Y.V.: Universality of level correlation function of sparse random matrices. J. Phys. A 24(10), 2273 (1991) · Zbl 0760.15017 · doi:10.1088/0305-4470/24/10/016
[52] Mohar, B.: Isoperimetric numbers of graphs. J. Combin. Theory Ser. B 47(3), 274-291 (1989) · Zbl 0719.05042 · doi:10.1016/0095-8956(89)90029-4
[53] Mohar, B.: The Laplacian spectrum of graphs. In: Y. Alavi, G. Chartrand, O.R. Oellermann, A.J. Schwenk (eds.) Graph Theory, Combinatorics, and Applications, vol. 2, pp. 871-898. Wiley (1991) · Zbl 0840.05059
[54] Mohar, B.: Laplace eigenvalues of graphs—a survey. Discret. Math. 109(13), 171-183 (1992) · Zbl 0783.05073 · doi:10.1016/0012-365X(92)90288-Q
[55] Mohar, B., Poljak, S.: Eigenvalues in combinatorial optimization. In: R. Brualdi, S. Friedland, V. Klee (eds.) Combinatorial and Graph-Theoretical Problems in Linear Algebra, The IMA Volumes in Mathematics and Its Applications, vol. 50, pp. 107-151. Springer, New York (1993) · Zbl 0806.90104
[56] Monasson, R.: Diffusion, localization and dispersion relations on small-world lattices. Eur. Phys. J. B 12(4), 555-567 (1999) · doi:10.1007/s100510051038
[57] Mülken, O., Blumen, A.: Continuous-time quantum walks: models for coherent transport on complex networks. Phys. Rep. 502(23), 37-87 (2011) · doi:10.1016/j.physrep.2011.01.002
[58] Newman, M.: Networks. An Introduction. Oxford University Press, Oxford (2010) · Zbl 1195.94003 · doi:10.1093/acprof:oso/9780199206650.001.0001
[59] Newman, M., Watts, D.: Renormalization group analysis of the small-world network model. Phys. Lett. A 263(46), 341-346 (1999) · Zbl 0940.82029 · doi:10.1016/S0375-9601(99)00757-4
[60] Oguey, C., Rivier, N., Aste, T.: Stratifications of cellular patterns: hysteresis and convergence. Eur. Phys. J. B 33(4), 447-455 (2003) · doi:10.1140/epjb/e2003-00185-4
[61] Pachner, U.: Konstruktionsmethoden und das kombinatorische Homöomorphieproblem für Triangulationen kompakter semilinearer Mannigfaltigkeiten. Abh. Math. Sem. Univ. Hamburg 57, 69-85 (1986) · Zbl 0651.52007 · doi:10.1007/BF02941601
[62] Parzen, E.: On estimation of a probability density function and mode. Ann. Math. Stat. 33, 1065 (1962) · Zbl 0116.11302 · doi:10.1214/aoms/1177704472
[63] Rosenblatt, M.: On estimation of a probability density function and mode. Remarks on some nonparametric estimates of a density function. Ann. Math. Statist. 27, 832 (1956) · Zbl 0073.14602 · doi:10.1214/aoms/1177728190
[64] Rovelli, C.: Quantum Gravity. Cambridge Monographs on Mathematical Physics. Cambridge University Press, Cambridge (2007) · Zbl 1140.83005 · doi:10.1016/B978-044451560-5/50015-4
[65] Silverman, B.: Density Estimation for Statistics and Data Analysis. Monographs on Statistics & Applied Probability. Chapman & Hall/CRC, London (1986) · Zbl 0617.62042 · doi:10.1007/978-1-4899-3324-9
[66] Song, W.M., Di Matteo, T., Aste, T.: Building complex networks with platonic solids. Phys. Rev. E 85, 046115 (2012) · doi:10.1103/PhysRevE.85.046115
[67] Stauffer, A.: A Lyapunov function for Glauber dynamics on lattice triangulations. arXiv:1504.07980 (2015) · Zbl 1407.60125
[68] Sulanke, T., Lutz, F.H.: Isomorphism-free lexicographic enumeration of triangulated surfaces and 3-manifolds. Eur. J. Comb. 30(8), 1965-1979 (2009) · Zbl 1189.57019 · doi:10.1016/j.ejc.2008.12.016
[69] Sullivan, J.M.: The geometry of bubbles and foams. In: J. Sadoc, N. Rivier (eds.) Foams and Emulsions, NATO Science Series E, vol. 354, pp. 379-402. Springer (1999)
[70] Trinajstić, N.: Graph theory and molecular orbitals. In: D. Bonchev, D. Rouvray (eds.) Chemical Graph Theory: Introduction and Fundamentals, Mathematical Chemistry Series, chap. 6, pp. 235-275. Abacus Press (1991)
[71] van den Heuvel, J., Peji, S.: Using Laplacian eigenvalues and eigenvectors in the analysis of frequency assignment problems. Ann. Oper. Res. 107(1-4), 349-368 (2001) · Zbl 1015.90051 · doi:10.1023/A:1014927805247
[72] Varshney, L.: The wiring economy principle for designing inference networks. IEEE J. Select. Areas Commun. 31(6), 1095-1104 (2013) · doi:10.1109/JSAC.2013.130611
[73] Wang, F., Landau, D.P.: Determining the density of states for classical statistical models: a random walk algorithm to produce a flat histogram. Phys. Rev. E 64, 056101 (2001) · doi:10.1103/PhysRevE.64.056101
[74] Wang, F., Landau, D.P.: Efficient, multiple-range random walk algorithm to calculate the density of states. Phys. Rev. Lett. 86, 2050-2053 (2001) · doi:10.1103/PhysRevLett.86.2050
[75] Watts, D.J., Strogatz, S.H.: Collective dynamics of small-world networks. Nature 393(6684), 440-442 (1998) · Zbl 1368.05139 · doi:10.1038/30918
[76] Wigner, E.P.: Characteristic vectors of bordered matrices with infinite dimensions. Ann. Math. 62(3), 548-564 (1955) · Zbl 0067.08403 · doi:10.2307/1970079
[77] Wigner, E.P.: On the distribution of the roots of certain symmetric matrices. Ann. Math. 67(2), 325-327 (1958) · Zbl 0085.13203 · doi:10.2307/1970008
[78] Wüst, T., Landau, D.P.: Versatile approach to access the low temperature thermodynamics of lattice polymers and proteins. Phys. Rev. Lett. 102, 178101 (2009) · doi:10.1103/PhysRevLett.102.178101
[79] Wüst, T., Landau, D.P.: Optimized Wang-Landau sampling of lattice polymers: ground state search and folding thermodynamics of hp model proteins. J. Chem. Phys. 137(6), 064903 (2012) · doi:10.1063/1.4742969
[80] Yu, A., Lu, M., Tian, F.: On the spectral radius of graphs. Linear Algebra Appl. 387, 41-49 (2004) · Zbl 1041.05051 · doi:10.1016/j.laa.2004.01.020
[81] Zhou, T., Yan, G., Wang, B.H.: Maximal planar networks with large clustering coefficient and power-law degree distribution. Phys. Rev. E 71, 046141 (2005) · doi:10.1103/PhysRevE.71.046141
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.