Abstract
We examine the sensitivity of community-structured graph spectra to graph size, block size and inter-block edge probability. We use the Planted Partition Model because of its transparency. While this generative model may seem simplistic, it allows us to isolate the effects of graph and block size, edge probabilities and, consequently, vertex degree distribution on spectra. These sensitivities to key graph characteristics also generalize beyond Planted Partition Model graphs, because they are based on graph structure. Notably, our results show that eigenvalues converge to those of a complete graph, with increases in graph size or inter-block edge probability. Such convergence severely limits the use of spectral techniques.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Albert, R., Barabási, A.L.: Statistical mechanics of complex networks. Rev. Mod. Phys. 74, 47–97 (2002). https://doi.org/10.1103/RevModPhys.74.47
Barabási, A.L., Albert, R.: Emergence of scaling in random networks. Science 286, 509–512 (1999)
Broido, A.D., Clauset, A.: Scale-free networks are rare. Nature Commun. 10(1), 1017 (2019)
Bruneau, P., Parisot, O., Otjacques, B.: A heuristic for the automatic parametrization of the spectral clustering algorithm. In: 2014 22nd International Conference on Pattern Recognition, pp. 1313–1318 (2014). https://doi.org/10.1109/ICPR.2014.235
Chen, J., Lu, J., Zhan, C., Chen, G.: Laplacian Spectra and Synchronization Processes on Complex Networks, pp. 81–113. Springer US, Boston, MA (2012). https://doi.org/10.1007/978-1-4614-0754-6_4. URL https://doi.org/10.1007/978-1-4614-0754-6_4
Chung, F.R.K.: Spectral graph theory. American Mathematical Soc. (1997)
Coja-Oghlan, A., Goerdt, A., Lanka, A.: Spectral partitioning of random graphs with given expected degrees. In: Navarro, G., Bertossi, L., Kohayakawa, Y. (eds.) Fourth IFIP International Conference on Theoretical Computer Science- TCS 2006, pp. 271–282. Springer, US, Boston, MA (2006)
Condon, A., Karp, R.: Algorithms for graph partitioning on the planted partition model. Random Struct. Algorithms 18(2), 116–140 (2001). https://doi.org/10.1002/1098-2418(200103)18:2<116::AID-RSA1001>3.0.CO;2-2
Erdös, P., Rényi, A.: On random graphs I. Publicationes Mathematicae Debrecen 6, 290–297 (1959)
Fortunato, S.: Community detection in graphs. Phys. Rep. 486, 75–174 (2010). https://doi.org/10.1016/j.physrep.2009.11.002
Fortunato, S., Hric, D.: Community detection in networks: A user guide. arXiv (2016)
Gan, L., Wan, X., Ma, Y., Lev, B.: Efficiency evaluation for urban industrial metabolism through the methodologies of emergy analysis and dynamic network stochastic block model. Sustainable Cities and Society, p. 104396 (2023)
Gilbert, E.: Random graphs. Ann. Math. Statist. 30(4), 1141–1144 (1959). https://doi.org/10.1214/aoms/1177706098.
Hagberg, A., Schult, D., Swart, P.: Exploring Network Structure, Dynamics, and Function using NetworkX. In: G. Varoquaux, T. Vaught, J. Millman (eds.) Proceedings of the 7th Python in Science Conference, pp. 11–15. Pasadena, CA USA (2008)
Lancichinetti, A., Fortunato, S., Radicchi, F.: Benchmark graphs for testing community detection algorithms. arXiv 78(4), 046110 (2008). https://doi.org/10.1103/PhysRevE.78.046110
Lee, C., Wilkinson, D.J.: A review of stochastic block models and extensions for graph clustering. Appl. Netw. Sci. 4(1), 1–50 (2019)
Leskovec, J., Lang, K.J., Dasgupta, A., Mahoney, M.W.: Community structure in large networks: natural cluster sizes and the absence of large well-defined clusters. Internet Mathematics 6(1), 29–123 (2009). https://doi.org/10.1080/15427951.2009.10129177
Lutzeyer, J.F., Walden, A.T.: Comparing Graph Spectra of Adjacency and Laplacian Matrices. arXiv e-prints arXiv:1712.03769 (2017). https://doi.org/10.48550/arXiv.1712.03769
von Luxburg, U.: A tutorial on spectral clustering. Stat. Comput. 17, 395–416 (2007)
Newman, M.E.J., Strogatz, S., Watts, D.J.: Random graphs with arbitrary degree distributions and their applications. Phys. Rev. E 64, 026,118 (2001). https://doi.org/10.1103/PhysRevE.64.026118.
Priebe, C.E., et al.: On a two-truths phenomenon in spectral graph clustering. Proc. Natl. Acad. Sci. 116(13), 5995–6000 (2019)
Rao Nadakuditi, R., Newman, M.E.J.: Graph spectra and the detectability of community structure in networks. arXiv e-prints arXiv:1205.1813 (2012). https://doi.org/10.48550/arXiv.1205.1813
Rohe, K., Chatterjee, S., Yu, B.: Spectral clustering and the high-dimensional stochastic blockmodel. Ann. Stat. 39(4), 1878–1915 (2011). https://doi.org/10.1214/11-AOS887.
Spielman, D.A.: Spectral graph theory and its applications. In: 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS’07), pp. 29–38 (2007). https://doi.org/10.1109/FOCS.2007.56
documentaton page (author unknown), O.: Planted partition model. https://networkx.org/documentation/stable/reference/generated/networkx.generators.community.planted_partition_graph.html
documentaton page (author unknown), O.: Stochastic block model. https://networkx.org/documentation/stable/reference/generated/networkx.generators.community.stochastic_block_model.html
Zhan, C., Chen, G., Yeung, L.F.: On the distributions of Laplacian eigenvalues versus node degrees in complex networks. Physica A: Statistical Mechanics and its Applications 389(8), 1779–1788 (2010). https://doi.org/10.1016/j.physa.2009.12.005. URL https://www.sciencedirect.com/science/article/pii/S0378437109010012
Acknowledgments
– The work of P.M. was funded by a MITACS grant (grant# IT33832).
– The authors thank Prof. Valery A. Kalyagin of the Laboratory of Algorithms and Technologies for Networks Analysis in Nizhny Novogorod, Russia, for his comments on the early stages of this work.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2024 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Miasnikof, P., Shestopaloff, A.Y., Bravo, C., Lawryshyn, Y. (2024). Empirical Study of Graph Spectra and Their Limitations. In: Cherifi, H., Rocha, L.M., Cherifi, C., Donduran, M. (eds) Complex Networks & Their Applications XII. COMPLEX NETWORKS 2023. Studies in Computational Intelligence, vol 1141. Springer, Cham. https://doi.org/10.1007/978-3-031-53468-3_25
Download citation
DOI: https://doi.org/10.1007/978-3-031-53468-3_25
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-53467-6
Online ISBN: 978-3-031-53468-3
eBook Packages: EngineeringEngineering (R0)