在信息爆炸的互联网时代，如何将搜索得到的网页按照重要性进行排序并呈现给用户？
这个问题困扰着无数早期的搜索引擎。
打破游戏规则的是创始人布林和佩奇提出的页面排名算法，该算法为这个问题提供了突破性的解决方案：为每个网页计算重要性分数或分数。分数越高，网页的质量越好。 ，在信息检索中的重要性越高。
因此，在向用户反馈网络搜索结果时，应该将这些重要的网页排名靠前，以便为用户提供更好的搜索体验。
考虑到互联网的巨大规模，“如何高效地计算互联网上每个网页的得分？”这个问题一提出就引起了研究者的长期关注。研究问题大致可分为两类：
1、计算互联网上所有网页的得分。更一般地说，如果将互联网中的网页链接结构转换为图结构，网页对应图节点，网页之间的链接关系对应节点之间的边，这类问题有望高效计算分数图上所有节点的数量；
2、相比之下，另一类问题侧重于互联网上少数特定网页的分数计算，例如计算几个知名网站的分数。这类问题称为单点计算（-node）。
对于上述两类问题，第一类的研究已经基本成熟，但第二类“单点计算”的计算复杂度还远未达到最优。
近日，中国人民大学研究人员在2024年ACM计算理论年会（ACM on of，STOC）上发表论文，将单点计算复杂度优化至1级，同时给出了匹配的理论下界证明了所提出的复杂度上限和下限的最优性。
论文链接：
论文所有作者均来自中国人民大学，包括魏哲伟教授、温继荣教授、博士生王含志和杨明吉。
这项研究解决了单点计算的问题，这个问题已经研究了很多年，但实现最优计算复杂度的理论证明非常简单。
几位 STOC 审稿人评论道：
“文章给出的证明出人意料的简短和简洁，但却令人难以想象，这让我感到惊讶。” “这篇文章使用了非常复杂的分析来解决一个已经被广泛研究的问题。”
定义想法
最初基于以下两点给出了网页得分的计算方法：
1.人们普遍倾向于引用质量较高的网页。如果一个网页被大量网页引用，那么它的质量就应该更好，那么它的得分就应该提高，从而提高它在搜索结果中的排名；
2. 另一方面，如果已知某个网页很重要（例如知名组织的官方网站），那么它所引用的网页也应该很重要。因此，得分较高的网页所引用的网页也应具有较高的得分，在搜索结果中的排名也应较高。
因此，将每个网页的初始得分设置为1，然后根据上述两个规则迭代更新每个网页的得分，直到每个网页的得分收敛，从而完成网页上的重要任务以简单而优雅的方式上网。性质的量化有效提高了搜索引擎的检索质量。
该算法具有简洁的定义形式和良好的数学性质。它提出后，受到了广泛关注。相关的计算形式后来被视为图结构中节点中心性的重要衡量标准，并应用于网络分析、信息检索、推荐系统、图神经网络，甚至化学、生物学、神经科学等领域。由于其重要性和影响力，它还被评为“数据挖掘十大算法”之一。
单点计算
作为研究中的一类重要问题，单点计算有望高效计算互联网上少量目标网页的得分。
从2004年开始，学者们开始尝试设计以次线性复杂度为目标的算法，即希望在不获取整个互联网结构的情况下完成计算。
这里之所以强调次线性时间复杂度，是因为现在的互联网规模太大了，而传统的迭代算法需要对整个网络进行多轮迭代计算，直到每个网页的指标收敛。在大数据时代，面对海量的网页，这种全局迭代算法的计算成本变得难以承受，对于问题的输出规模（即多个目标页面的分数）而言太大。
但直到2018年才首次提出用于单点计算的亚线性时间算法，而且算法结构非常复杂。计算的复杂度与问题的理论下界仍有一定差距，尚未达到理论最优。
中国人民大学的研究改进了单点问题的计算复杂度，将问题的计算复杂度优化至理论最优值，完全符合问题计算复杂度的理论下界。
更有趣的是，本文给出的最优复杂度结果是通过重新分析2016年WSDM论文中提出的算法BiPPR的计算复杂度而得到的。
具体来说，在单点计算中，常用的基本算子有两种：蒙特卡洛采样（Monte Carlo）和确定性概率反推（简称Push算法），分别于2005年和2007年提出。
其中，蒙特卡洛采样的思想是将单点计算转化为随机游走概率估计。这里的随机游走对应的是一个直观的动态过程：想象一个用户在网上冲浪，随机点击一个网页进行浏览。在浏览过程中，他可能会沿着网页中嵌入的链接跳转到网页，或者当您到达某个网页时，您可能会结束上网。
可以证明，互联网上任意网页t的得分等于用户在互联网上浏览网页时，浏览到网页t并在浏览网页t后结束上网的概率。
借助上述概率意义，蒙特卡洛采样方法的思想是：在互联网上重复多次网页浏览过程，记录网页被浏览的次数，浏览结束后网页浏览结束网页，并用这个数字占网页重复浏览过程的次数比例，作为网页得分的估计。
蒙特卡罗采样法简单直接，是单点计算的基本方法。然而，它的缺点是在估计小分数时会消耗大量时间。继蒙特卡罗采样方法之后，来自加州大学圣地亚哥分校、微软、康奈尔大学、波士顿大学的学者Borgs和Teng在2007年提出了另一种重要的单点计算方法：确定性概率反向预测（又称Push算法）。
确定性概率反推法可以理解为蒙特卡罗采样中随机游走的逆过程。它擅长估计较小的分数，补充了蒙特卡罗采样方法的优点。然而，确定性概率反演方法的计算复杂度分析始终缺乏有意义的结论。为此，Borgs、Borgs 和 Teng 在论文的最后也留下了悬而未决的问题，希望改进确定性概率反推方法。在计算复杂度分析方面取得了突破。
2016年，来自斯坦福大学和康奈尔大学的三位学者以及Goel在WSDM会议上提出了BiPPR算法。其核心思想是提供蒙特卡罗采样和确定性概率回溯这两种基本方法之一。巧妙的结合，兼顾了两者的优点。然而，由于确定性概率反演的计算复杂性缺乏有意义的结果，BiPPR算法的最坏情况计算复杂性也不清楚。
BiPPR方法提出后，研究人员多次尝试改进BiPPR算法。最有代表性的是来自罗马大学和意大利帕多瓦大学的三位学者在2018年FOCS会议上提出的算法。蒙特卡罗 采样和确定性反演方法都很复杂，并且对两种方法的组合进行了修改。最后得到计算复杂度结果，其中n和m分别是图节点和边的数量，Δ是图节点的最大出度。 ，这里表示隐藏了对数因子的大 O 表示法。该复杂度结果是次线性级别（即o(m+n)级别）的第一个单点计算复杂度结果。
然而，获得这种复杂度的算法结构非常复杂，与计算复杂度的下界有很大差距。 2023年，复杂度将进一步优化至100%，但算法结构仍然复杂，与理论下界仍有差距。
旧算法新解析：基础算法巧妙组合、简洁解析
中国人民大学今年的STOC论文重新分析了2016年提出的BiPPR算法的计算复杂度，证明其复杂度可以被限制在级别上。同时，人大论文还给出了与其复杂度上限相匹配的理论下界，证明其复杂度结果达到了理论最优。
本文的核心思想可以概括为两点：第一，蒙特卡洛采样和确定性概率反推两种基本方法优势互补。如果两者能够巧妙地结合起来，可以有效提高该问题的计算效率。其次，BiPPR算法提供了一种将蒙特卡洛采样和确定性概率推理相结合的良好方法。之前之所以没有得到理想的复杂度结论，主要是由于确定性概率反演方法的计算问题。复杂程度尚不清楚。
由此，人大STOC论文首先分析了确定性概率反推法在最坏情况下的计算复杂度，首次提供了有效的复杂度结果，同时证明了所得复杂度的最优性，从而回答了Liao、Borgs 和 Teng 在 2007 年提出了关于确定性概率反演方法的计算复杂性的开放性问题。
本文进一步将这种复杂度分析应用到BiPPR方法的计算复杂度分析中，最终解决了研究历史悠久的单点计算问题。
参考：
