重启随机游走算法Random Walk with Restart (RWR)

最近找了一下RWR算法的介绍，发现中文的blog全是互相抄的，讲的不是很清楚。最后发现medium上面有个博文写的还不错，下面抄了一点。

https://medium.com/@chaitanya_bhatia/random-walk-with-restart-and-its-applications-f53d7c98cb9

最基本的随机游走：给定一个连接图，以及图中每个节点搏迹余的转移概率，目的就是找到从某个起点开始随机走动，最终停在每个点的概率。

重启随机游走的区别就是在每次游走之后有一定概率回到起点。

先看一下公式：

的大小在0,1之间， 为转移概率矩阵， 是从节点 到节点 的概率。 是起点向量，i为起点则 。r是终点向量。

下面来解释这个公式

当e为起点，下次移动的落点为 的概率可以用下面这个公式得到：

为 的第i行。所以如果没有重启机制的话，k次移动之后的落点为 的概率是：

如果有重启机制就只能用递推公式：

如果假定随着移动次数增加， 最终会收敛（事实也是如此），递推公式就可以写基滚成最开始给出的那个公式：

暴力一点就是迭代直到收敛。

或者求逆州段矩阵

得到

感觉基本上都是把落点概率作为一种相似度度量。

Image segmentation

图像分割中，每个像素作为图中的节点，转移概率为像素之间的相似度，以某个像素为起点游走，落点概率高的可以作为一个cluster。

类似的应用还有Community detection， Recommender Systems等。

其中的分析和可视化是用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元素中展示可视化。

---