PageRank

互联网发展到现在，搜索引擎已经非常好用，基本上输入关键词，都能找到匹配的内容，质量还不错。但在1998年之前，搜索引擎的体验并不好。早期的搜索引擎，会遇到下面的两类问题：

• 返回结果质量不高：搜索结果不考虑网页的质量，而是通过时间顺序进行检索
• 容易被人钻空子：搜索引擎是基于检索词进行检索的，页面中检索词出现的频次越高，匹配度越高，这样就会出现网页作弊的情况。有些网页为了增加搜索引擎的排名，故意增加某个检索词的频率

基于这些缺陷，当时Google的创始人拉里·佩奇提出了PageRank算法，目的就是要找到优质的网页，这样Google的排序结果不仅能找到用户想要的内容，而且还会从众多网页中筛选出权重高的呈现给用户

Google的两位创始人都是斯坦福大学的博士生，他们提出的PageRank算法受到了论文影响力因子的评价启发。当一篇论文被引用的次数越多，证明这篇论文的影响力越大。正是这个想法解决了当时网页检索质量不高的问题

PageRank的简化模型

我们假设一共有4个网页A、B、C、D。它们之间的链接信息如图所示：

出链指的是链接出去的链接。入链指的是链接进来的链接。比如图中A有2个入链，3个出链

简单来说，一个网页的影响力=所有入链集合的页面的加权影响力之和，用公式表示为：

u为待评估的页面，Bu​为页面u的入链集合。针对入链集合中的任意页面v，它能给u带来的影响力是其自身的影响力PR(v)除以v页面的出链数量，即页面v把影响力PR(v)平均分配给了它的出链，这样统计所有能给u带来链接的页面v，得到的总和就是网页u的影响力，即为PR(u)

出链会给被链接的页面赋予影响力，当我们统计了一个网页链出去的数量，也就是统计了这个网页的跳转概率

在这个例子中，A有三个出链分别链接到了B、C、D上。那么当用户访问A的时候，就有跳转到B、C或者D的可能性，跳转概率均为1/3。

B有两个出链，链接到了A和D上，跳转概率为1/2

这样，我们可以得到A、B、C、D这四个网页的转移矩阵M：

我们假设A、B、C、D四个页面的初始影响力都是相同的，即：

当进行第一次转移之后，各页面的影响力$w_1$​变为：

然后我们再用转移矩阵乘以 $w_1$ ​得到 $w_2$ ​结果，直到第n次迭代后 $w_n$ 影响力不再发生变化，可以收敛到(0.3333,0.2222,0.2222,0.2222），也就是对应着A、B、C、D四个页面最终平衡状态下的影响力

你能看出A页面相比于其他页面来说权重更大，也就是PR值更高。而B、C、D页面的PR值相等

至此，我们模拟了一个简化的PageRank的计算过程，实际情况会比这个复杂，可能会面临两个问题：

• 等级泄露（Rank Leak）：如果一个网页没有出链，就像是一个黑洞一样，吸收了其他网页的影响力而不释放，最终会导致其他网页的PR值为0

• 等级沉没（Rank Sink）：如果一个网页只有出链，没有入链（如下图所示），计算的过程迭代下来，会导致这个网页的PR值为0（也就是不存在公式中的V）

针对等级泄露和等级沉没的情况，我们需要灵活处理

比如针对等级泄露的情况，我们可以把没有出链的节点，先从图中去掉，等计算完所有节点的PR值之后，再加上该节点进行计算。不过这种方法会导致新的等级泄露的节点的产生，所以工作量还是很大的

PageRank的随机浏览模型

为了解决简化模型中存在的等级泄露和等级沉没的问题，拉里·佩奇提出了PageRank的随机浏览模型

他假设了这样一个场景：用户并不都是按照跳转链接的方式来上网，还有一种可能是不论当前处于哪个页面，都有概率访问到其他任意的页面，比如说用户就是要直接输入网址访问其他页面，虽然这个概率比较小

所以他定义了阻尼因子d，这个因子代表了用户按照跳转链接来上网的概率，通常可以取一个固定值0.85，而1-d=0.15则代表了用户不是通过跳转链接的方式来访问网页的，比如直接输入网址

其中N为网页总数，这样我们又可以重新迭代网页的权重计算了，因为加入了阻尼因子d，一定程度上解决了等级泄露和等级沉没的问题

通过数学定理也可以证明，最终PageRank随机浏览模型是可以收敛的，也就是可以得到一个稳定正常的PR值

PageRank在社交影响力评估中的应用

网页之间会形成一个网络，是我们的互联网，论文之间也存在着相互引用的关系，可以说我们所处的环境就是各种网络的集合

只要是有网络的地方，就存在出链和入链，就会有PR权重的计算，就可以使用PageRank算法

我们可以把PageRank算法延展到社交网络领域中。比如在微博上，如果我们想要计算某个人的影响力，该怎么做呢？

一个人的微博粉丝数并不一定等于他的实际影响力。如果按照PageRank算法，还需要看这些粉丝的质量如何

如果有很多明星或者大V关注，那么这个人的影响力一定很高。如果粉丝是通过购买僵尸粉得来的，那么即使粉丝数再多，影响力也不高

同样，在工作场景中，比如说脉脉这个社交软件，它计算的就是个人在职场的影响力

如果你的工作关系是李开复、江南春这样的名人，那么你的职场影响力一定会很高。反之，如果你是个学生，在职场上被链入的关系比较少的话，职场影响力就会比较低

同样，如果你想要看一个公司的经营能力，也可以看这家公司都和哪些公司有合作。如果它合作的都是世界500强企业，那么这个公司在行业内一定是领导者，如果这个公司的客户都是小客户，即使数量比较多，业内影响力也不一定大

除非像淘宝一样，有海量的中小客户，最后大客户也会找上门来寻求合作。所以权重高的节点，往往会有一些权重同样很高的节点在进行合作

PageRank给我们带来的启发

PageRank可以说是Google搜索引擎重要的技术之一，在1998年帮助Google获得了搜索引擎的领先优势，现在PageRank已经比原来复杂很多，但它的思想依然能带给我们很多启发

比如，如果你想要自己的媒体影响力有所提高，就尽量要混在大V圈中；如果想找到高职位的工作，就尽量结识公司高层，或者认识更多的猎头，因为猎头和很多高职位的人员都有链接关系

同样，PageRank也可以帮我们识别链接农场。链接农场指的是网页为了链接而链接，填充了一些没有用的内容。这些页面相互链接或者指向了某一个网页，从而想要得到更高的权重

总结

如何使用工具实现PageRank算法

PageRank算法工具在sklearn中并不存在，有一个关于图论和网络建模的工具叫NetworkX，内置了常用的图与网络分析算法，可以方便我们进行网络数据分析

PageRank的简化模型中，我们假设一共有4个网页A、B、C、D。它们之间的链接信息如图所示：

针对这个例子，我们看下用NetworkX如何计算A、B、C、D四个网页的PR值，具体代码如下：

import networkx as nx
# 创建有向图
G = nx.DiGraph() 
# 有向图之间边的关系
edges = [("A", "B"), ("A", "C"), ("A", "D"), ("B", "A"), ("B", "D"), ("C", "A"), ("D", "B"), ("D", "C")]
for edge in edges:
    G.add_edge(edge[0], edge[1])
pagerank_list = nx.pagerank(G, alpha=1)
# pagerank值是： {'A': 0.33333396911621094, 'B': 0.22222201029459634, 'C': 0.22222201029459634, 'D': 0.22222201029459634}
print("pagerank值是：", pagerank_list)

运行完这个例子之后，我们来看下NetworkX工具都有哪些常用的操作

①. 关于图的创建

• 图可以分为无向图和有向图，在NetworkX中分别采用不同的函数进行创建。无向图指的是不用节点之间的边的方向，使用nx.Graph()进行创建
• 有向图指的是节点之间的边是有方向的，使用nx.DiGraph()来创建。在上面这个例子中，存在A→D的边，但不存在D→A的边

②. 关于节点的增加、删除和查询

• 如果想在网络中增加节点，可以使用G.add_node('A')添加一个节点，也可以使用G.add_nodes_from(['B','C','D','E'])添加节点集合
• 如果想要删除节点，可以使用G.remove_node(node)删除一个指定的节点，也可以使用G.remove_nodes_from(['B','C','D','E'])删除集合中的节点
• 如果你想要得到图中所有的节点，就可以使用G.nodes()，也可以用G.number_of_nodes()得到图中节点的个数

③. 关于边的增加、删除、查询

• 增加边与添加节点的方式相同，使用G.add_edge('A','B')添加指定的'从A到B'的边，也可以使用add_edges_from函数从边集合中添加
• 我们也可以做一个加权图，也就是说边是带有权重的，使用add_weighted_edges_from函数从带有权重的边的集合中添加。在这个函数的参数中接收的是1个或多个三元组(u,v,w)作为参数，u、v、w分别代表起点、终点和权重
• 另外，我们可以使用remove_edge函数和remove_edges_from函数删除指定边和从边集合中删除
• 也可以使用edges()函数访问图中所有的边，使用number_of_edges()函数得到图中边的个数

如何用PageRank揭秘希拉里邮件中的人物关系

希拉里邮件事件相信你也有耳闻，对这个数据的背景我们就不做介绍了。你可以从 GitHub 上下载这个数据集

整个数据集由三个文件组成：Aliases.csv，Emails.csv和Persons.csv，其中Emails文件记录了所有公开邮件的内容，发送者和接收者的信息。Persons这个文件统计了邮件中所有人物的姓名及对应的ID

因为姓名存在别名的情况，为了将邮件中的人物进行统一，我们还需要用Aliases文件来查询别名和人物的对应关系

整个数据集包括了9306封邮件和513个人名，数据集还是比较大的。不过我们不需要对邮件的内容进行分析，只需要通过邮件中的发送者和接收者（对应Emails.csv文件中的MetadataFrom和MetadataTo字段）来绘制整个关系网络

因为涉及到的人物很多，因此我们需要通过PageRank算法计算每个人物在邮件关系网络中的权重，最后筛选出来最有价值的人物来进行关系网络图的绘制

了解了数据集和项目背景之后，我们来设计到执行的流程步骤：

①. 首先我们需要加载数据源

②. 在准备阶段：我们需要对数据进行探索，在数据清洗过程中，因为邮件中存在别名的情况，因此我们需要统一人物名称

另外邮件的正文并不在我们考虑的范围内，只统计邮件中的发送者和接收者，因此我们筛选MetadataFrom 和 MetadataTo 这两个字段作为特征

同时，发送者和接收者可能存在多次邮件往来，需要设置权重来统计两人邮件往来的次数。次数越多代表这个边（从发送者到接收者的边）的权重越高

③. 在挖掘阶段：我们主要是对已经设置好的网络图进行PR值的计算，但邮件中的人物有500多人，有些人的权重可能不高，我们需要筛选PR值高的人物，绘制出他们之间的往来关系

④. 在可视化的过程中，我们可以通过节点的PR值来绘制节点的大小，PR值越大，节点的绘制尺寸越大

import pandas as pd
import networkx as nx
import numpy as np
from collections import defaultdict
import matplotlib.pyplot as plt

# 数据加载
emails = pd.read_csv("./Emails.csv")
# 读取别名文件
file = pd.read_csv("./Aliases.csv")
aliases = {}
for index, row in file.iterrows():
    aliases[row['Alias']] = row['PersonId']
# 读取人名文件
file = pd.read_csv("./Persons.csv")
persons = {}
for index, row in file.iterrows():
    persons[row['Id']] = row['Name']


# 针对别名进行转换
def unify_name(name):
    # 姓名统一小写
    name = str(name).lower()
    # 去掉, 和 @后面的内容
    name = name.replace(",", "").split("@")[0]
    # 别名转换
    if name in aliases.keys():
        return persons[aliases[name]]
    return name


# 画网络图
def show_graph(graph, layout='spring_layout'):
    '''
        spring_layout布局，类似中心放射状
        circular_layout布局，在一个圆环上均匀分布节点
        random_layout布局，随机分布节点
        shell_layout布局，节点都在同心圆上
    '''
    if layout == 'circular_layout':
        positions = nx.circular_layout(graph)
    else:
        positions = nx.spring_layout(graph)
    # 设置网络图中的节点大小，大小与 pagerank 值相关，因为 pagerank 值很小所以需要 *20000
    nodesize = [x['pagerank'] * 20000 for v, x in graph.nodes(data=True)]
    # 设置网络图中的边长度
    edgesize = [np.sqrt(e[2]['weight']) for e in graph.edges(data=True)]
    # 绘制节点
    nx.draw_networkx_nodes(graph, positions, node_size=nodesize, alpha=0.4)
    # 绘制边
    nx.draw_networkx_edges(graph, positions, node_size=edgesize, alpha=0.2)
    # 绘制节点的 label
    nx.draw_networkx_labels(graph, positions, font_size=10)
    # 输出希拉里邮件中的所有人物关系图
    plt.show()


# 将寄件人和收件人的姓名进行规范化
emails.MetadataFrom = emails.MetadataFrom.apply(unify_name)
emails.MetadataTo = emails.MetadataTo.apply(unify_name)
# 设置边的权重等于发邮件的次数
edges_weights_temp = defaultdict(list)
for row in zip(emails.MetadataFrom, emails.MetadataTo, emails.RawText):
    temp = (row[0], row[1])
    if temp not in edges_weights_temp:
        edges_weights_temp[temp] = 1
    else:
        edges_weights_temp[temp] = edges_weights_temp[temp] + 1
# 转化格式 (from, to), weight => from, to, weight
edges_weights = [(key[0], key[1], val) for key, val in edges_weights_temp.items()]
# 创建一个有向图
graph = nx.DiGraph()
# 设置有向图中的路径及权重 (from, to, weight)
graph.add_weighted_edges_from(edges_weights)
# 计算每个节点（人）的 PR 值，并作为节点的 pagerank 属性
pagerank = nx.pagerank(graph)
# 将 pagerank 数值作为节点的属性
nx.set_node_attributes(graph, name='pagerank', values=pagerank)
# 画网络图
show_graph(graph)

# 将完整的图谱进行精简
# 设置 PR 值的阈值，筛选大于阈值的重要核心节点
pagerank_threshold = 0.005
# 复制一份计算好的网络图
small_graph = graph.copy()
# 剪掉 PR 值小于 pagerank_threshold 的节点
for n, p_rank in graph.nodes(data=True):
    if p_rank['pagerank'] < pagerank_threshold:
        small_graph.remove_node(n)
# 画网络图,采用circular_layout布局让筛选出来的点组成一个圆
show_graph(small_graph, 'circular_layout')

实战总结