本文主要介绍 PageRank 算法原理和其 Python 实现

PageRank 算法原理

  1. 如果一个网页被很多其他网页链接到的话说明这个网页比较重要，也就是 PageRank 值会相对较高。
  2. 如果一个 PageRank 值很高的网页链接到一个其他的网页，那么被链接到的网页的 PageRank 值会相应地因此而提高。

计算公式：

PR(pi)=α∑pj∈MpiPR(pj)L(pj)+1−αNPR(p_i)=\alpha\sum_{p_j\in M_{p_i}}\frac{PR(p_j)}{L(p_j)}+\frac{1-\alpha}{N}

其中MpiM_{p_i}是所有对pip_i网页有出链的网页集合，L(pj)L(p_j)是网页pjp_j的出链的数目，NN是网页总数，α\alpha取值一般为 0.85。

Python 实现过程

将 Pagerank 算法运用在社团检测中，需要对计算公式进行重构。如果是有向图可以依然按照上式进行计算，如果是无向图那么将节点的出度设为节点的度。

Python 实现代码：

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
# -*- coding: UTF-8 -*-

"""
Created on 17-12-3

@summary: python 实现 PageRank 算法

@author: dreamhome
"""
import networkx as nx

def read_graph_from_file(path):
    """
    :param path: 从文件中读取图结构
    :return: Graph graph
    """
    # 定义图
    graph = nx.Graph()
    # 获取边列表 edges_list
    edges_list = []
    # 开始获取边
    fp = open(path)
    edge = fp.readline().split()
    while edge:
        if edge[0].isdigit() and edge[1].isdigit():
            edges_list.append((int(edge[0]), int(edge[1])))
        edge = fp.readline().split()
    fp.close()
    # 为图增加边
    graph.add_edges_from(edges_list)

    return graph

def pagerank(graph, damping_factor, max_iterations, delta):
    """
    pagerank 算法
    :param path: 图
    :param damping_factor: 阻尼系数
    :param max_iterations: 最大迭代次数
    :param delta: 算法终止条件
    :return: 返回每个节点的重要性
    """
    # 获取图属性
    nodes = graph.nodes()
    graph_size = graph.number_of_nodes()
    # 每个节点赋予初始 PR 值
    page_rank = dict.fromkeys(nodes, 1.0 / graph_size)
    # 公式中的 (1−α)/N 部分
    damping_value = (1.0 - damping_factor) / graph_size
    for i in xrange(max_iterations):
        change = 0
        for node in nodes:
            rank = 0
            # 根据邻居计算 PR 值
            for neighbor in graph.neighbors(node):
                rank += damping_factor * \
                    (page_rank[neighbor] / len(graph.neighbors(neighbor)))
            rank += damping_value
            change += abs(page_rank[node] - rank)  # 绝对值
            page_rank[node] = rank

        # print("%sth iteration" % (i + 1))
        # print(page_rank)

        if change < delta:
            break
    return page_rank

if __name__ == "__main__":
    path = "/home/dreamhome/network-datasets/dolphins/out.dolphins"
    graph = read_graph_from_file(path)
    print pagerank(graph, 0.85, 100, 0.00001)

联系作者