图论与复杂网络

近10年来迅猛发展起来的复杂网络理论为研究复杂性与复杂系统科学提供了一个重要支撑点,它高度概括了复杂系统的重要特征,无论是在理论还是在应用方面都具有很强的生命力,而且在各个方面都得到了很大发展.重点讨论图论在复杂网络中的应用,特别是代数图论在复杂网络同步问题中的应用.首先给出一些图的最小非零与最大特征值以及同步能力的估计,并且讨论了子图与图特征向量在同步能力估计中的作用.其次以两个简单图指出同步能力与网络结构参数的关系复杂,并给出补图与加边对同步研究的意义,然后给出图运算在复杂网络同步中的作用.最后从图论与控制理论角度展望了复杂网络领域未来可能的发展方向. 

GRAPH THEORY AND COMPLEX NETWORKS

In the past ten years, the fast development of complex network theory has provided a good support for the study of complexity and complex systems, since they describe clearly the important characteristics of complex systems, and show bright prospects in theory and applications. This paper presents mainly the application of graph theory to complex networks, especially to the synchronization problem of complex networks. First, its application to the estimations of smallest nonzero, largest eigenvalues and synchronizability index of certain graphs are commented, followed by the effects of subgraph and graph eigenvector in the estimation of synchronizability index. Furthermore, the complexity between the relationships of synchronizability and network structural parameters are discussed via two simple graphs, and the effects of complementary graph, edge-addition and graph operation on the synchronization of complex networks are elaborated. Finally, some possible development directions in complex networks are predicted from the viewpoint of graph and control theory.