「搜索引擎」网页权重经典算法HITS与PageRank实现

在搜索引擎中,页面排序是一个非常重要的部分,一个页面的排名顺序决定了网站的流量。为了公平起见(忽视国内某度的竞价排名),当然是价值越高、越能满足检索意图的页面应该尽量排在前面,所以就需要一些指标用来定义网页的权重,作为排序的标准。

HITS和PageRank是两个经典的网页权重计算算法,甚至google当年就是靠发明的后者起家的。两个算法就不再介绍,网上有算法的详细介绍和证明。以下是我的实现版本,如果有任何错误,感谢提出。 

HITS算法

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
# HITS算法
# para@mat: 邻接矩阵,表示图中结点之间连接关系,1有边,0无边
# return: 返回authority值数组和hub值数组
# author: 喻永生
def hits(mat):
    iter_times = 0              # 迭代次数
    max_iter_times = 100        # 最大迭代次数
    min_iter_change = 0.000001  # 最小相邻迭代差别阈值
    iter_changes = 1.0          # 相邻迭代差别值
    h = np.ones(mat.shape[0])   # 初始化hub
    a = np.ones(mat.shape[0])   # 初始化authority
    while iter_times < max_iter_times and iter_changes > min_iter_change:
        iter_changes = 0.0
        tot = 0.0               # 标准化使用变量
        tmp = a.copy()
        # --- 计算 authority 值 ---
        for node in range(mat.shape[0]):
            a[node] = sum(h[mat[:, node] > 0])
            tot += pow(a[node], 2)
        # --- 标准化 authority 值 ---
        tot = np.sqrt(tot)
        for node in range(mat.shape[0]):
            a[node] /= tot
            iter_changes += abs(a[node] - tmp[node])
 
        # --- 计算 hub 值 ---
        tmp = h.copy()
        tot = 0.0
        for node in range(mat.shape[0]):
            h[node] = sum(a[mat[node, :] > 0])
            tot += pow(h[node], 2)
        # --- 标准化 hub 值 ---
        tot = np.sqrt(tot)
        for node in range(mat.shape[0]):
            h[node] /= tot
            iter_changes += abs(h[node] - tmp[node])
 
        iter_times += 1
    print u'迭代进行到第 ',; print iter_times-1,; print u' 次结束.'
    return a, h

 

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
31
32
33
34
35
36
# pagerank算法(pygraph库实现)
# para@tab: 图的邻接表
# return: 各结点的PR值
# author: 喻永生
def pagerank(tab, ALPHA):
    _ALPHA = ALPHA              # 阿尔法值
    max_iter_times = 100        # 最大迭代次数
    iter_times = 1              # 当前迭代次数
    min_iter_change = 0.000001  # 最小相邻迭代差别阈值
    iter_changes = 1.0          # 相邻迭代差别值
    node_size = len(tab.nodes())# 结点个数
    # 初始化PR数组(用字典存储)
    pr = dict.fromkeys(tab.nodes(), 1.0/node_size)
    _NORM = _ALPHA/node_size    # 公式中的常数
 
    # 如果某个结点没有出度,则将他指向所有结点,包括自身
    rec = datetime.now()
    for i in tab.nodes():
        if len(tab.neighbors(i)) == 0:
            for j in tab.nodes():
                tab.add_edge((i, j))
    now = datetime.now()
    print u'预处理(处理无出度结点)耗时:',; print (now - rec).seconds
 
    while iter_times < max_iter_times and iter_changes > min_iter_change:
        tmp_pr = pr.copy()
        iter_changes = 0.0
        for node in tab.nodes():
            value = _NORM
            for pNode in tab.incidents(node):   # 遍历指向node结点的所有点
                value += (1.0-_ALPHA)*tmp_pr[pNode]/len(tab.neighbors(pNode))
            iter_changes += abs(value - tmp_pr[node])
            pr[node] = value
        iter_times += 1
    print u'迭代进行到第 ',; print iter_times - 1,; print u' 次结束.'
    return pr

这是pagerank简化算法,需要预处理无出度结点,在稀疏图中可能有很多多余的计算时间。下面进行优化,实现PageRank的加速算法。

 

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
# pagerank加速算法
# para@tab: 图的邻接表
# return: 各结点的PR值
# author: 喻永生
def accPageRank(tab):
    _ALPHA = 0.15               # 阿尔法值
    max_iter_times = 30         # 最大迭代次数
    iter_times = 1              # 当前迭代次数
    min_iter_change = 0.000001  # 最小相邻迭代差别阈值
    iter_changes = 1.0          # 相邻迭代差别值
    node_size = len(tab.nodes())# 结点个数
    # 初始化PR数组(用字典存储)
    pr = dict.fromkeys(tab.nodes(), 1.0/node_size)
    _NORM = _ALPHA/node_size    # 公式中的常数
    I = dict.fromkeys(tab.nodes(), _NORM)
 
    # 第一步:计算每个结点的outdegree
    outdegree = dict.fromkeys(tab.nodes(), 0.0)
    for edge in tab.edges():
        outdegree[edge[0]] += 1
    # 第二步:计算S(记录无出链接节点的PageRank值之和)
    S = 0
    for node in tab.nodes():
        if len(tab.neighbors(node)) == 0:
            S += pr[node]
    while iter_times < max_iter_times and iter_changes > min_iter_change:
        iter_changes = 0.0
        # 第三步
        tmp_pr = pr.copy()
        for edge in tab.edges():
            i = edge[0]; j = edge[1]
            I[j] += (1 - _ALPHA) * tmp_pr[i] / outdegree[i]
        # 第四步
        tmp_S = 0
        for node in tab.nodes():
            pr[node] = I[node] + (1-_ALPHA)*S/node_size
            iter_changes += abs(tmp_pr[node] - pr[node])
            I[node] = _NORM
            if len(tab.neighbors(node)) == 0:
                tmp_S += pr[node]
        S = tmp_S
        iter_times += 1
    print u'迭代进行到第 ', ;print iter_times - 1, ; print u' 次结束.'
    return pr