Another estimation of Laplacian spectrum of the Kronecker product of graphs

Abstract

The characterization of Laplacian eigenvalues and eigenvectors of the Kronecker product of graphs using the Laplacian spectra and eigenvectors of the factors turned out to be quite challenging and has remained an open problem to date. Several approaches for the estimation of Laplacian spectrum of the Kronecker product of graphs have been proposed in recent years. However, it turns out that not all the methods are practical to apply in network science models, particularly in the context of multilayer networks. Here we develop a practical and computationally efficient method to estimate Laplacian spectra of this graph product from spectral properties of their factor graphs, which is more stable than the alternatives proposed in the literature. We emphasize that the median of percentage errors of our estimated Laplacian spectrum almost coincides with the x-axis, unlike the alternatives having sudden jumps. The percentage errors confined up to ±10% for all considered approximations, depending on graph density. Moreover, we theoretically prove that the percentage errors become smaller when the network grows or the edge density level increases. Additionally, some novel theoretical results considering the exact formulas and lower bounds related to the certain correlation coefficients corresponding to the estimated eigenvectors are presented.