PageRank 算法原理

PageRank 算法是一种简单有效且流行的网页排序算法，它通过一个网页的所有入链数目来计算该网页的重要性（PageRank 值，简称 PR），其思想类似于一篇论文被引用的次数越大，该论文的影响力越大。

以下给出一个简单的例子，一个个网页就是互联网中的一个个节点，这些网页之间相互引用，构成一个有向图。

这里有着和算法相关的两个概念。

  • 出链：网页链接出去的链接，相当于离散数学的图论中的出度概念；
  • 入链：链接进来的链接，相当于入度。

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

$$RP(u) = \sum_{v ∈ B_u} \frac{PR(v)}{L(v)}$$

其中，u 为待评估的节点网页，$B_u$ 为所有入链到节点u的网页集合，$PR_(v)$ 为入链到u的网页影响力值，而 $L(v)$ 则是网页 v 的出链数目。 以上述图像为例子，已知一个网页出链的数目，可以计算一个网页跳转到另外一个网页的概率，由此 A，B，C，D四个网页的转移矩阵 M

假设这四个网页的初始影响力（权重） w 都是一致的，给出如下向量 w0，代表A，B，C，D初始影响力。

经过第一次转移之后，各页面计算结果如下 w1, (矩阵乘法的过程，其实就是PR公式计算了)。

由此不断产生迭代，直到第 n 次迭代之后，wn 的影响力不再发生变化，收敛的最终结果就是各网页的最终PR值。

存在两种特殊情况：

１.　等级泄露：一个网站如果没有出链，只有入链，那么吸收了其他页面的影响力，但却不释放，最终会导致其他页面的PR值为０；

２.　等级沉没，如果一个网站只有出链，没有入链，多次迭代，这个网站的影响力PR将会变为０。

为了解决这两个问题，ＰａｇｅＲａｎｋ有了一个优化模型，称为随机浏览模型。

随机浏览模型

在原来模型的基础上，引入了一个阻尼因子ｄ，这个因子代表用户按照跳转链接来上网的概率，通常取一个固定值，而 1 - d 则代表了用户不是通过跳转链接来访问的网页，比如直接输入网址。其中 N代表比较网页的总数。

PageRank 算法实践

首先我们需要了解如何使用 PageRank 算法以及如何用python快速构建一个图。

这里直接使用工具包，networkx，里面内置了PageRank 计算函数和建图的函数，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
import networkx as nx

# creat directed graph
G = nx.DiGraph()

# define the edge relationship
edges = [("a", "b"), ("a", "c"), ("a", "d"), ("b", "a"), ("b", "d"), ("c", "a"), ("d", "b"), ("d", "b")]

# add edge
for edge in edges:
    G.add_edge(edge[0], edge[1])

# calculate pr value with the pagerank
pagerank_list = nx.pagerank(G, alpha = 1)
print (pagerank_list)

# node operations
G.add_node('c')
G.add_nodes_from(['d', 'e'])
G.remove_node('d')
G.remove_nodes_from(['c', 'd'])
print(G.nodes())
print(G.number_of_nodes())

# edge operations
G.add_edge('x', 'y')
print(G.edges())
G.remove_edge('x', 'y')
print(G.edges())
print(G.number_of_edges())

实战项目来自 Github, 主要是分析 希拉里邮件发送接收的关系网，由此来发现与希拉里关系密切的人。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
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("./data/Emails.csv")

file = pd.read_csv("./data/Aliases.csv")

# key: alias  value: personId
aliases = {}
for index, row in file.iterrows():
    aliases[row['Alias']] = row['PersonId']
    
file = pd.read_csv("./data/Persons.csv")

# key: id  value: name
persons = {}
for index, row in file.iterrows():
    persons[row['Id']] = row['Name']

# transform the alias name to the same
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 draw_graph(graph):
    # graph is a direct graph object
    
    # set spring_layout
    positions = nx.spring_layout(graph)
    
    # set the size of the nodes. The PR value is higher, the node is larger.
    nodesize = [x['pagerank']*20000 for v, x in graph.nodes(data=True)]
    
    # set the length of the edges
    edgesize = [np.sqrt(e[2]['weight']) for e in graph.edges(data = True)]
    
    # draw nodes
    nx.draw_networkx_nodes(graph, positions, node_size = nodesize, alpha = 0.4)

    # draw edges
    nx.draw_networkx_edges(graph, positions, edge_size = edgesize, alpha = 0.6)
    
    # draw nodes' label
    nx.draw_networkx_labels(graph, positions, font_size = 10)

    plt.show()
    

# normalize the from and to value.
# the metadataFrom and metadatato is the columns's name
emails.MetadataFrom = emails.MetadataFrom.apply(unify_name)
emails.MetadataTo = emails.MetadataTo.apply(unify_name)

# set the weight is equal the sending times
# {  (from, to): num }
edges_weights_temp = defaultdict(list)  # the key can be a tuple
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] += 1

        
# transfer the format (from, to):value  -> from, to, value
edge_weights = [(key[0], key[1], val) for key, val in edges_weights_temp.items()]

# create the direct graph
graph = nx.DiGraph()

# add weight 
graph.add_weighted_edges_from(edge_weights)

# calculate the pr value of every node
pagerank = nx.pagerank(graph)  # return a dict

# get the pr of per value
pagerank_list = {node: rank for node, rank in pagerank.items()}

# set the pr value as the attribute of the node
nx.set_node_attributes(graph, name = 'pagerank', values=pagerank_list)

# draw graph
draw_graph(graph)

# simplify the graph
pagerank_threshold = 0.02
# copy a graph
small_graph = graph.copy()

for n, p_rank in graph.nodes(data = True):
    if p_rank['pagerank'] < pagerank_threshold:
        small_graph.remove_node(n)
draw_graph(small_graph)

结果如下：