Spectral Coarse Graining Algorithm Of Complex Network And Its Application

Complex networks is a key approach to understanding many complex systems in nature and society,such as biological,chemical,physical,technology and social systems,which are ubiquitous,and complex networks has gradually became the research focus of network science and its interdiscipline.Synchronization of large-scale complex network is one of the most important concept in network science.Many real networks consist of even hundreds of millions of nodes,analyzing the synchronization of such large-scale coupled complex dynamic networks often generate a large quantity of coupled differential equations,which may make many synchronization algorithms for meso-scale networks inapplicable due to the complexity of simulation experiments.Coarse graining method can map the large-scale networks into meso-scale networks while preserving some of topological properties or dynamic characteristics of the original network,which is one of the important ways to study large-scale networks.This paper is basically focused on the coarse graining algorithm of large-scale complex network based on synchronization ability,the main contents are summarized as follow:(1)The Spectral Coarse Graining Method(SCG)proposed by David Gfeller and Paolo De Los Rios in 2008 is one of the most typical coarse graining methods at present,and reduce the network size while preserving the synchronization capacity of the initial network as well it can better maintain the original network's ability to synchronize at the same time.However,a large number of simulation experiments show that SCG method present the limitations to great computation and poor executable with large-scale network in actual calculation.For this purpose,we propose an improved spectral coarse graining algorithm(ISCG),can significantly reduce the amount of computation,while achieving better spectral coarse granulation effect.Theoretica l analysis and extensive numerical simulation experiments results demonstrate that the effect of coarse graining and calculation of ISCG algorithm are obviously outperfor ms the SCG method.(2)To propose a coarse graining method of complex network based on the spectral clustering algorithm.According to the analysis and theoretical derivation of the spectral clustering algorithm,it has been found that the way of clustering network nodes can transform into the method of clustering the components of eigenvectors for the eigenvalues of the Laplacian matrix.Therefore,this paper presents a coarse graining method of complex network based on the spectral clustering algorithm(SCA-CG).A large number of numerical simulation experiments show that this method can also betterly maintained the synchronization ability of network while course graining the network.(3)For further study of internal relationships between SCG method and SCACG algorithm.It is found by analyzed that the SCA-CG algorithm based on spectral clustering is consistent with the SCG method based on synchronization,and the substantial mechanism of SCG is an application of spectral clustering algorithm to coarse graining network.