复杂网络谱粗粒化方法的改进算法

Improved algorithm of spectral coarse graining method of complex network

大规模网络的同步问题是网络科学的重要研究课题之一.粗粒化方法提供了一种将大规模网络转化为小规模网络,同时又能较好地保持原始网络的拓扑性质或动态特性的研究途径,其中比较有代表性的谱粗粒化方法能较好地保持初始网络的同步能力.然而,谱粗粒化方法在实际计算中计算量大、对实际大规模网络可执行性差.本文提出一种改进的谱粗粒化算法,能大幅减少计算量,同时获得更好的谱粗粒化效果.通过理论分析和大量的数值仿真实验验证了所提改进算法的粗粒化效果和计算量都明显优于原谱粗粒化方法.

Complex network as a key approach to understanding many complex systems,such as biological,chemical,physical,technological and social systems,is ubiquitous in nature and society.Synchronization of large-scale complex networks is one of the most important issues in network science.In the last two decades,much attention has been paid to the synchronization of complex dynamic networks,especially the meso-scale networks.However,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 number of coupled differential equations,which may make many synchronization algorithms inapplicable for meso-scale networks due to the complexities 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.Especially,the spectral coarse-graining scheme,as a typical coarse graining method,is proposed to reduce the network size while preserving the synchronization capacity of the initial network.Nevertheless,plenty of studies demonstrate that the components of eigenvectors for the eigenvalue of the coupling matrix,which can depict the ability to synchronizing networks,distribute unevenly.Most of the components distribute concentrically and the intervals are small,while some other components distribute dispersedly and the intervals are large,which renders the applications of original spectral coarse graining method unsatisfactory.Inspired by the adaptive clustering,we propose an improved spectral coarse graining algorithm,which clusters the same or the similar nodes in the network according to the distance between the components of eigenvectors for the eigenvalue of network coupling matrices,so that the nodes with the same or the similar dynamic properties can be effectively clustered together.Compared with the original spectral coarse graining algorithm,this method can improve the accuracy of the result of clustering.Meanwhile,our method can greatly reduce algorithm complexity,and obtain better spectral coarse graining result.Finally,numerical simulation experiments are implemented in four typical complex networks： NW network,ER network,BA scale-free network and clustering network.The comparison of results demonstrate that our method outperforms the original spectral coarse graining approach under various criteria,and improves the effect of coarse graining and the ability to synchronize networks.