Recall that the spectrum (Laplacian spectrum resp.) of a simple undirected graph is the spectrum of its adjacency matrix (Laplcian matrix resp.).
Moreover, many products of graphs have been introduced and studied by mathematicians, the standard ones are : cartisien, lexicographic, direct and strong product of graphs.
Mathematicians like R.B. Bapat, Cardoso et al… have been specifically interested in finding the characteristic polynomial, eigenvalues, laplacian eigenvalues of such products, also sometimes if they were not able to find the spectrum explicitly, they search for the characteristic polynomial or they talk about some subset of the spectrum they found.
If someone could please explain what is the motivation behind finding the spectrum (Laplacian resp.) of such products of graphs. Thank you.
Best Answer
Think about a directed graph $G = (V, E)$ with the adjacency matrix $A$. Then, $A^T$ is the adjacency matrix of the product graph and $B = AA^T$ is also a weighted adjacency matrix. The element (u,v) of the adjacency matrix $B = AA^T$ denotes the number of common followers of the two nodes $u, v$. In other words, the number of nodes that have links pointing from both $u$ and $v$. Hence, it measures the similarity of the nodes $u$ and $v$ in terms of the number of common followers. Therefore, the laplacian of this similarity matrix $B = AA^T$ would reveal information about how the nodes in the original graph can be clustered in terms of the similarity of the common followers. Similarity, the matrix $C = A^TA$ measures similarity in terms of number of common followees and hence can be used to cluster nodes using this similarity measure.
This is one (of the most widely used) usage of the laplacian of the product matrix. This has other applications in social network analysis as well. For further information, have a look at:
--Symmetrizations for Clustering Directed Graphs (Satluri et al, 2011)
--Clustering and community detection in directed networks: A survey (Fragkiskos D Malliaros and Michalis Vazirgiannis, 2013)
-- Networks: An Introduction (M. Newman)
In the case of an undirected graph with adjacency matrix $A$, the product graph is also gives the similarity in terms of common neighbors (as a special case).
Hope this helps to give you some insights.