The order (defined as the number of nodes) of many scale-free networks grows over time, e.g., social networks, airport networks, and Internet topologies.^[1] Thus, it is inevitable to compare networks with different orders for the study of these evolving systems. Network comparison has been widely used for the classification and similarity analysis of diverse networks. Specifically, the comparison of networks with different orders strongly depends on the stability features of the evolving systems. This paper focuses on the stability analysis of a spectral graph feature of scale-free evolving systems, i.e., the weighted spectral distribution (WSD).

Graph spectra incorporate all eigenvalues of graph matrices, including adjacency and normalized Laplacian matrices. The natural connectivity is a spectral graph feature defined on the adjacency spectrum.^[2] Moreover, Wu et al.^[3] rigorously demonstrated that the feature is asymptotically independent of the order of regular graphs in which each node has an identical expected degree. However, our recent work^[4,5] found numerically that the stability of the natural connectivity does not work in scale-free networks. The WSD is another spectral graph feature defined on the normalized Laplacian spectrum that strongly corresponds to the distribution of random N-cycles in a network.^[6] Fay et al.^[7] designed a calculation algorithm for the WSD using Sylvester’s law of inertia which is restricted to networks with less than 30000 nodes. Using 4-cycle structures, Jiao et al.^[4] proposed a fast algorithm by which the WSD can be accurately calculated in scale-free networks with more than millions of nodes. The WSD captures the local connectivity of diverse networks.^[8,9] Additionally, Jiao et al.^[5] numerically observed that the WSD increases sublinearly with the network order in a stochastic scale-free network model. However, the stochastic models are not suitable for the rigorous analysis of the WSD’s stability since it is impossible to derive the WSD’s precise formula in these models. Therefore, there is a need to rigorously investigate the stability of the WSD for better understanding the performance of the spectral graph feature in evolving scale-free networks.

In contrast to stochastic models, deterministic models help us to understand the construction rules embedded in randomized structures and allow for rigorous computation of many graph features, e.g., clustering coefficients, diameter, betweenness, path length, and mean first-passage time.^[10–20] The primary deterministic scale-free model was proposed by Barabasi et al.^[19] However, this model lacks the small-world effect that exists in most real networks, i.e., its clustering coefficient is too small while the average length path remains relatively large. To remedy this weakness, Chen et al.^[20] constructed a pseudo tree-like (PTL) deterministic model having both the small-world and the scale-free characteristics. Moreover, in Chen’s model,^[20] the distribution of clustering coefficients C(k) with respect to degree k has the power-law form C(k) ∝ k⁻¹ which exists in most hierarchical systems.^[21] Therefore, our contribution includes the rigorous analysis of the WSD’s stability using Chen’s deterministic model.

Equations (2) and (3) show that the WSD counts the sum of the products of degree reciprocals embedded in all N-cycles (N = 4 is commonly selected) of graph G. For each node v ∈ V, let N(v) = {1,2,…,r} denote the set of neighbors of node v and denote the set of neighbors of node i ∈ {1,2, …,r}. Let C(i, j) = {v,c₁,c₂, …,c_tij} denote the set of common neighbors of nodes i and j with i, j ∈ N(v) and i ≠ j. Then, the WSD of graph G can be calculated as follows (see Appendix A):

According to Eqs. (4)–(6), the neighbor set of each node and the common neighbor set of each two nodes are crucial for the calculation of the WSD in T_n+1.

At level t (1 ≤ t ≤ n + 1) of T_n+1, 2^t−1 nodes t₁,t₂,…,t_2^t−1 are attached to other nodes in the same manner, i.e., node t₁ is equivalent to each node of other 2^t−1 − 1 nodes at level t. Hence, we only consider the neighbor set (i.e., N(t₁)) of node t₁ and the common neighbor set (i.e., C(t₁,s_k) = N(t₁) ∩ N(s_k)) of two nodes t₁ and s_k(≠ t₁), where 1 ≤ s ≤ n + 1 and 1 ≤ k ≤ 2^s−1. Without loss of generality, we assume s ≥ t.

According to the construction rules listed in Subsection 2.2,

If s_k is a descendant of node t₁, des(s_k) ⊆ des(t₁) and t₁ is one root of node s_k (i.e., rot(s_k) = rot(t₁) ∪ {t₁} ∪ (rot(s_k) ∩ des(t₁))). For this case,

If s_k (s ≥ t) is not a descendant of node t₁, des(s_k) ∩ (des(t₁) ∪ rot(t₁)) = Φ and rot(s_k) ∩ des(t₁) = Φ. For this case,

Specifically, N(s_k) = rot(s_k) ∪ des(s_k), where rot(s_k) includes all roots of node s_k and des(s_k) includes all descendants of node s_k.

In T_n+1, the network order can be expressed as

Let and , where des((t + 1)₁) and des((t + 1)₂) include all descendants of nodes (t + 1)₁ and (t + 1)₂, respectively. Then, the pairs of nodes in can be classified into four cases: case 1, pairs of nodes in rot(t₁); case 2, one node in rot(t₁) and the other node in ; case 3, one node in and the other node in ; and case 4, pairs of nodes in , which is equivalent to pairs of nodes in .

Let P_N(t1) denote the set of all pairs of nodes in N(t₁), where for ∀i, j ∈ N(t₁) ∧ i ≠ j, (i, j) and (j,i) are two different node pairs. Then, , where S₁,S₂,S₃, and are node pair sets associated with cases 1–4, respectively. Specifically, and correspond to and , respectively.

According to Eq. (6), we can obtain

For each pair of nodes (i.e., (i₁, j₁) with 1 ≤ i, j ≤ t − 1) in rot(t₁) = {(t − 1)₁, (t − 2)₁, …,1₁}, if i < j, node j₁ is a descendant of node i₁. According to Eq. (8), C(i₁, j₁) = N(j₁) − {i₁}. Hence, for node pair set S₁ associated with case 1,

According to Eq. (12), we can obtain

For each pair of nodes (i₁, (t + j)_l) with i₁ ∈ rot(t₁) = {(t − 1)₁, (t − 2)₁,…,1₁} and , node (t + j)_l is a descendant of node i₁. According to Eq. (8), C(i₁, (t + j)_l) = N((t + j)_l) − {i₁}. Hence, for node pair set S₂ associated with case 2,

For each pair of nodes ((t + i)_x, (t + j)_y) with and , nodes t₁, (t − 1)₁,…,1₁ are the common roots of nodes (t + i)_x and (t + j)_y, i.e., rot((t + i)_x) ∩ rot((t + j)_y) = {t₁, (t − 1)₁,…,1₁}. Additionally, there is no root-descendant relationship between nodes (t + i)_x and (t + j)_y. According to Eq. (9), C((t + i)_x, (t + j)_y) = {t₁, (t − 1)₁, …,1₁}. Hence, for node pair set S₃ associated with case 3,

Let denote the sum of the products of degree reciprocals associated with node pairs in S₃, i.e., is equal to Eq. (18) which can be expressed as

Due to the equivalence between and , we only consider node pair set S₄ generated by node set . As the extension of and , and . Hence, node pair set S₄ can be classified into three parts: part 1, one node (t + 1)₁ and the other node in ; part 2, one node in and the other node in ; part 3, pairs of nodes in , which is equivalent to pairs of nodes in .

As is well known,

According to Eq. (16), we can obtain

In T_n+1, node set . Therefore, according to Eq. (4) and the equivalence between node t₁ and each node t_j (2 ≤ j ≤ 2^t−1), the precise formula of the WSD in T_n+1 can be derived as

Using Eqs. (12), (13), and (14)–(22), we can obtain

Equation (11) shows that, for ∀t ∈ {1,2,…,n + 1}, the degree of node t_j (1 ≤ j ≤ 2^t−1) at level t ∈ {1,2,…,n + 1} in T_n+1 is d_t = 2 · (2^n−t+1 − 1) + (t − 1). If all node degrees of Eqs. (23)–(25) are substituted using Eq. (11), it is difficult to derive the sum formula of WSD_Tn+1. But we can derive two sum formulas to bound the WSD_Tn+1.

Theorem 1 For ∀t ∈ {1,2,…,n + 1} and ∀α > 1, with n → + ∞,

Proof t ≥ 1 ⇒ d_t ≥ 2 · (2^n−t+1 − 1) = 2^n−t+1 + (2^n−t+1 − 2). If t ∈ {1,2,…,n}, 2^n−t+1 ≥ 2 (i.e., d_t ≥ 2^n−t+1). If t = n + 1, d_t = n and 2^n−t+1 = 1 (i.e., d_t ≥ 2^n−t+1).

With increasing t, φ(t) = t − 1 monotonically increases and ψ(t) = 2^α·n−t+1 monotonically decreases. For ∀α > 1, φ (n + 1) = n ≤ ψ (n + 1) = 2^(α−1)·n with n → + ∞. Hence, for ∀t ∈ {1,2,…,n + 1}, with n → + ∞, φ(t) ≤ ψ(t) (i.e., t − 1 ≤ 2^α·n−t+1). That is, d_t ≤ 2 · (2^n−t+1 − 1) + 2^α·n−t+1 ≤ 3 · 2^α·n−t+1 ≤ 2^α·n−t+3. The proof is completed.

Corollary 1 For ∀t ∈ {1,2,…,n + 1} and ∀α > 1, with n → + ∞,

If 1/d_t(t ∈ {1,2,…,n}) of Eqs. (23)–(25) is substituted using 2^{−α·n+t−3} or 2^−n+t−1, the sum formula of WSD_Tn+1 is easy to derive using the geometric progression’s sum formula. Therefore, for ∀α > 1, with n → + ∞, using Eq. (27), we can obtain two boundaries of WSD₁₂(t₁) and WSD₃₄ (t₁) as follows:

With α → 1, we can obtain

Using Eq. (23), with n → + ∞, we can obtain

The classification of networks with different orders is an important application of the stability features embedded in evolving systems. This section first selects several simulated and real-world networks with different orders, and then classifies these networks into diverse evolving systems using the WSD’s stability.

The primary scale-free stochastic model was proposed by Barabasi and Albert.^[24] At each time step of the model’s growth process, a new node is attached to m different old nodes that are already present in the existing system. Furthermore, Zou et al.^[25] constructed another scale-free stochastic model that is an extension of Barabasi–Albert model. Specifically, the newly added node at each time step of Barabasi–Albert model is replaced by a newly added module generated by Watts–Strogatz model^[26] in Zou’s model. The module shows the morphology feature of many real networks,^[25] thus we select Zou’s model to generate diverse simulated networks.

The module generated by Watts–Strogatz model includes s nodes. Specifically, each node in the module is first connected with its 2k neighbors, and then each edge of the node is randomly rewired with a probability α. As shown in Fig. 2(a), when m = 3 and α = 1, by using different inputs s and k, Zou’s model can simulate diverse evolving networks with different modules. Figure 2(a) shows that for a certain module corresponding to unaltered inputs s and k, the WSD grows sublinearly as the network order increases. Additionally, figure 2(a) shows that the ratio of the WSD to the network order is a good indicator which can be used to distinguish evolving systems with different modules.

Fig. 2.

Figure Option ViewDownloadNew Window

Fig. 2. Classification of diverse simulated and real-world networks: (a) WSD vs. network order in Zou’s model with different modules (decided by the inputs s and k where other inputs of the model are set as m = 3 and α = 1). (b) Ratio of the WSD to the network order in 12 real-world networks whose descriptions are included in Table 1. Note that each quantity in panel (a) is an average over 10 realizations.

Furthermore, we choose 12 real-world networks with different orders,^[1] as shown in Table 1. Specifically, in Table 1, G₁, G₂, and G₃ correspond to a sequence of snapshots of the Gnutella peer-to-peer file sharing network, I₁, I₂, …, I₆ correspond to a sequence of snapshots of the autonomous-system-level Internet topology, and A₁, A₂, and A₃ are networks that were collected by trawling Amazon website.

Table 1.

Table 1.

Table 1. Twelve real-world networks with different orders.[1] . Item Node number Edge number Snapshot time G1 22687 54705 Aug 25 2002 I1 16301 65910 Jan 05 2004 A1 400727 3200440 Mar 12 2003 I2 17848 74344 Sep 06 2004 G2 36682 88328 Aug 30 2002 I3 19846 80970 Jul 04 2005 A2 410236 3356824 May 05 2003 I4 21901 89176 May 01 2006 G3 62586 147892 Aug 31 2002 I5 24454 99660 Mar 05 2007 A3 403394 3387388 Jun 01 2003 I6 26475 106762 Nov 05 2007

Table 1. Twelve real-world networks with different orders.[1] .

As shown in Fig. 2(b), we calculate the ratio of the WSD to the network order in the twelve real-world networks listed in Table 1. Figure 2(b) shows that the ratio indeed is a good indicator which distinguishes evolving systems.

Fig. A1.

	Figure Option ViewDownloadNew Window
	Fig. A1. All patterns of 4-cycles with start node v: (a) pattern 1, (b) pattern 2, (c) pattern 3, (d) pattern 4.[4]

Our recent work^[4,5] numerically verifies that the WSD increases sublinearly in a stochastic evolving scale-free network model as the network order increases. However, the stochastic models using interactive growth mechanisms are not suitable for the rigorous analysis of the scaling feature of the WSD. In this paper, our contributions focus on the derivation of the WSD’s precise formula in a deterministic model which captures the scale-free, small-world, and hierarchical features of many real-world networks. The precise formula rigorously explains the WSD’s stability (i.e., the ratio of the WSD to the network order is bounded as the network order increases). The stability indicates that the WSD can be applied to compare different order networks and to distinguish diverse evolving systems whose network orders grow over time.