图论与复杂网络

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

GRAPH THEORY AND COMPLEX NETWORKS

In the past ten years,the fast development of complex network theory has provided a goodsupport for the study of complexity and complex systems, sincethey describe clearly the important characteristics of complexsystems, and show bright prospects in theory and applications.This paper presents mainly the application of graph theory tocomplex networks, especially to the synchronization problem ofcomplex networks. First, its application to the estimations ofsmallest nonzero, largest eigenvalues and synchronizability indexof certain graphs are commented, followed by the effects ofsubgraph and graph eigenvector in the estimation ofsynchronizability index. Furthermore, the complexity between therelationships of synchronizability and network structuralparameters are discussed via two simple graphs, and the effects ofcomplementary graph, edge-addition and graph operation on thesynchronization of complex networks are elaborated. Finally, somepossible development directions in complex networks are predictedfrom the viewpoint of graph and control theory.