Determining Exact Solutions for Structural Parameters on Hierarchical Networks With Density Feature. (30th July 2020)

• Record Type: Journal Article
• Authors: Ma, Fei; Wang, Ping
• Is Part Of: Computer journal. Volume 64:Number 9(2021)
• Page Start: 1412
• Page End: 1424
• Publication Date: 2020-07-30
• Subjects: hierarchical networks -- trapping problem -- scale-free feature -- average trapping time -- density feature -- Kemeny's constant; Computers -- Periodicals; 005.1
• DOI: 10.1093/comjnl/bxaa067
• Languages: English
• ISSNs: 0010-4620

Abstract

Abstract: The problem of determining closed-form solutions for some structural parameters of great interest on networked models is meaningful and intriguing. In this paper, we propose a family of networked models $\mathcal{G}_{n}(t)$ with hierarchical structure where $t$ represents time step and $n$ is copy number. And then, we study some structural parameters on the proposed models $\mathcal{G}_{n}(t)$ in more detail. The results show that (i) models $\mathcal{G}_{n}(t)$ follow power-law distribution with exponent $2$ and thus exhibit density feature; (ii) models $\mathcal{G}_{n}(t)$ have both higher clustering coefficients and an ultra-small diameter and so display small-world property; and (iii) models $\mathcal{G}_{n}(t)$ possess rich mixing structure because Pearson-correlated coefficients undergo phase transitions unseen in previously published networked models. In addition, we also consider trapping problem on networked models $\mathcal{G}_{n}(t)$ and then precisely derive a solution for average trapping time $ATT$ . More importantly, the analytic value for $ATT$ can be approximately equal to the theoretical lower bound in the large graph size limit, implying that models $\mathcal{G}_{n}(t)$ are capable of having most optimal trapping efficiency. As a result, we also derive exact solution for another significant parameter, Kemeny's constant. Furthermore, we conduct extensive simulations that are in perfect agreement with all the theoretical deductions.