复杂网络上的偏好游走及其应用

Random walks on complex networks are the foundations of routing, propagation, search, as well as other dynamics on networks. They have found important applications in various disciplines, such as computer science, control science, physics, and biology. In this project, we will study biased walks on complex networks based on the importance of nodes and edges. Our goals are twofold. One is to uncover the effects of various biases related to nodes or edges on the primary quantities of random walks, including stationary distribution, mean first-passage time, mixing time, and cover time. The other is to apply biased walks to the field of graph data mining. First of all, according to different measures of node importance, such as degree, leading eigenvector of adjacency matrix, and leading eigenvector of high-order non-backtracking matrix, we will analyze or establish corresponding models for biased walks, and unveil the influences of different measures of node importance. Then we will further propose a unified framework for biased walks based on diverse measures of node importance. With respect to biased walks on different importance metrics of edges, we will introduce several methods to establish transition matrices, using which to study analytically or numerically the above-mentioned quantities on random walks, in order to find the roles of weight distribution and reciprocity in biased walks. Finally, we will present several fast and effective algorithms, in order to apply biased walks to node group centrality and link prediction.

复杂网络上的随机游走是路由、传播、搜索等网络上其它动力学的基础，在计算机、控制、物理、生物等学科中有着重要的应用。本项课题拟对复杂网络上基于节点与边重要性的偏好随机游走进行研究，旨在揭示不同的偏好对于稳态分布、平均首达时间、混合时间、覆盖时间等随机游走主要物理量的影响，并在图数据挖掘领域进行应用。首先，根据网络节点重要性的不同度量，如节点度、邻接矩阵主特征向量、高阶非回溯矩阵主特征向量等，分析或建立相应的偏好游走模型，比较基于节点的不同偏好对随机游走行为的影响，并进一步建立一个基于节点重要性偏好游走的统一框架。针对基于边重要性的偏好游走，拟提出若干方法，构建偏好游走转移矩阵，解析或数值研究不同偏好游走的相关物理量，揭示边权分布、边权互惠性等在偏好游走中所起的作用。最后，提出若干快速有效算法，将偏好游走应用于节点集团中心与链路预测等领域。

随机游走是复杂网络上最基础最重要的动力学过程之一，在图数据挖掘等诸多领域有着广泛应用。本项课题对复杂网络上偏好随机游走的理论与应用进行了研究，揭示了无标度拓扑、分形性、边中心性等对随机游走行为的影响，并对随机游走在网络中心性、一致性问题、观点动力学中的广泛应用进行了深入探讨。..项目实施四年中，在国际重要会议和期刊上发表标注项目资助的论文31篇，包括1篇NeurIPS，2篇KDD，3篇WWW，1篇WSDM, 2篇CIKM，2篇ICDM，3篇IEEE Transactions on Information Theory，4篇IEEE Transactions on Cybernetics，1篇IEEE Transactions on Control of Network Systems，1篇Theoretical Computer Science，10篇The Computer Journal，1篇Fractals。项目主要研究成果获2022年中国计算机学会自然科学二等奖，项目负责人为第一完成人。项目培养出站2名博士后；培养毕业1名博士研究生，该博士的毕业论文获2020年“复旦大学优秀博士学位论文”奖；培养毕业2名硕士研究生，他们分别获得“上海市优秀毕业生”与“复旦大学优秀毕业生”称号。参与项目的研究生中，3人共获得国家奖学金4次，1人获复旦大学“学术之星”称号。此外，还培养十余名本科生，他们与项目负责人合作发表多篇论文。