谱图理论及其在复杂网络中的应用研究

Several active and important topics in spectral graph theory and its applications of finding community structures in complex networks will be investigated. 1. Properties of graph spectrum. The upper and lower bounds for the adjacency, Laplacian, signless Laplacian eigenvalues of graphs will be studied for better values; The coefficients of related characteristic polynomial of graphs, especially some special classes of graphs, will be studied; Some new parameters of graphs will be introduced, and their relationships with the spectrum of graphs will be establised. 2.Spectrum of corona. The adjacency(respectively, Laplacian, signless Laplacian) spectrum of some kinds of corona of two graphs will be computed and expressed by that of the two factor graphs. 3. Which graphs are determined by their spectrum? Some graphs will be studied and proved to be determined by their adjacency, Laplacian or signless Laplacian spectrum such as some trees, unicyclic graphs, bicyclic graphs, disjoint union graphs, product graphs, ling graphs, digraphs, etc.. More classes of graphs will be proved to be determined or not determined (have cospectral graphs) by their spectrum. 4. Applications of spectral graph theory. The relationship between spectral space and community structures of little-sized complex network will be studied; Some improved or new algorithms will be proposed to capture community structures in little-sized complex network with lower time complexity, and which will be used to find the community structures of public transpot network to help plan the intelligent transport of city. The study will deepen the properties of graph spectrum, compute the spectrum of some kinds of corona, broaden the classes of graphs characterized by their adjacency, Laplacian or signless Laplacian spectrum, and reveal the community structures of little-sized real complex network by using spectral clustering algorithm which will provide a new solution for route optimization of public transport.

研究谱图理论中的几个重要问题并将其应用于复杂网络社团挖掘：1.图的谱性质。研究各类图的邻接、拉普拉斯、无符号拉普拉斯特征值的估计；特征多项式的系数与谱的关系，特别是一些结构特殊的图类；寻找图的新的不变量，建立与谱之间的内在联系。2.冠图的谱。研究各类冠图的谱，将其表示为原图的谱。3.图的谱确定。研究一些树图、单圈图、双圈图及图的不交的并、乘积图、线图、有向图等的谱确定问题。证明更多的能由谱确定或不能由谱确定的图类。4.图的谱应用。研究谱空间与规模较小的复杂网络社团结构间的关系，改进或提出新的社团挖掘算法以实现对规模较小的复杂网络社团结构的提取和算法复杂性的降低，并将此算法用于城市公共交通网络中社团结构的提取，为城市智能交通规划服务。本项目将深化图的谱性质，得到更多类冠图的谱，拓宽谱确定图的范围，实现用谱聚类算法挖掘规模较小的真实网络社团结构，为城市交通线路优化提供新的解决途径。

图谱理论主要是通过图的邻接矩阵、拉普拉斯矩阵、无符号拉普拉斯矩阵、关联矩阵等的代数表示，应用组合矩阵论（尤其是非负矩阵论）来研究图的谱计算、谱性质及谱应用。图谱理论在计算机科学、通信网络、信息科学和量子化学等领域都有着广泛的应用。图谱中包含图的拓扑结构信息及代数性质。生物网、社会网、交通网等各种复杂网络都可以用图有效表示并加以研究。复杂网络中的社团结构划分算法是研究复杂网络的关键，利用图的一些谱性质设计算法对复杂网络中的社团结构进行划分有现实意义。.本项目通过对图的谱性质的研究，进而研究了冠图的谱、图的谱确定、复杂网络社团挖掘算法，主要研究内容和结论为：（1）复杂图（特别是冠图）的谱及应用。证明了几类联图及几类一般冠图的邻接谱、Laplacian谱及Signless Laplacian 谱可表示为原图的相应谱。证明了一些无穷A-整谱图类、同谱图类。得到了一些图的广义特征多项式，证明了一些广义同谱图。证明了几类广义冠图的谱，并巧妙地构造了一系列无穷图谱图。给出了一些图的电阻距离及Kirchhoff指数公式，并且用计算机编程实现了求一些图的电阻距及Kirchhoff指数的具体值。（2）图的谱确定。证明了dumbbell graph, theta graph的谱刻画，证明了一些树图的谱刻画。（3）研究了图谱与复杂网络社团结构间的关系，研究了节点相似度、基于Laplacian 特征根及特征向量的谱平分算法，提出了几种复杂网络社团划分算法，并将其应用于复杂网络中。.研究成果深化了图的谱性质，求得了一些复杂图的谱及电阻距离及Kirchhoff指数，扩大了谱确定图类的范围，提出了有效的复杂网络社团划分算法，为图谱理论在复杂网络中的应用奠定了理论基础和应用指导。