本文将介绍PageRank算法的相关内容，具体如下：
1. 算法来源
这个要从搜索引擎的发展讲起。最早的搜索引擎采用的是 分类目录 的方法，即通过人工进行网页分类并整理出高质量的网站。那时 Yahoo 和国内的 hao123 就是使用的这种方法。
后来网页越来越多，人工分类已经不现实了。搜索引擎进入了 文本检索 的时代，即计算用户查询关键词与网页内容的相关程度来返回搜索结果。这种方法突破了数量的限制，但是搜索结果不是很好。因为总有某些网页来回地倒腾某些关键词使自己的搜索排名靠前。
于是我们的主角要登场了。没错，谷歌的两位创始人，当时还是美国斯坦福大学 (Stanford University) 研究生的佩奇 (Larry Page) 和布林 (Sergey Brin) 开始了对网页排序问题的研究。他们的借鉴了学术界评判学术论文重要性的通用方法， 那就是看论文的引用次数。由此想到网页的重要性也可以根据这种方法来评价。于是PageRank的核心思想就诞生了，非常简单：
如果一个网页被很多其他网页链接到的话说明这个网页比较重要，也就是PageRank值会相对较高
如果一个PageRank值很高的网页链接到一个其他的网页，那么被链接到的网页的PageRank值会相应地因此而提高
就如下图所示（一个概念图）:
2. 算法原理
PageRank算法总的来说就是预先给每个网页一个PR值（下面用PR值指代PageRank值），由于PR值物理意义上为一个网页被访问概率，所以一般是1N，其中N为网页总数。另外，一般情况下，所有网页的PR值的总和为1。如果不为1的话也不是不行，最后算出来的不同网页之间PR值的大小关系仍然是正确的，只是不能直接地反映概率了。
预先给定PR值后，通过下面的算法不断迭代，直至达到平稳分布为止。
互联网中的众多网页可以看作一个有向图。下图是一个简单的例子：
这时A的PR值就可以表示为：
PR(A)=PR(B)+PR(C)
然而图中除了C之外，B和D都不止有一条出链，所以上面的计算式并不准确。想象一个用户现在在浏览B网页，那么下一步他打开A网页还是D网页在统计上应该是相同概率的。所以A的PR值应该表述为：
PR(A)=PR(B)2+PR(C)1
互联网中不乏一些没有出链的网页，如下图：
图中的C网页没有出链，对其他网页没有PR值的贡献，我们不喜欢这种自私的网页（其实是为了满足 Markov 链的收敛性），于是设定其对所有的网页（包括它自己）都有出链，则此图中A的PR值可表示为：
PR(A)=PR(B)2+PR(C)4
然而我们再考虑一种情况：互联网中一个网页只有对自己的出链，或者几个网页的出链形成一个循环圈。那么在不断地迭代过程中，这一个或几个网页的PR值将只增不减，显然不合理。如下图中的C网页就是刚刚说的只有对自己的出链的网页：
为了解决这个问题。我们想象一个随机浏览网页的人，当他到达C网页后，显然不会傻傻地一直被C网页的小把戏困住。我们假定他有一个确定的概率会输入网址直接跳转到一个随机的网页，并且跳转到每个网页的概率是一样的。于是则此图中A的PR值可表示为：
PR(A)=α(PR(B)2)+(1-α)4
在一般情况下，一个网页的PR值计算如下：
PR(pi)=α∑pj∈MpiPR(pj)L(pj)+(1-α)N
其中Mpi是所有对pi网页有出链的网页集合，L(pj)是网页pj的出链数目，N是网页总数，α一般取0.85。
根据上面的公式，我们可以计算每个网页的PR值，在不断迭代趋于平稳的时候，即为最终结果。具体怎样算是趋于平稳，我们在下面的PR值计算方法部分再做解释。
3. 算法证明
limn→∞Pn是否存在？
如果极限存在，那么它是否与P0的选取无关？
PageRank算法的正确性证明包括上面两点。为了方便证明，我们先将PR值的计算方法转换一下。
仍然拿刚刚的例子来说
我们可以用一个矩阵来表示这张图的出链入链关系，Sij=0表示j网页没有对i网页的出链：
S=??????01/31/31/31/2001/2001001/21/20??????
取e为所有分量都为 1 的列向量,接着定义矩阵：
A=αS+(1-α)NeeT
则PR值的计算如下，其中Pn为第n次迭代时各网页PR值组成的列向量：
于是计算PR值的过程就变成了一个 Markov 过程，那么PageRank算法的证明也就转为证明 Markov 过程的收敛性证明：如果这个 Markov 过程收敛，那么limn→∞Pn存在，且与P0的选取无关。
若一个 Markov 过程收敛，那么它的状态转移矩阵A需要满足：
A为随机矩阵。
A是不可约的。
A是非周期的。
先看第一点，随机矩阵又叫概率矩阵或 Markov 矩阵，满足以下条件：
令aij为矩阵A中第i行第j列的元素，则?i=1…n,j=1…n,aij≥0,且?i=1…n,∑j=1naij=1
显然我们的A矩阵所有元素都大于等于0，并且每一列的元素和都为1。
第二点，不可约矩阵：方针A是不可约的当且仅当与A对应的有向图是强联通的。有向图G=(V,E)是强联通的当且仅当对每一对节点对u,v∈V，存在从u到v的路径。因为我们在之前设定用户在浏览页面的时候有确定概率通过输入网址的方式访问一个随机网页，所以A矩阵同样满足不可约的要求。
第三点，要求A是非周期的。所谓周期性，体现在Markov链的周期性上。即若A是周期性的，那么这个Markov链的状态就是周期性变化的。因为A是素矩阵（素矩阵指自身的某个次幂为正矩阵的矩阵），所以A是非周期的。
至此，我们证明了PageRank算法的正确性。
4. PR值计算方法
4.1 幂迭代法
首先给每个页面赋予随机的PR值，然后通过Pn+1=APn不断地迭代PR值。当满足下面的不等式后迭代结束，获得所有页面的PR值：
|Pn+1-Pn|&?
4.2 特征值法
当上面提到的Markov链收敛时，必有：
P=AP=>P为矩阵A特征值1对应的特征向量（随机矩阵必有特征值1，且其特征向量所有分量全为正或全为负）
4.3 代数法
相似的，当上面提到的Markov链收敛时，必有：
P=AP=>P=?αS+(1-α)NeeT?P又∵e为所有分量都为1的列向量，P的所有分量之和为1=>P=αSP+(1-α)Ne=>(eeT-αS)P=(1-α)Ne=>P=(eeT-αS)-1(1-α)Ne
5. 算法实现
5.1 基于迭代法的简单实现
用python实现，需要先安装python-graph-core。
from pygraph.classes.digraph import digraph
class PRIterator:
__doc__ = '''计算一张图中的PR值'''
def __init__(self, dg):
self.damping_factor = 0.85
self.max_iterations = 100
self.min_delta = 0.00001
self.graph = dg
def page_rank(self):
for node in self.graph.nodes():
if len(self.graph.neighbors(node)) == 0:
for node2 in self.graph.nodes():
digraph.add_edge(self.graph, (node, node2))
nodes = self.graph.nodes()
graph_size = len(nodes)
if graph_size == 0:
page_rank = dict.fromkeys(nodes, 1.0 / graph_size)
damping_value = (1.0 - self.damping_factor) / graph_size
flag = False
for i in range(self.max_iterations):
change = 0
for node in nodes:
for incident_page in self.graph.incidents(node):
rank += self.damping_factor * (page_rank[incident_page] / len(self.graph.neighbors(incident_page)))
rank += damping_value
change += abs(page_rank[node] - rank)
page_rank[node] = rank
print("This is NO.%s iteration" % (i + 1))
print(page_rank)
if change & self.min_delta:
flag = True
print("finished in %s iterations!" % node)
print("finished out of 100 iterations!")
return page_rank
if __name__ == '__main__':
dg = digraph()
dg.add_nodes(["A", "B", "C", "D", "E"])
dg.add_edge(("A", "B"))
dg.add_edge(("A", "C"))
dg.add_edge(("A", "D"))
dg.add_edge(("B", "D"))
dg.add_edge(("C", "E"))
dg.add_edge(("D", "E"))
dg.add_edge(("B", "E"))
dg.add_edge(("E", "A"))
pr = PRIterator(dg)
page_ranks = pr.page_rank()
print("The final page rank is\n", page_ranks)
运行结果：
finished in 36 iterations!
The final page rank is
{'A': 0.0821, 'C': 0.68992, 'B': 0.68992, 'E': 0.34013, 'D': 0.15852}
程序中给出的网页之间的关系一开始如下：
迭代结束后如下：
上面的代码的初版有一个错误，我感觉对于PageRank的理解比较有价值，遂在这里贴出链接：。
5.2 MapReduce实现
作为Hadoop（分布式系统平台）的核心模块之一，MapReduce是一个高效的分布式计算框架。下面首先简要介绍一下MapReduce原理。
所谓MapReduce，就是两种操作：Mapping和Reducing。
映射（Mapping）：对集合里的每个目标应用同一个操作。
化简（Reducing ）：遍历Mapping返回的集合中的元素来返回一个综合的结果。
就拿一个最经典的例子来说：现在有3个文本文件，需要统计出所有出现过的词的词频。传统的想法是让一个人顺序阅读这3个文件，每遇到一个单词，就看之前有没有遇到过。遇到过的话词频加一：（单词，N + 1），否则就记录新词，词频为一：（单词，1）。
MapReduce方式为：把这3个文件分给3个人，每个人阅读一份文件。每当遇到一个单词，就记录这个单词：（单词，1）（不管之前有没有遇到过这个单词，也就是说可能出现多个相同单词的记录）。之后将再派一个人把相同单词的记录相加，即可得到最终结果。
词频统计的具体实现可见。
下面是使用MapReduce实现PageRank的具体代码。首先是通用的map与reduce模块。若是感觉理解有困难，可以先看看词频统计的实现代码，其中同样使用了下面的模块：
class MapReduce:
__doc__ = '''提供map_reduce功能'''
@staticmethod
def map_reduce(i, mapper, reducer):
map_reduce方法
:param i: 需要MapReduce的集合
:param mapper: 自定义mapper方法
:param reducer: 自定义reducer方法
:return: 以自定义reducer方法的返回值为元素的一个列表
intermediate = []
for (key, value) in i.items():
intermediate.extend(mapper(key, value))
groups = {}
for key, group in itertools.groupby(sorted(intermediate, key=lambda im: im[0]), key=lambda x: x[0]):
groups[key] = [y for x, y in group]
return [reducer(intermediate_key, groups[intermediate_key]) for intermediate_key in groups]
接着是计算PR值的类，其中实现了用于计算PR值的mapper和reducer：
class PRMapReduce:
__doc__ = '''计算PR值'''
def __init__(self, dg):
self.damping_factor = 0.85
self.max_iterations = 100
self.min_delta = 0.00001
self.num_of_pages = len(dg.nodes())
self.graph = {}
for node in dg.nodes():
self.graph[node] = [1.0 / self.num_of_pages, len(dg.neighbors(node)), dg.neighbors(node)]
def ip_mapper(self, input_key, input_value):
看一个网页是否有出链，返回值中的 1 没有什么物理含义，只是为了在
map_reduce中的groups字典的key只有1，对应的value为所有的悬挂网页
:param input_key: 网页名，如 A
:param input_value: self.graph[input_key]
:return: 如果没有出链，即悬挂网页，那么就返回[(1,这个网页的PR值)]；否则就返回[]
if input_value[1] == 0:
return [(1, input_value[0])]
def ip_reducer(self, input_key, input_value_list):
计算所有悬挂网页的PR值之和
:param input_key: 根据ip_mapper的返回值来看，这个input_key就是:1
:param input_value_list: 所有悬挂网页的PR值
:return: 所有悬挂网页的PR值之和
return sum(input_value_list)
def pr_mapper(self, input_key, input_value):
mapper方法
:param input_key: 网页名，如 A
:param input_value: self.graph[input_key]，即这个网页的相关信息
:return: [(网页名, 0.0), (出链网页1, 出链网页1分得的PR值), (出链网页2, 出链网页2分得的PR值)...]
return [(input_key, 0.0)] + [(out_link, input_value[0] / input_value[1]) for out_link in input_value[2]]
def pr_reducer_inter(self, intermediate_key, intermediate_value_list, dp):
reducer方法
:param intermediate_key: 网页名，如 A
:param intermediate_value_list: A所有分得的PR值的列表:[0.0,分得的PR值,分得的PR值...]
:param dp: 所有悬挂网页的PR值之和
:return: (网页名，计算所得的PR值)
return (intermediate_key,
self.damping_factor * sum(intermediate_value_list) +
self.damping_factor * dp / self.num_of_pages +
(1.0 - self.damping_factor) / self.num_of_pages)
def page_rank(self):
计算PR值，每次迭代都需要两次调用MapReduce。一次是计算悬挂网页PR值之和，一次
是计算所有网页的PR值
:return: self.graph，其中的PR值已经计算好
iteration = 1
change = 1
while change & self.min_delta:
print("Iteration: " + str(iteration))
dangling_list = MapReduce.map_reduce(self.graph, self.ip_mapper, self.ip_reducer)
if dangling_list:
dp = dangling_list[0]
new_pr = MapReduce.map_reduce(self.graph, self.pr_mapper, lambda x, y: self.pr_reducer_inter(x, y, dp))
change = sum([abs(new_pr[i][1] - self.graph[new_pr[i][0]][0]) for i in range(self.num_of_pages)])
print("Change: " + str(change))
for i in range(self.num_of_pages):
self.graph[new_pr[i][0]][0] = new_pr[i][1]
iteration += 1
return self.graph
最后是测试部分，我使用了python的digraph创建了一个有向图，并调用上面的方法来计算PR值：
if __name__ == '__main__':
dg = digraph()
dg.add_nodes(["A", "B", "C", "D", "E"])
dg.add_edge(("A", "B"))
dg.add_edge(("A", "C"))
dg.add_edge(("A", "D"))
dg.add_edge(("B", "D"))
dg.add_edge(("C", "E"))
dg.add_edge(("D", "E"))
dg.add_edge(("B", "E"))
dg.add_edge(("E", "A"))
pr = PRMapReduce(dg)
page_ranks = pr.page_rank()
print("The final page rank is")
for key, value in page_ranks.items():
print(key + " : ", value[0])
附上运行结果：
Iteration: 44
Change: 1.069e-05
Iteration: 45
Change: 1.2694e-05
Iteration: 46
Change: 7.62e-06
The final page rank is
以上便是PageRank的MapReduce实现。代码中的注释较为详细，理解应该不难。
6. PageRank算法的缺点
这是一个天才的算法，原理简单但效果惊人。然而，PageRank算法还是有一些弊端。
第一，没有区分站内导航链接。很多网站的首页都有很多对站内其他页面的链接，称为站内导航链接。这些链接与不同网站之间的链接相比，肯定是后者更能体现PageRank值的传递关系。
第二，没有过滤广告链接和功能链接（例如常见的“分享到微博”）。这些链接通常没有什么实际价值，前者链接到广告页面，后者常常链接到某个社交网站首页。
第三，对新网页不友好。一个新网页的一般入链相对较少，即使它的内容的质量很高，要成为一个高PR值的页面仍需要很长时间的推广。
针对PageRank算法的缺点，有人提出了TrustRank算法。其最初来自于2004年斯坦福大学和雅虎的一项联合研究，用来检测垃圾网站。TrustRank算法的工作原理：先人工去识别高质量的页面(即“种子”页面)，那么由“种子”页面指向的页面也可能是高质量页面，即其TR值也高，与“种子”页面的链接越远，页面的TR值越低。“种子”页面可选出链数较多的网页，也可选PR值较高的网站。
TrustRank算法给出每个网页的TR值。将PR值与TR值结合起来，可以更准确地判断网页的重要性。
7. 写在最后
谷歌用PR值来划分网页的等级，有0~10级，一般4级以上的都是比较好的网页了。谷歌自己PR值为9，百度也是9，的PR值则为7。
如今PR值虽不如以前重要了（没有区分页面内的导航链接、广告链接和功能链接导致PR值本身能够反映出的网页价值不精确，并且对新网页不友好），但是流量交易里PR值还是个很重要的参考因素。
最后，有一个图形化网站提供PageRank过程的动态图：。
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：1530次
排名：千里之外PageRank与社交网络模型评估（1-3）
SNS社交网络在近几年流行起来，并呈现出火爆的增长趋势。在仿制国外Facebook、twitter等成功先例的基础上，国内的人人网、新浪微博等一系列社交网络正风生水起。
这些社交网站表面上看起来十分普通和其他网站别无二致，但我们可以研究它们背后更深层次的数学原理，从而更有利于推广营销。在后面的分析中，我会分别举例，大家就会明白实际中的应用价值。
我们需要考虑的是怎样度量一个网络。网络其实就是一张图，图中有各个节点，节点连接起来，形成边。在社交网络中，每个人就是一个节点，人们通过好友关系相互连接。节点是有权重的，就像人具有影响力一样。
给你一张网络拓扑图，你怎样挖掘这张图所蕴含的信息呢？你怎样知道图中哪一个节点是最重要的？事实上有很多方法，我们自己也可以定义度量的标准。经常用到的有Degree
Centrality，Eigenvector Centrality，Katz
Centrality，PageRank，Closeness Centrality，Betweenness
Centrality，Transitivity……它们从简单到复杂，从偏重某个属性到综合考虑，很多都在现实中合理地使用着，例如PageRank就是Google使用的网页排名方法。
1. Degree Centrality（节点度）
这是对网络最为简单直白的一种度量：仅仅统计每个节点有多少边。它的现实意义在于有更多边的节点具有更大的连接性，就像有更多好友的人具有更大的影响力。例如对一个产品做推广营销，我们发放免费的试用样品给消费者，如果消费者满意他们就会购买，并且推荐给自己的朋友也去购买。这就是口碑影响力。作为厂家，我们当然希望将样品发放给更具影响力的人，因为他们的一句赞美会传递到更多的节点上，为我们带来更多的潜在客户。我们知道，图分为有向图和无向图，他们的区别在于节点之间的联系是否是双向的。例如Facebook或者人人网中的好友关系，就是一个无向图，你是我的好友那么我也是你的好友；而twitter或者新浪微博则是一个有向图，因为我“关注”（follow）某些人，又有另外一些人“关注”我，这是一个从一个节点指向另一个节点的关系，不具有可逆性。我们在讨论Degree
Centrality时，对于有向图来说，其实有in-degree centrality和out-degree
centrality两种。例如在微博上很多人关注了李开复，也就是说有很多节点指向他，那么李开复就具有很高的in-degree
centrality.
但是要小心，in-degree高的节点不一定是最有价值的，例如在论文参考文献引用中，一篇文章的in-degree很高表示很多人引用了这篇论文。这篇文章可能提出了一个有价值的研究问题，但是却犯了明显的错误，于是大家在写这个研究方向的论文时都会说：“快去围观这篇文章，作者太SB了，哈哈哈哈……”
我们希望通过Degree Centrality来找出最有影响力的节点们。问题来了，想要获得具有Degree
Centrality最高的前10个节点，我们需要知道整张图的结构才行。从数学上讲，即需要得到图的邻接矩阵A，对于A中的每一行统计有多少个1，最后进行排序取前k个即可得到Degree
Centrality值最高的前k个节点。这在实际中并不可行，你并不是Facebook的所有者或者人人网的管理员，你怎么知道整个社会网络里谁的好友更多？
2. Eigenvector Centrality（特征向量）
这是对Degree Centrality的一种改进版。我们希望得到节点重要性的估值，但什么是重要性？什么是影响力？在Degree
Centrality中，所有的邻居节点都是平等的。而在实际情况中，不同的邻居节点可能会有不同的价值。例如我有10个好友，他们都是普通人，而如果有一个人他也有10个好友，但是他的好友都是李嘉诚巴菲特奥巴马们，显然，我比不上他，自惭形秽了。
为此我们建立另一种模型：给邻居节点打分，高分的邻居会给予我更多积极的影响，使得我的得分也升高。设xi(t)为节点i在t时刻的centrality评估值（得分），centrality值越高说明这个节点越重要。则
或者表示为矩阵形式
其中A为图的邻接矩阵。不知道邻接矩阵？回去复习线性代数离散数学和数据结构吧……
公式（1）比较好理解。基本思想其实就是说，节点j为节点i的邻居节点（我所说的邻居意思就是他们有边相连），在t-1时刻，我们对j叠加求和，意思就是统计节点i的所有邻居节点的centrality值，然后累加，就是t时刻节点i的centrality值。这个公式对所有节点有效，如果我的邻居们的centrality值改变了，我的值也会改变，所以这是一个不断迭代的过程，直到最后所有节点的值在一个阈值内进行可忽略的波动，即收敛。
第二个公式x(0)是0时刻初始化时所有节点的centrality值，它是一个数组。而
不断迭代就可以得到公式（2）了。
于是x(0)可以看作是A的特征向量Vi的线性组合，我们可以选取合适的ci使得等式
结合（2）（3）两个式子，我们得到
其中ki为矩阵A的特征值，k1为特征值中的最大值。
当k&1时，&，于是当&&时，&，或者直接表示为
这就是eigenvector
centrality。我们如果得到图A的邻接矩阵的特征向量，那么这个向量x就是所有节点的eigenvector
centrality值。我们只需解方程（5）即可。它的一个明显的属性就是，xi即节点i的eigenvector
centrality，与该节点所有邻居的eigenvector centrality之和成正比。即
所以，这正解决了我们之前的问题，它将我们邻居的重要性施加到我们自己身上。有几种情况会使得xi的值很大，一是节点有很多邻居，二是它有一个重要邻居（该邻居拥有高eigenvector
centrality值），或者以上两种情况同时存在。
同样的问题在这里也存在，那就是我们必须知道图的邻接矩阵，也就是整个网络的拓扑结构。如果网络中有100万个节点，我们生成一个100万&100万的矩阵也是困难的。另外，还有可能出现下面的情况
这是一个有向图，注意节点A，它没有in-degree，也就是说没有其他节点可以影响到它的centrality值。假如A的centrality值是0，那么它对它的3个邻居的贡献也为0，其中最上面的那个邻居只有A对它施加影响，于是它的centrality值也为0，最后我们一步步地推断，会发现整个图所有节点的centrality值都是0，也就是说图的邻接矩阵A=0.这不是我们预想的那样，因为如果我们希望对网页做PageRank，这将导致所有页面的PageRank值都一样，没法做排名了。
上边提到两种网络模型，都有着这样那样的缺陷。下面我们继续来改善建模。
3. Katz Centrality
Katz Centrality解决了之前的问题。它的原理与eigenvector
centrality差不多，只是我们给每一个节点提供一个初始化的centrality值β，即对式（6）做简单改变：
α 和 β 都是正常数。
使用矩阵表达式，我们得到：
我们只关心centrality值的相对性，也就是说不管你的centrality值是10还是100，我们只关注你的centrality值是不是大于我的centrality值，因为我们希望找到centrality值最大的前10个节点，目的是做排名。于是β可以设置为1，于是Katz
Centrality表达为：
事实上α和β的比值体现了对邻居节点centrality值的侧重，如果α=0那么所有的节点的centrality值都是β=1了，完全不受邻居的影响了。所以说这个公式更具有普遍性，这就是数学之美。
需要注意的是α不可以太大，当 &&会导致&，于是&无法收敛。所以有&.
要计算Katz centrality，就要做逆矩阵运算 ，直接计算的复杂度为O(n3)。我们可以用迭代法
4. PageRank
centrality的一个缺陷就是，一个拥有高centrality值的节点会将它的高影响力传递给它的所有邻居，这在实际生活中可能并不恰当。比如说Google的网页有很高的centrality值，同时Google也链接了海量的页面。如果Google的网页链接到了我的网页，那我的网页作为一个无名小卒centrality值岂不是有可能比Google还高？我们希望Katz
centrality能够由节点的out-degree稀释，或者说我的centrality值能平均分给我的邻居，而不是给每个邻居都得到我的整个centrality值。用数学语言表达为
对比公式（7）就很容易理解这里对Katz centrality做的修改了。
对于没有外链的节点（例如很多链接指向了一张图片，但图片是没有out-degree指向别处的），将其&值设为1.我们将式（12）写为矩阵形式：
其中D是对角矩阵，&.同样设β=1，上式可以变形为
这就是著名的PageRank算法。
同样，α的取值也是有范围的，它应该小于AD-1最大的特征值的倒数。对于无向图来说，这个值是1，对于有向图来说就不一定了。Google的搜索引擎将α设为0.85。同样，要执行这个算法，我们需要知道整个图的拓扑结构。
5. HITS算法
与类似，HITS也是在网络建模和权重排名中比较经典的算法。
有的时候我们希望把高centrality值赋予那些链接了很多重要节点的节点，例如综述性的学术论文引用了该研究领域内的大量重要论文，于是这篇综述也被认为很有价值。因为即使这篇论文没有为该科研领域做出什么突破，但它总结了已有成果，告诉大家去哪里找做出了突出贡献的论文。
于是我们拥有两种节点：authorities（权威型）的节点包含了具有贡献的原创信息，hubs（枢纽型）节点总结了很多信息，指向了很多authorities节点。Kleinberg是康奈尔大学一位十分牛B的年轻教授（70后年轻有为啊！），他提出了hyperlink-induced
topic search (HITS)算法来量化计算authority centrality和hubs
centrality。
在HITS中对于某个节点i，xi用来表示authority
centrality，yi用来表示hubs
centrality。每个节点既有authority属性又有hubs属性。节点若有高xi值则该节点被很多其他hub节点关注，如论文被大量引用、微博有很多粉丝。节点若有高yi值则该节点指向了很多其他authority节点，例如一篇综述论文，又例如这样的网址导航站点（理解百度为什么要收购hao123了吧）。
用数学语言描述如下：
或者矩阵表达式
合并演化得到
这意味着authority centrality为AAT的特征向量，而hubs
centrality为ATA的特征向量。有趣的是AAT和ATA拥有相同的特征值λ，大家可以自行证明。
继续演化，我们对式（17）左乘一个AT，得到&，也就是说
我们知道了x，也就可以计算得到y。
6. 社交网络建模工具（Python）
最近比较忙，如果没有需求，这个系列可能就不会再继续写下去了。下面用一个python程序来演示社交网络的建模分析，以实际应用作为结束吧。
假设有这样两个文本文件sigcomm_author.txt和sigcomm_network.txt，文件内容如下：
这是一个学术圈的社交网络，描述了发表论文的作者之间的一些合作关系。它一个无向图，也就是说[ID_1, ID_2] 等同于 [ID_2,
ID_1]。通过编写程序，我们可以挖掘如下信息：
NetworkX是一个用Python语言开发的图论与复杂网络建模工具，内置了常用的图与复杂网络分析算法，包括我已经介绍过的degree
centrality，eigenvector
centrality等等。使用NetworkX可以方便的进行复杂网络数据分析、仿真建模等工作。
一般Linux都默认自带Python运行环境，Ubuntu下只需要执行以下命令即可获得NetworkX库进行程序开发。
sudo apt-get install python-setuptools
sudo easy_install networkx
Windows下则需要手动安装，具体可以参考这个。环境都搭建好了之后就可以对社交网络之间的关系进行分析了，查看这个。
回到上文提出的例子，在调用NetworkX提供的接口的基础上，我们可以挖掘论文作者之间的关系，分析整个网络的一些属性。示例源代码和测试数据。
-------------------------小结：优化后的PAGERANK算法，可以利用测算网页中相互连接的重要性来判断网页重要等级的模型，来延伸到计算社交网络中意见领袖的寻找中，当然，也可以通过这种方法推算内容型站点，如轻博客中人们对内容交互后的“内容重要等级/内容喜爱程度”，对于游戏而言，如果能够发现游戏社交中的核心领袖，甚至能够反推出交互过程中行为的重要程度，那么就可以帮助运营做出及时决策改进，这也是一个很好的方向。
已投稿到：
以上网友发言只代表其个人观点，不代表新浪网的观点或立场。}