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等。
随机游走本来是“物理上布朗运动”相关的分子，还是微观粒子的运动形成的一个模型。
现在过多的谈到随机游走假说是数理金融中最重要的假设，它把有效市场的思想与物理学中的布朗运动联系起来，由此而来的一整套的随机数学方法成为构建数理金融的基石。（其研究的机理已经在股票研究中应用很广泛） 随机游走模型的提出是与证券价格的变动模式紧密联系在一起的。最早使用统计方法分析收益率的著作是在 1900年由路易·巴舍利耶（Louis Bachelier）发表的，他把用于分析赌博的方法用于股票、债券、期货和期权。在巴舍利耶的论文中，其具有开拓性的贡献就在于认识到随机游走过程是布 朗运动。1953年，英国统计学家肯德尔在应用时间序列分析研究股票价格波动并试图得出股票价格波动的模式时，得到了一个令人大感意外的结论：股票价格没 有任何规律可寻，它就象“一个醉汉走步一样，几乎宛若机会之魔每周仍出一个随机数字，把它加在目前的价格上，以此决定下一周的价格。”即股价遵循的是随机 游走规律。
随机游走模型有两种，其数学表达式为 ：
Y t =Y t-1 +e t ①
Y t =α+Y t-1 +e t ②
式中：
Y t 是时间序列（用股票价格或股票价格的自然对数表示）；
e t 是随机项，E(e t )=0；Var(e t )=σ 2 ；
α是常数项。
模型①称为“零漂移的随机游走模型”，即当天的股票价格是在前一天价格的基础上进行随机变动。股票价格差全部包含在随机项 e t 中。
模型②称为“α漂移的随机游走模型”，即当天的股票价格是在前一天价格的基础上先进行一个固定的α漂移，再进行随机变动。股票价格差包括两部分，一部分是固定变动α，另一部分也是随机项 e t 。
由以上随机游走模型可以看出，证券价格的时间序列将呈现随机状态，不会表现出某种可观测或统计的确定趋势。即证券价格的变动是不可预测的，这恰恰是随机 游走模型所揭示的证券价格变动 规律 的中心思想。那么，随机游走模型下所确定的证券价格的这一变动模式与资本市场的效率性之间是什么关系呢？随机变动的证券价格，不仅不是市场非理性的证据， 而正是众多理性的投资者开发有关信息，并对其做出反映的结果。事实上，如果证券价格的变动是可以预测的，那才真正说明市场的无效率和非理性。也就是说，若 证券市场是有效率的，证券价格应当真正符合随机游走模型。
t）=0，而这正是独立随机过程所必须的条件。然而当H≠1/2时，不管t取何值，C（t）≠0。分数布朗运动的这一特征，导致了状态持续性或逆状态持续性。
当H>1/2时，存在状态持续性，即在某一时刻t以前存在上升（或下降）趋势隐含着在时刻t以后总体上也存在着上升（或下降）的趋势；反之，当H<1/2 时存在逆状态持续性，即在某一时刻t以前存在上升（或下降）趋势隐含着在时刻t以后总体上也存在着下降（或上升）的趋势
进一步地，应用R/S分析法，可以确定信息的两个重要方面，Hurst指数H和平均的周期长度。周期的存在对于进一步的讨论分析具有重要影响。当H≠1 /2时，概率分布不是正态分布；当1/2<H<1时，时间序列是分形。分维时间序列不同于随机游走，它是有偏的随机过程，其偏离的程度取决于H大于1/2 的程度，并且随着H逐步逼近1状态持续性逐步增强。
值得指出的是，R/S分析法是十分有效的工具，不必假定潜在的分布是高斯分布。H=1/2并不能说明时间序列是一个高斯随机游走，仅表明不存在长期记忆。 如果随机游走不再适用，那么许多数量分析的方法将失去效用，尤其是CAPM和以方差或波动程度度量的风险概念。
通过以上的论述，得到下列基本结论：
1．对有效市场假说，α必须始终等于2；而对分形市场分析，α可以在1到2之间变化。这是有效市场假说与分形市场分析对市场特性认识的主要区别。正是由于α的分数维性质充分反映了市场本身所具有的特性
2．分形市场分析不必依赖于独立、正态或方差有限的假设。
3．应用R/S分析法，可以确定信息的两个重要方面，Hurst指数H和平均的周期长度。
4．公众对于信息以非线性方式作出反应，因而有偏的随机游走是市场的常态，表现为分数布朗运动。
5．对于随机游走的偏离程度取决于指数H。
本文从对EMH的产生及其发展讨论出发，从分形的角度探讨市场特性的分形市场分析方法及其所反映的市场特性，推广了资本市场理论，认为市场是分形的，服 从分数布朗运动，即有偏的随机游走，其研究方法可以采用R/S分析法。公众对于信息以非线性的方式作出反应，因而呈现出对信息的不一致性消化、吸收，导致 对随机游走的偏离，并表现为市场的常态。
其中的分析和可视化是用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元素中展示可视化。
