Topological and Spectral Properties of Small-World Hierarchical Graphs. (22nd September 2018)

• Record Type: Journal Article
• Authors: Qi, Yi; Yi, Yuhao; Zhang, Zhongzhi
• Is Part Of: Computer journal. Volume 62:Number 5(2019)
• Page Start: 769
• Page End: 784
• Publication Date: 2018-09-22
• Subjects: complex network -- hierarchical product -- network analysis -- network model -- spectra -- epidemic spreading; Computers -- Periodicals; 005.1
• DOI: 10.1093/comjnl/bxy087
• Languages: English
• ISSNs: 0010-4620

Abstract

Abstract: Hierarchical product of graphs has found wide applications in various fields, e.g. polymer and biological networks. In this paper, we study the topological and spectral properties of hierarchical graphs as a model of complex networks, which are generated by iterative hierarchical product of complete graphs. We first derive analytically various critical structural properties of the hierarchical graphs, including degree distribution, clustering coefficient, average distance, degree correlations and modularity, and show that they exhibit simultaneously the striking properties of many real networks. We then fully characterize the eigenvalues and eigenvectors of the adjacency matrix and Laplacian matrix pencil of the hierarchical graphs, with the latter subsuming both Laplacian matrix and signless Laplacian matrix. We finally study the susceptible-infectious-susceptible model on the hierarchical graphs and determine the epidemic threshold based on the spectral radius of the adjacency matrix.