Spectral Analysis and its applications for a class of scale-free network based on the weighted m-clique annex operation

In this Section, the construction of weighted $m-$clique annex operation and some topological properties are introduced . First of all, it should be clear that the $m-$clique mentioned here is a complete subgraph with $m$ nodes, denoted as $K_{m}$. Since the initial network is only required to be a connected network, which is denoted as $G_{0}$, the weighted $m-$clique annex operation has strong applicability. Then, the construction of the weighted $m-$clique annex operation is as follows: for any edge with weight of $\omega$ in network $G_{0}$, add a clique $K_{m}$, and connect all nodes in the $K_{m}$ to the two nodes connected by the edge, and then specify that the weight of all newly generated edges is $r\omega$. The new weighted network generated by the network operation of the initial network $G_{0}$ is denoted as $G_{1}$. The weighted $m-$clique annex operation is controlled by and only by two parameters, namely scale factor $m(m\in\mathbb{N}^{+})$ and weight factor $r(r\in\mathbb{R}^{+})$. Therefore, the network operation process is denoted as $\tau^{r}_{m}(\cdot)$, so the following relation can be obtained:

Obviously, in this operation, each edge in $G_{0}$ will correspond to a weighted clique $K_{m}$, and the weight of the edge connected by all nodes in this clique is determined by the edge in this $G_{0}$, so we call this edge the ”parent” of this weighted clique $K_{m}$. For example, when the size factor $m=4$, the process of network operation $\tau^{r}_{4}(\cdot)$ is shown in Fig.1.

Naturally, for any initial network $G_{0}$, the weighted $m-$clique annex operation $\tau^{r}_{m}(\cdot)$ can be repeatedly used to generate a complex network model, denoted as $G_{t}$, where $t$ represents the number of iterations of the operation. Therefore, network $G_{t}$ can be expressed as follows:

According to the definition of operation $\tau^{r}_{m}(\cdot)$, as the number of iterations increases, the size of the network will increase exponentially, but the diameter of the network will only increase linearly, so the iterative weighted network has a small-world property. In order to facilitate later calculation, when we consider the relevant properties of weighted iterative network $G_{t}$, each edge in the initial network $G_{0}$ is set as unit weight.

Then, the iterative rules of nodes, edges and strengths in the network under this operation will be studied. First, we specify that the symbol $|\cdot|$ represents the number of elements in the set. For any initial network $G_{0}$, the set of nodes and the set of edges are denoted as $V_{0}$ and $E_{0}$, respectively. Obviously, after the weighted $m-$clique annex operation $\tau^{r}_{m}(\cdot)$, the number of nodes and the number of edges in network $G_{1}$ satisfy the following relation:

Then, the sets of nodes and edges in the iterated weighted network $G_{t}$ are denoted as $N_{t}$ and $E_{t}$ respectively. From the above relationship, it can be naturally deduced that:

Then, the set of nodes already existing in the previous generation network $G_{t-1}$ contained in $V_{t}$ is denoted as $\hat{V}_{t}$. Therefore, the rest nodes are newly generated after the $t$-th operation $\tau_{m}^{r}(\cdot)$, and the set of this nodes is denoted as $\bar{V}_{t}$. Moreover, for any node $i\in V_{t}$, the set formed by nodes adjacent to node $i$ is denoted as $V^{i}_{t}$. Then, for any node $j\in V^{i}_{t}$, there must be an edge between node $i$ and node $j$, denoted as $e_{ij}$, and the weight of this edge denoted as $\omega_{ij}$. In addition, for the convenience of later calculation, the following provisions are made:

Then, for any node $i\in V_{t}$, its strength is defined as:

Naturally, if $i\in\hat{V}_{t}$, from the construction mode of operation $\tau_{m}^{r}(\cdot)$, it can be obtained that $s_{t}^{i}$ satisfies the following relation:

If node $i$ belongs to set $\bar{V}_{t}$, the parent edge of this node is denoted as $e^{*}_{i}$, and the weight of this edge is denoted as $\omega^{*}_{i}$, then the strength of this node must satisfy:

Therefore, the total strength of the iterative weighted network $G_{t}$, denoted as $S_{t}$, can be defined as:

The total strength $S_{t}$ of weighted iterative network $G_{t}$ can be obtained by network operation $\tau_{m}^{r}(\cdot)$, which satisfies the following relation:

In the iterative weighted network $G_{t}$, since the weight of each edge of the initial network $G_{0}$ is defined as $1$, it can be obtained that $S_{0}=E_{0}$.

Next, the influence of the weighted $m-$clique annex operation $\tau^{r}_{m}(\cdot)$ on the network degree distribution will be discussed. Firstly, for any node $i\in V_{t}$, its degree, denoted as $d_{t}^{i}$, is defined as the number of adjacent nodes of the node $i$, which satisfy $d_{t}^{i}=|V_{t}^{i}|$. Similar to the node strength in network $G_{t}$, it is easy to prove that for any node $i\in V_{t}$, its degree $d_{t}^{i}$ must satisfy the following relation:

From the above relation, it can be further obtained:

where $d_{0}^{i}$ represents the degree of node $i$ in network $G_{0}$.

Then, for the iterative network $G_{t}$, its degree distribution, denoted as $P^{t}(\alpha)$, is defined as the probability that a node is randomly selected from set $V_{t}$ with degree $\alpha$. However, since the degree distribution of the network is generally a discrete function, we pay more attention to the cumulative degree distribution on the iterative network $G_{t}$, denoted as $P^{t}_{cum}(\alpha)$, which is defined as the probability that the degree of randomly selected node is greater than or equal to $\alpha$, that is:

Since the network structure of the initial network $G_{0}$ is known, the degree distribution $P^{0}(\alpha)$ and the accumulative degree distribution $P^{0}_{cum}(\alpha)$ on the network are known initial conditions. Therefore, for node $i\in V_{0}$ in iterative network $G_{t}$, its degree distribution must satisfy the following conditions:

According to the weighted $m-$clique annex operation $\tau^{r}_{m}(\cdot)$, the degree of nodes generated in the same iteration operation in the iterative network $G_{t}$ is equal, and the degree of nodes generated in different generations must not be equal. Therefore, based on the iterative rule of node degree, it is easy to prove that the number of nodes with degree $(m+1)^{k}$ belonging to set $V_{t}/V_{0}$ is $E_{0}\cdot m(\frac{1}{2}m^{2}+\frac{3}{2}m+1)^{t-k}$, where $1\leq k\leq t$. Therefore, for node $i\in V_{t}/V_{0}$ with degree $(m+1)^{k}$ in network $G_{t}$, its degree distribution satisfies the following relation:

From Eq.(5) and Eq.(6), the degree distribution on the iterative network $G_{t}$ can be obtained, and then its cumulative degree distribution can be solved.

If $\alpha\in\mathbb{R}^{+}$ and $\alpha\leq(m+1)^{t}$, according to the definition, the cumulative degree distribution $P^{t}_{cum}(\alpha)$ on the iterative network $G_{t}$ can be expressed as:

where $\beta$ is the largest positive integer that satisfy $(m+1)^{\beta}<\alpha$, so it can be obtained that $\beta=\lceil\frac{\ln\alpha}{\ln(m+1)}\rceil-1$.

If $\alpha\in\mathbb{R}^{+}$ and $\alpha>(m+1)^{t}$, it is easy to deduce from Eq.(5) that the accumulative degree distribution $P_{cum}^{t}(\alpha)$ on the iterative network $G_{t}$ satisfies the following relation:

where $\beta=\lceil\frac{\alpha}{(m+1)^{t}}\rceil$. Therefore, from Eq.(7) and Eq.(2.3), the analytic expression of the accumulative degree distribution of iterated network $G_{t}$ have obtained.

When the number of iterations in the network $G_{t}$ is large enough so that $|V_{t}|\gg|V_{0}|$, we can obtain:

Therefore, the accumulative degree distribution $P^{t}_{cum}(\alpha)$ on network $G_{t}$ can be approximately expressed as:

where $\gamma=2+\frac{\ln(\frac{m}{2}+1)}{\ln(m+1)}$. Naturally, for large number of iterations $t$, it can be proofed that:

where $2<\gamma<3$. Therefore, when the number of iterations $t$ is large enough, the iterated network $G_{t}$ generated by this weighted $m-$clique annex operation $\tau^{r}_{m}(\cdot)$ is a scale-free network model with power exponent $\gamma=2+\frac{\ln(\frac{m}{2}+1)}{\ln(m+1)}$.Barabási & Albert [1999]

Due to the global self-similarity of the network, the network $G_{t}$ will have transfinite fractal properties when the number of iterations $t\rightarrow\infty$.Rozenfeld et al. [2007] First, based on the network architecture, it is easy to prove that the network diameter $L_{t}$ satisfies:

where, $L_{0}$ is the diameter of the initial network $G_{0}$. Then, the network transfinite fractal dimension $\bar{d}_{f}$ satisfies Rozenfeld et al. [2007]:

Therefore, the transfinite fractal dimension $\bar{d}_{f}$ of the iterative network $G_{t}$ is:

In this Section, the spectral properties of the normalized Laplacian matrix corresponding to the iterative weighted network $G_{t}$ will be studied. Firstly, the relevant definitions need to be given. For the iterative weighted network $G_{t}$ $(t\geq 0)$, the corresponding generalized adjacency matrix, denoted as $W_{t}$, is the square matrix with $|V_{t}|$ rows and $|V_{t}|$ columns, where the element of the $i$-th row and the $j$-th column is denoted as $W_{t}(i,j)$, which satisfies the following relation:

where $i$ and $j$ correspond to two nodes in the network $G_{t}$ respectively, while $i\sim j$ represents that two nodes are adjacent. Then, the diagonal strength matrix of iterative weighted network $G_{t}$ can be defined as: $D_{t}=diag\{s_{t}^{1},s_{t}^{2},\ldots,s_{t}^{|V_{t}|}\}$. Based on the generalized adjacency matrix $W_{t}$ and diagonal strength matrix $D_{t}$, the probability transfer matrix, denoted as $T_{t}$, can be defined as: $T_{t}=D_{t}^{-1}W_{t}$, where the element $T_{t}(i,j)$ in the $i$-th row and the $j$-th column represents the probability of the walker transferring from node $i$ to node $j$. It is noteworthy that the probability transfer matrix $T_{t}$ is an asymmetric matrix in most cases. In order to make it symmetric, the normalized adjacency matrix $P_{t}$ of iterative weighted network $G_{t}$ can be defined as:

Clearly, the normalized adjacency matrix $P_{t}$ is similar to the probability transfer matrix $T_{t}$, so they have the same eigenvalues. Then, we can define the normalized Laplacian matrix $L_{t}$ as:

where $I_{|V_{t}|}$ is the identity matrix with rank $|V_{t}|$.

To represent the spectrum of normalized Laplacian matrix of the iterative weighted network $G_{t}$, the eigenvalues of matrix $L_{t}$ are denoted as $\sigma_{t}^{i}$ $(1\leq i\leq|V_{t}|)$ which satisfy $\sigma_{t}^{1}\leq\sigma_{t}^{2}\leq\cdots\leq\sigma_{t}^{|V_{t}|}$, and the set of all its eigenvalues is denoted as $\Psi_{t}=\{\sigma_{t}^{1},\sigma_{t}^{2},\ldots,\sigma_{t}^{|V_{t}|}\}$. Similarly, the eigenvalues of normalized adjacency matrix $P_{t}$ of the network $G_{t}$ are defined as $\lambda_{t}^{i}$ $(1\leq i\leq|V_{t}|)$, which satisfies $\lambda_{t}^{1}\geq\lambda_{t}^{2}\geq\cdots\geq\lambda_{t}^{|V_{t}|}$, and the set of all eigenvalues is denoted as: $\Lambda_{t}=\{\lambda_{t}^{1},\lambda_{t}^{2},\ldots,\lambda_{t}^{|V_{t}|}\}$. From the Eq.(9), it is easy to prove that its eigenvalues satisfy the following relation:

Therefore, only by solving all the eigenvalues of the normalized adjacency matrix $P_{t}$ of the iterative weighted network $G_{t}$, the spectrum of normalized Laplacian matrix can be given by Eq.(10). In addition, previous studies have proved that the eigenvalue $\lambda_{t}^{i}$ of normalized adjacency matrix $P_{t}$ of weighted connected network must satisfy the following properties:Chung & Graham [1997]

Therefore, the spectrum of the normalized Laplacian matrix $L_{t}$ of the iterative weighted network $G_{t}$ that satisfies the following condition:

whih is very important for us to solve the eigenvalues of the matrices $P_{t}$ and $L_{t}$ later.

Since the iterative weighted network $G_{t}$ is generated by the operation $\tau^{r}_{m}(\cdot)$, the spectrum of the normalized Laplacian matrix between two successive generations may also have some correlation. In this Subsection, the iterative relationship of the eigenvalues of the normalized Laplacian matrix $L_{t}$ will be revealed.

For any eigenvalue $\lambda_{t}\in\Lambda_{t}$ of the normalized adjacency matrix $P_{t}$, the corresponding eigenvector is denoted as $\psi_{t}$, where $\psi_{t}$ can be expressed as $\psi_{t}=[\psi_{t}^{1},\psi_{t}^{2},\ldots,\psi_{t}^{|V_{t}|}]^{\top}$, and the element $\psi_{t}^{i}$ in the vector corresponds to the node $i$ in the network $G_{t}$. According to the definition given by Eq.(8), the elements in the normalized adjacency matrix can be expressed as:

If node $i$ is specified to satisfy $i\in\hat{V}_{t}$, the following equation can be obtained from the relationship between eigenvalues and eigenvectors:

From Eq(3), the first term of Eq.(11) can be simplified to obtain the following relation:

When $k\in\bar{V}_{t}^{i}$, it can be obtained from the definition in the first Section that

Therefore, the second term of Eq.(11) can be expressed as:

Obviously, the number of nodes in $\bar{V}_{t}^{ij}$ is $m$ and these nodes are equivalent to each other, so it is easy to prove that Eq.(13) can be simplified to the following form:

Then, when $k\in\bar{V}_{t}^{ij}$, the relation between its corresponding eigenvector and eigenvalue can be expressed as:

where we used the conclusions: $\omega_{kh}=r\omega_{ij}$, $s_{t}^{k}=s_{t}^{h}=(m+1)r\omega_{ij}$ and the equivalence relation of the inner nodes of set $\bar{V}_{t}^{ij}$. Therefore, the eigenvector element $\psi_{t}^{k}$ corresponding to node $k\in\bar{V}_{t}^{ij}$ satisfies the following relation:

where the eigenvalue $\lambda_{t}$ must satisfy: $\lambda_{t}\neq\frac{m-1}{m+1}$. Then, the eigenvector element $\psi_{t}^{k}$ in Eq.(16) is substituted into Eq.(14) to obtain:

Therefore, if Eq.(12) and Eq.(17) are substituted into Eq.(11), the following relation can be obtained:

Then simplify Eq.(18) to obtain the following equation:

where $\lambda_{t}\neq\frac{m-1}{m+1}$ and $\lambda_{t}\neq\frac{m-1-mr}{m+1}$. From Eq.(19), it is easy to prove that when $i\in\hat{V}_{t}$, the new vector $\psi_{t}^{*}$ composed of the eigenvector element $\psi_{t}^{i}$ satisfies the following relation:

Thus, it can be determined that $\lambda_{t}^{*}$ is the eigenvalue of normalized adjacency matrix $P_{t-1}$, and $\psi_{t}^{*}$ is the eigenvector corresponding to the eigenvalue $\lambda_{t}^{*}$. The above Eq.(3.2) reflects the relationship between the eigenvalues of two successive generations of normalized adjacency matrices. Thus, it is easy to prove that, for $\forall\lambda_{t-1}\in\Lambda_{t-1}$, there is $\lambda_{t}\in\Lambda_{t}$ such that the following relationship holds:

Then, we define the equations $f_{1}(x)$ and $f_{2}(x)$ as follows:

Therefore, it can be concluded that for $\forall\lambda_{t-1}\in\Lambda_{t-1}$, $f_{1}(\lambda_{t-1})$ and $f_{2}(\lambda_{t-1})$ are the eigenvalues of the adjacency matrix $P_{t}$, that is $f_{1}(\lambda_{t-1}),f_{2}(\lambda_{t-1})\in\Lambda_{t}$. Here, it is worth noting that, according to the properties of matrix eigenvalues in Section 3.1 above, there is only one maximum eigenvalue in $\Lambda_{t-1}$ that satisfies: $\lambda_{t-1}^{1}=1$, so it can be obtained that:

The monotonicity of $f_{1}(x)$ and $f_{2}(x)$ also ensures that the eigenvalues generated by $f_{1}(x)$ and $f_{2}(x)$ meet the following requirements:

Then, combining Eq(10) and Eq(20), it is easy to prove that the eigenvalues of the Laplacian matrix $L_{t}$ satisfy the following relationship:

Similarly, equations $g_{1}(x)$ and $g_{2}(x)$ can be defined as follows:

Therefore, for $\forall\sigma_{t-1}\in\Psi_{t-1}$, $g_{1}(\sigma_{t-1})$ and $g_{2}(\sigma_{t-1})$ are the eigenvalues of the normalized Laplacian matrix $L_{t}$ of the $t$ generation respectively, that is $g_{1}(\sigma_{t-1}),g_{2}(\sigma_{t-1})\in\Psi_{t}$. In addition, for $\sigma_{t-1}^{1}=1$, it can be obtained that