On the Normalized Laplacian Spectra of Random Geometric Graphs
Tóm tắt
In this work, we study the spectrum of the normalized Laplacian and its regularized version for random geometric graphs (RGGs) in various scaling regimes. Two scaling regimes are of special interest, the connectivity and the thermodynamic regime. In the connectivity regime, the average vertex degree grows logarithmically in the graph size or faster. In the thermodynamic regime, the average vertex degree is a constant. We introduce a deterministic geometric graph (DGG) with nodes in a grid and provide an upper bound to the probability that the Hilbert–Schmidt norm of the difference between the normalized Laplacian matrices of the RGG and DGG is greater than a certain threshold in both the connectivity and thermodynamic regime. Using this result, we show that the RGG and DGG normalized Laplacian matrices are asymptotically equivalent with high probability (w.h.p.) in the full range of the connectivity regime. The equivalence is even stronger and holds almost surely when the average vertex degree
$$a_n$$
satisfies the inequality
$$a_n > 24 \log (n).$$
Therefore, we use the regular structure of the DGG to show that the limiting eigenvalue distribution of the RGG normalized Laplacian matrix converges to a distribution with a Dirac atomic measure at zero. In the thermodynamic regime, we approximate the eigenvalues of the regularized normalized Laplacian matrix of the RGG by the eigenvalues of the DGG regularized normalized Laplacian and we provide an error bound which is valid w.h.p. and depends upon the average vertex degree.
Tài liệu tham khảo
Bai, Z., Silverstein, J.W.: Spectral Analysis of Large Dimensional Random Matrices. Springer, New York (2010)
Bai, Z.D.: Methodologies in spectral analysis of large dimensional random matrices, a review. Stat. Sinica 9, 611–677 (1999)
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(2), 026704 (2001)
Van Mieghem, P.: Graph Spectra for Complex Networks. Cambridge University Press, Cambridge (2010)
Couillet, R., Debbah, M.: Random Matrix Methods for Wireless Communications. Cambridge University Press, Cambridge (2011)
Erdos, P.: On random graphs. Publicationes mathematicae 6, 290–297 (1959)
Haas, Z. J., Deng, J., Liang, B., Papadimitratos, P., Sajama, S.: “Wireless ad hoc networks,” Encyclopedia of Telecommunications, (2002)
Yick, J., Mukherjee, B., Ghosal, D.: Wireless sensor network survey. Comput. Netw. 52(12), 2292–2330 (2008)
Preciado, V. M., Jadbabaie, A.: “Spectral analysis of virus spreading in random geometric networks,” IEEE Conference on Decision and Control, (2009)
Ganesh, A., Massoulié, L., Towsley, D.: “The effect of network topology on the spread of epidemics,” in Proc. of IEEE Conference on Computer Communications (INFOCOM), (2005)
Penrose, M.: Random Geometric Graphs. Oxford University Press, Oxford (2003)
Maier, M., Hein, M., von Luxburg, U.: Optimal construction of k-nearest-neighbor graphs for identifying noisy clusters. Theor. Comput. Sci. 410(19), 1749–1764 (2009)
Sadri, A. M., Hasan, S., Ukkusuri, S. V., Lopez, J. E. S.: “Analyzing social interaction networks from twitter for planned special events,” arXiv preprintarXiv:1704.02489, (2017)
Page, L., Brin, S., Motwani, R., Winograd, T.: “The pagerank citation ranking: Bringing order to the web.” Stanford InfoLab, Tech. Rep., (1999)
Avrachenkov, K., Ribeiro, B., Towsley, D.: “Improving random walk estimation accuracy with uniform restarts,” in International Workshop on Algorithms and Models for the Web-Graph. Springer, pp. 98–109 (2010)
Nyberg, A.: “The Laplacian spectra of random geometric graphs,” Ph.D. dissertation, University of Houston, (2014)
Nyberg, A., Gross, T., Bassler, K.E.: Mesoscopic structures and the Laplacian spectra of random geometric graphs. J. Complex Netw. 3(4), 543–551 (2015)
Dettmann, C.P., Knight, G.: Symmetric motifs in random geometric graphs. J. Complex Netw. 6(1), 95–105 (2017)
El Karoui, N.: The spectrum of kernel random matrices. Ann. Stat. 38(1), 1–50 (2010)
Jiang, T.: Distributions of eigenvalues of large Euclidean matrices generated from lp balls and spheres. Linear Algebra Appl. 473, 14–36 (2015)
Bordenave, C.: Eigenvalues of Euclidean random matrices. Random Struct. Algorithms 33(4), 515–532 (2008)
Blackwell, P., Edmondson-Jones, M., Jordan, J.: Spectra of adjacency matrices of random geometric graphs. Unpublished, (2007)
Rai, S.: The spectrum of a random geometric graph is concentrated. J. Theor. Probab. 20(2), 119–132 (2007)
Billingsley, P.: Probability and Measure. John Wiley & Sons, Hoboken (2008)
Gray, R.M.: “Toeplitz and circulant matrices: a review,’’ Foundations and Trends®. Commun. Inf. Theory 2(3), 155–239 (2006)
Hoffman, A.J., Wielandt, H.: The variation of the spectrum of a normal matrix. Duke Math. J. 20, 37–39 (1953)
Müller, T.: Two-point concentration in random geometric graphs. Combinatorica 28(5), 529 (2008)
Janson, S., Luczak, T., Rucinski, A.: Random Graphs. John Wiley & Sons, Hoboken (2011)