TY - JOUR
T1 - Estimation of Laplacian spectra of direct and strong product graphs
AU - Sayama, Hiroki
N1 - Funding Information:
The author thanks Eduardo Altmann for reviewing the draft version of this manuscript, and the two anonymous reviewers for providing very helpful comments. This work was conducted under financial support offered by the Max Planck Institute for the Physics of Complex Systems.
Publisher Copyright:
© 2015 Elsevier B.V.
PY - 2016
Y1 - 2016
N2 - Calculating a product of multiple graphs has been studied in mathematics, engineering, computer science, and more recently in network science, particularly in the context of multilayer networks. One of the important questions to be addressed in this area is how to characterize spectral properties of a product graph using those of its factor graphs. While several such characterizations have already been obtained analytically (mostly for adjacency spectra), characterization of Laplacian spectra of direct product and strong product graphs has remained an open problem. Here we develop practical methods to estimate Laplacian spectra of direct and strong product graphs from spectral properties of their factor graphs using a few heuristic assumptions. Numerical experiments showed that the proposed methods produced reasonable estimation with percentage errors confined within a ±10% range for most eigenvalues.
AB - Calculating a product of multiple graphs has been studied in mathematics, engineering, computer science, and more recently in network science, particularly in the context of multilayer networks. One of the important questions to be addressed in this area is how to characterize spectral properties of a product graph using those of its factor graphs. While several such characterizations have already been obtained analytically (mostly for adjacency spectra), characterization of Laplacian spectra of direct product and strong product graphs has remained an open problem. Here we develop practical methods to estimate Laplacian spectra of direct and strong product graphs from spectral properties of their factor graphs using a few heuristic assumptions. Numerical experiments showed that the proposed methods produced reasonable estimation with percentage errors confined within a ±10% range for most eigenvalues.
KW - Direct product
KW - Laplacian spectrum
KW - Multilayer network
KW - Product graph
KW - Strong product
UR - http://www.scopus.com/inward/record.url?scp=84951849710&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84951849710&partnerID=8YFLogxK
U2 - 10.1016/j.dam.2015.12.006
DO - 10.1016/j.dam.2015.12.006
M3 - Article
AN - SCOPUS:84951849710
SN - 0166-218X
VL - 205
SP - 160
EP - 170
JO - Discrete Applied Mathematics
JF - Discrete Applied Mathematics
ER -