Skip to main content Accessibility help

We use cookies to distinguish you from other users and to provide you with a better experience on our websites. Close this message to accept cookies or find out how to manage your cookie settings.

Close cookie message
×
Hostname: page-component-745bb68f8f-grxwn Total loading time: 0 Render date: 2025-01-12T21:20:48.177Z Has data issue: false hasContentIssue false

2 - Quantum probability approach to spectral analysis of growing graphs

Published online by Cambridge University Press:  11 May 2024

By
Nobuaki Obata
Edited by
R. A. Bailey ,
Peter J. Cameron  and
Yaokun Wu
R. A. Bailey
Affiliation:
University of St Andrews, Scotland
Peter J. Cameron
Affiliation:
University of St Andrews, Scotland
Yaokun Wu
Affiliation:
Shanghai Jiao Tong University, China
Get access

Summary

These lecture notes provide quantum probabilistic concepts and methods for spectral analysis of graphs, in particular, for the study of asymptotic behavior of the spectral distributions of growing graphs. Quantum probability theory is an algebraic generalization of classical (Kolmogorovian) probability theory, where an element of a (not necessarily commutative) ∗-algebra is treated as a random variable. In this aspect the concepts and methods peculiar to quantum probability are applied to the spectral analysis of adjacency matrices of graphs. In particular, we focus on the method of quantum decomposition and the use of various concepts of independence. The former discloses the noncommutative nature of adjacency matrices and gives a systematic method of computing spectral distributions. The latter is related to various graph products and provides a unified aspect in obtaining the limit spectral distributions as corollaries of various central limit theorems.

Keywords

adjacency matrixasymptotic combinatoricscentral limit theoremgraph productgraph spectrumgrowing graphorthogonal polynomialsquantum decompositionquantum probabilityspectral distribution
Type
Chapter
Information
Groups and Graphs, Designs and Dynamics , pp. 87 - 175
Publisher: Cambridge University Press
Print publication year: 2024

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Accardi, L., Topics in quantum probability. New stochastic methods in physics, Phys. Rep. 77 (1981), 169–192.CrossRefGoogle Scholar
Accardi, L., Ben Ghorbal, A. and Obata, N., Monotone independence, comb graphs and Bose-Einstein condensation, Infin. Dimens. Anal. Quantum Probab. Relat. Top. 7 (2004), 419–435.CrossRefGoogle Scholar
Accardi, L. and Bożejko, M., Interacting Fock spaces and Gaussianization of probability measures, Infin. Dimens. Anal. Quantum Probab. Relat. Top. 1 (1998), 663–670.Google Scholar
Accardi, L., Rebei, H. and Riahi, A., The quantum decomposition of random variables without moments, Infin. Dimens. Anal. Quantum Probab. Relat. Top. 16 (2013), 1350012.CrossRefGoogle Scholar
Accardi, L., Riahi, A. and Rebei, H., The quantum decomposition associated with the Lévy white noise processes without moments, Probab. Math. Stat. 34 (2014), 337–362.Google Scholar
Accardi, L., Lu, Y. G. and Volovich, I., Quantum Theory and its Stochastic Limit, Springer-Verlag, Berlin, 2002.CrossRefGoogle Scholar
Akhiezer, N. I., The Classical Moment Problem and Some Related Questions in Analysis, Hafner Publishing Co., New York, 1965.Google Scholar
Arizmendi, O. and Gaxiola, T., On the spectral distribution of distance-k graph of free product graphs, Infin. Dimens. Anal. Quantum Probab. Relat. Top. 19 (2016), 1650017.CrossRefGoogle Scholar
Bannai, E. and T. Ito: Algebraic Combinatorics. I. Association Schemes, The Benjamin Cummings Publ. Co., Menlo Park, CA, 1984.Google Scholar
Biggs, N., Algebraic Graph Theory (2nd Ed.), Cambridge University Press, Cambridge, 1993.Google Scholar
M. Bożejko, Positive definite functions on the free group and the noncommutative Riesz product, Boll. Un. Mat. Ital. A (6) 5 (1986), 13–21.Google Scholar
M. Bożejko, B. Kümmerer and R. Speicher, q-Gaussian processes: Non-commutative and classical aspects, Commun. Math. Phys. 185 (1997), 129–154.CrossRefGoogle Scholar
M. Bożejko and R. Speicher, An example of a generalized Brownian motion, Commun. Math. Phys. 137 (1991), 519–531.CrossRefGoogle Scholar
Brouwer, A. E., Cohen, A. M. and Neumaier, A., Distance-Regular Graphs, Springer-Verlag, Berlin, 1989.CrossRefGoogle Scholar
Brouwer, A. E. and Haemers, W. H., Spectra of Graphs, Springer, Berlin, 2012.CrossRefGoogle Scholar
Chihara, T. S., An Introduction to Orthogonal Polynomials, Gordon and Breach Science Publishers, New York, 1978.Google Scholar
Chung, K. L., A Course in Probability Theory (3rd Ed.), Academic Press, San Diego, 2001.Google Scholar
Chung, F. and Lu, L., Complex Graphs and Networks, Amer. Math. Soc., Providence, 2006.CrossRefGoogle Scholar
Cvetković, D., Rowlinson, P. and Simić, S., Eigenspaces of Graphs, Cambridge University Press, Cambridge, 1997.CrossRefGoogle Scholar
Cvetković, D., Rowlinson, P. and Simić, S., An Introduction to the Theory of Graph Spectra, Cambridge University Press, Cambridge, 2010.Google Scholar
Dhahri, A., Obata, N. and Yoo, H. J., Multivariate orthogonal polynomials: quantum decomposition, deficiency rank and support of measure, J. Math. Anal. Appl. 485 (2020), 123775.CrossRefGoogle Scholar
Durrett, R., Probability; Theory and Examples (4th Ed.), Cambridge University Press, Cambridge, 2010.CrossRefGoogle Scholar
Durrett, R., Random Graph Dynamics, Cambridge University Press, Cambridge, 2010.Google Scholar
Godsil, C. D. and McKay, B. D., A new graph product and its spectrum, Bull. Austral. Math. Soc. 18 (1978), 21–28.CrossRefGoogle Scholar
Gudder, S. P., Quantum probability spaces, Proc. Amer. Math. Soc. 21 (1969), 296–302.CrossRefGoogle Scholar
Gudder, S. P., Quantum Probability, Academic Press, Boston, 1988.Google Scholar
Hammack, R., W. Imrich and S. Klavˇzar, Handbook of Product Graphs (2nd Ed.), CRC Press, Boca Raton, 2011.CrossRefGoogle Scholar
Hasebe, T., Monotone convolution and monotone infinite divisibility from complex analytic viewpoint, Infin. Dimens. Anal. Quantum Probab. Relat. Top. 13 (2010), 111–131.CrossRefGoogle Scholar
Hasegawa, T., Saigo, H., Saito, S. and Sugiyama, S., A quantum probabilistic approach to Hecke algebras for p-adic PGL2, Infin. Dimens. Anal. Quantum Probab. Relat. Top. 21 (2018), 1850015.CrossRefGoogle Scholar
Hashimoto, Y., Quantum decomposition in discrete groups and interacting Fock spaces, Infin. Dimens. Anal. Quantum Probab. Relat. Top. 4 (2001), 277–287.CrossRefGoogle Scholar
Hashimoto, Y., Obata, N. and Tabei, N., A quantum aspect of asymptotic spectral analysis of large Hamming graphs, in Quantum Information III (ed. Hida, T. and K. Saitˆo), pp. 45–57, World Scientific Publ., River Edge, 2001.CrossRefGoogle Scholar
Hashimoto, Y., Hora, A. and Obata, N., Central limit theorems for large graphs: method of quantum decomposition, J. Math. Phys. 44 (2003), 71–88.CrossRefGoogle Scholar
Hiai, F. and Petz, D., The Semicircle Law, Free Random Variables and Entropy, Amer. Math. Soc., Providence, 2000.Google Scholar
Hora, A., Central limit theorems and asymptotic spectral analysis on large graphs, Infin. Dimens. Anal. Quantum Probab. Relat. Top. 1 (1998), 221–246.CrossRefGoogle Scholar
Hora, A., Scaling limit for Gibbs states for Johnson graphs and resulting Meixner classes, Infin. Dimens. Anal. Quantum Probab. Relat. Top. 6 (2003), 139–143.CrossRefGoogle Scholar
Hora, A. and Obata, N., Quantum Probability and Spectral Analysis of Graphs, Springer, 2007.Google Scholar
Hora, A. and Obata, N., Asymptotic spectral analysis of growing regular graphs, Trans. Amer. Math. Soc. 360 (2008), 899–923.CrossRefGoogle Scholar
Igarashi, D. and Obata, N., Asymptotic spectral analysis of growing graphs: Odd graphs and spidernets, Banach Center Publications 73 (2006), 245–265.CrossRefGoogle Scholar
Jafarizadeh, S., Sufiani, R. and Jafarizadeh, M. A., Evaluation of effective resistances in pseudo-distance-regular resistor networks, J. Stat. Phys. 139 (2010), 177–199.CrossRefGoogle Scholar
Kang, Y., Quantum decomposition of random walk on Cayley graph of finite group, Physica A 458 (2016), 146–156.CrossRefGoogle Scholar
Karlin, S. and McGregor, J., Random walks, Illinois J. Math. 3 (1959), 66–81.CrossRefGoogle Scholar
Kesten, H., Symmetric random walks on groups, Trans. Amer. Math. Soc. 92 (1959), 336–354.CrossRefGoogle Scholar
Kolmogorov, A. N., Grundbegriffe der Wahrscheinlichkeitsrechnung, Julius Springer, Berlin, 1933.CrossRefGoogle Scholar
Konno, N., Obata, N. and Segawa, E., Localization of the Grover walks on spider-nets and free Meixner laws, Commun. Math. Phys. 322 (2013), 667–695.CrossRefGoogle Scholar
Koohestani, M., Obata, N. and Tanaka, H., Scaling limits for the Gibbs states on distance-regular graphs with classical parameters, SIGMA 17 (2021), 104, 22 pages.Google Scholar
Lenczewski, R., Unification of independence in quantum probability, Infin. Di-mens. Anal. Quantum Probab. Relat. Top. 1 (1998), 383–405.CrossRefGoogle Scholar
Leyva, M. T. G., Analysis of growing graphs and quantum probability, Thesis, Centro de Investigación en Matemáticas, Mexico, 2017.Google Scholar
Lovász, L., Large Networks and Graph Limits, Amer. Math. Soc., Providence, RI, 2012.CrossRefGoogle Scholar
Lu, Y. G., An interacting free Fock space and the arcsine law, Probab. Math. Stat. 17 (1997), 149–166.Google Scholar
Meyer, P.-A., Quantum Probability for Probabilists, Lect. Notes in Math. Vol. 1538, Springer, 1993.CrossRefGoogle Scholar
Morales, J. V. S., Obata, N. and Tanaka, H., Asymptotic joint spectra of Cartesian powers of strongly regular graphs and bivariate Charlier-Hermite polynomials, Colloq. Math. 162 (2020), 1–22.CrossRefGoogle Scholar
Muraki, N., Noncommutative Brownian motion in monotone Fock space, Com-mun. Math. Phys. 183 (1997), 557–570.CrossRefGoogle Scholar
Muraki, N., Monotonic independence, monotonic central limit theorem and monotonic law of small numbers, Infin. Dimens. Anal. Quantum Probab. Relat. Top. 4 (2001), 39–58.CrossRefGoogle Scholar
Muraki, N., The five independences as natural products, Infin. Dimens. Anal. Quantum Probab. Relat. Top. 6 (2003), 337–371.CrossRefGoogle Scholar
Muraki, N., A simple proof of the classification theorem for positive natural products, Probab. Math. Statist. 33 (2013), 315–326.Google Scholar
Nica, A. and Speicher, R., Lectures on the Combinatorics of Free Probability, Cambridge University Press, Cambridge, 2006.CrossRefGoogle Scholar
Obata, N., Quantum probabilistic approach to spectral analysis of star graphs, In-terdiscip. Inform. Sci. 10 (2004), 41–52.Google Scholar
Obata, N., Quantum probability aspects to lexicographic and strong products of graphs, Interdiscip. Inform. Sci. 22 (2016), 143–146.Google Scholar
Obata, N., Spectral Analysis of Growing Graphs. A Quantum Probability Point of View, Springer, 2017.CrossRefGoogle Scholar
Parthasarathy, K. R., An Introduction to Quantum Stochastic Calculus, Birkhäuser Verlag, Basel, 1992.Google Scholar
Saigo, H., A simple proof for monotone CLT, Infin. Dimens. Anal. Quantum Probab. Relat. Top. 13 (2010), 339–343.CrossRefGoogle Scholar
Schmüdgen, K., The Moment Problem, Springer, 2017.CrossRefGoogle Scholar
Schott, R. and Staples, G. S., Connected components and evolution of random graphs: an algebraic approach, J. Alg. Comb. 35 (2012), 141–156.CrossRefGoogle Scholar
Shohat, J. A. and Tamarkin, J. D., The Problem of Moments, Amer. Math. Soc., New York, 1943.CrossRefGoogle Scholar
Speicher, R., Free Probability Theory, Oxford University Press, Oxford, 2011.Google Scholar
Speicher, R. and Woroudi, R., Boolean convolution, in Free Probability Theory (ed. Voiculescu, D.), pp. 267–279, Amer. Math. Soc., Providence, 1997.Google Scholar
Suppes, P., The probabilistic argument for a non-classical logic of quantum mechanics, Philosophy of Science 33 (1966), 14–21.CrossRefGoogle Scholar
Takesaki, M., Theory of Operator Algebra I, Springer, Berlin, 2002.Google Scholar
van Leeuwen, H. and Maassen, H., A q deformation of the Gauss distribution, J. Math. Phys. 36 (1995), 4743–4756.CrossRefGoogle Scholar
Vargas, J. G. and Kulkarni, A., Spectra of infinite graphs via freeness with amalgamation, Canad. J. Math. 75 (2023), 1633–1684.CrossRefGoogle Scholar
Vershik, A. M., Asymptotic combinatorics and algebraic analysis, Proc. ICM, Zürich (ed. Chatterji, S. D.), Vol. 2, pp. 1384–1394, Birkhäuser, Basel, 1995.Google Scholar
Vershik, A. M., Between “very large” and “infinite”: The asymptotic representation theory, Probab. Math. Stat. 33 (2013), 467–476.Google Scholar
Voiculescu, D., Symmetries of some reduced free product C∗-algebras, in Operator Algebras and Their Connections with Topology and Ergodic Theory (ed. Araki, H., Moore, C. C., S¸. Stratila, D. Voiculescu and Gr. Arsene), pp. 556–588, Lect. Notes in Math., Vol. 1132, Springer, Berlin, 1985.Google Scholar
Voiculescu, D. V., Dykema, K. J. and Nica, A., Free Random Variables, Amer. Math. Soc., Providence, 1992.CrossRefGoogle Scholar
von Neumann, J., Mathematische Grundlagen der Quantenmechanik, Springer, Berlin, 1932.Google Scholar
Wall, H. S., Analytic Theory of Continued Fractions, D. Van Nostrand Company, New York, 1948.Google Scholar

Save book to Kindle

To save this book to your Kindle, first ensure [email protected] is added to your Approved Personal Document E-mail List under your Personal Document Settings on the Manage Your Content and Devices page of your Amazon account. Then enter the ‘name’ part of your Kindle email address below. Find out more about saving to your Kindle.

Note you can select to save to either the @free.kindle.com or @kindle.com variations. ‘@free.kindle.com’ emails are free but can only be saved to your device when it is connected to wi-fi. ‘@kindle.com’ emails can be delivered even when you are not connected to wi-fi, but note that service fees apply.

Find out more about the Kindle Personal Document Service.

Available formats
×

Save book to Dropbox

To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Dropbox.

Available formats
×

Save book to Google Drive

To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Google Drive.

Available formats
×