19您现在可以使用的图形算法
#database #memgraph #graphdatabase #graphalgorithms

在数据上运行任何图形算法的最快是使用memgraph和mage。这是超级容易的。 Download Memgraph,导入您的数据,选择最受欢迎的图形算法之一,然后开始处理数字。

memgraph 是一个内存图数据库。您可以使用它来遍历遍布的网络并运行复杂的图形算法。

Mage 是由Memgraph支持的开源存储库工具。法师以查询模块的形式携带不同的模块和图形算法。

您可以从19个图算法中选择查询模块的GitHub存储库。您可以立即将这些算法与Memgraph和法师一起使用。

算法列表

这是我们支持的19种算法列表。您可以立即将这些算法与Memgraph(图DB)和MAGE(图库)一起使用。

1.中心性

中心分析提供了有关该节点对信息流或网络连接性的重要性的信息。 Betweenness centrality是最常用的中心度指标之一。间隔中心性衡量节点在图中其他节点之间的路径上的程度。因此,在网络中,由于其控制其他人之间传播的信息,在网络中可能会产生很大的影响。中心中心性的计算不是标准化,并且有很多方法可以解决。

它被定义为通过节点的图表中最短路径的数量除以最短路径的总数。实施算法在University of Konstanz的Ulrik Brandes的论文“ A Faster Algorithm for Betweenness Centrality”中描述了。

memgraph-betweeness-centrality

一个更大的圆意味着更大的中心性。中间的路径最短的路径流过它。

Implementation Link

2.双连接组件

Biconnected components是最初分析中重要的图表的一部分。查找双连接组件意味着找到最大的双连接子图。如果:

  • 可以从双连接子图中的每个节点转到另一个节点
  • 即使在子图中删除任何顶点后,第一种情况仍然是正确的

John HopcroftRobert Tarjan以线性时间复杂性解决了问题。根据用例,双连接组件可能有助于发现图中的隐藏结构。

memgraph-biconnected-components

不同的颜色是不同的组件。多色顶点是铰接点。

Implementation Link

3.双方匹配

双方图是一个图形,我们可以将顶点分为两个独立的集合,从而使每个边缘在这些集合之间连接顶点。在集合中无法建立连接。

在两部分图中匹配(两部分匹配)被描述为一组边缘,以不共享端点的方式选择。此外,最大匹配是所选边缘设置的最大基数的这种匹配。该算法在O(| V |*| E |)时间中运行,其中V表示一组节点,E表示一组边缘。

在计算实体之间的作业时,这个小工具可能会变得非常少。在大量行业中完成了两组实体之间的分配,因此有一种方法可以使开发过程更容易。

memgraph-bipartite-matching

Implementation Link

4.桥梁检测

就像在现实世界中一样,图理论中的桥梁的定义表示将实体分为多个组成部分的事物。因此,更确切地说,图理论中的bridge表示一个边缘,当将图分为两个单独的组件时,该边缘。

memgraph-bridge-detection

图上的桥梁的示例。大胆的边缘代表桥梁。

Implementation Link

5.社区检测

图中社区的概念与现实世界中所代表的相似。不同的社交圈就是此类社区的例子。类似地,在图中,社区代表图的分区,即一组节点。 M. GirvanM. E. J. Newman认为,节点在社区中更加紧密,即,有更多的边缘,而另一方面,节点在社区本身之间稀少。

有更多潜在的候选人可以解决社区发现。在最受欢迎的算法中包括:

  1. Louvain community detection-基于模块化优化 - 测量社区内的网络连接
  2. Leiden community detection-调整Louvain的算法,该算法介绍了一种精致级别,并汇集了紧密联系的社区
  3. Label propagation-一种机器学习技术,将标签分配给未标记的节点并将其修改为邻居

memgraph-community-detection

社区检测标签每个节点都有一个社区标签。在这里,标签以不同的颜色为颜色。

Implementation Link

6.循环检测

在图理论中,一个循环代表图中只有启动和结束节点相似的路径。此外,循环可以是相邻节点或自动浮子之间的双连接链接。

在他的tortoise and hare algorithm中,Robert W. Floyd定义了找到周期的解决方案的最简单概念,在他的tortoise and hare algorithm中,野兔以乌龟的速度移动的两倍,因此如果有循环,则会遇到它。周期检测有许多实施,其中最快的是宾夕法尼亚州立大学Finding all the elementary circuits of a directed graphDonald B. Johnson教授。

循环不仅在图形结构中流行,而且在数字理论和密码学中也起着重要作用。然而,图理论概念在其他学科中都使用,并且在初始图形分析中将循环检测作为极为重要的工具。

memgraph-cycle-detection

示例中图中有两个循环,每个循环颜色不同。

Implementation Link

7.图形着色

某些应用需要特殊标记,称为graph coloring。此特殊标签是指标签(我们称之为颜色)的分配方式,即不能给予连接的邻居的颜色相同。由于此问题是NP-hard,因此没有可以在多项式时间内解决该问题的算法。因此,使用称为heuristics的各种计算机科学技术来求解图形。

当然,问题的主要部分是分配最少数量的标签。有一些贪婪的算法可以解决该问题,但是并非最佳。使用动态编程,最快的算法可以保证O(2.44 ^ n)复杂性。另一方面,有启发式应用,例如genetic algorithms

memgraph-graph-coloring

在简单的图上进行图形颜色的示例。标签用不同的颜色表示。

Implementation Link

8.节点相似性

可以通过几种不同的方式描述similarity的概念,但是在图理论中,它包含了几个公认的定义。图节点的相似性基于相邻节点或邻域结构的比较。这些是传统的定义,仅考虑了图的布局。如果我们扩展了具有其他属性的节点的定义,那么也可以根据这些属性定义比较,但这不是此处提到的方法的主题。

这种类型的算法的结果始终是一对节点和指示它们之间的匹配度量的分配值。我们将仅提及基于邻里节点的最受欢迎的措施,并简要说明。

  • Cosine similarity-将产物定义为两个节点的共同邻居的基数角度的余弦,并且分母是节点度乘积的根
  • Jaccard similarity-不同计算机科学模型中的一种经常使用的度量包括通过总计邻居数量的比例
  • Overlap similarity-定义为邻域与小于两个节点的邻居的横截面的比率。在少数相邻节点
  • 的情况下,重叠相似性效果最好

memgraph-node-similarity

节点共享邻域的图的示例。此信息用于计算相似性。

Implementation Link

9. Pagerank

在中心度测量领域,PageRank可以说是最受欢迎的工具。如今,世界上最受欢迎的搜索引擎Google,仅归功于该算法,该算法是由其创始人在早期开发的。

如果我们将节点作为页面和链接之间的定向边缘表示,则Pagerank算法输出一个概率分布,用于表示一个人随机单击链接的人将到达任何特定页面。

>

>

Pagerank可以用作对各种应用程序的影响的量度,而不仅仅是网站排名。 Pagerank的一种流行类型是Personalized PageRank,它在推荐系统中非常有用。

memgraph-PageRank

Pagerank在一个简单的网络上。最大的顶点指向相邻的顶点,因此使其更重要。

Implementation Link

10.工会发现

这是另一个重要的图分析算法。通过使用disjoint-set-一种数据结构,可以跟踪非重叠集集,该算法使用户能够快速检查一对给定节点是在相同还是不同的连接组件中。拥有这种结构的好处是,在O(1)时间内有效地执行了对一对节点的检查。

实施不相关的数据结构及其操作通过Robert Tarjan和abiaoqian的“最坏情况分析联合算法”中所述的等级和路径拆分优化使用联合。

memgraph-union-find

在右侧设置的不相交的结构,并在左侧进行图形示例。检查组件时,算法仅检查左侧的浅树。

Implementation Link

11. Dynamic Node2Vec

Dynamic Node2Vec是一种基于步行的随机方法,可为添加到图的每个新节点创建嵌入。对于每个新的边缘,都有用于步行采样的概率(权重)的重新计算。该方法的一个目的是强制执行节点V的嵌入类似于节点的嵌入,并且能够跨越一个面前的边缘到达节点V的能力。

为什么动态节点2vec

许多方法,例如node2vec,deepwalk,专注于计算具有其质量和一些大缺点的静态图的嵌入。
实际应用中的网络是动态的,并且随着时间的流逝不断发展。例如,形成了新的链接(当人们在社交网络上结交新朋友时),旧链接可能会消失。此外,可以将新节点引入图表(例如,用户可以加入社交网络)并创建指向现有节点的新链接。
由于以下挑战,天真地应用一种静态嵌入算法会导致性能不令人满意:

  • 稳定性:即使图形不会改变太大,在连续时间的嵌入也可能会有很大差异。
  • 成长的图:所有现有方法都假设学习图嵌入中有固定数量的节点,因此无法处理成长的图。
  • 可伸缩性:每个快照独立学习嵌入式嵌入方式导致快照数量的运行时间线性。由于学习单个嵌入在计算上很昂贵,因此天真的方法不会扩展到许多快照
  • 的动态网络

Dynamic Node2Vec由F.Beres等人在“动态图中的节点嵌入”中创建。

memgraph-dynamic-node2vec

Implementation Link

12.动态Pagerank

在估计图节点重要性的领域中,PageRank可以说是最受欢迎的工具。如今,世界上最受欢迎的搜索引擎Google,仅归功于该算法,该算法是由其创始人在早期开发的。

如果我们将节点显示为页面和它们之间的指向边缘,则作为链接,Pagerank算法输出了一个概率分布,用于表示一个人随机单击链接的人将到达任何特定页面。

>

当节点和边缘在短时间内到达时,需要进行动态实现。每次图表更改时,大量更改会导致到达时不一致的信息或重新启动算法。由于这种变化经常发生,因此动态实现允许保留先前处理的状态,并以这种方式更新新的更改,使得只有在恒定时间处理到达实体的附近。这节省了时间,并使我们能够更新和准确的有关Pagerank的新值的信息。

这种方法也存在一些缺点,那就是这种方法不能保证明确正确的解决方案,而是其近似值。这种权衡在计算机科学中很常见,但可以快速执行并确保大规模这样的近似值接近正确的结果。

有价值的工作解释了如何快速计算这些价值观是由Bahmani et. al.StanfordTwitter的工程师开发的。该论文值得在Fast Incremental and Personalized PageRank上阅读。

memgraph-dynamic-pageRank

Implementation Link

13.动态社区检测

要解决图中节点之间的隐藏关系,尤其是那些直接连接的节点,community detection可以提供帮助。这种熟悉的图分析方法正在以各种不同的方式解决。但是,多年来对规模和速度的需求有所增加,因此导致了动态社区检测算法的构建。为了利用可伸缩性和速度的需求,社区检测非常适合动态操作,原因有两个:

  • 复杂性:算法通常具有较高的时间复杂性,该算法与网络中的节点数量缩放
  • 当地:部分更新后,社区变化往往是本地的。

时间图的学术研究产生了LabelRankT: Incremental Community Detection in Dynamic Networks via Label Propagation(Xie等人)。

memgraph-dynamic-community-detection

动态群落检测算法如何适应本地变化的说明

Implementation Link

14.图神经网络(GNN)

Machine learning方法基于数​​据。由于每天都会与音频,视觉或文本的数据(例如图像,视频,文本和语音)相遇 - 研究这些结构的机器学习方法今天正在取得巨大进步。

基于连接的数据可以显示为图形。由于结构本身的多个连接性,这种结构是more complex than images和文本,这是完全不规则且不可预测的。随着图表结构中组织的神经网络的发展,graph machine learning领域正在改善。

在图像中应用相同的原理,例如图像(卷积)将是一个错误。这样的原理基于网格结构,而在任意大小,复杂拓扑和随机连接的图表上,应用相同的策略将导致灾难。

所有卷积网络图方法均基于message propagation。此类消息通过由图表的节点和边缘组成的网络携带信息,而每个节点实体都携带其计算单元。每个节点的任务是处理信息并将其传递给邻居。

已经开发了各种可能性,可以通过图神经网络实现机器学习。从在Spectral Networks and Deep Locally Connected Networks on Graphs出版的卷积网络图开始(Bruna等,2014)。

今天最受欢迎的型号是GraphSAGEGraph Convolutional Networks (GCN)Graph Attention Networks (GAT)Temporal Graph Networks (TGN)-对于动态网络很重要。

memgraph-graph-neural-networks-GNN

上面的网络显示了GNNS中消息传播的计算图。

Implementation Link

15.图分类

让我们查看一个有用的工具,使您可以整体分析图形。 Graph classification启用了这一点。节点的结构和排列可以在图中揭示一些隐藏的特征。

因此,例如,可以通过在其连接图中搜索该模式来检测具有共同行为模式的欺诈者。

为了实现这一目标,主要技术是在图本身的结构上设计功能,然后应用分类算法。这可以通过几种方式实现:

  • Graphlet features-特定图表的数量指示特征向量的单个元素
  • Weisfeiler-Lehman kernel-颜色精致,向附近教授颜色,直到获得收敛
  • 图形深度学习 - 设计一个可以根据图的结构提取更深特征的网络

memgraph-graph-classification

分子结构图分类的不同标签的概率

Implementation Link

16.链接预测

Link prediction是预测连接以前未连接在图中的两个节点的概率的过程。可以将各种不同的解决方案应用于此类问题。

这个问题在推荐系统,共同创作预测,药物发现等方面非常重要。

解决方法从传统到基于机器学习。传统方法主要基于邻里相似性。如果有许多常见的邻居,则更有可能存在两个节点之间的链接。这些是:

  1. Jaccard similarity
  2. Overlap similarity
  3. Adamic-Adar index

另一方面,可以通过查看相似性指标从节点端点学习这样的预测。节点越相似,它们之间连接性的可能性就越大。 Cosine similarity and Euclidean distance就是这样的一个例子。

然后,到目前为止,有最先进的模型,它们基于graph embeddings,它是进一步分类任务的功能。同样,可以驱动相同任务的图形神经网络(GNN)方法。

memgraph-link-prediction

预测某些社区中的关系

Implementation Link

17.节点分类

可以在节点级别完成预测。此类预测系统的基础是从图实体中提取的特征。

提取功能可能是一个复杂的问题,它可以基于不同的图属性属性,节点邻接或邻居的结构。

从节点中提取知识的传统方法包括centrality的度量,重要性或特征结构,例如graphlets

更高级的方法是提取单个节点的embedding,然后是一种从嵌入本身中获取知识的预测算法。最受欢迎的工具是Node2Vec

但是,这些方法只有少数。当今的图形机器学习正在开发,其中我们区分了许多不同的模型,例如:

  1. GraphSAGE
  2. DeepWalk
  3. Graph convolutional networks (GCN)
  4. Graph Attention Network (GAT)

还有很多。该任务已经变得非常流行,并且在许多行业中使用了知识以图形结构的形式存储。

以前标记的节点可用于确定未分类的节点

memgraph-node-classification

Implementation Link

18. node2vec

Embedding方法用于将图形实体映射到n维矢量中。这种方法的目的是根据所选的相似性估计方法将密切相关的实体映射到具有高度相似性的向量。

Node2Vec是最受欢迎的方法。它基于随机步行。该方法的重点是映射节点,这些节点最有可能在n维空间中的常见随机步行中到达同一位置。该方法由斯坦福大学的教授Aditya GroverJure Leskovec开发。

映射向量本身的优化是通过诸如梯度下降之类的众所周知的机器学习方法来完成的。最后,获得的结果可用于节点分类或链接预测,两者都真正流行。

memgraph-node2Vec

图表如何映射到2D空间。类之间的边界比图中更可见。

Implementation Link

19.图聚类

graph theory中,图形聚类用于查找类似节点的子集并将它们分组在一起。它是图形分析的一部分,由于现实世界中网络的普遍存在,近年来一直引起人们的关注。

图形聚类也称为网络分区,可以是两种类型:

  • 基于结构的
  • 基于属性的聚类

基于结构的基于结构可以进一步分为两个类别,即基于社区和结构等效的聚类。

基于社区的方法旨在查找具有大量群集内边缘和群间边缘数量少的密集子图。示例是以下算法:

相反,

结构等效聚类旨在识别具有相似作用的节点(例如桥梁和轮毂)。一个例子是SCAN: A Structural Clustering Algorithm for Networks

一个可以在社区基于社区和结构等效聚类之间变化的示例是Node2Vec

基于属性的方法,除了观察到的链接外,还利用节点标签,以群集节点,例如以下算法:Graph clustering based on structural/attribute similarities

memgraph-graph-clustering

memgraph-graph-clustering-2

基于结构的社区聚类

Implementation Link

结论

这些是要检查的前19个图形算法 - 从Pagerank到中心性,这里的所有内容。让他们走吧,让我们知道您是否有任何挑战,即通过在DiscourseDiscord

上发布将它们与memgraph一起使用。

Read more about graph algorithms on memgraph.com