Press "Enter" to skip to content

图数据科学和机器学习图算法概览

本站内容均来自兴趣收集,如不慎侵害的您的相关权益,请留言告知,我们将尽快删除.谢谢.

携手创作,共同成长!这是我参与「掘金日新计划 · 8 月更文挑战」的第12天,点击查看活动详情

 

算法介绍参考:

 

cloud.tencent.com/developer/a…

tech.it168.com/a2018/0428/…

各算法详细用法参考:

 

github.com/neo4j-contr…

 

遍历和寻路算法

 

1.广度优先算法(BFS)

 

做什幺:遍历树数据结构,探索最近的邻居和他们的次级邻居。它用于定位连接,是许多其他图算法的前身。

 

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

 

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

 

2.深度优先算法(DFS)

 

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

 

如何使用:深度优先算法通常用于游戏模拟,其中每个选择或动作引发另一个操作,从而扩展成可能性的树形图。它将遍历选择树,直到找到最佳解决方案路径(即胜利)。

 

3.单源最短路径

 

做什幺:计算节点与所有其他节点之间的路径,以及其与所有其他节点的总和值(成本,距离,时间或容量等关系的权重)并得出总和最小。

 

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

 

4.全源最短路径

 

做什幺:计算包含图中节点之间所有最短路径的最短路径森林(组)。当最短路径被阻塞或变得次优时,切换到新的最短路径,通常用于备用路由。

 

如何使用:用于评估备用路由,例如高速公路备份或网络容量。它也是为逻辑路由提供多路径的关键,比如呼叫路由选择。

 

5.最小生成树(MWST)

 

做什幺:计算与访问树中所有节点相关的最小值(如成本,时间或容量等关系的权重)的路径,用于逼近一些NP难题,如旅行商问题和随机或迭代舍入。

 

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

 

Centrality Algorithms(中心性算法)

 

6. PageRank

 

做什幺:估计当前节点对其相邻节点的重要性,然后再从其邻居那里获得节点的重要性。一个节点的排名来源于其传递链接的数量和质量。PageRank虽然被谷歌抛弃了,但它还是被广泛认为是检测任何网络中有影响力的节点的常用方式。

 

如何使用:PageRank用于评估重要性和影响力,经常的用法是推荐推特账户以及一般的情绪分析。

 

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

 

MERGE (home:Page {name:'Home'})
MERGE (about:Page {name:'About'})
MERGE (product:Page {name:'Product'})
MERGE (links:Page {name:'Links'})
MERGE (a:Page {name:'Site A'})
MERGE (b:Page {name:'Site B'})
MERGE (c:Page {name:'Site C'})
MERGE (d:Page {name:'Site D'})
MERGE (home)-[:LINKS]->(about)
MERGE (about)-[:LINKS]->(home)
MERGE (product)-[:LINKS]->(home)
MERGE (home)-[:LINKS]->(product)
MERGE (links)-[:LINKS]->(home)
MERGE (home)-[:LINKS]->(links)
MERGE (links)-[:LINKS]->(a)
MERGE (a)-[:LINKS]->(home)
MERGE (links)-[:LINKS]->(b)
MERGE (b)-[:LINKS]->(home)
MERGE (links)-[:LINKS]->(c)
MERGE (c)-[:LINKS]->(home)
MERGE (links)-[:LINKS]->(d)
MERGE (d)-[:LINKS]->(home)

 

CALL algo.pageRank.stream('Page', 'LINKS', {iterations:20, dampingFactor:0.85})
YIELD nodeId, score
RETURN algo.asNode(nodeId).name AS page,score
ORDER BY score DESC

 

 

7. Degree Centrality(程度中心性)

 

做什幺:测量节点(或整个图表)所具有的关系数量,被分为流入和流出两个方向,关系具有指向性。

 

如何使用:Degree Centrality着眼于用途的直接连通性,例如评估患者接近病毒或听取信息的近期风险。在社会研究中,可以用来预估人气或者其它情感。

 

CALL algo.degree.stream("Page", "LINKS", {direction: "incoming"}) 
YIELD nodeId, score 
RETURN algo.asNode(nodeId).name AS name, score AS followers 
ORDER BY followers DESC

 

 

8. Closeness Centrality(亲密度中心性)

 

做什幺:衡量一个节点对其集群内所有邻居的集中程度。假定到所有其他节点的路径都是最短的,那幺该节点就能够以最快的速度到达整个组。

 

如何使用:Closeness Centrality适用于多种资源、交流和行为分析,尤其是当交互速度显着时。

 

在新公共服务中,被用于确定最大可访问性的位置。

 

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

 

CALL algo.closeness.stream('Page', 'LINKS') 
YIELD nodeId, centrality 
RETURN algo.asNode(nodeId).name AS name, centrality 
ORDER BY centrality DESC

 

 

9. Betweenness Centrality(中介中心性)

 

做什幺:测量通过节点的最短路径的数量(首先通过广度优先算法找到)。出现在最短路径上次数最多的节点具有较高的介数中心性,并且是不同集群之间的桥梁。它通常与控制资源和信息的流动有关。

 

如何使用:Betweenness Centrality适用于网络科学中的各种问题,用于查明通信和交通网络中的瓶颈或可能的攻击目标。在基因组学中,被用于了解控制某些基因在蛋白质网络中的改进,例如更好的药物/疾病靶向。

 

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

 

CALL algo.betweenness.stream('Page','LINKIS',{direction:'out'}) 
YIELD nodeId, centrality 
MATCH (page:Page) WHERE id(page) = nodeId 
RETURN page.name AS page,centrality 
ORDER BY centrality DESC;

 

 

社区发现算法

 

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

 

10. Label Propagation(标签传播)

 

做什幺:基于邻域多数的标签作为推断集群的手段。这种极其快速的图形分割需要很少的先验信息,并且被广泛地应用于大规模的社区检测网络中。这是理解图组织的一个关键方法,通常是其他分析的主要步骤。

 

如何使用:Label Propagation具有不同的应用,例如了解社会团体中的共识形成、识别在生物网络的过程(功能模块)中所涉及的蛋白质集合等等。甚至还可以用于半监督和无监督的机器学习作为初始的预处理步骤。

 

11. Strongly Connected(强连通)

 

做什幺:定位节点组,其中每个节点可从同一组中的所有其他节点按照关系的方向到达,常被应用于深度优先算法。

 

如何使用:Strongly Connected通常用于在识别的集群上独立运行其他算法。作为有向图的预处理步骤,它有助于快速识别不连通的集群。

 

在零售推荐中,它有助于识别具有强亲和性的组,然后将向那些尚未购买商品的群体推荐首选商品。

 

12. Union-Find/Connected Components/Weakly Connected(并查集、连通分量、弱连通)

 

做什幺:查找节点组,其中每个节点可从同一组中的任何其他节点到达,而不考虑关系的方向。它提供几乎恒定的时间操作(独立于输入大小)来添加新的组,合并现有的组,并确定两个节点是否在同一组中。

 

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

 

13. Louvain Modularity

 

做什幺:通过比较它的关系密度与适当定义的随机网络来测量社团分组的质量(即假定的准确性)。它通常用于评估复杂网络的组织和社区层次结构。这对于无监督机器学习中的初始数据预处理也是有用的。

 

如何使用:Louvain用于评估Twitter,LinkedIn和YouTube上的社交结构;用于欺诈分析,以评估一个组织是只存在一些不良行为,还是背后一个连环欺诈。Louvain在比利时电信网络中揭示了一个六级客户层级。

 

14. Local Clustering Coefficient/Node Clustering Coefficient(局部集聚系数/节点聚类系数)

 

做什幺:对于一个特定的节点,量化了其到邻居节点的距离, (每个节点都直接连接到其他节点)。例如,如果您的所有朋友都直接了解对方,那幺您的本地集群系数将是1。集群的小值表明尽管存在一个分组,但节点之间并没有紧密连接。

 

如何使用:Local cluster coefficient通过理解群体相关性或碎片化的可能性,对估计弹性具有重要意义。用这种方法对欧洲电网的分析发现,与稀疏连接的节点相比,集群更能抵御普遍的故障。

 

15. Triangle-Count and Average Clustering Coefficient(三角计数和平均聚类系数)

 

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

 

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

Be First to Comment

发表回复

您的电子邮箱地址不会被公开。