A Statistical Study of the Eigenvalues of Random Graphs through Random Matrix theory
DOI:
https://doi.org/10.58445/rars.1075Keywords:
graph theory, computer science, random graphs, random matrix theoryAbstract
Randomness is inherent in nature. From bacterial population growth to noise in electrical circuits, stochastic processes highlight the randomness which is evident in the inherent nature of physical phenomena. In this work we perform a numerical experiment by studying the statistics of eigenvalues of adjacency matrices of randomly connected graphs. We motivate graph theory and highlight the method of generating random graphs used for this study. We then look at the eigenvalues of the adjacency matrices to look at their eigen- spectrum. We further statistically observe the spacing distribution and find that the spacing exhibits Gaussian Orthogonal Ensemble (GOE) distribution.
References
Bondy, J. A., & Murty, U. S. R. (1976). Graph theory with applications (Vol. 290). London: Macmillan.
West, D. B. (2001). Introduction to graph theory (Vol. 2). Upper Saddle River: Prentice hall.
Mondal, B., & De, K. (2017). An overview of applications of graph theory in the real field. International Journal of Scientific Research in Computer Science, Engineering and Information Technology, 2(5), 751-759.
Bollobás, B., & Bollobás, B. (1998). Random graphs (pp. 215-252). Springer New York.
Kang, M., & Petrasek, Z. (2014). Random graphs: Theory and applications from nature to society to the brain. Internationale Mathematische Nachrichten, 227, 1-24.
Singh, H., & Sharma, R. (2012). Role of adjacency matrix & adjacency list in graph theory. International Journal of Computers & Technology, 3(1), 179-183.
Chung, F. R. (1995). Eigenvalues of graphs. In Proceedings of the International Congress of Mathematicians: August 3–11, 1994 Zürich, Switzerland (pp. 1333-1342). Birkhäuser Basel.
Doob, M. (2004). Eigenvalues of graphs. Topics in algebraic graph theory, 30-57.
Adjacency Matrix -- from Wolfram MathWorld. (n.d.). Adjacency Matrix -- From Wolfram MathWorld. https://mathworld.wolfram.com/
Matrix | Definition, Types, & Facts. (n.d.). Encyclopedia Britannica. https://www.britannica.com/science/matrix-mathematics
Introduction to Adjacency Matrix For Graphs. (2023, January 13). Codedamn News. https://codedamn.com/news/programming/introduction-to-adjacency-matrix-for-graphs
Milo, R., Kashtan, N., Itzkovitz, S., J. Newman, M. E., & Alon, U. (2003, December 1). On the uniform generation of random graphs with prescribed degree sequences. arXiv.org. https://arxiv.org/abs/cond-mat/0312028v2
Tao, T. (2023). Topics in random matrix theory (Vol. 132). American Mathematical Society.
Guhr, T., Müller–Groeling, A., & Weidenmüller, H. A. (1998). Random-matrix theories in quantum physics: common concepts. Physics Reports, 299(4-6), 189-425.
Bohigas, O. (1991). Random matrix theories and chaotic dynamics (No. IPNO-TH--90-84). Paris-11 Univ.
Edelman, A., & Rao, N. R. (2005). Random matrix theory. Acta numerica, 14, 233-297.
Sugiyama, M., Ghisu, M. E., Llinares-López, F., & Borgwardt, K. (2018). graph kernels: R and Python packages for graph comparison. Bioinformatics, 34(3), 530-532.
Chung, J., Pedigo, B. D., Bridgeford, E. W., Varjavand, B. K., Helm, H. S., & Vogelstein, J. T. (2019). Graspy: Graph statistics in python. Journal of Machine Learning Research, 20(158), 1-7.
Downloads
Posted
Categories
License
Copyright (c) 2024 Vannsh Jagtiani
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.