Preprint / Version 1

A Statistical Study of the Eigenvalues of Random Graphs through Random Matrix theory

##article.authors##

  • Vannsh Jagtiani The Shri Ram School, Moulsari

DOI:

https://doi.org/10.58445/rars.1075

Keywords:

graph theory, computer science, random graphs, random matrix theory

Abstract

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

2024-04-07

Categories

License

Copyright (c) 2024 Vannsh Jagtiani

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

You are free to:

  1. Share — copy and redistribute the material in any medium or format for any purpose, even commercially.
  2. Adapt — remix, transform, and build upon the material for any purpose, even commercially.
  3. The licensor cannot revoke these freedoms as long as you follow the license terms.

Under the following terms:

  1. Attribution — You must give appropriate credit, provide a link to the license, and indicate if changes were made. You may do so in any reasonable manner, but not in any way that suggests the licensor endorses you or your use.
  2. No additional restrictions — You may not apply legal terms or technological measures that legally restrict others from doing anything the license