Power-law graphs with small diameter: Framework, structural properties, and average trapping time.

Abstract

Here, we propose a simple algorithmic framework for creating power-law graphs with small diameters and then study structural properties, for instance, average degree, on graphs built. The results show that our graphs have not only some commonly seen properties including scale-free feature, small-world property, and disassortative structure, but also many rarely found characteristics, such as the density feature due to power-law exponents equal to 2 and the diameter equivalent to 2, compared to most previous scale-free models. In addition, we also consider the trapping problem on the proposed graphs and then find that they have more optimal trapping efficiency by means of their own average trapping times achieving the theoretical lower bound, a phenomenon that is seldom observed in existing scale-free models. We conduct extensive simulations, and the results show that empirical simulations are consistent with theoretical analysis.