最近我和所带本科毕业论文的基地班学生朱恒辉同学一道，阅读了发表在PLoS ONE 2011年第6期的文章《Leaders in Social Networks, the Delicious Case》，作者是Linyuan Lü, Yi-Cheng Zhang, Chi Ho Yeung, Tao Zhou，吕琳媛和周涛是我们很熟悉的国内复杂网络圈内的新秀和杰出青年，这几年他们在网络建模、人类行为动力学、社会推荐、链路预测等许多方面做出非常喜人的成绩，值得我们小组好好学习，也真让我觉得自己确实老了，跟不上了。

Google创始人Larry Page发明的PageRank算法是一个著名的排序算法，Google 的成功很大程度上决定于网页这个排序算法。它的基本思想是：从网页A指向网页B的链接被看作是页面A对页面B的支持投票，但是网页的“重要性”不能简单地看投票数(即链接数目)，而是要看是否有重要的网页链接，重要的网页链接你那么你就变得重要。有了这个想法，很容易建立网页重要性指标的数学模型，转化为一个列随机矩阵的1特征值对应的特征向量问题，特征向量的分量就是网页的“重要性”指标。

几年前我们读过SIAM REVIEW 上的一篇很好的文章《The $25,000,000,000 Eigenvector: The Linear Algebra behind Google》，有详细的数学分析。但是原始的PageRank模型仍然存在几个问题，其中一个问题是当网络有r个不连通的子网的时候，该网络的网页排序方式至少有r种，于是排序不唯一怎么办呢？

PageRank的办法是作素性修正，构造一个所有元素都为1/n的列随机矩阵，与原来的矩阵按加权（一般取0.15和0.85）叠加变成所谓的素矩阵 (primitive matrix),使得网络连通（解决了排序不唯一），并且仍然保持为列随机矩阵（保证了1特征值的存在）。这显然解决了排序不唯一的问题，但是新的矩阵全连接了，但是原来的结构也遭到很大的变形，排序会不会走样呢？吕琳媛他们提出的LeaderRank是这样做的，在已有节点外另加一个节点(ground node)，并且将它与已有的所有节点双向连接，于是得到N+1个节点的网络，这个新的网络是一个强连通的网络，再按照原始的PageRank算法计算得到原来N个节点的“重要性”排序。于是由于加入ground node后的图是一个连通图，排序的唯一性就解决了。下面考虑关于LeaderRank和PageRank素性修正的几个不同的地方。

首先，之前的素性修正的目的可以视为在PageRank的原始思想上加入一个假设，在网络用户沿着网页链接进行随机游走时，会有一定的很小的概率访问其他的任何一个网页。比方说在访问到某个网页时，下一个时间点不点击网页的链接，而是在地址栏上输入某个网站的网址或者其它形式访问其它网页。就像访问“科学网”的时候，猛然间想起自己邮箱里面可能有未查收的信件，于是点击了下自己收藏夹收藏的自己邮箱的链接。而吕琳媛他们提出的LeaderRank，可以理解成访问其它站点时候加了个延迟。比如在访问“科学网”的时候，想访问自己的邮箱，这时采取的方法是，在下一个时间点打开一个“ground node”，比如浏览器的空白页，然后再下一个时间点上在空白页上访问自己的邮箱。空白页起到了个ground node的作用，缓冲了访问非本网页链接的网页的过程，也就是本来一步的点击，变成两步完成，稍稍地强化了根据链接访问其他网站这一过程的重要性。这是本人认为的PageRank素性修正的蕴含假设和LeaderRank的蕴含假设的区别。

其次LeaderRank和PageRank素性修正对待这种访问非本网页链接的节点对待的方式不同。PageRank加入的素性修正是原先网络的随机状态转移矩阵和一个全部元素都是1/n的随机状态转移矩阵按照0.85:0.15的比例加权相加。这个比例可以粗略地看成根据链接访问网站和不根据链接随机访问网站两个过程的比例。素性修正视这个比例是一成不变的。但是LeaderRank就不同了，网页上连接数少的网页访问ground node的概率比网页上连接数大的网页访问ground node的概率要来得大。而在LeaderRank中，根据链接随机访问网站的过程是通过ground node的媒介完成的。于是这里就蕴含了，访问含有连接数大的网页之后随机访问其他网页的概率较小。这种自动根据网页上的链接个数来变化加权比例，从某种意义上看类似于自适应地增强了稳定性，而不是像素性修正比例一成不变那样。

最后，对于PageRank素性修正和LeaderRank在保留原始网络信息的区别。因为这两种排序都是对原始的PageRank产生的网络矩阵进行修正后，利用马尔可夫链式的迭代求得其终止状态，或者从数值上理解是用幂法求解最大特征值的特征根。这两种方法修正后的矩阵保留了原始矩阵什么信息呢？PageRank素性修正后，每个元素都加了小扰动，而LeaderRank修正的矩阵，原来图上没链接的地方，矩阵对应元素还是0，有链接的地方加了点小扰动，因此更多地保留了图的原来形态。

    吕琳媛他们的文章对两种排序算法的P.K.,从以下几个方面证实LeaderRank outperforms PageRank。（1）利用传染免疫的模型验证排序得到的最优节点的影响力；（2）排序对噪声(随机增加或者减少边)的抗干扰性；（3）对于人为增加垃圾页面指向某个页面企图操纵排序下，排序方法的鲁棒性。