Neo4j中的图形算法:15种不同的图形算法及其功能

只有你拥有使用图形分析的技巧,并且图形分析能快速提供你需要的见解时,它才具有价值。因而最好的图形算法易于使用,快速执行,并且产生有权威的结果。

Neo4j包含一个不断增长的开放式高性能图形算法库,可以揭示关联数据中的隐藏模式和结构。

在这个关于图算法的系列中,我们将讨论图算法的价值以及它们可以为你做些什么。之前我们探讨了数据连接如何驱动未来的数据发现以及如何使用图形分析来简化这些数据发现

本周我们将详细介绍Neo4j中提供的许多图算法以及它们的功能。

使用Neo4j图形算法,您将有办法理解,建模并预测复杂的动态特性,如资源或信息的流动,传染病或网络故障传播的途径,以及群组的影响和弹性。

并且由于Neo4j将原图平台中的分析和事务操作结合在一起,您不仅可以揭示真实世界系统的内在本质以形成新的发现,还可以更快地开发和部署基于图形的解决方案,并具有易于使用,简化的工作流程。这就是优化方法的威力。

以下是Neo4j在其图形分析平台中使用的许多算法的列表,以及它们做了什么的解释。

遍历和寻路算法

遍历和寻路算法

1.并行广度优先搜索(BFS)

功能:遍历树数据结构,通过扇出探索最近的邻居和他们的次级邻居。它用于定位连接,并且是许多其他图算法的前身。

当树较不平衡或目标更接近起点时,BFS是首选。它也可用于查找节点之间的最短路径或避免深度优先搜索的递归过程。

如何使用:广度优先搜索可用于在像BitTorrent这样对等网络中定位邻居节点,在GPS系统中精确定位附近的位置,在社交网络服务中在特定距离内查找人员。

2.并行深度优先搜索(DFS)

功能:通过在回溯之前尽可能探索每个分支来遍历树数据结构。它用于深层次的数据,是许多其他图算法的前身。当树更平衡或目标更接近端点时,深度优先搜索是首选。

如何使用:深度优先搜索通常用于游戏模拟,其中每个选择或操作引发下一个选择或操作,扩展成树状的概率图。它将遍历选择树,直到找到最佳解决方案路径(即胜利)。

3.单源最短路径

功能:计算节点与所有其他节点的路径中汇总值(如成本、距离、时间或容量等关系的权重) 最小的路径。

如何使用:应用单源最短路径通常应用于自动获取物理位置之间的路线,例如通过Google地图获取驾车路线。它在逻辑路由中也很重要,例如电话呼叫路由(最低成本路由)。

4.全对最短路径

用途:计算一个最短路径林森林(组), 其中包含关系图中节点之间的所有最短路径。当最短路径被阻塞或变得次优时,它通常用于推算备用路由。

如何使用:全对最短路径用于计算备用路径的情境,例如高速公路备份或网络容量。它也是逻辑路由提供多路径的关键;,例如备选的呼叫路由。

5.最小权重生成树(MWST)

它的作用:连接树结构中所有点,计算路径的值(如成本、时间或容量)之和最小的路径。它也被用来逼近一些NP难题,如旅行商问题和随机或迭代舍入。

如何使用:最小权重生成树广泛用于网络设计:成本最低的逻辑或物理路由,如铺设电缆,最快的垃圾收集路线,供水系统容量,高效电路设计等等。它还可以实时应用于滚动优化,如化学炼油厂的流程或行驶路线修正。

中心性算法

中心性算法

6. PageRank

作用:从当前节点的邻居,和邻居的邻居评估当前节点的重要性。用来源于其传递链接的数量和质量的的排名来估计一个节点的影响力。虽然已经被Google普及,但它被广泛认为是检测任何网络中有影响力的节点的方法。

如何使用:PageRank用于评估重要性和影响力的方法有很多。它被用来推荐推特账户以及一般情绪分析。

PageRank也用于机器学习以确定最有影响的提取特征。在生物学中,它被用来识别食物链中哪些物种的灭绝会导致物种死亡的最大连锁反应。

7.程度中心性

作用:测量节点(或整个图)的关系数量。它被分解成入度(流入)和出度(流出),其中关系是有方向的。

如何使用:程度中心性着眼于即时连通性的使用, 如评估一个人的短期风险, 捕捉病毒或听觉信息。在社会研究中,朋友关系的入度可以用来评估人气,而出度可以用来评估合群性。

8.亲密度中心性

作用:衡量一个节点对其集群内所有邻居的中心程度。拥有到所有其他节点的路径最短的节点被认为能够以最快的速度到达整个群组。

如何使用:亲密度中心性适用于多种资源,交流和行为分析,尤其是当交互速度显着时。。它被用于确定新公共服务的最佳位置以获得最大的可访问性。

在社交网络分析中,它用于找到具有理想社交网络位置的人,以便更快地传播信息。

9.中介中心性

作用:测量通过节点的最短路径的数量(首先通过广度优先搜索找到)。最经常位于最短路径上的节点具有较高的中介中心性分数,并且是不同群集之间的桥梁。它通常与控制资源和信息的流动有关。

如何使用:中介中心性适用于网络科学中的各种问题,并用于查明通信和运输网络中的瓶颈或可能的攻击目标。在基因组学中, 它已经被用来理解蛋白质网络中的控制基因, 例如更好的药物/疾病靶向。

中介中心性也被用来评估多人在线游戏玩家和共享医师专业知识的信息流动。

社区检测算法

社区检测算法

这个类别也被称为聚类算法分区算法

10.标签传播

作用:将基于邻里多数的标签作为推断簇的一种手段进行传播。这种极其快速的图形分割需要很少的先验信息, 广泛应用于大规模网络的社区检测。它是理解图形组织的关键方法, 通常是其他分析的主要步骤。

如何使用:标签传播具有多种应用,从了解社会社区的共识形成,到在生物网络中医一个识别一个过程(功能模块)中涉及的蛋白质组。它也用于半监督和无监督机器学习作为一个初始的预处理步骤。

11.强连通

作用:查找关系网中可以互相访问到的一组节点。它通常是从深度优先搜索中应用的。

如何使用:强连通一般用于在已识别的群集上启用并独立运行其他算法。作为定向图的预处理步骤, 它有助于快速识别断开连接的组。在零售建议中, 它有助于识别关联性强的一组商品, 然后向购买其中一些商品的用户推荐没有购买的那些。

12.并查集/联通分量/弱连通

作用:查找节点组, 其中每个节点都可从同一组中的任何其他节点访问, 而不考虑关系的方向。它提供近恒定时间操作 (与输入大小无关) 来添加新组、合并现有组以及确定两个节点是否位于同一组中。

如何使用:并查集/联通分量经常与其他算法结合使用,特别是对于高性能分组。作为无向图的预处理步骤,它有助于快速识别断开的组。

13.Louvain模块度

作用:通过将关系密度与适当定义的随机网络进行比较, 测量社区分组的质量 (被认为是准确性)。它经常用于评估复杂网络和社区层次结构的组织。它对于非监督机器学习中的初始数据预处理也很有用。

如何使用:Louvain用于评估Twitter,LinkedIn和YouTube上的社交结构。它被用于欺诈分析,以评估一个组织是否只有一些不良行为,或者是作为一个欺诈环,而这个欺诈环的关系密度高于平均值。Louvain在比利时电信网络中揭示了一个六级客户层级。

14.局部集聚系数/节点聚类系数

作用:对于特定的节点, 它可以量化它的邻居是如何接近一个派系 (每个节点都直接连接到每个其他节点)。例如, 如果您的所有朋友都直接了解对方, 您的本地聚类系数将为1。群集中的较小的值表示尽管存在分组, 但节点没有紧密连接。

如何使用:局部聚类系数对于通过理解群一致性或碎片的可能性来估计复原力是很重要的。利用这种方法对欧洲电网进行分析发现, 具有稀疏连通节点的集群对广泛的故障具有更强的适应性。

15.三角计数和平均聚类系数

作用:测量有多少节点具有三角形以及节点倾向于聚集在一起的程度。平均聚类系数为1时有一个集团,为0时没有连接。为使聚类系数有意义,它应该明显高于网络中所有关系随机打乱的版本。

如何使用:平均聚类系数通常用于估计网络是否可能展现基于紧密集群的“小世界”行为。这也是集群稳定性和弹性的一个因素。流行病学家使用平均聚类系数来帮助预测不同社区的各种感染率。

结论

世界是由关系驱动的。Neo4j图形分析使用实用,优化的图形算法(包括上面详述的那些算法)揭示了那些关系的含义。

我们的Neo4j系列中关于图形算法的部分就总结在这里。我们希望这些算法能够帮助您以更有意义和更有效的方式理解连接的数据。

本文的版权归 ★忆先★ 所有,如需转载请联系作者。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏AI研习社

机器学习开发者应该收藏的 DIY 计算机视觉和深度学习项目

受到 Akshay Bahadur 所做伟大工作的鼓舞,在这篇文章中你将看到一些应用计算机视觉和深度学习的项目,包括具体实现和细节,你可以在自己的电脑上复现这些...

1793
来自专栏ATYUN订阅号

机器学习项目:建立一个酒店推荐引擎

所有在线旅行社都在争先恐后地满足亚马逊和网飞(Netflix)设定的AI驱动的个性化标准。此外,在线旅游已经成为一个竞争激烈的领域,品牌试图通过推荐,对比,匹配...

1032
来自专栏机器之心

斯坦福提出机器学习开发新思路:无Bug的随机计算图Certigrad(已开源)

选自Github 机器之心编译 参与:李泽南、蒋思源 在实践中,机器学习算法经常会出现各种错误,而造成错误的原因也经常难以找到。近日,斯坦福大学的研究者提出了...

2817
来自专栏深度学习之tensorflow实战篇

协同过滤算法概述与python 实现协同过滤算法基于内容(usr-item,item-item)

协调过滤推荐概述   协同过滤(Collaborative Filtering)作为推荐算法中最经典的类型,包括在线的协同和离线的过滤两部分。所谓在线协同,...

7774
来自专栏PaddlePaddle

AI不思议|说说那些偶尔混淆的概念

但是产品和运营两队小伙伴一不小心就遇到概念混淆的场景,有些时候是自己记模糊了、有些时候自己没记错、却被别人“拐到沟里“了…

1081
来自专栏张俊红

数学之美(二)

总第75篇 本篇为数学之美连载篇二,你还可以看:数学之美(一) 11|矩阵运算与文本处理: 无论是词汇的聚类还是文本的分类,都可以通过线性代数中的奇异值分解来进...

3365
来自专栏ArrayZoneYour的专栏

TensorFlow强化学习入门(2)——基于策略的Agents

在本教程系列的(1)中,我演示了如何构建一个agent来在多个选择中选取最有价值的一个。在本文中,我将讲解如何得到一个从现实世界中获取 观测值 ,并作出 长期收...

7866
来自专栏机器之心

初学者怎么选择神经网络环境?对比MATLAB、Torch和TensorFlow

选自arXiv 机器之心编译 参与:吴攀、蒋思源、李亚洲 初学者在学习神经网络的时候往往会有不知道从何处入手的困难,甚至可能不知道选择什么工具入手才合适。近日...

46110
来自专栏新智元

【TensorFlow开发者峰会】重磅发布TensorFlow.js,完全在浏览器运行机器学习

1797
来自专栏美团技术团队

美团技术团队博客:推荐算法实践

前言 推荐系统并不是新鲜的事物,在很久之前就存在,但是推荐系统真正进入人们的视野,并且作为一个重要的模块存在于各个互联网公司,还是近几年的事情。 随着互联网的深...

48611

扫码关注云+社区

领取腾讯云代金券