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 Gm(t) are generated. Then, we study some structural properties on graphs Gm(t) in detail. First, graphs Gm(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 Gm(t) when tuning parameter m. Specifically, graph G1(t) turns out to follow exponential degree distribution. However, for an arbitrary m≥2, the resulting graphs Gm(t) obey power-law degree distribution. In addition, assortativity index of graph G1(t) is always larger than zero and thus has assortativity. Graph G2(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 Gm(t) possess negative assortativity index and thus are disassortative. Next, we determine the total number of spanning trees of graphs Gm(t), and verify that graphs Gm(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 Gp,q(m,i,j;t) where i,j≥2. The resulting graphs Gp,q(m,i,j;t) are always sparse regardless of parameters i and j. Furthermore, we show that given m≥2, graph Gp,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 Gp,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.