Influence of Topological Properties of Complex Networks on the Effect of Spectral Coarse-Grained Network ()
1. Introduction
Synchronization, as an emerging phenomenon of a population of dynamically interacting systems, is ubiquitous in nature and plays an important role within various contexts in biology, chemistry, ecology, sociology, and technology [1] . In the past two decades, synchronization of complex networks has been extensively investigated and discussed, both numerically and theoretically [2] - [8] . Unfortunately, many real-world networks are too huge to be dealt with current tools or algorithms. For example, human brain contains 1011 neurons and more than 1015 connections, which brings a big challenge to research on such networks. Especially for the dynamics of large-scale coupling nodes, large number of coupled differential equations result in the trouble of the computation and simulation. Many techniques and methods at the level of mesoscale networks are useless in large networks. Therefore, when using model reduction for simulation and analysis, it is crucial to be able to reduce the network size while keeping most of the relevant properties of the initial networks [1] . Essentially, the coarse-graining process is very similar to the problem of cluster finding or community detection in networks [9] [10] [11] [12] [13] .
Therefore, some coarse-grained methods are proposed to try to transform large-scale networks into mesoscale networks [14] [15] [16] . For example, D. Gfeller et al. [14] [15] proposed a spectral coarse-graining method (SCG) aiming at maintaining network synchronizability. Zhou and Jia proposed an improved spectral coarse-grained algorithm (ISCG) [16] based on the SCG method, which reduced the computational complexity and improved the synchronization capability. Chen et al. [1] investigated the effects of the coarse graining process on synchronizability over complex clustered networks. They found that a more prominent cluster structure implies a higher capability of the coarse graining strategy in preserving the synchronizability of the initial networks.
Many articles only studied the maintenance of the topological properties of the initial networks by the coarse-grained method, but few people discussed the influence of the topological properties of the initial network on the effect of the coarse graining method. In this paper, we find that the longer the average path length or the more heterogeneous the degree distribution of the initial network, the spectral coarse-grained algorithm becomes more effective in keeping the synchronization ability.
The rest of the paper is organized as follows. In Section 2, Mathematical basis is introduced. Influence of topological properties of complex networks on the effect of coarse-grained networks are proposed in Section 3. In Section 4, we verify our results through the real world networks. Finally, some conclusions are drawn in Section 5.
2. Mathematical Basis
2.1. Characterization of Network Synchronization Capability
Consider a general complex dynamic network with N nodes. The dynamic equation as follow:
(1)
where
is the n-dimensional state variable of the ith node,
is the coupling strength,
is the inner coupling function, and the Laplacian matrix
describes the coupling topology of the network, in which
if j connects to i (otherwise 0). The matrix L satisfies the dissipation coupling conditions:
. If the network is undirected and connected, then L is a symmetric and positive semi-definite matrix with nonnegative eigenvalues satisfying
. If there is
and
, then
, the state of all nodes of the Equation (1) is fully (asymptotically) synchronized to
and
is called a synchronous state, and which
is the variation of the ith node, The variational equation is obtained by:
(2)
where
and
are the Jacobian matrices of
and
with respect to
, Diagonalizing Equation (2) yields the following form:
(3)
where
is the eigenmode associated with the eigenvalue
of L. Generalize Equation (3) to get the main stability equation:
(4)
The largest Lyapunov exponent of this equation is a function of real variables α, It is called the main stable function of network (1) [17] . For node’s dynamics, there exist
, such that the synchronized state is linearly stable. As a consequence, the network can be synchronized if
, which means that larger
or larger
leads to better synchronizability. In this paper, both
and
are used to characterize network synchronizability.
2.2. The Spectral Coarse-Graining Method
In 2008, D. Gfeller et al. proposed a spectral coarse graining method based on merging nodes with similar characteristic components in reference [15] . The aim is to obtain a simplified network that maintains the synchronization capability of the initial network. The network synchronization capability is represented by
and
. Take the indicator of maintaining synchronization as an example, the algorithm is as follows:
First, determine which nodes merge. Let p2 denotes the eigenvector for the smallest nonzero eigenvalue
. Merging nodes that correspond to the same or similar components in p2. Here
and
are the largest and the smallest components of p2. Divide the elements in p2 evenly between
and
into I intervals. The smaller I is, the smaller the size of the coarse-grained network will be, and the more the size of the network is reduced.
Second, update edges and extract the coarse-grained network. Let the N nodes of the initial network be labeled with
, and the coarse-grained network has
nodes corresponding to
groups, labeled with
. The edges of the coarse-grained network (corresponding to the new Laplacian matrix
) can be updated by the following matrix product
(5)
where,
and
are defined by
(6)
Here,
is the cardinality of group C;
is the index of the I’th node group, and Ψ is the Kronecker symbol.
2.3. The Random Interchanging Algorithm
To investigate the structural effects on network synchronizability, we use random interchanging algorithm [18] to adjust the average path length while keeping degree distribution unchanged. The process is as follows:
1) Randomly pick two existing edges
and
, such that
and there is no edge between
and
as well as
and
.
2) Cross reconnect these four nodes., that is, connect
and
as well as
and
, and remove the edges
and
.
3) Ensure that the network is connected and calculate whether this interchange increases/decreases the network average path length. If it does, accept the new configuration, else restore the original network structure.
4) Repeat step 1) unless the desired average path length is achieved.
Because the algorithm is only reconnected, it does not change the degree of any node. So the degree distribution and degree sequence are fixed. Figure 1 provides a sketch map of random interchanging algorithm, which may help us understand the program flow.
3. Influence of Topological Properties of Complex Networks on the Effect of Coarse-Grained Network
3.1. Influence of the Average Path Length
We consider a small-world network with average degree
, 1000 nodes. By random interchanging, we obtain four small-world networks with the same degree distribution and different average path lengths, respectively 5.5219, 5.5518, 5.9301 and 6.6772. Similarly, we consider the scale-free network with
![]()
Figure 1. A schematic diagram of random interchanging algorithm (cited in reference [18] ).
power exponent 2.05, 1000 nodes. Through random interchanging, we obtain four scale-free networks with the same degree distribution and different average path lengths, and the average path lengths are 4.1000, 4.2530, 4.3048, 4.4591.
Based on the spectral coarse-graining method, The initial network of N = 1000 nodes is merged into
groups, and
and
denote the smallest non-zero eigenvalue and the largest non-zero eigenvalue of the new Laplacian matrix, respectively. The relationship between
,
and
for different values of average path lengths are shown in Figure 2(a) Figure 2(c) and Figure 3(a) Figure 3(c), respectively. We find that the more the average path length increases, the better the synchronization ability of the network is maintained. This means that the smaller the average path length of the network, the larger the size of the coarse-grained network is needed to keep the values of
and
unchanged with the corresponding values of the initial
![]()
![]()
Figure 2. (a) (c) Evolution of
and
with respect to
for WS small-world networks with a constant degree of distribution and different average path lengths; (b) (d) Evolution of the corresponding absolute error.
![]()
![]()
Figure 3. (a) (c) Evolution of
and
with respect to
for scale free networks with a constant degree of distribution and different average path lengths; (b) (d) Evolution of the corresponding absolute error.
network. On the other hand, Figure 2(b) Figure 2(d) and Figure 3(b) Figure 3(d) show the evolution trend of the absolute error of the eigenvalue
and the eigenratio
between the initial network and the coarse-grained network as a function of
for different average path lengths. It can be seen that when the average path length decreases, the absolute error of
and
between the initial network and coarse-grained networks increases. This result shows that compared with a network with long average path length, a network with short average path length needs more
to achieve the same absolute error.
In summary, regardless of the small-world networks or scale-free networks, as the average path length increases, the eigenvalue
and the eigenratio
of coarse-grained networks become closer to the original values of the initial networks, which is to say that, with the increase of the average path length, the spectral coarse-grained method becomes more effective in keeping the network synchronization.
In Figure 4(a), the initial network is small-world network with 1000 nodes and average degree
. Different curves indicate the variance of the degree distribution of the generated small-world networks, which are 1.0840, 0.7620 and 0.4180, respectively. In Figure 4(b), the initial network is scale-free network with 1000 nodes and average degree
. The variance of degree distributions expressed by each curve is 26.368, 19.558 and 15.348, respectively. It is obvious that the above two figures show positive correlation between average path length and clustering coefficient. Chen et al. [12] studied that the more obvious the clustering is, the better the coarse-graining effect is, which means that the longer the average path length, the better the ability of spectral coarse-graining method in preserving the network synchronizability.
3.2. Influence of the Degree Distribution
In order to measure the heterogeneity of the degree distribution of the network, we use the degree variance σ to represent the heterogeneity of the degree distribution. The greater the degree variance, the more inhomogeneous the network.
Similarly, we first obtain small-world networks with different four-degree variances by reconnecting probabilities p = 0.1, 0.2, 0.3, and 0.4. We use the random interchanging algorithm to equalize the average path lengths of these four networks. Then we get four networks with the same average path length and different degree distribution. The degree variance is 0.3657, 0.7640, 1.0840, and 1.3200, respectively. Equally, we consider the four scale-free networks with 1000 nodes, uniform average path length and different degree distributions. The degree variances are 14.2060, 15.2419, 18.6693, and 24.4806, respectively.
![]()
Figure 4. The relationship between average distance and clustering coefficient in the process of random interchanging.
Figure 5(a) Figure 5(c) and Figure 6(a) Figure 6(c) show the evolution of
and
respect to
for networks with uniform average path length and different degree variances. We observe that with smaller σ, the more uniformly distributed the network degree, the larger the size of the coarse-grained network needs to be, to remain the values of
and
unchanged. In addition, Figure 5(b) Figure 5(d) and Figure 6(b) Figure 6(d) indicate the evolution trends of the absolute error of
and
of the initial network and the coarse-grained networks, respectively. It can be seen that as the degree variance decreases, the error of the eigenvalues and eigenvalues ratio corresponding to the coarse-grained network and the initial network become larger. This also shows that the reduction of the variance of degree is not conducive to coarse graining network.
![]()
![]()
Figure 5. (a) (c) Evolution of
and
with respect to
for WS small-world networks with the same average path length and different degree of distribution; (b) (d) Evolution of the corresponding absolute error.
![]()
![]()
Figure 6. (a) (c) Evolution of
and
with respect to
for scale free networks with the same average path length and different degree of distribution; (b) (d) Evolution of the corresponding absolute error.
The simulation results show, with the increase of degree variance, the distribution of network degree becomes more heterogeneous in both small-world networks and scale-free networks. The
and
of coarse-grained network are more close to the corresponding values of the initial networks, that is to say, the effect of coarse-grained network will be better with the increase of degree variance.
4. Example
To demonstrate our conclusions, we consider two real world networks-scientific cooperation network (
) [19] and protein-protein interaction network in budding yeast (
). We obtain four scientific cooperation networks with average path lengths of 4.4783, 5.5061, 5.5832, and 6.0419 through the random
![]()
![]()
![]()
Figure 7. (a) (c) (e) Evolution of
and
with respect to
for scientific cooperation network with
and protein-protein interaction network with
; (b) (d) (f) Evolution of the corresponding absolute error.
interchanging algorithm. Moreover, we get three protein-protein interaction networks with average path lengths of 4.0122, 4.2111, and 4.3763 through the random interchanging algorithm. The results are shown in Figure 7. We find that the experimental results are consistent with above conclusion. As the average path length increases, the effect of coarse-graining method is better.
5. Conclusion
This paper studies the influence of the average path length and the heterogeneity of the degree distribution on the ability of spectral coarse-graining method in keeping the network synchronizability. According to the large number of simulation experiments, the average path length and the heterogeneity of degree distribution are closely related to keep the
and
of the initial networks when applying spectral coarse-graining method to reduce the network size. The longer the average path length, the more inhomogeneous the degree distribution, which can better maintain the network synchronization ability in the coarse-grained process.
Acknowledgements
This project is supported by National Natural Science Foundation of China (Nos.61563013, 61663006) and the Natural Science Foundation of Guangxi (No.2018GXNSFAA138095).