网络科学中谱图理论

项目名称： 网络科学中谱图理论

项目编号： No.11271256

项目类型： 面上项目

立项/批准年度： 2013

项目学科： 数理科学和化学

项目作者： 张晓东

作者单位： 上海交通大学

项目金额： 60万元

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

中文关键词： 谱图理论；网络科学；特征值与特征向量；随机图；网络模型

英文摘要： 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.

英文关键词： Spectral graph theory；Network Science；Eigenvalue and Eigenvector；Random graph；Network model