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  . In the past two decades, synchronization of complex networks has been extensively investigated and discussed, both numerically and theoretically  -  . 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  . Essentially, the coarse-graining process is very similar to the problem of cluster finding or community detection in networks      .
Therefore, some coarse-grained methods are proposed to try to transform large-scale networks into mesoscale networks    . For example, D. Gfeller et al.   proposed a spectral coarse-graining method (SCG) aiming at maintaining network synchronizability. Zhou and Jia proposed an improved spectral coarse-grained algorithm (ISCG)  based on the SCG method, which reduced the computational complexity and improved the synchronization capability. Chen et al.  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:
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:
where and are the Jacobian matrices of and with respect to , Diagonalizing Equation (2) yields the following form:
where is the eigenmode associated with the eigenvalue of L. Generalize Equation (3) to get the main stability equation:
The largest Lyapunov exponent of this equation is a function of real variables α, It is called the main stable function of network (1)  . 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  . 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
where, and are defined by
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  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  ).
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.  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.
To demonstrate our conclusions, we consider two real world networks-scientific cooperation network ( )  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.
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.
This project is supported by National Natural Science Foundation of China (Nos.61563013, 61663006) and the Natural Science Foundation of Guangxi (No.2018GXNSFAA138095).
 Chen, J., Lu, J.A., Lu, X.F., Chen, G.R., et al. (2013) Spectral Coarse Graining of Complex Clustered Networks. Communications in Nonlinear Science and Numerical Simulation, 18, 3036-3045.
 Wang, X.F. and Chen, G.R. (2002) Synchronization in Scale-Free Dynamical Networks: Robustness and Fragility. IEEE Transactions on Circuits and Systems I, 49, 54-62.
 Motter, A.E., Zhou, C.S. and Kurths, J. (2005) Network Synchronization, Diffusion, and the Paradox of Heterogeneity. Physical Review E, 71, Article ID: 016116.
 Zhou, J., Lu, J.A. and Lü, J.H. (2006) Adaptive Synchronization of an Uncertain Complex Dynamical Network. IEEE Transactions on Automatic Control, 51, 652-656.
 Lafon, S. and Lee, A.B. (2006) Diffusion Maps and Coarse-Graining: A Unified Framework for Dimensionality Reduction, Graph Partitioning, and Data Set Parameterization. IEEE Transactions on Pattern Analysis and Machine Intelligence, 28, Article ID: 13931403.
 Li, T. and Vanden-Eijnden, E. (2008) Optimal Partition and Effective Dynamics of Complex Networks. Proceedings of the National Academy of Sciences of the United States of America, 105, 7907-7912.
 Liu, J. and Liu, T. (2010) Coarse-Grained Diffusion Distance for Community Structure Detection in Complex Networks. Journal of Statistical Mechanics: Theory and Experiment, 2010, Article ID: 12030.
 Gfeller, D. and De, L.R.P. (2008) Spectral Coarse Graining and Synchronization in Oscillator Networks. Physical Review Letters, 100, Article ID: 174104.
 Zhao, M., Zhou, T., Wang, B.H., Yan, G., Yang, H.J. and Bai, W.J. (2006) Relations between Average Distance, Heterogeneity and Network Synchronizability. Physica A: Statistical Mechanics and Its Applications, 371, 773-780.