The weighted spectral distribution (WSD) is a metric defined on the normalized Laplacian spectrum. Although the WSD is first proposed^[1–3] for the study of Internet topologies, our recent work^[4–7] has demonstrated that the WSD is a good indicator for distinguishing diverse evolving physical systems. Additionally, we explained the physical meaning of the WSD in Internet topologies,^[8] that is, the metric indicates the transformation from single-homed to multi-homed networks. Also, we designed an algorithm^[9] for calculating the WSD which induces that the metric can be applied to networks with more than millions of nodes. However, these studies^[1–9] focused on unweighted networks. To rigorously analyze the WSD in diachronic networks which focus on the time evolution and are similar to dynamical processes in nature,^[10] we have designed a tree model^[5] and a scale-free model.^[6] However, the two models’ clustering coefficients are strictly zero. Furthermore, the γ exponent of the degree distribution of the used scale-free models^{[6, 7]} is one, whereas the γ exponent of most real evolving scale-free networks falls in a range between two and three.^[11] Therefore, in this paper, we rigorously study the WSD on diachronic weighted small-world scale-free networks which have more reasonable γ exponents.

Synchronic random models are rigorous tools to analyze many graph metrics,^[12] e.g., average path length and graph spectra. However, these models consider the statistical ensemble of graphs at a fixed time point and cannot capture the dynamical process in nature.^[10] For diachronic networks, both random models^[13–16] and deterministic models^[17–23] have received much attention. Specifically, deterministic models are suitable for the rigorous analysis of more graph metrics, e.g., diameter, clustering coefficients, graph matrices, and graph spectra. The first deterministic scale-free model was proposed by Barabasi et al.^[20] Another elegant model, called pseudo fractral scale-free web (PSW), was introduced by Dorogovtsev et al.^[11] The PSW has been extended to many versions,^[21–23] and the latest version proposed by Zhang et al.^[23] is called deterministic weighted scale-free small-world network (WSSN) model. The WSSN model has highly tunable exponents for three power-law distributions of node degree, node strength, and edge weight. Additionally, all of the exponents fall in a range between 2 and 3 and the average clustering coefficient of the model is high and independent of the network order. These features of this model might lead to a better understanding of realistic networks. Therefore, in this paper, we rigorously study the WSD by using the WSSN model.

Currently, the scaling feature of many graph metrics has received much attention. The average receiving time is defined as the average of the mean first-passage times for a random walker to a given hub node in a graph, averaged over all source points in the graph.^[24] Dai and Sun et al.^[25–27] studied the average receiving time and the average weighted receiving time in deterministic Koch and hierarchical network models and found that the average receiving time grows sublinearly with increasing network order and the average weighted receiving time grows as power-law function of the network order. The Kemeny constant is defined as the expected time for a walker starting from a node to another node selected randomly from all nodes.^[28] Zhang et al.^[29] studied the Kemeny constant in deterministic scale-free fractal networks and found that the Kemeny constant scales linearly with network order. Additionally, many graph metrics (e.g., degree distribution, clustering coefficient, and spectral radius)^[30–32] can be used to capture the unaltered features of evolving systems. As one number of these graph metrics with scaling features, this study on the WSD is helpful for a better understanding of evolving weighted and small-world systems.

The WSSN model is controlled by two parameters m and δ. Zhang et al.^[23] denoted the network after t steps of the model by . Specifically, the network is constructed as follows.^[23] For , is a triangle consisting of three links with unit weight. For , is obtained from : new nodes are added for each of the links with weight w in , and each new node is connected to both ends of this link in by two new links of unit weight; moreover, the weight of these links in is increased by . It is noteworthy that m and δ are positive integers. When and , the constructed networks with , 1, and 2 are shown in Fig. 1.

Fig. 1.

	Figure Option ViewDownloadNew Window
	Fig. 1. ( , 1, and 2) with and . The white, gray, and black nodes are respectively added at steps , 1, and 2, and the weights of the most thick lines, the second thick lines, and the thinnest lines are respectively 4, 2, and 1.

In , we represent all nodes added at step k as k and let denote an edge linking two nodes i and j for . If , both i and j must be zero. Then, according to the study of Zhang et al.,^[23] the strength of node k and the weight of edge in can be expressed as

(1)

(2)

Additionally, Zhang et al.^[23] derived the number of all nodes in as

(3)

3. in weighted networks

To this day, the study on the WSD has been restricted to unweighted networks. Let denote a simple and undirected graph where V and E are respectively node set and edge set, and d _v denote the degree of node v in graph G. Let n denote the cardinality of node set V. If is the adjacency matrix of graph G ( if there is an edge between nodes v _i and v _j and otherwise) and B is a diagonal matrix with , the normalized Laplacian matrix of graph G is defined as where I denotes the identity matrix.^[1] Let λ ₁, denote all eigenvalues of matrix , called the normalized Laplacian spectrum of graph G. Then, the WSD is defined as^[1]

(4)

Because all eigenvalues of fall in a range , Fay et al. ^[1] transformed Eq. (4) into another expression as follows:

(5)

Additionally, Fay et al.^[1] derived the following equation:

(6)

If G is an unweighted graph, is a 0 − 1 matrix and node degree . For this case, Fay et al.^[1] obtained the following equation:

(7)

In this paper, we consider the WSD on weighted networks. Thus, entry a _ij in A should be the weight of edge between nodes v _i and v _j , and entry in B should be the strength of node v _i . Additionally, equation (6) holds for weighted networks. Therefore, for weighted networks, we can obtain

(8)

Based on Eq. (8), for the WSD calculation, it is critical to enumerate all N-cycles (4 is the best selection of in weighted graph G. Specifically, all 4-cycles can be classified as four patterns as shown in Fig. 2.^{[6, 7, 9]}

Fig. 2.

	Figure Option ViewDownloadNew Window
	Fig. 2. All patterns of 4-cycles with start node v in simple and undirected graph G.

It is noteworthy that the multiple edges between two nodes in these patterns are related to only one edge in weighted graph G that does not have any multiple edge. Let denote the set of neighbors of node v, represent the set of neighbors of node , and refer to the set of common neighbors of nodes i and j with and .

As an extension for unweighted graphs,^[6] in weighted graph G, the sum over all 4-cycles associated with patterns 1 and 3 , and the sum over all 4-cycles associated with patterns 2 and 4 can be calculated as

(9)

(10)

However, it is extremely difficult to derive Eq. (10) in the WSSN model, because we cannot obtain the formula of for . In this paper, we decompose Eq. (10) into the sum over all 4-cycles associated with pattern 2 and the sum over all 4-cycles associated with pattern 4 as follows:

(11)

(12)

As is well known, the WSD in weighted graph G can be expressed as

(13)

5. in WSSN model

First, we will further classify the nodes labeled as k (i.e., added at step in (see Section 2). Based on the construction rule of the WSSN model, each node k must be generated by an edge in and any edge with weight w in must generate nodes k. Thus, we define as a node k generated by edge where . If , both i and j must be zero, and if , all of i, j, and k must be zero. Let denote the number of all nodes .

Then, we can obtain the following theorem (see Appendix A for the proof).

Second, we will derive the formula of which is defined as a set of neighbors of node in . As is well known, includes only one node i and only one node j, and for , includes all nodes in and all nodes , and where and .

Thus, can be expressed as

(14)

As is well known, , where denotes the cardinality of a set.

Additionally, according to the edges that generate nodes ,

(15)

In , the weight of edge for is , and the weight of edges and is . Because the number of edges attached to node is equal to , we have in Eq. (15). Moreover, and in Eq. (15).

Thus, for , we can obtain

(16)

Based on Eq. (16), . Using , we can derive the following equations:

(17)

(18)

(19)

Third, we will derive . According to Eq. (9), for each neighbor , we need to derive its neighbor set . Based on Eqs. (14) and (15), except for nodes in and , the neighbor sets of all nodes in are easy to derive. Thus, it is critical to investigate the generation process of edge which generates node with (both i and j must be zero if and all of i, j, and k must be zero if .

Category 1  When , both nodes i and j can be expressed as , and the number of nodes is (see Theorem 1).

Category 2  When , both nodes i and j can be expressed as , and the number of nodes is (see Theorem 1).

When , we analyze the following five categories:

Category 3  When and , both nodes i and j can be expressed as , and the number of nodes is (see Theorem 1).

Category 4  When , node i can be expressed as , node j must be generated by an edge where , and the number of nodes is . Additionally, each edge must generate nodes j, and each edge must generate nodes k. Specifically, according to Eqs. (14) and (15), we can obtain

(20)

(21)

Note that the intersection of two sets in Eq. (20) is null, because the two sets include different nodes that are marked as the same symbol.

Categories 5, 6, and 7  When , we assume that the edge that generates node i is where (both x and y must be zero if . Then, node j must be generated by an edge or where . Additionally, each edge or must generate nodes j, and each edge must generate nodes k.

Specifically, we can obtain

(22)

(23)

Now, we should further analyze the following three categories for nodes .

Category 8  When node i is generated by edge , the number of nodes is (see Theorem 1).

Category 9  When node i is generated by edge where , the number of nodes is (see Theorem 1).

Category 10  When node i is generated by edge where and , the number of nodes is (see Theorem 1).

According to the above analysis, we can determine the edges which generate the nodes in and . Thus, the neighbor set of each node in can be derived. Assume that node is generated by edge , i.e., nodes i and j are respectively generated by edges and .

Then, based on Eqs. (1), (2), (9), (14), and (15), in weighted graph , we can derive the following equation:

(24)

The above analysis has classified nodes as seven categories: 1. ; 2. ; 3. and ; 4. and ; 5. and ; 6. and ; 7. 2 and . For each category above, the edges and that respectively generate nodes i and j can be determined.

Thus, we expand as follows:

(25)

Specifically, we can obtain

(26)

(27)

(28)

(29)

(30)

(31)

(32)

Fourth, we will derive . According to Eq. (11), it is critical to extract all pairs of nodes in for the calculation of . Based on Eq. (14), the node pairs u and v can be classified as three cases as follows.

Case 1  For and , the sum over 4-cycles associated with can be expressed as

(33)

Case 2  For and , the sum over 4-cycles associated with can be expressed as

(34)

Case 3  For and where , the sum over 4-cycles associated with can be expressed as

(35)

(36)

(37)

Fifth, we will derive . According to Eq. (12), we need to determine all 4-cycles of pattern 4 with start node for calculating . Using the schematic illustration shown in Fig. 3, we present seven cases for these 4-cycles as follows.

Fig. 3.

	Figure Option ViewDownloadNew Window
	Fig. 3. A subgraph of that is used to illustrate all 4-cycles of pattern 4 with start node . In this subgraph, edge generates node i; and if or y, edge generates node j, otherwise edge generates node j.

Case 1  Assume that node j is generated by edge if where edge generates node i (or generated by edge if , and are among these cases.

An example of Case 1 in Fig. 3 is .

Case 2  For any node that is generated by edge and different from the start node , and are among these cases. An example of case 2 in Fig. 3 is .

Case 3  Assume node , for any pair of nodes l and that are generated by edge if (or edge if , and are among these cases.

An example of Case 3 in Fig. 3 is .

Case 4  Assume that node and p is a node generated by edge if (or edge if , for any node q generated by edge , and are among these cases.

An example of Case 4 in Fig. 3 is .

Case 5  Assume that node and q is a node generated by edge if (or edge if , for any node p generated by edge , and are among these cases.

An example of Case 5 in Fig. 3 is .

Case 6  For any node q that is generated by edge , and are among these cases.

An example of Case 6 in Fig. 3 is .

Case 7  For any node q that is generated by edge , and are among these cases.

An example of Case 7 in Fig. 3 is .

For start node , the above cases 2–7 do not need to determine which edges generate nodes i and j where edge generates the start node. Thus, it is easy to calculate for these cases.

For Case 2, edge generates nodes p for , and nodes p for . Thus, the corresponding of this case can be expressed as

(38)

For Case 3, based on Eq. (14), if , the set of all nodes generated by edge is where denotes a set composed of nodes that are added at step x. If where , the set of all nodes generated by edge is . Thus, the corresponding of this case can be expressed as follows:

(39)

Like the analyses of Cases 2 and 3, we can respectively derive the corresponding of Cases 4–7 as follows:

(40)

(41)

(42)

(43)

It is worth noting that and in Eqs. (40)–(43) have been respectively substituted by Eqs. (1) and (eqs. (2)). Thus, associated with Cases 2–7 can be expressed as follows:

(44)

(45)

For start node , Case 1 needs to determine which edges generate nodes i and j. Thus, we need to classify nodes as seven categories: 1. ; 2. ; 3. and ; 4. and ; 5. and ; 6. and ; 7. and . This classification of nodes has been analyzed in detail for the calculation of . Let denote the sum of associated with Case 1, then, using a similar method for calculating WSD ₁₃, we will be able to expand as follows:

(46)

Specifically, we can obtain

(47)

(48)

(49)

(50)

(51)

(52)

(53)

Thus, according to Eqs. (44) and (Eqs. (46)), we can obtain

(54)

Finally, according to Eqs. (25), (Eqs. (37)), and (54), we can derive the WSD in as follows:

(55)

It is extremely complicated to manually express the WSD in with three parameters m, δ, and t. Fortunately, the Symbolic Math Toolbox of Matlab can help us to simplify the expression of the WSD. However, it is not intelligent enough for the toolbox to finish the work alone. For example, if we assume that and , for functions and , Matlab R2015a code returns to which is an invalid result, but can return to the expected result 1. Thus, we need to compile extra codes to deal with the transformation from φ to ψ.

Because the expression of the WSD is very long, according to Eq. (3), we only present the limit of the ratio of the WSD to the network order with as follows:

(56)

(57)

(58)

(59)

(60)

(61)

Therefore, the WSD grows sublinearly as the network order of the WSSN model increases. Additionally, it is easy to verify that both the partial derivatives of Eq. (56) with respect to m and δ are smaller than 0 for (because the expressions of the two partial derivatives are very long, we do not present the expressions in this paper, but we can use the “diff” function of Matlab to demonstrate these results). Thus, the limit of the ratio of the WSD to the network order monotonically decreases with increasing m and δ, i.e., the limit provides a sensitive discrimination for each input of the WSSN model.

The mathematical derivation process of Section 5 demonstrates that the WSD is a good indicator to distinguish different weighted evolving systems. In this section, we choose three evolving weighted systems derived by classical Barrat’s model [33] to verify the applicability of the WSD. The model generates weighted networks based on growth and weights’ dynamics: at each time step, the model adds a new node and connects it to m previously existing nodes for the growth; also, for each of the m existing nodes, the model updates the weights of edges connected to the node and makes the node strength increased by δ. According to the study of Barrat et al.,^[33] reflects the influence of newly added edges on the weight distribution where denotes the initial weights of the newly added edges. As shown in Fig. 4, the WSD grows sublinearly as the network order of a certain weighted evolving system increases, that is, the ratio of the WSD to the network order remains stable for these networks with different orders. Furthermore, figure 44 shows that the ratio of the WSD to the network order can effectively distinguish different weighted evolving systems. Therefore, this study is important for promoting the WSD applicability in weighted evolving networks.

Fig. 4.

	Figure Option ViewDownloadNew Window
	Fig. 4. WSD versus network order of three weighted evolving systems derived by classical Barrat’s model. Note that each quantity represents the average of 10 realizations.

Weighted, high and order-independent clustering coefficient and restricted power-law exponent falling in are features existing in most realistic evolving networks. In this paper, we rigorously investigate the WSD in the WSSN model which captures all of the mentioned features. In contrast to the unweighted model with zero clustering coefficient, the derivation of the WSD in the WSSN model is very complicated. However, with the help of the Symbolic Math Toolbox of Matlab, we demonstrate that the ratio of the WSD to the network order is asymptotically independent of the network order of the WSSN model and monotonically decreases as each input of the model increases. Furthermore, the rigorous derivation process of the WSD studied in this paper will provide a helpful insight into a understanding of the WSD in weighted network systems.

As is well known, the number of nodes is 3. Thus, and Case A is correct.

Based on Eq. (2), the weight of each edge in is . Thus, nodes k are generated by edge in when . There are 3 edges which induce that if . Thus Case B is correct.

Using an induction method to prove Case C: when , j must be 1, and (i.e., Case C holds for k = 2 and .

Assume that Case C holds for and . When , is determined by the number of all edges in (i.e., and the weight of edge in (i.e., derived by Eq. (2)).

Edge is generated if and only if nodes are added at step j of the WSSN model. Specifically, generates only one edge and generates two edges . Thus, we can obtain

(A1)

(A2)

According to the above assumption and Case B, we can derive the formulas of and . Furthermore, we can obtain

(A3)

Therefore, for and , Case C remains correct.

Using an induction method to prove Case D: when , i and j must be 1 and 2, respectively, and (i.e., Case D holds for and .

Assume that Case D holds for and . When , is determined by the number of all edges in (i.e., and the weight of edge in (i.e., derived by Eq. (2)).

Edge is generated if and only if nodes , are added at step j of the WSSN model. Specifically, each node or generates only one edge . Thus, we can obtain

(A4)

And according to the construction rule of the WSSN model, we have

(A5)

According to the above assumption and Case C, we can derive the formulas of , and . Furthermore, we can obtain

(A6)

Therefore, for and , Case D remains correct.

First of all, we extract two properties of weighted graph as follows.

Property 1  For any node k (i.e., a node added at step with , if two different nodes i and j are connected with node k and , must be the only one edge that generates node k and edge .

Property 2  For any node k with , if node i is attached to node k in , we can determine that .

The above two properties can be easily confirmed by Eq. (14).

Proof  We analyze the 4-cycle as shown in Fig. A1.

Fig. A1.

	Figure Option ViewDownloadNew Window
	Fig. A1. A 4-cycle of pattern 4 with start node .

Without loss of generality, we assume .

If , then due to Property 2. Because includes only three nodes 0, we can determine . Thus, p is a node generated by edge due to property 1, i.e., the 4-cycle belongs to Case 2.

If , then and due to Property 2. If , then due to the assumption , and edge generates node p due to Property 1. Because , node q is generated by edge due to Property 1, i.e., the 4-cycle belongs to Case 5.

When :

1) if , then edge generates node due to Property 1. If , then node p is generated by edge , i.e., the 4-cycle belongs to Case 2. If , then due to Property 2. Thus, node q is generated by edge , i.e., the 4-cycle belongs to Case 1. Note that Case 2 requires . If , then . Because and , node q is generated by edge , i.e., the 4-cycle belongs to Case 1.

2) if , . Thus, edge generates node p due to Property 1. Because and , and node q is generated by edge , i.e., the 4-cycle belongs to Case 5.

If , then and due to Property 2.

3) if , then edge generates node q due to Property 1. If , then (otherwise that is contradictive to the precondition . Because edge , due to Property 2 and node p is generated by edge due to Property 1, i.e., the 4-cycle belongs to Case 4. If , then and node l is generated by edge due to Property 1, i.e., the 4-cycle belongs to Case 3. If , then and for node due to Property 1. Then, the 4-cycle belongs to Case 6 if , or belongs to Case 7 if .