网络科学中谱图理论

Network science is a new discipline that combines statistical physics, computer science, biological science and social science with network theory and graph theory, where spectral graph theory is an important part of the network science and is a vital mathematical tool and method for dealing with complex networks. The project focuses on mathematical problems and models in network science. The main purpose of this project is to establish qualitative and quantitative relationship between important parameters and features (including average path length, diameter, clique number, matching number, cluster coefficient, between, node centrality, community partition, degree distribution and the correlation) of a variety of graphs, Erd?s-Rényi random graphs, random graphs with given degree distribution, the small-world networks, the scale-free networks and their corresponding eigenvalues (spectral density, spectral graph sparsifiers and spectral gap) and eigenvectors (eigenspace). The project also investigates some important properties of quasi-random graphs and spectral extremal theory which reflect essential features of random graphs. The expected results will provide appropriately rigorous mathematical bases and methods for network science and extend combinatorial matrix theory.

网络科学是由统计物理、计算机科学、生物科学、社会科学、数学（图论）等学科相互交叉形成的一门新学科，其中谱图理论是网络科学重要组成部分和研究网络科学重要的数学方法和工具。本项目着重研究网络科学中提出的数学问题和网络数学模型。主要围绕能够揭示确定性的图、（伪）随机图、给定度分布随机图、小世界网络、无标度网络等网络拓扑结构和动力学行为中重要的不变量和特征（包括平均距离、直径、团数、匹配、聚集系数、介数、节点中心、社团划分、度分布及其相关性等）与网络的特征值（包括谱密度、谱稀疏性和谱隙等）和特征向量（特征空间）之间的内在定性关系以及定量刻画开展深入细致地研究和探索。研究反映和揭示各种随机图的本质和性质的伪随机图理论和谱极值理论。本项目通过提出网络科学研究的新思路以及采用新手段来发展和完善网络科学坚实的数学理论基础与网络科学研究的数学方法，同时拓展组合矩阵论与图论的广度和深度。

网络科学是由统计物理、计算机科学、生物科学、社会科学、数学（图论）等学科相互交叉形成的一门新学科，其中谱图理论是网络科学重要组成部分和研究网络科学重要的数学方法和工具。本项目主要围绕具有给定结构的网络，特别具有随机图某种性质的确定性的图、伪随机图、经典随机图以及它的各种推广的随机网络包括给定度分布的随机图、小世界网络和无标度网络等拓扑结构和动力学行为与代表它们的不同类型的矩阵包括邻接矩阵、拉普拉斯矩阵、无符号拉普拉斯矩阵、距离矩阵等特征值和特征向量之间关系开展细致深入的研究。在国内外重要期刊上一共发表了 27篇 SCI 论文，组织了第八届组合论国际学术会议。 . 本项目的重要结果包括下面九个方面， 第一、解决了Sills 和 Wang等人提出关于距离矩阵的谱与图的拓扑参数和度分布的两个猜想； 第二、证明了Lin 等人提出关于完全多部图可以由它们的距离谱所确定的猜想。第三、建立了图的拉普拉斯系数、图的谱、图的匹配多项式、图的参数、图的能量等之间联系。第四、建立了小世界网络的拉谱拉斯谱与等周常数之间重要的不等式。从数学上严格证明了小世界网络具有大的聚集系数和小的直径。第五、 提出了一种基于公共近邻和距离的新算法用来提高复杂网络中丢失的链路预测精度。第六、全部解决了Gorgol关于极值图论不含k个顶点为3的路的并的边的极值以及极图的情况的猜想。第七、给出给定弧的最大谱半径的上界， 并且刻画达到极值的所有极图。第八、基于有限域构造了一类代数CAYLEY 图， 该类图具有很好的伪随机的性质和特征。 第九、得到了树的拓扑结构的性质与树的局部子树之间关系。 . 本项目研究成果着重揭示网络拓扑结构和动力学行为中重要的不变量与网络的特征值和特征向量之间的内在定性关系以及定量刻画。这些关于图谱理论的新的结果和新的方法将可能应用到线性系统快速算法、图的稀疏化、局部的随机游动、网络科学等领域。 另一方面这些研究成果和新方法将丰富和发展谱图理论的研究内容和深度，建立谱图理论与其他学科之间，例如计算机科学、算法理论等，内在联系，同时拓展组合矩阵论与图论的广度和深度。本项目研究成果为网络科学研究进一步提供数学理论根据和新的数学方法和技巧。.