Hitting times and resistance distances of $q$-triangulation graphs: Accurate results and applications

Abstract

Graph operations or products, such as triangulation and Kronecker product have been extensively applied to model complex networks with striking properties observed in real-world complex systems. In this paper, we study hitting times and resistance distances of $q$-triangulation graphs. For a simple connected graph $G$, its $q$-triangulation graph $R_q(G)$ is obtained from $G$ by performing the $q$-triangulation operation on $G$. That is, for every edge $uv$ in $G$, we add $q$ disjoint paths of length $2$, each having $u$ and $v$ as its ends. We first derive the eigenvalues and eigenvectors of normalized adjacency matrix of $R_q(G)$, expressing them in terms of those associated with $G$. Based on these results, we further obtain some interesting quantities about random walks and resistance distances for $R_q(G)$, including two-node hitting time, Kemeny's constant, two-node resistance distance, Kirchhoff index, additive degree-Kirchhoff index, and multiplicative degree-Kirchhoff index. Finally, we provide exact formulas for the aforementioned quantities of iterated $q$-triangulation graphs, using which we provide closed-form expressions for those quantities corresponding to a class of scale-free small-world graphs, which has been applied to mimic complex networks.

arXiv commentarXiv admin note: substantial text overlap with arXiv:1808.00372

References in corpus (10)

• Emergence of scaling in random networks
• The structure and function of complex networks
• Community structure in social and biological networks
• Kronecker Graphs: An Approach to Modeling Networks
• Pseudofractal Scale-free Web
• The Role of Kemeny's Constant in Properties of Markov Chains
• On the spectrum of the normalized Laplacian of iterated triangulations of graphs
• A general geometric growth model for pseudofractal scale-free web
• Kirchhoff Index As a Measure of Edge Centrality in Weighted Networks: Nearly Linear Time Algorithms
• Deterministic hierarchical networks