链接分析之Google PageRank 算法

作者: lilyblspku | 来源:发表于2019-05-23 17:19 被阅读0次

一、引言

1. 链接分析算法

链接分析是指源于对Web结构中超链接的多维分析。在图网络的链接分析中，存在两类模型：

随机游走模型：网页节点通过链接进行跳转，对应跳转的概率；这类模型主要基于PageRank，如随机游走模型（random walk）、主题敏感PageRank、智能游走模型及偏置游走模型；
子集传播模型：网页划分子集，给予特殊子集内网页初始权重，根据特殊子集内网页与其他网页的链接关系，将权值传递到其他网页。这类模型包括Hilltop算法、HITS算法、PHITS算法。
算法之间关系如下：

其中的两个算法最为经典，一个是PageRank算法，另外一个为HITS（Hyperlink - Induced Topic Search）算法。本文先介绍PageRank算法，在后续文章中会对HITS算法原理做一简单介绍。

2. PageRank算法背景及应用

随着网络信息量越来越庞大，如何有效的搜索出用户真正需要的信息非常重要。自1998年搜索引擎网站Google创立以来，网络搜索引擎称为解决上述问题的主要手段。
1998年，美国斯坦福大学博士生Larry Page和Sergey Brin创立了Google公司，他们核心技术是通过PageRank技术对海量的网页进行重要性分析。该技术利用网页相互链接的关系对网页进行组织，确定出每个网页的重要级别（Page Rank）。当用户进行搜索时，Google找出符合搜索条件的网页，并按它们的PageRank大小依次列出。用户一般在显示结果的第一页或者前几页就能找到真正有用的结果。在 Google技术的发展基础上， PR只是目前页面排序的一个小小的权重，谷歌最新的算法称为企鹅算法（Google Penguin）。
形象的解释，PageRank的基本原理是：如果网页A链接到网页B，则认为“网页A投了网页B”一票，如果网页A级别高，则网页B级别也相应的高。
PageRank除了网站搜索之外，还有很多其他应用。更进一步说，只要有图谱，就可以使用PageRank。以下为一些应用举例：

社交网络：评估社交网络节点影响力，如寻找关系网中的牛人；基于用户的相似度的内容推荐、可以挖掘用户的价值、用户的社交影响力等
生物领域：基因、蛋白研究，如通过PageRank确定七个与遗传有关的肿瘤基因（Google Goes Cancer: Improving Outcome Prediction for Cancer Patients by Network-Based Ranking of Marker Genes )；
体育运动：评估特定体育运动项目中历史最佳球队或球员（1968年文章）；
神经科学：评估不同大脑区域之间的联结和重要性；
交通网络：预测城市的交通流量和人流动向；
推荐系统：在推荐系统中，用户行为数据可以表示成图的形式，具体来说是二部图。用户的行为数据集由一个个（u,i）二元组组成，表示为用户u对物品i产生过行为。用户对他产生过行为的物品的兴趣度是一样的，也就是只考虑“感兴趣”OR“不感兴趣”。用G(V, E)来表示这个图，则顶点集V=U∪I，图中的边则是由数据集中的二元组确定。二元组（u, i）表示u对i有过行为，则在图中表现为有边相连，即e(u,i)。对u进行推荐物品，就转化为计算用户顶点u和与所有物品顶点之间的相关性，然后取与用户没有直接边相连的物品，按照相关性的高低生成推荐列表。

二、原始算法原理

PageRank的核心思想

如果一个网页被很多其他网页链接到，则说明这个网页很重要，也就是PageRank值会相对较高；
如果一个PageRank很高的网页链接到一个其他的网页，则链接到的网页的PageRank 值会相应的提高。
如下图，每个球代表一个网页，球的大小反应了网页的PageRank值的大小。指向网页B和网页E的链接很多，所以B和E的PageRank值较高，另外，虽然很少有网页指向C，但是最重要的网页B指向了C，所以C的PageRank值比E还要大。

PageRank算法预先给每个网页设定一个PR值，PR值物理意义上代表一个网页被访问的概率，常规设置为1/N，N为网页总数。所有网页的PR值总和为1。多个网页的连接可以认为是一个有向图（不含权重与时间，图为静态）。
第1步：假设有5个网页，分别用A, B, C, D, E表示：

第2步：对网页进行爬虫决定链接关系如下图

第3步：给每个网页的rank赋值为1/N，N为网页个数，此例中为5，所以每个网页的Rank值为0.2.

第4步：通过将链接到它的每个页面的权重除以从引用页面发出的链接数量，连续更新每个页面的rank。以E为例，分别从C， D出发，E有两个进入的链接。因为C可到达三个页面，页面C贡献了1/3的Rank给页面E；同理，页面D贡献了1/2 Rank给页面E，所以E的rank更新如下：

如果一个页面没有出去的链接，则其权重平均分配到剩余节点，如示例中E，E的rank均分值A， B， C， D。之所以均分是因为，当用户到达一个没有外部链接的网站后，会继续搜索其他网页。

第5步：重复第4步直到页面rank不在发生变化

注：在实际应用中，PageRank算法会添加一个阻尼系数来模拟用户停止搜索的情况，在添加阻尼系数后，一个网页的PR值计算如下：

其中是所有对网页有出链的网页集合（进入的节点集合），是网页的出链数目，为网页总数，一般取0.85。根据上述公式，反复计算网页PR值，在不断迭代稳定时，为最终结果。

三、PageRank算法变种

1. 无向图的PageRank

无向图的PageRank统计上与图的链接分布（degree distribution）相近，但又存在不同。假定 $R$ 是PageRank向量， $D$ 是链接分布向量。
$D=\frac{1}{2|E|}\left[ \begin{matrix} deg(P_1) \\ deg(p_2) \\ \vdots\\ deg(p_N)\\ \end{matrix} \right] \tag{3}$
$deg(p_i)$ 表示页面 $p_i$ 的链接， $E$ 为无向图的边集合， $|E|$ 为图的总边数。

2. 主题敏感PageRank（Topic-Sensitive PageRank）

PageRank算法遵循随机游走模型，即用户在浏览某网页时，如果希望跳转到其他页面，可随机选择本网页包含的某个链接，进入另外一个页面，与查询搜索的主题无关。主题敏感PageRank引入更符合现实的假设：一般用户会对特定领域感兴趣，当浏览某一网页时，这个页面与主题相关；当用户浏览完毕后，希望跳转到主题类似的链接。主题敏感PageRank将用户兴趣、页面主题以及链接所指向网页与当前网页主题相似程度综合考虑而建立模型。
主题敏感PageRank引入16类主题，对于某网页，对应某个主题类型都有相应的PageRank分值，即每个网页会被赋予16个主题相关的PageRank分值。主题敏感与查询相关，在接收到用户查询后，主题敏感PageRank需要分类器，计算该查询隶属于事先定义好的16个主题的隶属度。16大主题如下：

ODP（Open Directory Project）上16大主题
ODP(Open Directory Project)是人工整理的多层级网页分类导航站点，在顶级的16个大分类下还有更细致的小粒度分类结构，在最底层目录下，人工收集了符合该目录主题的精选高质量网页地址，以供互联网用户导航寻址。主题敏感PageRank采用了ODP最高级别的16个分类类别作为事先定义的主题类型。其计算流程如下：
（1）确定话题分类：参考IDP网站；
（2）网页主题归属：将每个页面归入最合适的分类，归类方法如使用TF-IDF 或聚类后人工归类。每个页面会被归属到一类主题；
（3）分主题计算网页的PageRank向量：在计算网页在特定类别的PageRank分值时，在每个类别中网页划分为两个集合，一个集合是ODP对应分类主题下所包括的所有网页，即人工精选的高质量网页，可以称之为集合S，剩下的网页放入另外一个集合内，可称之为集合T。在计算PageRank时，由于集合S内的网页能够很好地表征分类主题，所以赋予较大的跳转概率值。通过这种设定，集合S内的网页根据链接关系向集合T中网页传递权值，因为直接有链接指向的往往主题类似，这样就将与该分类主题内容相似的网页赋予较高的PageRank值，而无关的网页则赋予较低权重的PageRank分值。

对于相同的网页1，在不同类别的集合中，所计算出的PageRank不同
假设有个编号为1号的网页，其被列为ODP目录中的艺术类别中，在对艺术类别进行PageRank计算时，1号网页在集合S内，计算结束后，该网页获得的PageRank分值为0.5。当计算体育和商业类别的主题PageRank分值时，1号网页在集合T中，获得了相应的集合S中网页传递的权值，分别为0.02和0.01。在所有类别计算结束后，1号网页获得了3个不同主题对应的PageRank分值，组成一个主题PageRank向量[0.5, 0.02, 0.01]。
（4）在线相似度计算：在用户提交搜索时，确定用户的主题倾向，以选择合适的Rank向量。例如用户输入查询请求“乔丹”，“乔丹”隶属于体育类别的概率为0.6，娱乐类别的概率为0.1，商业类别的概率为0.3，那么查询条件的类别概率向量为[0.6, 0.1, 0.3]。
同时，搜索系统读取包含“乔丹”的所有网页，对于每个网页，利用计算好的分类主题PageRank向量与查询条件的类别概率向量相乘，得到相似度。假定网页A的分类主题PageRank向量为[0.2,0.3,0.1]，则相似度为：

对于其他网页类似，计算所搜寻到网页相似度，按照相似度由高到低排序输出，作为搜索结果返回到用户。

3. PersonalRank

在推荐系统中，目标一般是向用户推荐商品，如在购物网站中，需要根据用户历史购买行为，向用户推荐实际的商品；在社交网站中，推荐的可能是用户，图展示如下：

A、B、C表示三个用户，a、b、c、d表示四个商品，中间联系表示用户与商品之间有过关联，推荐的目的是从商品列表中向指定的用户推荐用户未接触过的商品。推荐算法种类很多，包括协同过滤（基于用户的协同过滤、基于物品的协同过滤）和其他算法。在协同过滤中，用户与商品之间的关系表示成二维矩阵（用户商品矩阵），而在基于图的推荐算法中，上述关系表示为二部图的形式。
PersonalRank算法对每个节点打分，具体讲，算法不区分用户和商品。若计算用户A对所有商品的感兴趣程度转变为对用户A计算各个节点B、C、a、b、c、d的重要程度。
具体的过程如下（以用户A为例）：

初始化：
$PR(A)=1, PR(B)=0, PR(C)=0, PR(a)=0, PR(b)=0, PR(c)=0, PR(d)=0$
选择PR值不为0的节点开始，停在当前节点的概率为，往前走的概率为：
- 从A开始，A到a、c的概率为0.5，则 $PR(a)=PR(c)= \alpha\times PR(A)\times 0.5$ , A的PR值变为 $1-\alpha$ ；
- 此时PR值不为0的节点为A、a、c，从这三点出发，继续上述过程，直到收敛为止。
  节点PR的更新公式为：
  若 $j\neq u$ , $PR(j)=\alpha \sum_{i \in in(j)}\frac{PR(i)}{|out(i)|}$ ;
  若 $j=u$ , $PR(j)=(1-\alpha)+\alpha \sum_{i \in in(j)}\frac{PR(i)}{|out(i)|}$ ;

四、PageRank算法R及python实现

1. R实现：igraph包的page_rank函数

示例：

require(igraph)
g <- sample_gnp(20, 5/20, directed=TRUE)
#plot(g, layout=layout_with_kk, vertex.color="green")
page_rank(g)$vector

结果：

> page_rank(g)$vector
 [1] 0.02341596 0.02631466 0.01231889 0.06031833 0.05306684 0.02874900 0.04125774
 [8] 0.05669780 0.06568727 0.03468001 0.04879063 0.10330288 0.03968495 0.04109741
[15] 0.03534523 0.04664756 0.04055067 0.08679532 0.05055317 0.10472569

2. Python实现

使用第三方模块python-graph，python-graph模块实现了很多图算法，使用前需要安装，代码如下：

pip3 install graphviz
pip3 install python-graph-core
pip3 install python-graph-dot

python版本的算法实现带阻尼系数的pagerank：

# coding=utf-8

# python-graph https://code.google.com/p/python-graph/

# Import graphviz
import graphviz as gv #可视化graph

# Import pygraph
from pygraph.classes.digraph import digraph
from pygraph.readwrite.dot import write

# Define pagerank function
def pagerank(graph, damping_factor=0.85, max_iterations=100, \
             min_delta=0.00001):
    """
    Compute and return the PageRank in an directed graph.

    @type  graph: digraph
    @param graph: Digraph.

    @type  damping_factor: number
    @param damping_factor: PageRank dumping factor.

    @type  max_iterations: number
    @param max_iterations: Maximum number of iterations.

    @type  min_delta: number
    @param min_delta: Smallest variation required for a new iteration.

    @rtype:  Dict
    @return: Dict containing all the nodes PageRank.
    """

    nodes = graph.nodes()
    graph_size = len(nodes)
    if graph_size == 0:
        return {}
    # value for nodes without inbound links
    min_value = (1.0-damping_factor)/graph_size

    # itialize the page rank dict with 1/N for all nodes
    #pagerank = dict.fromkeys(nodes, 1.0/graph_size)
    pagerank = dict.fromkeys(nodes, 1.0)

    for i in range(max_iterations):
        diff = 0 #total difference compared to last iteraction
        # computes each node PageRank based on inbound links
        for node in nodes:
            rank = min_value
            for referring_page in graph.incidents(node):
                rank += damping_factor * pagerank[referring_page] / \
                        len(graph.neighbors(referring_page))

            diff += abs(pagerank[node] - rank)
            pagerank[node] = rank

        print("This is NO.%s iteration" % (i+1))
        print (pagerank)
        print("")

        #stop if PageRank has converged
        if diff < min_delta:
            break

    return pagerank

# Graph creation
gr = digraph()

# Add nodes and edges
gr.add_nodes(["A","B","C","D","E"])

gr.add_edge(("A","B"))
gr.add_edge(("A","C"))
gr.add_edge(("B","A"))
gr.add_edge(("B","C"))
gr.add_edge(("B","D"))
gr.add_edge(("C","A"))
gr.add_edge(("C","D"))
gr.add_edge(("C","E"))
gr.add_edge(("D","A"))
gr.add_edge(("D","E"))


# Draw as PNG
# dot = write(gr)
# gvv = gv.readstring(dot)
# gv.layout(gvv,'dot')
# gv.render(gvv,'png','Model.png')

pagerank(gr)

示例结果：

This is NO.1 iteration
{'A': 1.0216666666666667, 'B': 0.4642083333333334, 'C': 0.5957340277777778, 'D': 0.3303170023148148, 'E': 0.3391760338541666}

This is NO.2 iteration
{'A': 0.4707017282986111, 'B': 0.23004823452690973, 'C': 0.2952285676428675, 'D': 0.17882842728143689, 'E': 0.1896501757600898}

This is NO.3 iteration
{'A': 0.2548305088760476, 'B': 0.13830296627232022, 'C': 0.17748880671614428, 'D': 0.11947433568006494, 'E': 0.13106508790026847}

This is NO.4 iteration
{'A': 0.17025092834409253, 'B': 0.10235664454623933, 'C': 0.13135769383434048, 'D': 0.09621906254116427, 'E': 0.10811111483305796}

This is NO.5 iteration
{'A': 0.1371121641211591, 'B': 0.08827266975149262, 'C': 0.11328325951441552, 'D': 0.0871075132920073, 'E': 0.0991176166781875}

This is NO.6 iteration
{'A': 0.12412820644111042, 'B': 0.08275448773747193, 'C': 0.10620159259642231, 'D': 0.08353755609460337, 'E': 0.09559391257585942}

This is NO.7 iteration
{'A': 0.1190410174348098, 'B': 0.08059243240979416, 'C': 0.10342695492590251, 'D': 0.08213882641178073, 'E': 0.0942133051206792}

This is NO.8 iteration
{'A': 0.11704782763678755, 'B': 0.07974532674563471, 'C': 0.1023398359902312, 'D': 0.08159079610849534, 'E': 0.09367237521000937}

This is NO.9 iteration
{'A': 0.11626688445460587, 'B': 0.07941342589320749, 'C': 0.10191389656294961, 'D': 0.08137607469591118, 'E': 0.09346043577193132}

This is NO.10 iteration
{'A': 0.11596090644167344, 'B': 0.07928338523771122, 'C': 0.10174701105506273, 'D': 0.08129194561628596, 'E': 0.09337739668585598}

This is NO.11 iteration
{'A': 0.11584102250320749, 'B': 0.0792324345638632, 'C': 0.10168162435695777, 'D': 0.08125898336089928, 'E': 0.0933448614961869}

This is NO.12 iteration
{'A': 0.11579405128928147, 'B': 0.07921247179794463, 'C': 0.10165600547402895, 'D': 0.08124606856039251, 'E': 0.09333211402247502}

This is NO.13 iteration
{'A': 0.11577564769855933, 'B': 0.07920465027188772, 'C': 0.10164596784892257, 'D': 0.08124100846756292, 'E': 0.09332711948924231}

This is NO.14 iteration
{'A': 0.11576843706627717, 'B': 0.0792015857531678, 'C': 0.10164203504989867, 'D': 0.08123902589420218, 'E': 0.09332516260250723}

This is NO.15 iteration
{'A': 0.11576561189923809, 'B': 0.07920038505717619, 'C': 0.10164049415670945, 'D': 0.08123824911060093, 'E': 0.09332439588307308}

{'A': 0.11576561189923809,
 'B': 0.07920038505717619,
 'C': 0.10164049415670945,
 'D': 0.08123824911060093,
 'E': 0.09332439588307308}

参考资料

[1] wiki: https://en.wikipedia.org/wiki/PageRank;
[2] Eric Roberts, CS 54N, The Google Page Rank Algorithm;
[3] PageRank算法--从原理到实现: https://www.cnblogs.com/rubinorth/p/5799848.html;
[4] 深入浅出PageRank算法: https://segmentfault.com/a/1190000000711128;
[5] Google的PageRank算法无所不能?: https://36kr.com/p/214680;
[6] Christof Winter et.al, Google Goes Cancer: Improving Outcome Prediction for Cancer Patients by Network-Based Ranking of Marker Genes, PLOS Computational Biology, 2012.
[7]PageRank 与基于图的推荐算法: https://donche.github.io/2017/10/31/PageRankNPersonalRank.html;
[8]链接分析算法总结: https://www.jianshu.com/p/d81bc99f1fe2;
[9]链接分析算法之：主题敏感PageRank: https://blog.csdn.net/hguisu/article/details/8005192;
[10] 大话主题敏感PageRank: https://blog.csdn.net/malefactor/article/details/7192168;
[11] PersonalRank：一种基于图的推荐算法:https://www.cnblogs.com/zhangchaoyang/articles/5470763.html

链接分析之Google PageRank 算法

一、引言

1. 链接分析算法

2. PageRank算法背景及应用

二、原始算法原理

三、PageRank算法变种

1. 无向图的PageRank

2. 主题敏感PageRank（Topic-Sensitive PageRank）

3. PersonalRank

四、PageRank算法R及python实现

1. R实现：igraph包的page_rank函数

2. Python实现

参考资料

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读