网络的谱及其应用研究

项目名称： 网络的谱及其应用研究

项目编号： No.11275049

项目类型： 面上项目

立项/批准年度： 2013

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

项目作者： 章忠志

作者单位： 复旦大学

项目金额： 80万元

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

中文关键词： 复杂网络；谱图理论；拉普拉斯矩阵；马尔科夫矩阵；随机游走

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

英文关键词： Complex network；Spectral graph theory ；Laplacian matrix； Markov matrix；Random walk