PageRank算法
上文已经说到，PageRank的作用是评价网页的重要性，以此作为搜索结果的排序重要依据之一。实际中，为了抵御spam，各个搜索引擎的具体排名算法是保密的，PageRank的具体计算方法也不尽相同，本节介绍一种最简单的基于页面链接属性的PageRank算法。这个算法虽然简单，却能揭示PageRank的本质，实际上目前各大搜索引擎在计算PageRank时链接属性确实是重要度量指标之一。
简单PageRank计算
首先，我们将Web做如下抽象：1、将每个网页抽象成一个节点；2、如果一个页面A有链接直接链向B，则存在一条有向边从A到B（多个相同链接不重复计算边）。

显然这个图是强连通的（从任一节点出发都可以到达另外任何一个节点）。
然后需要用一种合适的数据结构表示页面间的连接关系。其实，PageRank算法是基于这样一种背景思想：被用户访问越多的网页更可能质量越高，而用户在浏览网页时主要通过超链接进行页面跳转，因此我们需要通过分析超链接组成的拓扑结构来推算每个网页被访问频率的高低。最简单的，我们可以假设当一个用户停留在某页面时，跳转到页面上每个被链页面的概率是相同的。例如，上图中A页面链向B、C、D，所以一个用户从A跳转到B、C、D的概率各为1/3。设一共有N个网页，则可以组织这样一个N维矩阵：其中i行j列的值表示用户从页面j转到页面i的概率。这样一个矩阵叫做转移矩阵（Transition Matrix）。 

然后，设初始时每个页面的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为： 

因此： 如果按这个公式迭代算下去，会发现Spider Traps的效应被抑制了，从而每个页面都拥有一个合理的pagerank。
Topic-Sensitive PageRank
其实上面的讨论我们回避了一个事实，那就是“网页重要性”其实没一个标准答案，对于不同的用户，甚至有很大的差别。例如，当搜索“苹果”时，一个数码爱好者可能是想要看iphone的信息，一个果农可能是想看苹果的价格走势和种植技巧，而一个小朋友可能在找苹果的简笔画。理想情况下，应该为每个用户维护一套专用向量，但面对海量用户这种方法显然不可行。所以搜索引擎一般会选择一种称为Topic-Sensitive的折中方案。Topic-Sensitive PageRank的做法是预定义几个话题类别，例如体育、娱乐、科技等等，为每个话题单独维护一个向量，然后想办法关联用户的话题倾向，根据用户的话题倾向排序结果。
Topic-Sensitive PageRank分为以下几步：
1、确定话题分类。
一般来说，可以参考Open Directory（DMOZ）的一级话题类别作为topic。目前DMOZ的一级topic有：Arts（艺术）、Business（商务）、Computers（计算机）、Games（游戏）、Health（医疗健康）、Home（居家）、Kids and Teens（儿童）、News（新闻）、Recreation（娱乐修养）、Reference（参考）、Regional（地域）、Science（科技）、Shopping（购物）、Society（人文社会）、Sports（体育）。
2、网页topic归属。
这一步需要将每个页面归入最合适的分类，具体归类有很多算法，例如可以使用TF-IDF基于词素归类，也可以聚类后人工归类，具体不再展开。这一步最终的结果是每个网页被归到其中一个topic。
3、分topic向量计算。
在Topic-Sensitive PageRank中，向量迭代公式为

首先是单位向量e变为了s。s是这样一个向量：对于某topic的s，如果网页k在此topic中，则s中第k个元素为1，否则为0。注意对于每一个topic都有一个不同的s。而|s|表示s中1的数量。
还是以上面的四张页面为例，假设页面A归为Arts，B归为Computers，C归为Computers，D归为Sports。那么对于Computers这个topic，s就是： 

而|s|=2。因此，迭代公式为：

最后算出的向量就是Computers这个topic的rank。如果实际计算一下，会发现B、C页在这个topic下的权重相比上面非Topic-Sensitive的rank会升高，这说明如果用户是一个倾向于Computers topic的人（例如程序员），那么在给他呈现的结果中B、C会更重要，因此可能排名更靠前。
4、确定用户topic倾向。
最后一步就是在用户提交搜索时，确定用户的topic倾向，以选择合适的rank向量。主要方法有两种，一种是列出所有topic让用户自己选择感兴趣的项目，这种方法在一些社交问答网站注册时经常使用；另外一种方法就是通过某种手段（如cookie跟踪）跟踪用户的行为，进行数据分析判断用户的倾向，这本身也是一个很有意思的话题，按时这个话题超出本文的范畴，不再展开细说。
针对PageRank的Spam攻击与反作弊
上文说过，Spammer和搜索引擎反作弊工程师的斗法从来就没停止过。实际上，只要是算法，就一定有spam方法，不存在无懈可击的排名算法。下面看一下针对PageRank的spam。
Link Spam
回到文章开头的例子，如果我想让我的博客在搜索“张洋 博客”时排名靠前，显然在PageRank算法下靠Term Spam是无法实现的。不过既然我明白了PageRank主要靠内链数计算页面权重，那么我是不是可以考虑建立很多空架子网站，让这些网站都链接到我博客首页，这样是不是可以提高我博客首页的PageRank？很不幸，这种方法行不通。再看下PageRank算法，一个页面会将权重均匀散播给被链接网站，所以除了内链数外，上游页面的权重也很重要。而我那些空架子网站本身就没啥权重，所以来自它们的内链并不能起到提高我博客首页PageRank的作用，这样只是自娱自乐而已。
所以，Spam PageRank的关键就在于想办法增加一些高权重页面的内链。下面具体看一下Link Spam怎么做。
首先明确将页面分为几个类型：
1、目标页
目标页是spammer要提高rank的页面，这里就是我的博客首页。
2、支持页
支持页是spammer能完全控制的页面，例如spammer自己建立的站点中页面，这里就是我上文所谓的空架子页面。
3、可达页
可达页是spammer无法完全控制，但是可以有接口供spammer发布链接的页面，例如天涯社区、新浪博客等等这种用户可发帖的社区或博客站。
4、不可达页
这是那些spammer完全无法发布链接的网站，例如政府网站、百度首页等等。
作为一个spammer，我能利用的资源就是支持页和可达页。上面说过，单纯通过支持页是没有办法spam的，因此我要做的第一件事情就是尽量找一些rank较高的可达页去加上对我博客首页的链接。例如我可以去天涯、猫扑等地方回个这样的贴：“楼主的帖子很不错！精彩内容：http://codinglabs.org”。我想大家一定在各大社区没少见这种帖子，这就是有人在做spam。
然后，再通过大量的支持页放大rank，具体做法是让每个支持页和目标页互链，且每个支持页只有一条链接。
这样一个结构叫做Spam Farm，其拓扑图如下： 
 
其中T是目标页，A是可达页，S是支持页。下面计算一下link spam的效果。
设T的总rank为y，则y由三部分组成：
1、可达页的rank贡献，设为x。
2、心灵转移的贡献，为β/n。其中n为全部网页的数量，β为转移参数。
3、支持页的贡献：
设有m个支持页，因为每个支持页只和T有链接，所以可以算出每个支持页的rank为：

则支持页贡献的全部rank为：

因此可以得到：

由于相对β，n非常巨大，所以可以认为β/n近似于0。 简化后的方程为：

解方程得：

假设β为0.2，则1/(2β-β^2) = 2.77则这个spam farm可以将x约放大2.7倍。因此如果起到不错的spam效果。

Link Spam反作弊
针对spammer的link spam行为，搜索引擎的反作弊工程师需要想办法检测这种行为，一般来说有两类方法检测link spam。
网络拓扑分析
一种方法是通过对网页的图拓扑结构分析找出可能存在的spam farm。但是随着Web规模越来越大，这种方法非常困难，因为图的特定结构查找是时间复杂度非常高的一个算法，不可能完全靠这种方法反作弊。
TrustRank
更可能的一种反作弊方法是叫做一种TrustRank的方法。
说起来TrustRank其实数学本质上就是Topic-Sensitive Rank，只不过这里定义了一个“可信网页”的虚拟topic。所谓可信网页就是上文说到的不可达页，或者说没法spam的页面。例如政府网站（被黑了的不算）、新浪、网易门户首页等等。一般是通过人力或者其它什么方式选择出一个“可信网页”集合，组成一个topic，然后通过上文的Topic-Sensitive算法对这个topic进行rank计算，结果叫做TrustRank。
TrustRank的思想很直观：如果一个页面的普通rank远高于可信网页的topic rank，则很可能这个页面被spam了。
设一个页面普通rank为P，TrustRank为T，则定义网页的Spam Mass为：(P – T)/P。
Spam Mass越大，说明此页面为spam目标页的可能性越大。