Term Spam
其实从搜索引擎出现的那天起，spammer 和搜索引擎反作弊的斗法就没有停止过。Spammer 是这样一群人——试图通过搜索引擎算法的漏洞来提高目标页面（通常是一些广告页面或垃圾页面）的重要性，使目标页面在搜索结果中排名靠前。
现在假设 Google 单纯使用关键词占比评价页面重要性，而我想让我的博客在搜索结果中排名更靠前（最好排第一）。那么我可以这么做：在页面中加入一个隐藏的 html 元素（例如一个 div），然后其内容是“张洋”重复一万次。这样，搜索引擎在计算“张洋博客”的搜索结果时，我的博客关键词占比就会非常大，从而做到排名靠前的效果。更进一步，我甚至可以干扰别的关键词搜索结果，例如我知道现在欧洲杯很火热，我就在我博客的隐藏 div 里加一万个“欧洲杯”，当有用户搜索欧洲杯时，我的博客就能出现在搜索结果较靠前的位置。这种行为就叫做“Term Spam”。
早期搜索引擎深受这种作弊方法的困扰，加之基于关键词的评价算法本身也不甚合理，因此经常是搜出一堆质量低下的结果，用户体验大大打了折扣。而 Google 正是在这种背景下，提出了 PageRank 算法，并申请了专利保护。此举充分保护了当时相对弱小 Google，也使得 Google 一举成为全球首屈一指的搜索引擎。
PageRank 算法
上文已经说到，PageRank 的作用是评价网页的重要性，以此作为搜索结果的排序重要依据之一。实际中，为了抵御 spam，各个搜索引擎的具体排名算法是保密的，PageRank 的具体计算方法也不尽相同，本节介绍一种最简单的基于页面链接属性的 PageRank 算法。这个算法虽然简单，却能揭示 PageRank 的本质，实际上目前各大搜索引擎在计算 PageRank 时链接属性确实是重要度量指标之一。
简单 PageRank 计算
首先，我们将Web 做如下抽象：1、将每个网页抽象成一个节点；2、如果一个页面A有链接直接链向B，则存在一条有向边从A到B（多个相同链接不重复计算边）。因此，整个 Web 被抽象为一张有向图。
现在假设世界上只有四张网页：A、B、C、D，其抽象结构如下图：
显然这个图是强连通的（从任一节点出发都可以到达另外任何一个节点）。
然后需要用一种合适的数据结构表示页面间的连接关系。其实，PageRank 算法是基于这样一种背景思想：被用户访问越多的网页更可能质量越高，而用户在浏览网页时主要通过超链接进行页面跳转，因此我们需要通过分析超链接组成的拓扑结构来推算每个网页被访问频率的高低。最简单的，我们可以假设当一个用户停留在某页面时，跳转到页面上每个被链页面的概率是相同的。例如，上图中A页面链向B、C、D，所以一个用户从A跳转到B、C、D的概率各为1/3。设一共有N个网页，则可以组织这样一个N维矩阵：其中i行j列的值表示用户从页面j转到页面i的概率。这样一个矩阵叫做转移矩阵（Transition Matrix）。下面的转移矩阵M对应上图：
然后，设初始时每个页面的 rank 值为1/N，这里就是1/4。按A-D顺序将页面 rank 为向量v：
注意，M第一行分别是A、B、C和D转移到页面A的概率，而v的第一列分别是A、B、C和D当前的 rank，因此用M的第一行乘以v的第一列，所得结果就是页面A最新 rank 的合理估计，同理，Mv 的结果就分别代表A、B、C、D新 rank：
然后用M再乘以这个新的 rank 向量，又会产生一个更新的 rank 向量。迭代这个过程，可以证明v最终会收敛，即v约等于 Mv，此时计算停止。最终的v就是各个页面的 pagerank 值。例如上面的向量经过几步迭代后，大约收敛在（1/4, 1/4, 1/5, 1/4），这就是A、B、C、D最后的 pagerank。
处理 Dead Ends
上面的 PageRank 计算方法假设 Web 是强连通的，但实际上，Web 并不是强连通（甚至不是联通的）。下面看看 PageRank 算法如何处理一种叫做 Dead Ends 的情况。
所谓 Dead Ends，就是这样一类节点：它们不存在外链。看下面的图：
注意这里D页面不存在外链，是一个 Dead End。上面的算法之所以能成功收敛到非零值，很大程度依赖转移矩阵这样一个性质：每列的加和为1。而在这个图中，M第四列将全为0。在没有 Dead Ends 的情况下，每次迭代后向量v各项的和始终保持为1，而有了 Dead Ends，迭代结果将最终归零（要解释为什么会这样，需要一些矩阵论的知识，比较枯燥，此处略）。
处理 Dead Ends 的方法如下：迭代拿掉图中的 Dead Ends 节点及 Dead Ends 节点相关的边（之所以迭代拿掉是因为当目前的 Dead Ends 被拿掉后，可能会出现一批新的 Dead Ends），直到图中没有 Dead Ends。对剩下部分计算 rank，然后以拿掉 Dead Ends 逆向顺序反推 Dead Ends 的 rank。
以上图为例，首先拿到D和D相关的边，D被拿到后，C就变成了一个新的 Dead Ends，于是拿掉C，最终只剩A、B。此时可很容易算出A、B的 PageRank 均为1/2。然后我们需要反推 Dead Ends 的 rank，最后被拿掉的是C，可以看到C前置节点有A和B，而A和B的出度分别为 3 和2，因此C的 rank 为：1/2 * 1/3 + 1/2 * 1/2 = 5/12；最后，D的 rank 为：1/2 * 1/3 + 5/12 * 1 = 7/12。所以最终的 PageRank 为（1/2, 1/2, 5/12, 7/12）。
Spider Traps 及平滑处理
可以预见，如果把真实的 Web 组织成转移矩阵，那么这将是一个极为稀疏的矩阵，从矩阵论知识可以推断，极度稀疏的转移矩阵迭代相乘可能会使得向量v变得非常不平滑，即一些节点拥有很大的 rank，而大多数节点 rank 值接近0。而一种叫做 Spider Traps 节点的存在加剧了这种不平滑。例如下图：
D 有外链所以不是 Dead Ends，但是它只链向自己（注意链向自己也算外链，当然同时也是个内链）。这种节点叫做 Spider Trap，如果对这个图进行计算，会发现D的 rank 越来越大趋近于1，而其它节点 rank 值几乎归零。
为了克服这种由于矩阵稀疏性和 Spider Traps 带来的问题，需要对 PageRank 计算方法进行一个平滑处理，具体做法是加入“心灵转移（teleporting）”。所谓心灵转移，就是我们认为在任何一个页面浏览的用户都有可能以一个极小的概率瞬间转移到另外一个随机页面。当然，这两个页面可能不存在超链接，因此不可能真的直接转移过去，心灵转移只是为了算法需要而强加的一种纯数学意义的概率数字。
加入心灵转移后，向量迭代公式变为：
其中β往往被设置为一个比较小的参数（0.2或更小），e为N维单位向量，加入e的原因是这个公式的前半部分是向量，因此必须将β/N转为向量才能相加。这样，整个计算就变得平滑，因为每次迭代的结果除了依赖转移矩阵外，还依赖一个小概率的心灵转移。
以上图为例，转移矩阵M为：
设β为0.2，则加权后的M为：
因此：
如果按这个公式迭代算下去，会发现 Spider Traps 的效应被抑制了，从而每个页面都拥有一个合理的 pagerank。
Topic-Sensitive PageRank
其实上面的讨论我们回避了一个事实，那就是“网页重要性”其实没一个标准答案，对于不同的用户，甚至有很大的差别。例如，当搜索“苹果”时，一个数码爱好者可能是想要看 iphone 的信息，一个果农可能是想看苹果的价格走势和种植技巧，而一个小朋友可能在找苹果的简笔画。理想情况下，应该为每个用户维护一套专用向量，但面对海量用户这种方法显然不可行。所以搜索引擎一般会选择一种称为 Topic-Sensitive 的折中方案。Topic-Sensitive PageRank 的做法是预定义几个话题类别，例如体育、娱乐、科技等等，为每个话题单独维护一个向量，然后想办法关联用户的话题倾向，根据用户的话题倾向排序结果。
联系客服
