Another estimation of Laplacian spectrum of the Kronecker product of graphs

DOI10.1016/J.INS.2022.07.082MaRDI QIDQ6203484zbMATH OpenOpenAlexFDO

Authors Milan Bašić, B. Arsić, Zoran Obradovic

Publication date 27 March 2024

Published in Information Sciences (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2102.02924

zbMATH Keywords

multilayer networksgraph miningKronecker product of graphsLaplacian eigenvalues and eigenvectorsnormalized Laplacian eigenvalues and eigenvestors

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Eigenvalues, singular values, and eigenvectors (15A18) Graph operations (line graphs, products, etc.) (05C76)

Abstract: The relationships between eigenvalues and eigenvectors of a product graph and those of its factor graphs have been known for the standard products, while 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 a median of the percentage errors of our estimated Laplacian spectrum almost coincides with the $x$-axis, unlike the alternatives which have sudden jumps at the beginning followed by a gradual decrease for the percentage errors. The percentage errors confined (confidence of the estimations) up to $pm$10% for all considered approximations, depending on a graph density. Moreover, we theoretically prove that the percentage errors becomes 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.

Recommendations

• Estimation of Laplacian spectra of direct and strong product graphs
• Approximate eigensolution of Laplacian matrices for locally modified graph products
• Laplacian matrices of product graphs: applications in structural mechanics
• On the Laplacian spectra of product graphs
• Some results on graph products determined by their spectra

Cites work

• scientific article; zbMATH DE number 1600999 (Why is no real title available?)
• scientific article; zbMATH DE number 5852541 (Why is no real title available?)
• scientific article; zbMATH DE number 3717357 (Why is no real title available?)
• scientific article; zbMATH DE number 2121251 (Why is no real title available?)
• A forgotten topological index
• Community structure in social and biological networks
• Estimation of Laplacian spectra of direct and strong product graphs
• Gaussian conditional random fields extended for directed graphs
• Graph spectra in computer science
• Hermitian Laplacian matrix and positive of mixed graphs
• Hermitian normalized Laplacian matrix for directed networks
• Kronecker graphs: an approach to modeling networks
• Laplacian matrices of graphs: A survey
• Lower and upper bounds of the forgotten topological index
• On the Laplacian spectra of product graphs
• On the spectra of general random graphs
• Singularity of Hermitian (quasi-)Laplacian matrix of mixed graphs
• Time series: theory and methods.
• Which weighted circulant networks have perfect state transfer?

Cited in

(1)

• Kronecker product of tensors and hypergraphs: structure and dynamics

This page was built for publication: Another estimation of Laplacian spectrum of the Kronecker product of graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6203484)