Structural transition on partial edge-based growing graph

It is of great interest to construct theoretical models that reliably display some properties observed in real-world networks. In this work, we propose a partial edge-based generative framework by which a family of growing graphs G_m(t) are generated. Then, we study some structural properties on graphs G_m(t) in detail. First, graphs G_m(t) turn out to have an invariable average degree regardless of parameter m and to be sparse. Second, we prove that there are structural transitions on graphs G_m(t) when tuning parameter m. Specifically, graph G₁(t) turns out to follow exponential degree distribution. However, for an arbitrary m≥2, the resulting graphs G_m(t) obey power-law degree distribution. In addition, assortativity index of graph G₁(t) is always larger than zero and thus has assortativity. Graph G₂(t) is proven to be neutral because its assortativity index is constantly equal to the critical value, i.e., zero. For other values of parameter m, we obtain that graphs G_m(t) possess negative assortativity index and thus are disassortative. Next, we determine the total number of spanning trees of graphs G_m(t), and verify that graphs G_m(t) have a relatively smaller spanning trees entropy compared with some previous graphs. Lastly, we introduce randomness controlled by a pair of probability parameters p and q into the proposed framework to further create a class of stochastic graphs G_p,q(m,i,j;t) where i,j≥2. The resulting graphs G_p,q(m,i,j;t) are always sparse regardless of parameters i and j. Furthermore, we show that given m≥2, graph G_p,q(m,i,j;t) follows power-law degree distribution and has scale-free feature. Among these, we find that given q=1 and j>i, randomness controlled by p has no effect on degree distribution of graph G_p,q(m,i,j;t) in the limit of large graph size. In the meantime, we conduct extensive experiments and confirm that computer simulations are in perfect agreement with the theoretical analysis.