精华内容
下载资源
问答
  • 2019-12-04 16:32:38

    一、 PageRank 的简化模型

    我们先来看下 PageRank 是如何计算的。

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

    这里有两个概念你需要了解一下。

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

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

    u 为待评估的页面, B_{u} 为页面 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 的计算过程,实际情况会比这个复杂,可能会面临两个问题:

    1. 等级泄露(Rank Leak):如果一个网页没有出链,就像是一个黑洞一样,吸收了其他网页的影响力而不释放,最终会导致其他网页的 PR 值为 0。

     

     

    2. 等级沉没(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 算法工具在 sklearn 中并不存在,我们需要找到新的工具包。实际上有一个关于图论和网络建模的工具叫 NetworkX,它是用 Python 语言开发的工具,内置了常用的图与网络分析算法,可以方便我们进行网络数据分析。

    上节课,我举了一个网页权重的例子,假设一共有 4 个网页 A、B、C、D,它们之间的链接信息如图所示:

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

    复制代码

     1 import networkx as nx
     2 
     3 # 创建有向图
     4 
     5 G = nx.DiGraph()
     6 
     7 # 有向图之间边的关系
     8 
     9 edges = [("A", "B"), ("A", "C"), ("A", "D"), ("B", "A"), ("B", "D"), ("C", "A"), ("D", "B"), ("D", "C")]
    10 
    11 for edge in edges:
    12 
    13     G.add_edge(edge[0], edge[1])
    14 
    15 pagerank_list = nx.pagerank(G, alpha=1)
    16 
    17 print("pagerank 值是:", pagerank_list)

    复制代码

    NetworkX 工具把中间的计算细节都已经封装起来了,我们直接调用 PageRank 函数就可以得到结果:

    1 pagerank 值是: {'A': 0.33333396911621094, 'B': 0.22222201029459634, 'C': 0.22222201029459634, 'D': 0.22222201029459634}

     

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

    1. 关于图的创建

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

     

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

    如果想在网络中增加节点,可以使用 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() 得到图中节点的个数。

     

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

    增加边与添加节点的方式相同,使用 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 算法,使用 nx.pagerank(G) 这个函数,函数中的参数 G 代表创建好的图。

     

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

    了解了 NetworkX 工具的基础使用之后,我们来看一个实际的案例:希拉里邮件人物关系分析。

    希拉里邮件事件相信你也有耳闻,对这个数据的背景我们就不做介绍了。你可以从 GitHub 上下载这个数据集: https://github.com/cystanford/PageRank

    整个数据集由三个文件组成:Aliases.csv,Emails.csv 和 Persons.csv,其中 Emails 文件记录了所有公开邮件的内容,发送者和接收者的信息。Persons 这个文件统计了邮件中所有人物的姓名及对应的 ID。因为姓名存在别名的情况,为了将邮件中的人物进行统一,我们还需要用 Aliases 文件来查询别名和人物的对应关系。

    整个数据集包括了 9306 封邮件和 513 个人名,数据集还是比较大的。不过这一次我们不需要对邮件的内容进行分析,只需要通过邮件中的发送者和接收者(对应 Emails.csv 文件中的 MetadataFrom 和 MetadataTo 字段)来绘制整个关系网络。因为涉及到的人物很多,因此我们需要通过 PageRank 算法计算每个人物在邮件关系网络中的权重,最后筛选出来最有价值的人物来进行关系网络图的绘制。

     

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

    首先我们需要加载数据源;

    在准备阶段:我们需要对数据进行探索,在数据清洗过程中,因为邮件中存在别名的情况,因此我们需要统一人物名称。另外邮件的正文并不在我们考虑的范围内,只统计邮件中的发送者和接收者,因此我们筛选 MetadataFrom 和 MetadataTo 这两个字段作为特征。同时,发送者和接收者可能存在多次邮件往来,需要设置权重来统计两人邮件往来的次数。次数越多代表这个边(从发送者到接收者的边)的权重越高;

    在挖掘阶段:我们主要是对已经设置好的网络图进行 PR 值的计算,但邮件中的人物有 500 多人,有些人的权重可能不高,我们需要筛选 PR 值高的人物,绘制出他们之间的往来关系。在可视化的过程中,我们可以通过节点的 PR 值来绘制节点的大小,PR 值越大,节点的绘制尺寸越大。

     

    设置好流程之后,实现的代码如下:

    复制代码

      1 # -*- coding: utf-8 -*-
      2 
      3 # 用 PageRank 挖掘希拉里邮件中的重要任务关系
      4 
      5 import pandas as pd
      6 
      7 import networkx as nx
      8 
      9 import numpy as np
     10 
     11 from collections import defaultdict
     12 
     13 import matplotlib.pyplot as plt
     14 
     15 # 数据加载
     16 
     17 emails = pd.read_csv("./input/Emails.csv")
     18 
     19 # 读取别名文件
     20 
     21 file = pd.read_csv("./input/Aliases.csv")
     22 
     23 aliases = {}
     24 
     25 for index, row in file.iterrows():
     26 
     27     aliases[row['Alias']] = row['PersonId']
     28 
     29 # 读取人名文件
     30 
     31 file = pd.read_csv("./input/Persons.csv")
     32 
     33 persons = {}
     34 
     35 for index, row in file.iterrows():
     36 
     37     persons[row['Id']] = row['Name']
     38 
     39 # 针对别名进行转换        
     40 
     41 def unify_name(name):
     42 
     43     # 姓名统一小写
     44 
     45     name = str(name).lower()
     46 
     47     # 去掉, 和 @后面的内容
     48 
     49     name = name.replace(",","").split("@")[0]
     50 
     51     # 别名转换
     52 
     53     if name in aliases.keys():
     54 
     55         return persons[aliases[name]]
     56 
     57     return name
     58 
     59 # 画网络图
     60 
     61 def show_graph(graph, layout='spring_layout'):
     62 
     63     # 使用 Spring Layout 布局,类似中心放射状
     64 
     65     if layout == 'circular_layout':
     66 
     67         positions=nx.circular_layout(graph)
     68 
     69     else:
     70 
     71         positions=nx.spring_layout(graph)
     72 
     73     # 设置网络图中的节点大小,大小与 pagerank 值相关,因为 pagerank 值很小所以需要 *20000
     74 
     75     nodesize = [x['pagerank']*20000 for v,x in graph.nodes(data=True)]
     76 
     77     # 设置网络图中的边长度
     78 
     79     edgesize = [np.sqrt(e[2]['weight']) for e in graph.edges(data=True)]
     80 
     81     # 绘制节点
     82 
     83     nx.draw_networkx_nodes(graph, positions, node_size=nodesize, alpha=0.4)
     84 
     85     # 绘制边
     86 
     87     nx.draw_networkx_edges(graph, positions, edge_size=edgesize, alpha=0.2)
     88 
     89     # 绘制节点的 label
     90 
     91     nx.draw_networkx_labels(graph, positions, font_size=10)
     92 
     93     # 输出希拉里邮件中的所有人物关系图
     94 
     95     plt.show()
     96 
     97 # 将寄件人和收件人的姓名进行规范化
     98 
     99 emails.MetadataFrom = emails.MetadataFrom.apply(unify_name)
    100 
    101 emails.MetadataTo = emails.MetadataTo.apply(unify_name)
    102 
    103 # 设置遍的权重等于发邮件的次数
    104 
    105 edges_weights_temp = defaultdict(list)
    106 
    107 for row in zip(emails.MetadataFrom, emails.MetadataTo, emails.RawText):
    108 
    109     temp = (row[0], row[1])
    110 
    111     if temp not in edges_weights_temp:
    112 
    113         edges_weights_temp[temp] = 1
    114 
    115     else:
    116 
    117         edges_weights_temp[temp] = edges_weights_temp[temp] + 1
    118 
    119 # 转化格式 (from, to), weight => from, to, weight
    120 
    121 edges_weights = [(key[0], key[1], val) for key, val in edges_weights_temp.items()]
    122 
    123 # 创建一个有向图
    124 
    125 graph = nx.DiGraph()
    126 
    127 # 设置有向图中的路径及权重 (from, to, weight)
    128 
    129 graph.add_weighted_edges_from(edges_weights)
    130 
    131 # 计算每个节点(人)的 PR 值,并作为节点的 pagerank 属性
    132 
    133 pagerank = nx.pagerank(graph)
    134 
    135 # 将 pagerank 数值作为节点的属性
    136 
    137 nx.set_node_attributes(graph, name = 'pagerank', values=pagerank)
    138 
    139 # 画网络图
    140 
    141 show_graph(graph)
    142 
    143  
    144 
    145 # 将完整的图谱进行精简
    146 
    147 # 设置 PR 值的阈值,筛选大于阈值的重要核心节点
    148 
    149 pagerank_threshold = 0.005
    150 
    151 # 复制一份计算好的网络图
    152 
    153 small_graph = graph.copy()
    154 
    155 # 剪掉 PR 值小于 pagerank_threshold 的节点
    156 
    157 for n, p_rank in graph.nodes(data=True):
    158 
    159     if p_rank['pagerank'] < pagerank_threshold:
    160 
    161         small_graph.remove_node(n)
    162 
    163 # 画网络图, 采用 circular_layout 布局让筛选出来的点组成一个圆
    164 
    165 show_graph(small_graph, 'circular_layout')

    复制代码

     

    运行结果如下:

    针对代码中的几个模块我做个简单的说明:

    1. 函数定义

    人物的名称需要统一,因此我设置了 unify_name 函数,同时设置了 show_graph 函数将网络图可视化。NetworkX 提供了多种可视化布局,这里我使用 spring_layout 布局,也就是呈中心放射状。

    除了 spring_layout 外,NetworkX 还有另外三种可视化布局,circular_layout(在一个圆环上均匀分布节点),random_layout(随机分布节点 ),shell_layout(节点都在同心圆上)。

    2. 计算边权重

    邮件的发送者和接收者的邮件往来可能不止一次,我们需要用两者之间邮件往来的次数计算这两者之间边的权重,所以我用 edges_weights_temp 数组存储权重。而上面介绍过在 NetworkX 中添加权重边(即使用 add_weighted_edges_from 函数)的时候,接受的是 u、v、w 的三元数组,因此我们还需要对格式进行转换,具体转换方式见代码。

    3.PR 值计算及筛选

    我使用 nx.pagerank(graph) 计算了节点的 PR 值。由于节点数量很多,我们设置了 PR 值阈值,即 pagerank_threshold=0.005,然后遍历节点,删除小于 PR 值阈值的节点,形成新的图 small_graph,最后对 small_graph 进行可视化(对应运行结果的第二张图)。

    更多相关内容
  • 具有时变传送的PageRank动态系统 简而言之,是一个用于计算动态pagerank的库。 有关更多详细信息,请参见[1]和[2]。 Ryan Rossi和David Gleich: ,网络图的算法和模型,第1卷。 LNCS的7323,第126-137页。 ...
  • PageRank算法R语言实现

    2021-03-03 23:03:55
    总结下来,还是感叹PageRank的神奇!改变世界的算法,PageRankPageRank是Google专有的算法,用于衡量特定网页相对于搜索引擎索引中的其他网页而言的重要程度。它由LarryPage和SergeyBrin在20世纪90年代后期发明。...
  • matlab实现pagerank

    2021-12-01 20:48:40
    matlab实现大型网络pagerank排序,数据挖掘实验成果,注释详细,附带操作步骤图
  • pagerank matlab代码网页排名 计算有向图的每个节点的页面排名。 ** 问题 1 ** 问题 1(5 分):简单的 PageRank 分数 使用您选择的任何编程语言(C/C++、Python、Java、MatLab、R 等)编写一个程序来计算输入网络图...
  • pagerank.zip

    2021-02-18 19:06:24
    使用java编写mapreduce实现pagerank算法,这里使用了web-Google.txt文件
  • 详细介绍了PageRank算法 PageRank算法优缺点 优点: 是一个与查询无关的静态算法,所有网页的PageRank值通过离线计算获得;有效减少在线查询时的计算量,极大降低了查询响应时间。 缺点: 1)人们的查询具有主题...
  • pagerank算法讲解.ppt

    2020-03-24 12:12:52
    PageRank是一种在搜索引擎中根据网页之间相互的链接关系计算网页排名的技术。PageRank是Google用来标识网页的等级或重要性的一种方法。其级别从1到10级,PR值越高说明该网页越受欢迎(越重要)。
  • 南开大学大数据课程大作业一 :PageRank算法代码
  • ##MapReduce 编程:使用 hadoop 计算维基百科文章的内部 PageRank。 本课程将向您介绍编程和数据操作的MapReduce模型。 它将提供分析真实数据源的有限实践经验:。 ###数据: 出于本次作业的目的,您已获得一...
  • PageRank_pageRank_python_

    2021-10-04 09:42:50
    计算大规模网络结点的PageRank值,python实现
  • pagerank:页面排名算法

    2021-06-08 21:58:23
    Google 的 PageRank(100 分) 如下所述实施 Google PageRank 算法。 此问题的输入将是通过邻接列表表示表示的图。 将使用的命令行界面如下。 三个参数中的前两个保存整数值; 最后一个参数是文件名。 % ./pagerank...
  • 本文基于有向加权复杂网络模型,借鉴PageRank排名算法,并结合复杂网络节点重要性评估特点,提出节点重要性评估的新指标―――DWCN - NodeRank和相应评估方法,该指标既反映出节点局部连接的特性,又从全局体现了有向加权...
  • 此文件夹包含4个MATLAB代码,用于计算双工网络和任意层数的网络的功能多路复用PageRank: functionalPageRank_duplex.m 在给定影响向量z的情况下,计算双工网络的功能多路复用PageRank fPR.m 计算影响向量的所有值的...
  • PageRank算法;一.Pagerank定义及终点自连接点的概念;1.早期搜索引擎的弊端; Pagerank思想 被越多优质的网页所指的网页它是优质的概率就越大; Pagerank是一个函数它对Web中的每个网页赋予一个实数值它的意图在于网页...
  • pagerank - 加权PageRank算法Go实现
  • 分布式随机PageRank算法的收敛性
  • gem pagerank为您提供了计算pagerank的方法。 安装 将此行添加到您的应用程序的Gemfile中: gem 'pagerank' 然后执行: $ bundle 或将其自己安装为: $ gem install pagerank 用法 待办事项:在此处写下使用...
  • PageRank对网页排名的算法,曾是Google发家致富的法宝。以前虽然有实验过,但理解还是不透彻,这几天又看了一下,这里总结一下PageRank算法的基本原理。PageRank的Page可是认为是网页,表示网页排名,也可以认为是...
  • 浅析PageRank算法

    2019-07-02 15:47:35
    很早就对Google的PageRank算法很感兴趣,但一直没有深究,只有个轮廓性的概念。前几天趁团队outing 的机会,在动车上看了一些相关的资料(PS:在动车上看看书真是一种享受),趁热打铁,将所看的东西 整理成此文。 ...
  • Pagerank实验.zip

    2020-06-30 18:43:58
    实时大数据分析Pagerank 算法 源代码,报告+数据集 根据网页链接数据集“Web-google.txt”,利用“抽税”法计算网页的PageRank排名;
  • pagerank数据集.rar

    2019-05-23 12:31:33
    Googleweb的pagerank算法测试数据集,每一行都是仿URL的数据
  • 南开大学大数据课程大作业一:PageRank算法(分块)
  • Google的PageRank算法的简单实现。 使用NodeJS服务器存储邻接列表状态,并使用Python计算每个页面的排名。 免责声明:我并不声称自己是PageRank,其用例等方面的专家。这是我追求的一个有趣的项目,目的是了解...
  • 因此,其他加速PageRank计算的方法逐渐得到研究者的重视。文中首先对布尔搜索引擎、向量空间模型引擎、概率模型搜索引擎、元搜索引擎等基本搜索引擎模型进行综述,总结各基本搜索引擎模型的特征和优缺点。文中立足于...
  • pagerank matlab代码多路PageRank 此存储库包含: 'multiplexPageRank.m' 一个用于计算 Multiplex PageRank 的 matlab 函数,可以根据自由软件基金会发布的 GNU 通用公共许可证的条款重新分发和/或修改代码,该许可...
  • Pagerank算法

    2018-10-29 21:06:42
    该算法用于谷歌中计算网络节点重要性的算法,也可将其与其它算法结合使用,比较综合。
  • 三种方法对web-Google.txt进行pagerank计算,1.python以稀疏矩阵方法实现单机计算谷歌网页数据计算pageRank值2.调用networkx库3.调用networkx库,其中pagerank自己实现。
  • Go用法包主要导入中的pagerank加权PageRank实现(“ fmt”“ github.com/alixaxel/pagerank”)func main(){graph:= pagerank.NewGraph()graph.Link(1,2,1.0)graph.Link (1、3、2.0)pagerank Go用法包...
  • pagerank算法

    2018-05-15 11:27:54
    改进的pagerank排序,基于概率转移矩阵和责任测度矩阵,具有较好的排序结果。

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 20,179
精华内容 8,071
关键字:

pageRank