注意，在算法中的asNode函数在新版使用中应该已经变为getNodeById，这种udf的定义方式与之前的example里面的join有很大的区别，也不同于需要关闭数据库的嵌入式编程以及类似于jdbc的服务器式编程。可以使用call dbms.functions() 来查看algo包里面定义了哪些udf，从而学习类似之前的Java与Cypher交互来获取值的接口。

1.2 马尔科夫过程

什么是马尔科夫过程？什么是马尔科夫链？？一直迭代至收敛？

马尔科夫过程指的是一类随机过程，该过程具有如下特性：在已知目前状态 (现在)的条件下，它未来的演变 (将来)不依赖于它以往的演变 ( 过去 ) 。在现实世界中，有很多过程都属于马尔可夫过程，例如布朗运动、谣言传播、游乐园游玩人数等。花丛中的一只蜜蜂的采蜜过程是马尔可夫过程的一个形象化的例子。

马尔可夫过程的条件概率仅仅与系统的当前状态相关，而与它的过去历史或未来状态，都是独立、不相关的。具备离散状态的马尔可夫过程，通常被称为马尔可夫链。

1.2.1 马尔科夫链细致平稳条件

首先，马尔科夫链要能收敛，需要满足以下条件：

可能的状态数是有限的。
状态间的转移概率需要固定不变。
从任意状态能够转变到任意状态。
不能是简单的循环，例如全是从x到y再从y到x

以上是马尔可夫链收敛的必要条件。

2 投影图模型

2.1 标签和关系类型进行投影

Neo4j的算法有很多时候并不需要在全局进行调用，所以我们可以通过使用label参数来描述节点来投影我们想要运行算法的子图，并使用关系类型来描述关系。

通用语法如下：

CALL algo.<name>('NodeLabel', "RelationshipType", {config})

如果我们想要投影包含底层Neo4j图中所有节点和关系的子图，我们可以通过传递null标签和关系类型的值来实现：

以下将在所有节点和关系上运行算法：

CALL algo.<name>(null, null)

2.1.1 大图投影

默认标签和关系类型投影具有20亿个节点和20亿个关系的限制，因此如果我们的项目图形大于此，我们需要使用巨大的图形投影。可以通过graph:'huge'在配置中进行设置来启用此功能。

通用调用语法是：

CALL algo.<name>('NodeLabel', "RelationshipType", {graph: "huge"})

2.2 Cypher投影

如果标签和关系类型投影没有足够的选择性来描述我们的子图来运行算法，我们可以使用Cypher语句来投影图的子集。使用node-statement和relationship-statement而不是节点标签和关系类型，并在config参数中说明graph:’cypher’。

只有在node-statement中描述了源节点和目标节点时，才会投影relationship-statement中描述的关系，否则将忽略它们。

Cypher投影使我们在描述我们想要分析的子图时更具表现力，但可能需要更长的时间来使用更复杂的密码查询来投影图。

通用调用语法是：


CALL algo.<name>(
  'MATCH (n) RETURN id(n) AS id',
  "MATCH (n)-->(m) RETURN id(n) AS source, id(m) AS target",
  {graph: "cypher"})

第一个查询MATCH (n) RETURN id(n) AS id返回节点ID。Cypher加载程序希望查询返回一个id字段。

第二个查询MATCH (n)-→(m) RETURN id(n) AS source, id(m) AS target返回在我们的投影图中具有它们之间关系的节点ID对。Cypher加载器期望查询返回source和target字段。

2.2.1 权重

除了这些语句中的ID之外，我们还可以返回属性值或权重（根据我们的配置）。我们通过返回可选weight字段来完成此操作。

以下将基于Cypher对节点和关系的投影在图表上运行algortihm，使用score每个关系的属性作为权重：


CALL algo.<name>(
  'MATCH (n) RETURN id(n) AS id',
  "MATCH (n)-[r]->(m) RETURN id(n) AS source, id(m) AS target, r.score AS weight",
  {graph: "cypher"})

2.2.2 示例用法

我们可以使用Cypher投影在DBpedia上运行PageRank算法，如以下示例所示。

以下内容将根据Cypher对节点和关系的投影在图形上运行PageRank算法：


CALL algo.pageRank(
  'MATCH (p:Page) RETURN id(p) as id',
  'MATCH (p1:Page)-[:Link]->(p2:Page) RETURN id(p1) as source, id(p2) as target',
  {graph:'cypher', iterations:5, write: true});

Cypher投影也可用于投影虚拟（非存储）图形。下面是一个示例，说明如何投影访问相同网页并在其上运行Louvain社区检测算法的人的无向图，使用人与人之间共同访问的网页数量作为关系权重：

以下将根据Cypher对节点和关系的预测在一个图表上运行Louvain algortihm：


CALL algo.louvain(
  'MATCH (p:Person) RETURN id(p) as id',
  'MATCH (p1:Person)-[:VISIT]->(:Page)<-[:VISIT]-(p2:Person)
   RETURN id(p1) as source, id(p2) as target, count(*) as weight',
  {graph:'cypher', iterations:5, write: true});

2.2.3 关系去重

默认情况下，Cypher投影加载器假定关系投影仅包含一对节点之间的一个关系。如果我们返回多个关系，我们可以传递duplicateRelationships在config中对应的值来决定关系的重复项应该发生什么。

duplicateRelationships 支持以下选项：

null - 假设返回的关系是唯一的。（默认）
skip - 保持遇到的第一个关系（和相关的重量）。
sum - 对遇到的关系的相关权重求和。
min - 保持遇到的最小关系重量。
max - 保持遇到的关系的最大权重。

如果我们知道对应的关系查询中不具备重复项，我们不该保留此参数。这会降低关系的加载速度

以下基于Cypher预测在图表上运行最短路径，ROAD以最低成本选择关系：


MATCH (start:Loc{name:'A'}), (end:Loc{name:'F'})
CALL algo.shortestPath(start, end, 'cost', {
  nodeQuery:'MATCH(n:Loc) RETURN id(n) as id',
  relationshipQuery:'MATCH(n:Loc)-[r:ROAD]->(m:Loc) RETURN id(n) as source, id(m) as target, r.cost as weight',
  {graph:'cypher', duplicateRelationships: 'min'})
YIELD writeMillis,loadMillis,nodeCount, totalCost
RETURN writeMillis,loadMillis,nodeCount,totalCost

2.2.4 并行加载

默认情况下，Cypher投影查询在单个线程上运行。

我们可以通过在我们的投影查询中包含SKIP子句和$skip参数以及LIMIT子句和$limit参数来并行加载。查询的并行化基于config参数中的batchSize键值，其默认值为10,000。

如果参数没有被命名$skip和$limit，他们将被忽略，并且顺序装载方法将被使用。

以下内容基于Cypher投影在一个图表上运行PageRank，并行加载节点和关系：


CALL algo.pageRank(
  'MATCH (p:Page) WITH p SKIP $skip LIMIT $limit RETURN id(p) as id',
  'MATCH (p1:Page)-[:Link]->(p2:Page) WITH * SKIP $skip LIMIT $limit RETURN id(p1) as source, id(p2) as target',
  {graph:'cypher', iterations:5, write: true});

2.3 命名图

本节介绍命名图，它们仅存储在内存中。重新启动Neo4j时，命名图表将丢失，需要重新加载。

由于将大型图形加载到算法数据结构中可能需要一些时间，因此可以预先加载图形，然后在调用图形算法过程时按名称引用它们。使用后，可以从内存中删除它们以释放使用的资源。

以下为节点标签Label和关系类型REL_TYPE，加载命名图my-graph


CALL algo.graph.load('my-graph','Label','REL_TYPE',{graph:'heavy',..other config...})
YIELD name, graph, direction, undirected, sorted, nodes, loadMillis, alreadyLoaded,
      nodeWeight, relationshipWeight, nodeProperty, loadNodes, loadRelationships;

以下内容将使用Cypher投影为节点和关系加载命名图。


CALL algo.graph.load('my-graph',
  'MATCH (n) RETURN id(n) AS id',
  'MATCH (a)-->(b) RETURN id(a) AS source, id(b) AS target',
  {graph:'cypher',..other config...})
YIELD name, graph, direction, undirected, sorted, nodes, loadMillis, alreadyLoaded,
      nodeWeight, relationshipWeight, nodeProperty, loadNodes, loadRelationships;

2.3.1 返回命名图的详细信息


CALL algo.graph.info('my-graph')
YIELD name, type, exists, removed, nodes;

使用命名图

我们可以通过在graphconfig 的键中指定其名称来在查询中使用我们的命名图。

以下将在my-graph命名图上运行PageRank算法：

CALL algo.pageRank(null,null,{graph:'my-graph',...})

2.3.3 删除命名图

一旦我们使用了命名图，我们就可以删除它们以释放内存。

以下将删除my-graph命名图：


CALL algo.graph.remove('my-graph')
YIELD name, type, exists, removed, nodes;

3 中心算法

3.1 Pagerank

Pagerank是一个典型的马尔科夫过程，即F=FP一直迭代直至收敛。这其实非常像标签传播的算法过程，只是标签传播并不见得是马尔科夫过程，markov过程要求任一状态都能切换至其他状态，标签传播似乎没有做到这一点。

中间一个状态可以跳到任意一个状态，包括自己。

个性化pagerank是PageRank的变体，偏向于一组sourceNodes。

PR(A) = (1-d) + d (PR(T1)/C(T1) + ... + PR(Tn)/C(Tn))

3.2 Articlerank

ArticleRank与PageRank的不同之处在于PageRank假设具有低出度的节点的关系比具有更高出度的节点的关系更重要。ArticleRank削弱了这一假设。

AR(A) = (1-d) + d (AR(T1)/(C(T1) + C(AVG)) + ... + AR(Tn)/(C(Tn) + C(AVG))

在分母处加上了所有页面的平均出度

3.3 中介中心度算法/间接中心性

中介中心性算法使用广度优先搜索算法计算连通图中每对节点之间的最短（加权）路径。每个节点基于通过节点的这些最短路径的数量来接收分数。最常出现在这些最短路径上的节点将具有更高的中介中心性得分。

还有简化版间接中心性

3.4 紧密中心性

紧密度中心性是一种检测能够通过图形非常有效地传播信息的节点的方法。

节点的紧密度中心度测量其与所有其他节点的平均距离（反向距离？？）。具有高紧密度得分的节点具有到所有其他节点的最短距离。

对于每个节点，Closeness Centrality算法基于计算所有节点对之间的最短路径来计算到所有其他节点的距离之和。然后反转得到的总和以确定该节点的紧密度中心性分数。

使用以下公式计算节点的原始接近度中心性：

raw closeness centrality(node) = 1 / sum(distance from node to all other nodes)

归一化紧密中心性公式如下：

normalized closeness centrality(node) = (number of nodes - 1) / sum(distance from node to all other nodes)

需要在连通图上使用，如果不连通。我们最终可以在单独的连接组件中的两个节点之间建立无限距离。

3.5 谐波中心性

谐波中心性（也称为有价值中心性）是亲密度中心性的一种变体，它是为解决原始公式在处理未连接图时所遇到的问题而发明的。与许多中心算法一样，它源于社交网络分析领域。

节点的原始谐波中心度使用以下公式计算：

raw harmonic centrality(node) = sum(1 / distance from node to every other node excluding itself)

归一化谐波中心度

normalized harmonic centrality(node) = sum(1 / distance from node to every other node excluding itself) / (number of nodes - 1)

在这个公式中，干净地处理∞值。

我们不是计算距离，而是将每个单元格的倒数相加并乘以1/(n-1)

之前是计算距离再取反，这里是先取反再求和，避免了正无穷的问题。

3.6 特征向量中心性算法

N阶矩阵的特征值和特征向量，是线性代数里面很重要的知识。

不同的特征值对应着不同的特征向量，特征向量的元素就是图中每个点的特征向量中心性。算法中是否对不同的特征值对应的特征向量进行了处理？？等待查看底层源码。

3.7 度中心性

检测节点的入度和出度的特征，如果一个节点具备高入度，低出度，例如Twitter和微博，则可以认为该节点是名人，

加权度中心性，已被用于帮助区分欺诈者与合法用户，欺诈的加权度中心性显著提高，欺诈者倾向于相互串通以人为地增加物品的价格。

4 社区检测算法

4.1 鲁汶算法

最大化模块度，主要用于社区检测以及分层社区检测。

4.2 标签传播算法

需要注意这里的标签传播算法和谷歌到的算法流程实现是不太一样的，

F=PF F是标注矩阵，P是概率转移矩阵或者权重矩阵

每次迭代都保证F最初标注的子矩阵不变，直至F收敛，即F的change小于某个值

而在algo包中的实现有比较大的区别，这里的权重矩阵，是由关系的weight属性来确定的，如果给出的图里面没有关系属性，则取默认值为1。那么权重矩阵则由稀疏的邻接表矩阵归一化之后直接可得。

在algo包中，仅仅是根据邻接表来获取权重，如果权重大于权重列表中对应的权重，则打上相邻节点的标签（如果在图中最初没有给出标签则使用通过web呈现的graphId

映射得到的nodeId作为初始的分类标签）。

每次遍历某个节点的邻接表矩阵，都会执行这样的一个操作，

ParallelUtil.runWithConcurrency(concurrency, computeSteps, executor);

最后调用到LabelPropagation的290行的compute，关键在294行的graph.forEachRelationship(nodeId, direction, this);

最后的accept调用的匿名函数为LabelPropagation的311行的重写的accept函数，编译时与ctrl+b时都检查的是父类（接口）定义的方法，实际运行时运行的是子类的方法，这是多态，父类的引用指向了子类的对象（实例），即向上转型。

核心的一句在于votes.addTo(partition, weight);

这里的votes map中加入的是partition，即分类标签而不是nodeId，即partition是随着程序在变化的。所以votes里面会出现5->2的数据，因为邻接表矩阵中的两个点现在都已经被打上了5的partition（即分类标签）！

4.3 连通分量算法

无向图连通分量，可用于计算连通分量的个数，以及各个连通分量中的节点数

加权连通分量：对权重进行判断，如果两个节点相连的边的权重小于1，那么忽略这条边，其中某个点有可能自身即为一个连通分量。

4.4 强连通分量

4.5 三角计数/聚类系数算法

三角计数算法（Triangle Count）统计图中三角形个数。三角形越多，代表图中节点关联程度越高，组织关系越严密。

聚类系数表示一个图中节点聚集程度的系数。在现实的网络中，尤其是在特定的网络中，由于相对高密度连接点的关系，节点总是趋向于建立一组严密的组织关系。聚类系数算法（Cluster Coeffcient）用于计算图中节点的聚集程度。

聚类系数算法（Cluster Coeffcient）适用于衡量图的结构特性场景。

5 寻路算法

5.1 最小生成树

创建示意图


MERGE (a:Place {id:"A"})
MERGE (b:Place {id:"B"})
MERGE (c:Place {id:"C"})
MERGE (d:Place {id:"D"})
MERGE (e:Place {id:"E"})
MERGE (f:Place {id:"F"})
MERGE (g:Place {id:"G"})
 
MERGE (d)-[:LINK {cost:4}]->(b)
MERGE (d)-[:LINK {cost:6}]->(e)
MERGE (b)-[:LINK {cost:1}]->(a)
MERGE (b)-[:LINK {cost:3}]->(c)
MERGE (a)-[:LINK {cost:2}]->(c)
MERGE (c)-[:LINK {cost:5}]->(e)
MERGE (f)-[:LINK {cost:1}]->(g);

最小生成树访问与起始节点在同一连通分量中的所有节点，并返回组件中所有节点的生成树，其中关系的总权重最小化。

以下运行最小权重生成树算法并写回结果，内部实际使用的是Prim算法。


MATCH (n:Place {id:"D"})
CALL algo.spanningTree.minimum('Place', 'LINK', 'cost', id(n),
  {write:true, writeProperty:"MINST"})
YIELD loadMillis, computeMillis, writeMillis, effectiveNodeCount
RETURN loadMillis, computeMillis, writeMillis, effectiveNodeCount;

以下将查询最小生成树


MATCH path = (n:Place {id:"D"})-[:MINST*]-()
WITH relationships(path) AS rels
UNWIND rels AS rel
WITH DISTINCT rel AS rel
RETURN startNode(rel).id AS source, endNode(rel).id AS destination, rel.cost AS cost

如果需要获得最大生成树，将spanningTree的minimum改成maxmum即可。

5.1.1 K生成树

有时我们想限制生成树结果的大小，因为我们只想在图中找到一个不跨越所有节点的较小树。K-Spanning树算法返回具有k节点和k − 1关系的树。

在我们的示例图中，我们有5个节点。当我们在上面运行MST时，我们返回了一个最小的5个生成树，它覆盖了所有五个节点。通过设置k=3，我们定义我们想要返回一个3个最小的生成树，它覆盖3个节点并有2个关系。

以下将运行k最小生成树算法并写回结果：


MATCH (n:Place{id:"D"})
CALL algo.spanningTree.kmin('Place', 'LINK', 'cost',id(n), 3,
  {writeProperty:"kminst"})
YIELD loadMillis, computeMillis, writeMillis, effectiveNodeCount
RETURN loadMillis,computeMillis,writeMillis, effectiveNodeCount;

可以使用如下的语句来查看属于我们的k生成树的结果的节点


MATCH (n:Place)
WITH n.kminst AS partition, count(*) as count
WHERE count = 3
RETURN partition,count

5.1.2 语法解释

生成树语法


CALL algo.spanningTree(label:String, relationshipType:String, weightProperty:String, startNodeId:int, {writeProperty:String})
YIELD loadMillis, computeMillis, writeMillis, effectiveNodeCount

write

boolean

true

yes

指定结果是否应该作为关系写回图数据库

writeProperty

string

'mst'

yes

结果返回的关系的类型

返回结果

名称

类型

描述

effectiveNodeCount

INT

访问节点的数量

loadMillis

INT

加载数据的毫秒数

computeMillis

INT

运行算法的毫秒数

writeMillis

INT

写回结果数据的毫秒数

K生成树语法

write

boolean

true

yes

指定结果是否应该作为节点属性

writeProperty

string

'mst'

yes

结果返回的节点属性

5.1.3 代码研究

对于Stream接口而言，Stream.of()方法没有对传入数据的类型做明确的要求，此处源码指定为泛型，即对任意类都可以进行封装。

5.2 最短路径算法

2.2的Cypher投影举例

Cypher投影上运行算法的完整语句如下：


MATCH (start:Loc{name:'A'}), (end:Loc{name:'F'})
CALL algo.shortestPath(start, end, 'cost',{
nodeQuery:'MATCH(n:Loc) WHERE not n.name = "c" RETURN id(n) as id',
relationshipQuery:'MATCH(n:Loc)-[r:ROAD]->(m:Loc) RETURN id(n) as source, id(m) as target, r.cost as weight',
graph:'cypher',defaultValue:1.0, write:true, writeProperty:'sssp', direction:'OUTGOING'})
YIELD writeMillis,loadMillis,nodeCount, totalCost
RETURN writeMillis,loadMillis,nodeCount,totalCost

5.2.1 Cypher投影的实际语法和参数解释

以下将运行算法并写回结果：


CALL algo.shortestPath(startNode:Node, endNode:Node, weightProperty:String
    {nodeQuery:'labelName', relationshipQuery:'relationshipName', defaultValue:1.0, write:'true'[w1] , writeProperty:'sssp', direction:'OUTGOING'})
YIELD nodeCount, totalCost, loadMillis, evalMillis, writeMillis

Name

Type

Default

Optional

Description

startNode

node

null

起始节点

endNode

node

null

终止节点

weightProperty

string

null

yes

包含权重的属性名称。如果为null，则将图表视为未加权。必须是数字

defaultValue

float

null

yes

权重的默认值

write

boolean

true

yes

指定是否应该将结果写回节点属性

writeProperty

string

'sssp'

yes

写回路径节点的节点属性名

nodeQuery[w2]

string

null

yes

要从图表加载的标签。如果为null，则加载所有节点

relationshipQuery

string

null

yes

要从图表加载的关系类型。如果为null，则加载所有节点

direction

string

outgoing

yes

从图表加载的关系方向。如果“Both”，则将关系视为无向

6 相似度算法

6.1 Jaccard相似度算法

我们可以使用Jaccard相似度算法来计算两件事之间的相似性。然后，我们可以将计算的相似性用作推荐查询的一部分。例如，您可以使用Jaccard Similarity算法来显示类似客户购买的产品，就以前购买的产品而言。

可用于计算图中某两个节点的相似性，例如美食喜好图中两个人喜欢的食物的相似性。

RETURN algo.similarity.jaccard([1,2,3], [1,2,4,5]) AS similarity 返回0.4

6.2 余弦相似度

6.3 Pearson相似度

Pearson相似度是两个n维向量的协方差除以它们的标准偏差的乘积。

6.4 欧氏距离算法

6.5 重叠相似度

RETURN algo.similarity.overlap([1,2,3], [1,2,4,5]) AS similarity

O(A,B) = (∣A ∩ B∣) / (min(∣A|,|B|))

O(A,B) = 2 / min(3,4)

= 2 / 3

= 0.66

7 链路预测算法

什么是链路预测？

预测网络中以后或是遗失的关系的问题叫做链路预测。

链路预测旨在根据观察到的链路和节点属性估计两个节点之间链路存在的可能性。链路预测有助于分析缺少数据的网络，例如，许多生物网络，如食物网，蛋白质 - 蛋白质交互网络和代谢网络，是否存在两个节点之间的链接必须通过现场和/或实验室实验来证明，这些实验通常非常昂贵。我们对这些网络的了解非常有限。

此外，链路预测算法可用于预测可能出现在不断发展的网络中的链路，例如在线社交网络中的友谊推荐和电子商务网站中的产品推荐[3]。链路预测的进一步应用包括伪链路的识别，对网络的竞争机制的估计，节点的分类等。

7.1 Adamic Adar算法

7.2 共同邻居算法

7.3 优先附着算法

7.4 资源分配算法

7.5 相同社区算法

7.6 总邻居算法

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/Cpp五条/article/detail/667286