信息来源：高瓴人工智能学院网站 发布日期：2025-10-14

近日，中国人民大学高瓴人工智能学院魏哲巍团队的论文被国际学术会议SODA 2026录用。SODA（ACM-SIAM Symposium on Discrete Algorithms，离散算法研讨会）是理论计算机科学领域的顶级国际会议之一，其核心议题为离散问题的数据结构与算法设计。SODA在学术界享有盛誉，属于公认发表难度较高的会议，被中国计算机学会（CCF）推荐为A类国际会议。2026年的SODA会议将于1月11-14日在加拿大温哥华召开。

本论文由丹麦哥本哈根大学BARC研究中心与中国人民大学高瓴人工智能学院合作完成，是高瓴人工智能学院成立以来的首篇SODA论文。本论文聚焦有向图上单节点PageRank计算的复杂度问题，给出了该问题的精确上下界。魏哲巍团队长期致力于图上随机游走概率计算的复杂度与优化研究，在单点、单源及个性化（Personalized）PageRank等方向上均取得系列成果。

论文题目：PageRank Centrality in Directed Graphs with Bounded In-Degree

论文作者：Mikkel Thorup、王涵之（BARC, 丹麦哥本哈根大学）、魏哲巍、杨铭基（人大高瓴人工智能学院）

注：同等贡献，遵从理论计算机领域惯例作者顺序按照作者姓氏首字母的字母序排列

论文概述：PageRank是经典的图分析指标，可用于衡量图网络中节点的全局重要性（亦称为节点中心性），最初由Google创始人提出用于搜索引擎中的网页排名。PageRank算法被称为“数据挖掘十大算法”之一，在信息检索、推荐系统、图机器学习等领域具有广泛应用。

本文关注有向图上单个节点PageRank中心性的计算复杂度，希望高效地得到大规模图上指定节点的PageRank中心性在常数相对误差内的估计值。对于这一问题，既往工作所给出的复杂度界在图节点最大入度值较小时未至最优，例如，对于节点入度均为常数级别的图结构，既往工作所提上、下界间具有多项式级别的理论差距。本篇论文消除了这一差距，成功使该问题的计算复杂度上、下界相匹配（忽略对数因子）。