Spectra, hitting times, and resistance distances of $q$-subdivision graphs

Abstract

Graph operations or products play an important role in complex networks. In this paper, we study the properties of $q$-subdivision graphs, which have been applied to model complex networks. For a simple connected graph $G$, its $q$-subdivision graph $S_q(G)$ is obtained from $G$ through replacing every edge $uv$ in $G$ by $q$ disjoint paths of length 2, with each path having $u$ and $v$ as its ends. We derive explicit formulas for many quantities of $S_q(G)$ in terms of those corresponding to $G$, including the eigenvalues and eigenvectors of normalized adjacency matrix, two-node hitting time, Kemeny constant, two-node resistance distance, Kirchhoff index, additive degree-Kirchhoff index, and multiplicative degree-Kirchhoff index. We also study the properties of the iterated $q$-subdivision graphs, based on which we obtain the closed-form expressions for a family of hierarchical lattices, which has been used to describe scale-free fractal networks.

References in corpus (23)

• Emergence of scaling in random networks
• The structure and function of complex networks
• Community structure in social and biological networks
• Self-similarity of complex networks
• Kronecker Graphs: An Approach to Modeling Networks
• Origins of fractality in the growth of complex networks
• Pseudofractal Scale-free Web
• Fractal and Transfractal Recursive Scale-Free Nets
• Self-similar disk packings as model spatial scale-free networks
• The Role of Kemeny's Constant in Properties of Markov Chains
• On the spectrum of the normalized Laplacian of iterated triangulations of graphs
• Self-similarity, small-world, scale-free scaling, disassortativity, and robustness in hierarchical lattices
• A general geometric growth model for pseudofractal scale-free web
• The normalized Laplacian spectrum of subdivisions of a graph
• Farey Graphs as Models for Complex Networks
• Optimal and suboptimal networks for efficient navigation measured by mean-first passage time of random walks
• Role of fractal dimension in random walks on scale-free networks
• Kirchhoff Index As a Measure of Edge Centrality in Weighted Networks: Nearly Linear Time Algorithms
• Deterministic hierarchical networks
• Domination number and minimum dominating sets in pseudofractal scale-free web and Sierpiński graph
• Corona graphs as a model of small-world networks
• Maximum matchings and minimum dominating sets in Apollonian networks and extended Tower of Hanoi graphs
• Maximum matchings in scale-free networks with identical degree distribution

Cited by in corpus (1)

• Biharmonic distance of graphs