网络的谱及其应用研究

Spectra (eigenvalues and eigenvectors) of a network determine many of its structural properties and dynamical processes taking places on the network. In this project, we will study the spectra and their applications for some important matrices of networks, including adjacency matrix, Laplacian matrix, and probability transition matrix. First, for different types of networks we will propose some new techniques to calculate their complete/partial spectra, with an aim to obtain the exact or approximate solutions. Then using these obtained results for spectra and combining those previously reported, we will study relevant structural features and dynamical processes. In the structural aspect, we will determine Estrada index, Kirchhoff index, as well as the number of spanning trees for some networks. While for dynamical processes, we will construct maximal entropy random walks by determining the transition probability, explore the behavior of quantum walks, compute the mixing time and eigentime for traditional unbiased random walks, and compare the results for different walks. This project can deepen the understanding of network complexity, and relation between structure and dynamics.

网络的谱（特征值与特征向量）决定了网络的众多结构性质与动力学过程。本项课题拟对网络若干重要矩阵的谱及其应用进行研究，包括邻接矩阵、拉普拉斯矩阵、概率转移矩阵等。首先，针对不同种类的网络，提出一些新方法，分别计算它们邻接矩阵、拉普拉斯矩阵、概率转移矩阵的谱，得到网络全部/部分谱的精确或近似结果。然后，利用所得的谱结果并结合前人的相关研究结果，研究与谱相关的网络结构性质与动力学过程。结构方面包括Estrada指数、基尔霍夫指数、生成树数目等相关量的计算，动力学方面主要包括最大熵随机游走的构造、量子游走的行为特征、传统无偏游走的混合时间与特征时间的计算、传统无偏游走与最大熵游走及量子游走的区别。本课题对于揭示网络的结构复杂性、理解网络结构与动力学过程的关系具有重要的科学意义。

本项课题通过运用统计物理、谱图理论、代数图论等方法，得到了复杂网络中的几类重要矩阵（邻接矩阵、拉普拉斯矩阵、转移矩阵、归一化拉普拉斯矩阵）谱的解析或数值解，并将相关谱结果用于计算网络的基尔霍夫指数、生成树数目、传统无偏游走的混合时间、最大熵随机游走的首达时间等网络的结构与动力学相关物理量。揭示了网络谱、结构、及动力学过程三者之间的关系。..项目实施四年中，在国际重要SCI期刊上发表标注项目资助的论文36篇，其中《Physical Review E》7篇，《Journal of Chemical Physics》11篇（其中1篇为封面论文），《EPL (Europhysics Letters)》1篇，《Chaos》2篇。项目主要研究成果获2013年上海市自然科学三等奖，项目负责人为第一完成人。项目培养毕业硕士研究生7名，其中1名硕士的毕业论文获“上海市优秀硕士学位论文”，6名硕士生毕业分别获得“上海市优秀毕业生”与“复旦大学优秀毕业生”称号。参与项目的研究生获得国家奖学金9人次，1人获“全国复杂网络会议最佳学生论文奖”，1名博士生获复旦大学“优秀博士生科研资助计划资助项目”，3名硕士生分别获复旦“研究生创新基金资助项目”资助。此外，还培养十余名本科生，他们与项目负责人合作发表论文10余篇。.