pagerank算法应用

1. 基于社区发现算法和图分析Neo4j解读《权力的游戏》下篇

其中的分析和可视化是用Gephi做的，Gephi是非常流行的图分析工具。但作者觉得使用Neo4j来实现更有趣。

节点中心度
节点中心度给出网络中节点的重要性的相对度量。有许多不同的方式来度量中心度，每种方式都代表不同类型的“重要性”。

度中心性(Degree Centrality)
度中心性是最简单度量，即为某个节点在网络中的联结数。在《权力的游戏》的图中，某个角色的度中心性是指该角色接触的其他角色数。作者使用Cypher计算度中心性：
MATCH (c:Character)-[:INTERACTS]- RETURN c.name AS character, count(*) AS degree ORDER BY degree DESC

character
degree

Tyrion
36

Jon
26

Sansa
26

Robb
25

Jaime
24

Tywin
22

Cersei
20

Arya
19

Joffrey
18

Robert
18

从上面可以发现，在《权力的游戏》网络中提利昂·兰尼斯特（Tyrion）和最多的角色有接触。鉴于他的心计，我们觉得这是有道理的。

加权度中心性（Weighted Degree Centrality）
作者存储一对角色接触的次数作为 INTERACTS 关系的 weight 属性。对该角色的 INTERACTS 关系的所有 weight 相加得到加权度中心性。作者使用Cypher计算所有角色的这个度量：
MATCH (c:Character)-[r:INTERACTS]- RETURN c.name AS character, sum(r.weight) AS weightedDegree ORDER BY weightedDegree DESC

character
weightedDegree

Tyrion
551

Jon
442

Sansa
383

Jaime
372

Bran
344

Robb
342

Samwell
282

Arya
269

Joffrey
255

Daenerys
232

介数中心性（Betweenness Centrality）
介数中心性：在网络中，一个节点的介数中心性是指其它两个节点的所有最短路径都经过这个节点，则这些所有最短路径数即为此节点的介数中心性。介数中心性是一种重要的度量，因为它可以鉴别出网络中的“信息中间人”或者网络聚类后的联结点。

图6中红色节点是具有高的介数中心性，网络聚类的联结点。
为了计算介数中心性，作者使用Neo4j 3.x或者apoc库。安装apoc后能用Cypher调用其170+的程序：
MATCH (c:Character) WITH collect(c) AS charactersCALL apoc.algo.betweenness(['INTERACTS'], characters, 'BOTH') YIELD node, scoreSET node.betweenness = scoreRETURN node.name AS name, score ORDER BY score DESC

name
score

Jon
1279.7533534055322

Robert
1165.6025171231624

Tyrion
1101.3849724234349

Daenerys
874.8372110508583

Robb
706.5572832464792

Sansa
705.1985623519137

Stannis
571.5247305125714

Jaime
556.1852522889822

Arya
443.01358430043337

Tywin
364.7212195528086

紧度中心性（Closeness centrality）
紧度中心性是指到网络中所有其他角色的平均距离的倒数。在图中，具有高紧度中心性的节点在聚类社区之间被高度联结，但在社区之外不一定是高度联结的。

图7 ：网络中具有高紧度中心性的节点被其它节点高度联结
MATCH (c:Character) WITH collect(c) AS charactersCALL apoc.algo.closeness(['INTERACTS'], characters, 'BOTH') YIELD node, scoreRETURN node.name AS name, score ORDER BY score DESC

name
score

Tyrion
0.004830917874396135

Sansa
0.004807692307692308

Robert
0.0047169811320754715

Robb
0.004608294930875576

Arya
0.0045871559633027525

Jaime
0.004524886877828055

Stannis
0.004524886877828055

Jon
0.004524886877828055

Tywin
0.004424778761061947

Eddard
0.004347826086956522

使用python-igraph
Neo4j与其它工具（比如，R和Python数据科学工具）完美结合。我们继续使用apoc运行 PageRank和社区发现（community detection）算法。这里接着使用python-igraph计算分析。Python-igraph移植自R的igraph图形分析库。 使用 pip install python-igraph 安装它。

从Neo4j构建一个igraph实例
为了在《权力的游戏》的数据的图分析中使用igraph，首先需要从Neo4j拉取数据，用Python建立igraph实例。作者使用 Neo4j 的Python驱动库py2neo。我们能直接传入Py2neo查询结果对象到igraph的 TupleList 构造器，创建igraph实例：
from py2neo import Graphfrom igraph import Graph as IGraph graph = Graph query = ''' MATCH (c1:Character)-[r:INTERACTS]->(c2:Character) RETURN c1.name, c2.name, r.weight AS weight '''ig = IGraph.TupleList(graph.run(query), weights=True)

现在有了igraph对象，可以运行igraph实现的各种图算法来。

PageRank
作者使用igraph运行的第一个算法是PageRank。PageRank算法源自Google的网页排名。它是一种特征向量中心性(eigenvector centrality)算法。
在igraph实例中运行PageRank算法，然后把结果写回Neo4j，在角色节点创建一个pagerank属性存储igraph计算的值：
pg = ig.pagerank pgvs = for p in zip(ig.vs, pg): print(p) pgvs.append({"name": p[0]["name"], "pg": p[1]}) pgvs write_clusters_query = ''' UNWIND {nodes} AS n MATCH (c:Character) WHERE c.name = n.name SET c.pagerank = n.pg '''graph.run(write_clusters_query, nodes=pgvs)

现在可以在Neo4j的图中查询最高PageRank值的节点：
MATCH (n:Character) RETURN n.name AS name, n.pagerank AS pagerank ORDER BY pagerank DESC LIMIT 10

name
pagerank

Tyrion
0.042884981999963316

Jon
0.03582869669163558

Robb
0.03017114665594764

Sansa
0.030009716660108578

Daenerys
0.02881425425830273

Jaime
0.028727587587471206

Tywin
0.02570016262642541

Robert
0.022292016521362864

Cersei
0.022287327589773507

Arya
0.022050209663844467

社区发现（Community detection）

图8
社区发现算法用来找出图中的社区聚类。作者使用igraph实现的随机游走算法（ walktrap）来找到在社区中频繁有接触的角色社区，在社区之外角色不怎么接触。
在igraph中运行随机游走的社区发现算法，然后把社区发现的结果导入Neo4j，其中每个角色所属的社区用一个整数来表示：
clusters = IGraph.community_walktrap(ig, weights="weight").as_clustering nodes = [{"name": node["name"]} for node in ig.vs]for node in nodes: idx = ig.vs.find(name=node["name"]).index node["community"] = clusters.membership[idx] write_clusters_query = ''' UNWIND {nodes} AS n MATCH (c:Character) WHERE c.name = n.name SET c.community = toInt(n.community) '''graph.run(write_clusters_query, nodes=nodes)

我们能在Neo4j中查询有多少个社区以及每个社区的成员数：
MATCH (c:Character) WITH c.community AS cluster, collect(c.name) AS members RETURN cluster, members ORDER BY cluster ASC

cluster
members

0
[Aemon, Alliser, Craster, Eddison, Gilly, Janos, Jon, Mance, Rattleshirt, Samwell, Val, Ygritte, Grenn, Karl, Bowen, Dalla, Orell, Qhorin, Styr]

1
[Aerys, Amory, Balon, Brienne, Bronn, Cersei, Gregor, Jaime, Joffrey, Jon Arryn, Kevan, Loras, Lysa, Meryn, Myrcella, Oberyn, Podrick, Renly, Robert, Robert Arryn, Sansa, Shae, Tommen, Tyrion, Tywin, Varys, Walton, Petyr, Elia, Ilyn, Pycelle, Qyburn, Margaery, Olenna, Marillion, Ellaria, Mace, Chataya, Doran]

2
[Arya, Beric, Eddard, Gendry, Sandor, Anguy, Thoros]

3
[Brynden, Catelyn, Edmure, Hoster, Lothar, Rickard, Robb, Roose, Walder, Jeyne, Roslin, Ramsay]

4
[Bran, Hodor, Jojen, Luwin, Meera, Rickon, Nan, Theon]

5
[Belwas, Daario, Daenerys, Irri, Jorah, Missandei, Rhaegar, Viserys, Barristan, Illyrio, Drogo, Aegon, Kraznys, Rakharo, Worm]

6
[Davos, Melisandre, Shireen, Stannis, Cressen, Salladhor]

7
[Lancel]

角色“大合影”
《权力的游戏》的权力图。节点的大小正比于介数中心性，颜色表示社区（由随机游走算法获得），边的厚度正比于两节点接触的次数。现在已经计算好这些图的分析数据，让我们对其进行可视化，让数据看起来更有意义。
Neo4j自带浏览器可以对Cypher查询的结果进行很好的可视化，但如果我们想把可视化好的图嵌入到其它应用中，可以使用Javascript可视化库Vis.js。从Neo4j拉取数据，用Vis.js的neovis.js构建可视化图。Neovis.js提供简单的API配置，例如：
var config = { container_id: "viz", server_url: "localhost", labels: { "Character": "name" }, label_size: { "Character": "betweenness" }, relationships: { "INTERACTS": }, relationship_thickness: { "INTERACTS": "weight" }, cluster_labels: { "Character": "community" } }; var viz = new NeoVis(config); viz.render;

其中：
节点带有标签Character，属性name；

节点的大小正比于betweenness属性；

可视化中包括INTERACTS关系；

关系的厚度正比于weight属性；

节点的颜色是根据网络中社区community属性决定；

从本地服务器localhost拉取Neo4j的数据；

在一个id为viz的DOM元素中展示可视化。

2. 数据挖掘算法 PageRank

数据挖掘算法：PageRank
1. 引言
PageRank是Sergey Brin与Larry Page于1998年在WWW7会议上提出来的，用来解决链接分析中网页排名的问题。在衡量一个网页的排名，直觉告诉我们：
1、当一个网页被更多网页所链接时，其排名会越靠前；
2、排名高的网页应具有更大的表决权，即当一个网页被排名高的网页所链接时，其重要性也应对应提高。
对于这两个直觉，PageRank算法所建立的模型非常简单：一个网页的排名等于所有链接到该网页的网页的加权排名之和：

PRi表示第i个网页的PageRank值，用以衡量每一个网页的排名；若排名越高，则其PageRank值越大。
网页之间的链接关系可以表示成一个有向图代表了网页j链接到了网页i；Oj为网页j的出度，也可看作网页j的外链数（ the number of out-links）。
假定P=(PR1,PR2,?,PRn)T为n维PageRank值向量，A为有向图G所对应的转移矩阵，

n个等式(1)可改写为矩阵相乘：

但是，为了获得某个网页的排名，而需要知道其他网页的排名，这不就等同于“是先有鸡还是先有蛋”的问题了么？幸运的是，PageRank采用power iteration方法破解了这个问题怪圈。欲知详情，请看下节分解。
2. 求解
为了对上述及以下求解过程有个直观的了解，我们先来看一个例子，网页链接关系图如下图所示：

那么，矩阵A即为

所谓power iteration，是指先给定一个P的初始值P0，然后通过多轮迭代求解:

最后收敛于||Pk?Pk?1||<ξ，即差别小于某个阈值。
我们发现式子(2)为一个特征方程（characteristic equation），并且解P是当特征值（eigenvalue）为1时的特征向量（eigenvector）。为了满足(2)是有解的，则矩阵A应满足如下三个性质：
1、stochastic matrix，则行至少存在一个非零值，即必须存在一个外链接（没有外链接的网页被称为dangling pages）；
2、不可约（irrecible），即矩阵A所对应的有向图G必须是强连通的，对于任意两个节点u,v∈V，存在一个从u到v的路径；
3、非周期性（aperiodic），即每个节点存在自回路。
显然，一般情况下矩阵A这三个性质均不满足。为了满足性质stochastic matrix，可以把全为0的行替换为e/n，其中e为单位向量；同时为了满足性质不可约、非周期，需要做平滑处理：

其中，d为 damping factor，常置为0与1之间的一个常数；E为单位阵。那么，式子(1)被改写为

3. pagerrank算法有何应用

．017 基于中心性和PageRank的网页综合评分方法 （1．西南交通大学信息科学与技术学院，四川成都610031；2．成都市公安局科技处，四川成都610017；3．西南财经大学经济信息工程学院，四川成都610074） 摘要：为准确、高效地对网页进行评分，提出了一种基于中心性（结点度、居间度和紧密度）和PageRank算法 的网页评分方法CentralRank．它采用PageRank算法计算网页分数，借助中心性度量的方法计算页面在Web社会 网络中的重要性．为了验证CentralRank的性能优势，设计了一个网页抓取器，可利用该抓取器自动、准确地下载 网页信息．该网页抓取器集成了网络信息采集、页面内容分析和页面消重3项技术．基于大量真实数据的实验结 果表明：CentralRank在保证网页评分时间性能的前提下，比单纯基于中心性的网页评分算法和PageRank算法更 准确、有效，预测准确性分别提高约14．2％和7．5％． 关键词：社会网络分析；Web社会网络；中心性；PageRank算法；网页评分 中图分类号：TP311．13 文献标志码：A Hybrid Page Scoring Algorithm Based PageRankqtAO Shaojiel，PENG Jin92，H Tianruil，LI Iton91，12 Taiyon93，WANG Cha01 （1．School InformationScience Technology，SouthwestJiaotong University，Cheng 610031，China； 2．Department Technology，ChengMunicipal Public Security Bureau，Cheng 610017，China； 3．School EconomicInformation Engineering，soutllwtem University Economics，Cheng610074， China） Abst豫ct：In order scor

4. 对pagerank算法的整理

1、首先先大致介绍下pagerank，pagerank是Google排名算法法则的一部分，是用来标记网页的等级的一种方法，也是用来衡量一个网页好坏的唯一标准。pagerank他采用PR值来划分网页的受欢迎度，PR值越高，则表名受欢迎度越高，PR最高为10，最低为0，一般PR达到4，则表名网站已经不错了。PR为4的网站比PR为3的网站不是单纯的好一点来形容，他是一种里氏震级的形式来形容的，就好比地震的等级，是指数刻度增长的，因此可以想象PR为10的网站是一种什么程度。因为这个算法是Google提出的，因此Google将自己的网站PR值设置为10，所以想要自己的网站PR达到10，是非常难的，如果你的网站可以达到Google的水平。

2、介绍完了pagerank是一个什么东西后，我们就来介绍一下pagerank如何计算的。

2.1、用个例子来说明下PageRank算法

在网页A中有B、C、D三个链接，在网页B中有A、C两个个链接，在网页C中有D链接，网页D中有A、B两个链接。（可以看出这个图是强链接的，任何一个节点都可以到达另一个节点）。

我们假设每一个链接访问的概率是相同的，为了计算方便我们将每一个网页的PageRank设置为1。

先给出计算公式

PR(pj) 表示网页 pj 的 PageRank 得分，L(pj) 表示网页 pj 的出链接数量，1/L(pj) 就表示从网页 pj 跳转到 pi 的概率。

所以我们来计算第一次迭代后的PR值：

PR(A)=PR(B)/2+PR(D)/2

PR(B)=PR(A)/3+PR(D)/2

PR(C)=PR(A)/3+PR(B)/2

PR(D)=PR(A)/3+PR(C)/1

PR(A)+PR(B)+PR(C)+PR(D)=1

PR(A)=0.265, PR(B)=0.235, PR(C)=0.206, PR(D)=0.294

通过上面的公式在不断的进行迭代，可以得到一个收敛值，大概是在（0.265，0.235，2.206，0.294）附近。

2.2看完公式之后，我们来考虑俩种特殊的情况

2.2.1终止问题

上面过程要满足收敛性，需要具备一个条件：图是强连通的，即从任意网页可以到达其他任意网页。

互联网中存在网页不满足强连通的特性，因为有一些网页不指向任何网页，按照上面公式迭代计算下去，导致前面累计得到的转移概率被清零，最终得到的概率分布向量所有元素几乎都为0。

假设把上面图中C到D的链接丢掉，C变成了一个终止点，得到下面这个图：

转移矩阵M为：

不断迭代，最终得到所有元素都为0。

2.2.2 、陷阱问题

陷阱问题：是指有些网页不存在指向其他网页的链接，但存在指向自己的链接。比如下面这个图：

这种情况下，PageRank算法不断迭代会导致概率分布值全部转移到c网页上，这使得其他网页的概率分布值为0，从而整个网页排名就失去了意义。如果按照上面图则对应的转移矩阵M为：

不断迭代，最终得倒如下结果：

为了解决终止点问题和陷阱问题 ，下面需要对算法进行改进。假设选取下一个跳转页面时，既不选 当前页面 ，也不选 当前网页上的其他链接 ，而是以一定概率跳转到其他不相关网页，那么上面两个问题就能得到很好的解决，这就是 完整 PageRank 算法思想 。

N表示的时网页链接的个数，α表示不进行随机跳转的概率。

利用上面公式继续迭代下去，直到收敛，得到最终rank值。

PageRank 的计算是采样迭代法实现的：一开始所有网页结点的初始 PageRank 值都可以设置为某个相同的数，例如 1，然后我们通过上面这个公式，得到每个结点新的 PageRank 值。每当一张网页的 PageRank 发生了改变，它也会影响它的出链接所指向的网页，因此我们可以再次使用这个公式，循环地修正每个网页结点的值。由于这是一个马尔科夫过程，所以我们能从理论上证明，所有网页的 PageRank 最终会达到一个稳定的数值。整个证明过程很复杂，这里我们只需要知道这个迭代计算的过程就行了。

3、基于本文主题叫做数学建模之美，也是一篇读后感，所以我们还是写一下感受吧。

这个算法的优美之处，就在于巧妙地将网页内容的好坏，根据链接数的形式，用PR值进行了排名，它不仅激发网页越做越好，也促进了各个网页之间的联系。

同时在结构方面，他将一个复杂的问题，进行了简单的类比，用图结构的形式代替链接的形式，用户访问的顺序，也就是节点的走向。所以数学之美就在于他是非常的简单，用简单的原理，向我们展示了一个复杂的问题。

5. pagerank算法可以用来干什么

目前很多重要的链接分析算法都是在PageRank算法基础上衍生出来的。PageRank是Google用于用来标识网页的等级/重要性的一种方法,是Google用来衡量一个网

6. pagerank算法是什么

PageRank算法是谷歌曾经独步天下的“倚天剑”，该算法由Larry Page和Sergey Brin在斯坦福大学读研时发明的。PageRank，网页排名，又称为网页级别，Google左侧排名，是一种由网页之间相互的超链接计算的技术，作为网页排名的要素之一。

Google用它来体现网页的相关性和重要性，在搜索引擎优化操作中是经常被用来评估网页优化的成效因素之一。

PageRank的思想

PageRank认为，一个节点对系统施加影响的结果，就是与它相连的节点也具有一定的影响力。PageRank的想法看起来很简单，实际上给我们留了一个难题：各个节点的PR值计算是存在依赖的，得先计算出PR(node1)才能计算PR(node0)。

也就是说需要首先把所有未被引用的节点的PR值算出来(一般默认是1.0)；然后把以它们为源头、只和源头相连、距离为1的节点的PR值算出来；接着计算距离为2、只和已经具有PR值节点相连的，所有节点的PR值；直到所有的节点都有PR值为止。这个计算方法复杂度比较高，不实用。

7. PageRank算法实现好友推荐(算法原理)

对于社交系统与电商网站，推荐系统占有很重要的位置，当数据量越来越大的时候，用户无法确定该选择什么商品，因此在电商系统中需要按照兴趣或者相似度给用户推荐相应的商品。相应的，在一个大型社交网络平台中，对于一些用户，我们希望推荐一些知名度较高，活跃度较高或者感兴趣的用户，比如一些明星，歌手，演员等等。在社交网络中，PageRank算法有着广泛的应用，因此，本篇文章主要介绍其原理。

对于大部分社交系统来说，如果只是简单的获取好友的信息远远不够，我们可以通过获取好友的好友的信息来扩展用户的朋友圈，使得信息量更加丰富，本项目中使用PageRank算法来完成二级邻居，然后按照Rank排序，选择Top5用户实现用户的好友的好友的推荐。

PageRank算法由Google的创始人拉里·佩奇和谢尔·布林于1998年发明.这项技术设计之初是为了体现网页的相关性和重要性,在搜索引擎优化操作中经常被用来评估网页优化的成效因素之一.

从技术上看,搜索引擎需要解决以下三个问题:

本质就是一个爬虫问题,通过爬虫获取整个互联网的数据

关键在于快速找到.

它的实现方式有: 倒排索引，签名文件，后缀树等。我们最熟悉的是 倒排索引 。(并不熟悉,以后有机会再看)

排序是Google的搜索引擎能够兴起的一个决定性因素。

对网页排序有很多种方式，我们来看三种：

就是原封不懂地把索引到的链接直接返回给用户，缺点就不说了，想找自己感兴趣的内容估计要费不少功夫。

这种方式是一种只从关键词出现的次数和位置进行排序的方法。该方法以一个关键词与网页的相关度大小作为排序标准，而关键词在网页的相关度大小作为排序标准，而关键词在网页中的相关度则由它在网页中出现的频次和位置两方面加权计算得出。

缺点也很明显，容易出现刷分的情况，整篇文章中大量地刷关键词就能提高排名。

真正找到计算网页自身质量的完美的数学模型是Google的创始人拉里佩奇和谢尔盖布林。 下一节讲一下原理。

我们模拟一个悠闲的上网者，上网者首先随机选择一个网页打开，然后在这个网页上呆了几分钟后，跳转到该网页所指向的链接，这样无所事事、漫无目的地在网页上跳来跳去，PageRank就是估计这个悠闲的上网者分布在各个网页上的概率，这个概率就代表这个网页的重要性.

PageRank主要基于两个重要的假设：

如果一篇文章被越来越多的人引用，那么这篇文章可能就是一篇经典之作，如果这篇文章引用了其他的论文，那么一定程度上这篇被引用的文章也是一篇很好的文章。应用到社交网络中，如果一个好友被更多的人关注，那么说明该好友有很高的知名度和活跃度，那么，我们可以将该好友推荐给用户。

基于这两个假设,我们可以总结出PageRank算法的核心:

如下图,可以更好的表达PageRank算法的思想:

由上图可知,每个页面将自己的一部分rank传递给某个页面，我们可以通过计算传递给某个页面的所有rank值的和来计算出它的rank值，当然，不可能是通过一次计算完成，我们刚开始可以给每个页面赋予一个初始rank值，比如 1/N(N为页面总数) ，通过迭代计算得到该页面的rank值。

迭代计算停止的条件为:

使用有向图表示:

这个例子中只有四个网页，如果当前在A网页，那么悠闲的上网者将会各以1/3的概率跳转到B、C、D，这里的3表示A有3条出链，如果一个网页有k条出链，那么跳转任意一个出链上的概率是1/k，同理D到B、C的概率各为1/2，而B到C的概率为0。

我们在做计算的时候会将该图表示成一个二维的矩阵，我们做一个转换，就会变成下图的矩阵形式。 M(i,j) 表示j节点指向i节点的概率 ，一般来说每列和为1。

生成的 转移矩阵 非常简单, 矩阵的每一列代表该顶点所代表的页面除以对应页面的出链数得到的 。

有了转移矩阵，我们可以来定义行向量 V ， V 的第i个分量记录 对应的Rank值，因此一次Rank的更新可以表示为：

在算法的第一轮计算中，我们假设上网者在每一个网页的概率都是相等的，即1/n，于是初试的概率分布就是一个所有值都为1/n的n维列向量 ，用 去右乘转移矩阵M，就得到了第一步之后上网者的概率分布向量 ,得到一个nX1的矩阵 ， 这个 一轮迭代计算出来的PageRank值 。下面是 的计算过程：

得到了 后，再用 去右乘M得到 ，一直下去，即 , 最终V会收敛 .

不断的迭代，最终得到结果.

但是在迭代计算中，我们需要考虑如下两大阻力： Dead End 和 Spider Trap ：

Dead End就是指一个页面只有入链但是没有出链，这时转移矩阵M的一列为零，导致最后结果为零。这时web不是强连通的，即存在某一类节点不指向别人，如下图的D。这个时候我们的算法就会出问题了，它不满足收敛性了。

为什么不满足收敛性了？

Spider Trap指页面的所有出链都指向自己，这样会使迭代结果中只有自己的页面的Rank值很高。其他页面的Rank值为零。

要克服上面两个问题，我们需要将迭代计算公式做如下转变。我们可以加入一个 随机跳转 机制.

即假设每个页面有很小概率拥有一个指向其他页面的链接。

表现出来就是：其他页面本来传递给一个页面的Rank值需要做一个折扣，作为补偿，可能需要一个页面指向该页面并且传递Rank值给该页面，该跳转的概率为β，因此表达式变为：

其中,N为页面总数; e 为一个N维且各个分量都是1的向量;β通过经验得知一般设为0.15.

此时的计算结果过程为:

有机会再写,先空着