Counterexample: scale-free networked graphs with invariable diameter and density feature

Abstract

Here, we propose a class of scale-free networks $G(t;m)$ with some intriguing properties, which can not be simultaneously held by all the theoretical models with power-law degree distribution in the existing literature, including (i) average degrees $⟨k⟩$ of all the generated networks are no longer a constant in the limit of large graph size, implying that they are not sparse but dense, (ii) power-law parameters $\gamma$ of these networks are precisely calculated equal to $2$, as well (iii) their diameters $D$ are all an invariant in the growth process of models. While our models have deterministic structure with clustering coefficients equivalent to zero, we might be able to obtain various candidates with nonzero clustering coefficient based on original networks using some reasonable approaches, for instance, randomly adding some new edges under the premise of keeping the three important properties above unchanged. In addition, we study trapping problem on networks $G(t;m)$ and then obtain closed-form solution to mean hitting time $⟨\mathcal{H}{⟩}_t$. As opposed to other previous models, our results show an unexpected phenomenon that the analytic value for $⟨\mathcal{H}{⟩}_t$ is approximately close to the logarithm of vertex number of networks $G(t;m)$. From the theoretical point of view, these networked models considered here can be thought of as counterexamples for most of the published models obeying power-law distribution in current study.

References in corpus (17)

• Emergence of scaling in random networks
• Assortative mixing in networks
• Hierarchical organization of modularity in metabolic networks
• Hierarchical Organization in Complex Networks
• Scale-Free Networks are Ultrasmall
• Complex network approaches to nonlinear time series analysis
• Deterministic Scale-Free Networks
• All scale-free networks are sparse
• Self-similar scaling of density in complex real-world networks
• Structural Transitions in Dense Networks
• Eigenvector localization in real networks and its implications for epidemic spreading
• Trapping in scale-free networks with hierarchical organization of modularity
• Dense Power-law Networks and Simplicial Complexes
• Large deviations of random walks on random graphs
• On the Widespread Occurrence of the Inverse Square Distribution in Social Sciences and Taxonomy
• Stability of glassy hierarchical networks
• Characterizing several properties of high-dimensional random Apollonian networks

Cited by in corpus (3)

• Analyses of Some Structural Properties on a Class of Hierarchical Scale-free Networks
• Trapping problem on star-type graphs with applications
• Exact mean first-passage time on generalized Vicsek fractal