爱游戏app马竞赞助商

爱游戏app马竞赞助商:爱游戏app马竞赞助商新闻

爱游戏app马竞赞助商师生论文被国际学术会议STOC 2024录用
日期:2024-02-17访问量:

近日,中国人民大学高瓴人工智能爱游戏app马竞赞助商魏哲巍、文继荣团队的论文被ACM计算理论年会(ACM Symposium on Theory of Computing,STOC)录用。ACM计算理论年会(STOC)始于 1969年,是理论计算机科学领域最顶级的国际会议,在整个计算机科学领域享有崇高的声望,属于公认难度最高的会议之一,被中国计算机学会(CCF)推荐为A类国际会议。本届STOC会议将于2024年6月24日至6月28日在加拿大温哥华召开。

本篇论文的所有作者均来自中国人民大学,论文作者为魏哲巍教授、文继荣教授、博士生王涵之和杨铭基。本文是首篇由人大师生独立完成的STOC论文,也是爱游戏app马竞赞助商师生发表于STOC会议的第二篇论文,爱游戏app马竞赞助商首篇STOC论文由王子贺团队于2023年6月发表。

stoc.png

论文介绍

论文题目:Revisiting Local Computation of PageRank: Simple and Optimal

论文作者:王涵之、魏哲巍、文继荣、杨铭基

(同等贡献,遵从理论计算机惯例作者顺序按照作者姓氏首字母的字母序排列)

通讯作者:魏哲巍

论文概述:PageRank是一种重要的图分析指标,其最初由Google公司的两位创始人提出以计算Google搜索引擎上的网页重要性排名,后成为一种经典的图节点中心性衡量指标,被广泛应用于社交网络、信息检索、推荐系统,甚至生物、化学、神经科学等领域。

2007年,Reid Andersen、Christian Borgs、Jennifer Chayes、John E. Hopcroft、Vahab S. Mirrokni和Shang-Hua Teng开始关注大图上PageRank contributions的计算问题,即给定图上一个节点t作为目标节点,希望寻找图上所有对节点t的PageRank分值影响较大的节点。Andersen等人联合提出了ApproxContributions算法,借助大图上局部搜索的方式完成PageRank contributions的计算。ApproxContributions算法(后又称LocalPush、Backward Search、Backward Push等)自提出后获得了广泛关注,现已成为PageRank计算的基石算法,其各种变形被广泛应用于图节点邻近度与相似度计算、随机游走概率计算、社区发现等多类图分析问题的求解中。

但是,ApproxContributions算法自提出至今,其在最坏情况下的计算时间复杂度(worst-case computational complexity)始终缺乏有意义的分析结果。Andersen、Borgs、Chayes、Hopcroft、Mirrokni和Teng在2007年留于WAW会议上的开放问题“ApproxContributions算法的最坏时间复杂度是否能摆脱对图中节点度数的依赖?”虽经多年研究但始终未被解决。

本文给出了ApproxContributions算法在arc-centric graph-access model下的最坏时间复杂度上界,并给出了与之匹配的理论下界,证明了原始的ApproxContributions算法已至最优,从而回答了上述2007年提出的开放问题。特别地,本文所给出的分析方法十分简洁,且分析结果已至最优。

进一步地,本文将该分析结果应用于有向图上单点PageRank的计算问题(single-node PageRank computation)中,给出了arc-centric graph-access model下该问题的最坏时间复杂度和与之匹配的理论下界,回答了Marco Bressan、Enoch Peserico和Luca Pretto于FOCS 2018、SICOMP 2023上提出的开放问题“单点PageRank计算问题的时间复杂度上、下界间的理论差距是否可被消除?”。本文对该问题的分析过程亦非常简洁,且分析结果已至最优。

检测到您当前使用浏览器版本过于老旧,会导致无法正常浏览网站;请您使用电脑里的其他浏览器如:360、QQ、搜狗浏览器的速模式浏览,或者使用谷歌、火狐等浏览器。

下载Firefox
爱游戏app马竞赞助商(集团)股份有限公司