Spectral properties of the hierarchical product of graphs

Abstract

The hierarchical product of two graphs represents a natural way to build a larger graph out of two smaller graphs with less regular and therefore more heterogeneous structure than the Cartesian product. Here we study the eigenvalue spectrum of the adjacency matrix of the hierarchical product of two graphs. Introducing a coupling parameter describing the relative contribution of each of the two smaller graphs, we perform an asymptotic analysis for the full spectrum of eigenvalues of the adjacency matrix of the hierarchical product. Specifically, we derive the exact limit points for each eigenvalue in the limits of small and large coupling, as well as the leading-order relaxation to these values in terms of the eigenvalues and eigenvectors of the two smaller graphs. Given its central roll in the structural and dynamical properties of networks, we study in detail the Perron-Frobenius, or largest, eigenvalue. Finally, as an example application we use our theory to predict the epidemic threshold of the Susceptible-Infected-Susceptible model on a hierarchical product of two graphs.

References in corpus (22)

• Emergence of scaling in random networks
• The structure and function of complex networks
• Community structure in social and biological networks
• Epidemic spreading in scale-free networks
• Finding community structure in networks using the eigenvectors of matrices
• Self-similar community structure in organisations
• Dynamical interplay between awareness and epidemic spreading in multiplex networks
• Diffusion dynamics on multiplex networks
• Mathematical Formulation of Multi-Layer Networks
• Synchronization reveals topological scales in complex networks
• Spontaneous synchrony in power-grid networks
• Discrete-time Markov chain approach to contact-based disease spreading in complex networks
• The onset of synchronization in large networks of coupled oscillators
• Spectral properties of the Laplacian of multiplex networks
• Characterizing the dynamical importance of network nodes and links
• A network analysis of committees in the United States House of Representatives
• Predicting criticality and dynamic range in complex networks: effects of topology
• Pattern formation in multiplex networks
• Optimal synchronization of complex networks
• Approximating the largest eigenvalue of network adjacency matrices
• Hierarchical Synchrony of Phase Oscillators in Modular Networks
• Social Climber attachment in forming networks produces phase transition in a measure of connectivity

Cited by in corpus (1)

• Diffusion dynamics and synchronizability of hierarchical products of networks