With the rapid development of big data, the scale of realistic networks is increasing continually. In order to reduce the network scale, some coarse-graining methods are proposed to transform large-scale networks into mesoscale networks. In this paper, a new coarse-graining method based on hierarchical clustering (HCCG) on complex networks is proposed. The network nodes are grouped by using the hierarchical clustering method, then updating the weights of edges between clusters extract the coarse-grained networks. A large number of simulation experiments on several typical complex networks show that the HCCG method can effectively reduce the network scale, meanwhile maintaining the synchronizability of the original network well. Furthermore, this method is more suitable for these networks with obvious clustering structure, and we can choose freely the size of the coarse-grained networks in the proposed method.
References
[1]
Jin, Y.P. (2016) Coarsening and Anomaly Detection of Complex Networks. (In Chinese)
[2]
Kim, B.J. (2004) Geographical Coarse Graining of Complex Networks. Physical Review Letters, 93, 168701. https://doi.org/10.1103/PhysRevLett.93.168701
[3]
Weiss, G.H. and Havlin, S. (1986) Some Properties of a Random Walk on a Comb Structure. Physica A Statistical Mechanics and Its Applications, 134, 474-482.
https://doi.org/10.1016/0378-4371(86)90060-9
[4]
Duan, Z., Chen, G. and Huang, L. (2007) Complex Network Synchronizability: Analysis and Control. Physical Review E Statistical Nonlinear and Soft Matter Physics, 76, 056103. https://doi.org/10.1103/PhysRevE.76.056103
[5]
Gfeller, D. and Rios, P.D.L. (2007) Spectral Coarse Graining of Complex Networks. Physical Review Letters, 99, 038701. https://doi.org/10.1103/PhysRevLett.99.038701
[6]
Gfeller, D. and Rios, P.D.L. (2008) Spectral Coarse Graining and Synchronization in Oscillator Networks. Physical Review Letters, 100, 174104.
https://doi.org/10.1103/PhysRevLett.100.174104
[7]
Zhou, J., Jia, Z. and Li, K.Z. (2017) Improved Algorithm of Spectral Coarse Graining Method of Complex Network. Acta Physica Sinica.
[8]
Chen, J., Lu, J.A., Lu, X.F., Wu, X.Q. and Chen, G.R. (2013) Spectral Coarse Graining of Complex Clustered Networks. Communications in Nonlinear Science and Numerical Simulation, 18, 3036-3045. https://doi.org/10.1016/j.cnsns.2013.03.020
[9]
Shuang, X. and Pei, W. (2016) Coarse Graining of Complex Networks: A k-Means Clustering Approach. Control and Decision Conference.
[10]
Liu, X.B. (2008) Research on the Clustering Algorithm of Cohesive Hierarchy. Scientific and Technological Information: Scientific Teaching and Research, 11, 202. (In Chinese)
[11]
Duan, M.X. (2009) Research and Application of Hierarchical Clustering Algorithms. Central South University. (In Chinese)
[12]
Zhang, J.H. (2007) K-Means Clustering Algorithms Research and Application. Wuhan University of Technology, Wuhan. (In Chinese)
[13]
Anonymous (2012) Introduction to Network Science. (In Chinese)
[14]
Watts, D.J. (1999) Networks, Dynamics, and the Small-World Phenomenon. American Journal of Sociology, 105, 1-10. https://doi.org/10.1086/210318
[15]
Watts, D.J. (1999) Small Worlds: The Dynamics of Networks between Order and Randomness. Princeton University Press, Princeton.
[16]
Chen, J., Lu, J.A., Lu, X.F., Wu, X.Q. and Chen, G.R. (2013) Spectral Coarse Graining of Complex Clustered Networks. Communications in Nonlinear Science and Numerical Simulation, 18, 3036-3045. https://doi.org/10.1016/j.cnsns.2013.03.020
[17]
Chen, J. and Lu, J. (2012) Medium-Scale Study of Complex Networks Uncovers the Process of Network Synchronization. Journal of University of Electronic Science and Technology, 41. (In Chinese)
[18]
Erdos, P. and Rnyi, A. (1960) On the Evolution of Random Graphs. Publication of the Mathematical Institute of the Hungarian Academy Offences, 38, 17-61.
[19]
Barabasi, A.L. and Albert, R. (1999) Emergence of Scaling in Random Networks. Science, 286, 509-512.
[20]
Barabasi, A.L., Albert, R. and Jeong, H. (1999) Mean-Field Theory for Scale-Free Random Networks. Physica A, 272, 173-187.
https://doi.org/10.1016/S0378-4371(99)00291-5
[21]
Li, Z., Liu, J., Jiang, P., et al. (2008) Effect of Average Degree on Synchronization Ability of Complex Networks. Guangxi Physics, No. 1, 18-20 (In Chinese)
