🔎大家好，我是Sonhhxg_柒，希望你看完之后，能对你有所帮助，不足请指正！共同学习交流🔎

📝个人主页－Sonhhxg_柒的博客_CSDN博客 📃

🎁欢迎各位→点赞👍 + 收藏⭐️ + 留言📝

📣系列专栏 – 机器学习【ML】自然语言处理【NLP】深度学习【DL】

🖍foreword

✔说明⇢本人讲解主要包括Python、机器学习（ML）、深度学习（DL）、自然语言处理（NLP）等内容。

如果你对这个系列感兴趣的话，可以关注订阅哟👋

文章目录

技术要求

社区检测及其应用介绍

识别节点集群

社区检测方法的应用

推荐引擎和有针对性的营销

欺诈识别

预测属性或链接

社区检测技术的简要概述

检测图形组件和可视化社区

弱连接组件

强连接组件

将 GDS 结果写入图表

使用 neovis.js 可视化图表

使用 NEuler，图形数据科学游乐场

用于社区检测可视化

运行标签传播算法

定义标签传播

加权节点和关系

半监督学习

在 Python 中实现标签传播

使用 GDS 中的标签传播算法

使用种子

将结果写入图表

了解Louvain算法

定义模块化

所有节点都在自己的社区中

所有节点都在同一个社区

最优分区

重现 Louvain 算法的步骤

GDS 中的 Louvain 算法

句法

关系投影中的聚合方法

中间步骤

Zachary 的空手道俱乐部图上的 Label Propagation 和 Louvain 之间的比较

超越 Louvain的重叠社区检测

Louvain算法的注意事项

分辨率限制

Louvain的替代品

重叠社区检测

动态网络

测量节点之间的相似性

基于集合的相似性

重叠

杰卡德相似度

基于向量的相似性

欧几里得距离

余弦相似度

概括

问题

进一步阅读

现实世界的图既不是规则的也不是完全随机的网格。它们的边缘密度不均匀，因此我们最终找到了一些有趣的模式。中心性算法利用一些节点可以比其他节点拥有更多连接的事实来评估节点重要性（参见第 6 章，节点重要性）。在本章中，我们将发现一种新型算法，其目标是识别彼此高度连接的节点组并形成社区或集群。其中一些社区检测算法已经在 GDS 中实现：组件算法、标签传播算法和 Louvain 算法。本章是我们使用 JavaScript 构建社区图形表示并发现 NEuler（由 Neo4j 开发的图形算法游乐场应用程序）的机会。最后，我们还将了解 GDS 中实现的不同指标，以在本地测量两个节点之间的相似性。

本章将涵盖以下主题：

社区检测及其应用介绍
检测图形组件和可视化社区
运行标签传播算法
了解Louvain算法
超越 Louvain 的重叠社区检测
测量节点之间的相似性

技术要求

在本章中，我们将使用以下工具：

Neo4j 图形数据库列出了以下缩进扩展：
插件：图形数据科学库
Neo4j 桌面应用程序
用于图形可视化的 NEuler
您还需要一个浏览器来打开 HTML 和我们将为图形可视化构建的 JavaScript 文件。
Python（推荐≥3.6）运行一些算法的示例实现。
本章使用的代码可在本书的 GitHub 存储库中找到，网址为
https://github.com/PacktPublishing/Hands-On-Graph-Analytics-with-Neo4j/ch7

如果您使用的是Neo4j < 4.0，那么GDS的最后一个兼容版本是1.1。
如果您使用的是Neo4j ≥ 4.0，那么GDS的第一个兼容版本是1.2。

社区检测及其应用介绍

社区检测收集已开发用于理解图结构并从中提取信息的技术。这种结构随后可以用于许多应用中，例如推荐引擎、欺诈检测、属性预测和链接预测。

在本章中，我将使用community、cluster或partition来指代一组共享公共属性的节点。

识别节点集群

下图显示了我们在第 2 章“ Cypher 查询语言”中构建的 Neo4j GitHub 用户图表。社区检测算法能够识别几个社区：

使用 Louvain 算法和 neoviz.js 生成的图像

在本章结束时，您将能够重现此图像。需要进一步分析以了解紫罗兰社区用户的共同属性。对该图的更深入分析告诉我们，紫罗兰社区中的用户显然从人群中脱颖而出，并且大部分都为独特的存储库做出了贡献。

在深入每个算法的技术细节之前，我们首先要更多地讨论知道节点属于哪个社区的优势。虽然我们在这里谈论的是由用户组成的社区，但这可以应用于许多其他领域。我们将在本节的其余部分介绍其中的一些。

社区检测方法的应用

社区检测和图聚类有很多应用。例如，它们可用于以下领域：

生物学：蛋白质-蛋白质相互作用网络模拟细胞内的蛋白质相互作用。属于同一群落的蛋白质更有可能参与相同的功能。
神经科学：研究人员将人脑建模为图形，其中每个节点都是少量细胞。事实证明，了解该图的社区结构对于了解大脑的不同部分如何相互协调特别有用。
公共卫生：我们可以使用人口的社区结构来尝试和预测疾病的演变和传播。

接下来的部分将重点介绍一些更有可能对您直接有用的应用程序。

欺诈识别

欺诈检测在前一章（第 6 章，节点重要性）中讨论过。我们讨论了欺诈者创建犯罪团伙并相互合作以避免被发现的方式。这种组织很难通过传统方法检测到，但由于其基于关系的原生结构，图表是打击所有类型欺诈的非常有用的工具。假设欺诈者之间会进行更多互动，例如在假用户共享相同电话号码或地址的情况下，图表可以形成一个社区并且更容易识别。

预测属性或链接

社区检测和上述大多数应用的基本思想之一是属于同一社区的节点共享一些属性。这可用于根据图的社区结构进行预测。让我们从下图所示的子图开始：

它包含三个节点A、B和C，以及两条边（（A，B）和（A，C））。这可能是具有更多输出边的更大图的一部分。节点A和B有一个值为 1 的属性。这可能是某些用户的年龄类别，这并不总是可用的。用户A和B填写了该字段，表明他们在 21 到 30 之间。最重要的是，一些社区检测算法已经设法将所有三个节点聚集到同一个社区中。直观地说，我们可以说节点C的概率随着有关图结构的新知识，也属于 21-30 岁年龄段。

类似地，如果我们试图测量B和C之间的边在我们不知道或将来出现的情况下存在的概率，那么对于同一社区中的节点来说它会更高。

社区检测技术的简要概述

最早的图结构研究之一是由 Weiss 和 Jacobson 进行的，并于 1955 年发表。从那时起，已经使用不同类型的规则研究和实现了几种类型的算法。

至于节点重要性问题，在社区检测问题的情况下，首先要考虑的是定义度量或目标函数，它将量化图分区的好坏。社区最常见的定义指出，社区是一组节点，其社区内连接（同一社区中的节点之间的边更多）比社区间连接（两个不同社区中的节点之间的边）多。但是即使有了这个定义，也有几种可能的方法可以实现令人满意的分区。

已经提出了许多算法，使用不同的度量。例如，层次聚类使用一些规则来创建树状图，从而创建聚类的层次结构。Girvan-Newman 算法是层次聚类的一个例子，它使用了通常用于节点到边的中介中心性的扩展：具有最高中介中心性的边是图中两对节点之间的最短路径中最常涉及的边。其他层次聚类算法使用相似性度量而不是拓扑度量。在本章的最后（在测量节点之间的相似性部分），我们将学习如何测量节点之间的相似性。

在本书中，我们将重点介绍 Neo4j 中实现的一些算法：

连接组件，它允许我们检测断开连接的子图。
标签传播，顾名思义，通过基于多数投票规则的图传播社区标签，以将每个节点分配给其新社区。
Louvain 算法优化了模块化，定义为社区内连接数与社区间连接数之间的差异。

即使尚未在 GDS 中实现，我们也会讨论这些算法的一些改进建议，尤其是 Leiden 算法，该算法旨在解决 Louvain 算法的一些问题。我们还将简要解决上述算法未涵盖的重叠社区问题。

现在让我们使用连接组件算法开始我们的社区检测之旅。在下一节中，我们将学习组件算法。我们还将发现以图形格式可视化检测到的社区的工具，这对于理解中图的结构至关重要。

检测图形组件和可视化社区

图形组件具有明确的数学定义。在给定的组件中，两个节点始终通过路径相互连接，但不连接到组件外的任何其他节点。有两个版本的连接组件：

强连接组件：这些确保同一组件中的两个节点之间的路径存在于两个方向。
弱连接组件：对于弱连接组件，单个方向就足够了。

让我们看看 Neo4j 中的一个例子。在本节中，我们还将在本书中首次使用写入过程将算法结果存储在 Neo4j 中。我们还将引入一个新的 JavaScript 库来自定义大图的可视化。

让我们从以下有向图开始：

用于创建图表的 Cypher 代码可在 GitHub ( https://github.com/PacktPublishing/Hands-On-Graph-Analytics-with-Neo4j/blob/master/ch7/test_graph.cql ) 上获得。

在视觉上，我们可以说这个图中至少有两个组件。节点Y和Z与图中的任何其他节点完全断开连接，因此从这两个节点到图中的任何其他节点都没有任何路径。让我们看看如何从 GDS 中实现的算法中学习这些信息。

我们将使用以下投影图：

CALL gds.graph.create("simple_projected_graph", "Node", "LINKED_TO")

此投影图包含带有标签的所有节点Node以及与自然方向上的类型的所有关系LINKED_TO（如使用 Cypher 创建它们时定义的那样，如上图所示），它们没有附加任何属性。

弱连接组件

我们将在这里学习的第一个算法是弱连接组件或联合查找。

弱连接组件，连同我们将在本章后面介绍的 Louvain 和标签传播算法，都是 GDS 1.0 版中的生产就绪算法。

要查看使用弱连接组件进行图分区的结果，请使用以下查询：

CALL gds.wcc.stream("simple_projected_graph") 
YIELD nodeId, componentId
RETURN gds.util.asNode(nodeId).name as nodeName, componentId
ORDER BY componentId

这是我们的结果：

╒══════════╤═════════════╕
│"nodeName"│"componentId"│
╞══════════╪═════════════╡
│"A"       │0            │
├──────────┼─────────────┤
│"B"       │0            │
├──────────┼─────────────┤
│"C"       │0            │
├──────────┼─────────────┤
│"D"       │0            │
├──────────┼─────────────┤
│"E"       │0            │
├──────────┼─────────────┤
│"F"       │0            │
├──────────┼─────────────┤
│"G"       │0            │
├──────────┼─────────────┤
│"Y"       │7            │
├──────────┼─────────────┤
│"Z"       │7            │
└──────────┴─────────────┘

如您所见，该算法成功识别出两个组件：

此示例中标记的组件7，包含节点Y和Z
另一个标记为的组件0，包含所有其他节点

用于标记社区的确切数字不相关；这取决于 GDS 的内部功能。根据您的图表的创建方式，您获得的数字可能会有所不同，但应该检测到相同的社区。

考虑到图是无向的，弱连接组件告诉我们，我们的图中有两个不连接的分区。如果关系方向很重要，例如在道路网络中，那么我们将不得不使用强连通分量算法。

强连接组件

在强连接的组件中，关系的方向很重要。组件中的每个节点都必须能够在两个方向上连接同一组件中的任何其他节点。关注节点A到G，通过弱连通分量算法将它们分组在同一个社区中，您可以看到并非总是可以从一个节点到另一个节点在两个方向上。例如，从D到A是可能的（通过C），但从A到D是不可能的。

要查看使用此更强规则标识的组件，我们可以gds.alpha.scc按以下方式使用该过程：

CALL gds.alpha.scc.stream("simple_projected_graph") 
YIELD nodeId, partition as componentId
RETURN gds.util.asNode(nodeId).name as nodeName, componentId
ORDER BY componentId

以下是前面代码的结果：

╒══════════╤═════════════╕
│"nodeName"│"componentId"│
╞══════════╪═════════════╡
│"A"       │0            │
├──────────┼─────────────┤
│"B"       │0            │
├──────────┼─────────────┤
│"C"       │0            │
├──────────┼─────────────┤
│"D"       │3            │
├──────────┼─────────────┤
│"E"       │3            │
├──────────┼─────────────┤
│"F"       │3            │
├──────────┼─────────────┤
│"G"       │3            │
├──────────┼─────────────┤
│"Y"       │7            │
├──────────┼─────────────┤
│"Z"       │7            │
└──────────┴─────────────┘

这一次，确定了三个组件：虽然节点Y和Z仍在它们自己的组件中，但节点A、B和C现在与D、E、F和断开连接G。

连通分量对于理解我们的图结构是非常有用的算法。一些算法，如 PageRank（参见第 6 章，节点重要性）可能会在具有多个组件的图上导致意外结果。在图形数据分析的数据探索部分运行连接组件算法是一种很好的做法。

在继续研究其他社区检测算法之前，我们将讨论一些允许我们以更好的格式可视化社区的工具。其中一些将要求社区编号 ( componentID) 是节点属性。这就是为什么我们现在要解决 GDS 的一个功能，我们目前还没有利用：在 Neo4j 图中写入算法结果的可能性，而不是将它们流回给用户并让他们决定如何处理它们.

将 GDS 结果写入图表

在第 4 章，图形数据科学库和路径查找中，我们介绍了 GDS 的写入功能，允许我们将算法的结果存储在 Neo4j 中。此功能适用于 GDS 中实现的几乎所有算法。基本上，不提供此选项的算法是返回矩阵的算法，例如All Pairs 最短路径算法或我们将在本章末尾介绍的一些相似性算法。

让我们看一下使用连接组件算法的写入过程的应用。

写入过程的语法与流一非常相似。主要区别在于它接受另一个配置参数，writeProperty它允许我们配置将添加到每个节点的属性的名称。

以下查询会将弱连接组件算法的结果写入wcc每个节点的属性中：

CALL gds.wcc.write("simple_projected_graph", {writeProperty: "wcc"}
)

这里，返回的结果包含有关算法运行时间和图结构的信息：

但是要查看每个节点所属的分区，我们将不得不使用另一个 Cypher 查询：

MATCH (n:Node) 
RETURN n.name as nodeName, n.wcc

使用强连接的组件也可以实现相同的目标：

CALL gds.alpha.scc.write("simple_projected_graph", {writeProperty: "scc"})

在其之上name，每个节点现在还包含另外两个名为wccand的属性scc，其中包含根据弱连接和强连接组件算法该节点所属的组件的 ID。在这里，您可以看到 node 的内容D：

{"name": "D","scc": 3,"wcc": 0
}

当图非常大时，将结果写入图有时是唯一的解决方案（我们将在第 12 章，Neo4j at Scale中更多地讨论大数据的情况）。但它在其他情况下也很有用。我们现在将讨论其中之一。

到目前为止，我们只使用了非常小的图表，通过从表格中读取结果很容易理解它们。但这不是图算法最常见的用例，它主要用于中型和大型图。在这些情况下，以图形格式可视化社区检测算法的结果对于理解图形的结构可能更为重要。在下一节中，我们将发现两种根据属性绘制不同大小或颜色的节点的方法：第一种是neovis.js用于将图形可视化嵌入 HTML 页面的 JavaScript 库，第二种是 NEuler，Graph Algorithms Playground，一个基于此包的 Neo4j 桌面应用程序。

使用 neovis.js 可视化图表

当涉及到社区时，有一种方法来可视化节点分类和它们之间的关系总是有用的。图形可视化本身就是一个研究领域，并且存在许多用于良好可视化的软件包。例如，用于数据可视化的最完整的 JavaScript 库之一d3.js，也具有绘制图形的功能。但是，在使用时d3.js，必须管理与 Neo4j 的连接、数据检索和格式化。这就是为什么在本节和本章的其余部分中，我们将使用开源neovis.jsJavaScript 库的原因。它非常易于使用，因为与 Neo4j 的连接是在内部管理的，我们不需要任何有关 Neo4j JavaScript 驱动程序的知识就可以使其工作。neovis.js还创建了非常漂亮的可视化，就像本章第一张图展示的 Neo4j GitHub 社区一样，它有很多可自定义的参数。

完整的工作示例可在https://github.com/PacktPublishing/Hands-On-Graph-Analytics-with-Neo4j/ch7/connected_components/graph_viz.htmlgraph_viz.html上的文件中找到。

使用以下命令从 GitHub 存储库导入库：

    <script src="https://rawgit.com/neo4j-contrib/neovis.js/master/dist/neovis.js"></script>

最小的 HTML 代码如下：

    <body onload="draw()"><div id="graph"></div></body>

加载body后会调用前面draw的函数，将图形绘制到div函数中id="graph"。主函数是draw函数，包含配置参数和渲染方法：

function draw() {let config = {// the ID of the "div" the graph will be drawn intocontainer_id: "graph",// connection parameters to your Neo4j Graph// default is "bolt://localhost:7687" server_url: "bolt://localhost:7687",server_user: "neo4j",server_password: "*****",// Node labels to be fetched// and properties used to customize each node renderinglabels: {"Node": {"caption": "name",  // label drawn next to each node"community": "scc",  // defines the node color}},relationships: {"LINKED_TO": {// disable caption for relationships // since they do not carry any relevant information in our case"caption": false, }},arrows: true, // display the relationships directioninitial_cypher: "MATCH (n:Node)-[r:LINKED_TO]->(m) RETURN *"};let viz = new NeoVis.default(config);viz.render();}

您需要更新图表的连接参数： server_url、server_user和server_password。server_password对应于在 Neo4j Desktop 中添加新图形时要求您创建的密码。

可以使用您喜欢的浏览器打开该文件graph_viz.html，以查看我们图中的不同社区，由强连通分量算法（scc属性）标识。生成的图像应如下图所示：

如果需要，您还可以通过在draw函数中指示节点配置的大小参数以及包含其重要性的节点的属性来可视化节点重要性；例如：

             labels: {"Node": {"caption": "name",  // label drawn next to each node"community": "scc",  // defines the node color"size": "pagerank"}},

要使此代码正常工作，您需要在投影图上使用写入过程运行 PageRank 算法：
CALL gds.pageRank("simple_projected_graph", {writeProperty: "pagerank"})

但请记住，PageRank 可能会在图不连贯的情况下产生意想不到的结果。

neoviz.js如果您想将图形嵌入到 HTML 页面中，它是一个强大而有趣的工具。但是，如果您只需要测试算法的结果，则存在一个更简单的解决方案：NEuler。

使用 NEuler，图形数据科学游乐场

NEuler 是集成在 Neo4j Desktop 中的开源应用程序，其代码可在 GitHub 上的GitHub – neo4j-devtools/neuler: Playground for Neo4j Graph Algorithms上找到。

它是一个非常强大的工具，允许我们测试 GDS 中实现的所有算法，从路径查找（第 4 章，图形数据科学库和路径查找）和中心性（第 5 章，节点重要性）到社区检测和相似性。它还可以使用基于neoviz.js.

本书的 GitHub 存储库中提供了安装说明。

用于社区检测可视化

以下屏幕截图所示的主屏幕是您可以选择要运行的算法类型的地方：

选择社区检测算法后，您可以从上方菜单中选择要尝试的算法。对于这个例子，我们将使用强连通分量算法。单击其名称后，您可以从右侧栏中配置投影图和算法参数。以下屏幕截图中所示的配置将执行以下操作：

在包含节点标签Node和关系类型LINKED_TO的投影图上运行算法orientation=UNDIRECTED。

将结果存储在名为的属性中scc。

单击“运行”按钮将调用正确的 Cypher 程序，您可以通过“代码”选项卡进行检查：

最后，您可以在“可视化”选项卡中可视化结果。在那里，您可以自定义将用于为它们着色的节点属性，就像我们在上一节中所做的那样neovis.js：

这将关闭我们关于连接组件的部分。我们已经了解了弱连接和强连接组件算法如何帮助我们识别图中不连接的社区。我们还发现了两种不同的可视化社区检测算法结果的方法。我们将在以下部分继续使用它们，我们将在其中发现新型社区检测算法：标签传播和 Louvain 算法，它们都是 GDS 生产质量层的一部分。

运行标签传播算法

标签传播是社区检测算法的另一个例子。于 2017 年提出，其优势在于可以为已知节点设置一些标签，并以半监督的方式从中导出未知标签。它还可以考虑关系和节点权重。在本节中，我们将通过 Python 中的简单实现来详细介绍该算法。

定义标签传播

存在标签传播的几种变体。主要思想如下：

标签被初始化，使得每个节点都位于自己的社区中。
标签根据多数投票规则迭代更新：每个节点接收其邻居的标签，并将其中最常见的标签分配给节点。当最常见的标签不是唯一的时，就会出现冲突。在这种情况下，需要定义一个规则，它可以是随机的或确定性的（就像在 GDS 中一样）。
重复迭代过程，直到所有节点都有固定的标签。

最佳解决方案是连接具有不同标签的两个节点的边数最少的分区。让我们考虑下图：

经过一些迭代，算法将节点A和B分配给一个社区（我们称之为CR），将节点E和G分配给另一个社区（CG）。根据多数投票规则，在下一次迭代中，节点C将被分配到CR社区，因为连接到C的两个节点已经属于这个分区，而只有一个节点 ( D ) 属于另一个集群。同样，节点D将分配给CG社区。生成的图表如下图所示：

加权节点和关系

为了考虑节点或关系的权重，我们可以更新多数投票规则，使其不仅计算具有给定标签的节点数，而且计算它们的权重。所选标签将是权重总和最高的标签。

让我们考虑下图所示的上图的加权版本：

这一次，为了选择节点D的标签，我们必须考虑连接到D的每条边的权重：

CR社区的权重= 1 (C) + 8 (D) = 9
CG社区的权重= 1 (E) + 2 (G) = 3

因此，在该图的加权版本中，节点D将属于CR社区。

半监督学习

标签传播的另一个有趣的方面是它考虑先验知识的能力。如果您已经知道某些节点的社区，则可以在初始化阶段使用此信息，而不是设置随机初始值。这种技术被称为半监督学习，因为只有一些节点被标记为他们的社区。

在 Python 中实现标签传播

在本节中，我们将实现标签传播的简化版本，考虑到种子标签只能取两个不同的值：0 或 1。

我们将使用与前几章相同的图形表示，基于 Python 字典。我们将使用的图形由以下对象表示：

    G = {'A': {'B': 1, 'C': 1},'B': {'A': 1, 'C': 1},'C': {'A': 1, 'B': 1, 'D': 1},'D': {'C': 1, 'E': 1, 'G': 1},'E': {'D': 1, 'F': 1, 'G': 1},'F': {'E': 1, 'G': 1},'G': {'D': 1, 'E': 1, 'F': 1},}

它告诉我们节点A连接到节点B和C，两条边的权重都等于 1。

现在让我们开始算法。在初始化阶段，我们用唯一值初始化所有标签。查找唯一值的一种方法是在循环中使用它们的索引来遍历的键G，这可以在 Python 中通过以下方式实现：

    labels = {node:k  for k, node in enumerate(G)}

该enumerate(iterable)函数返回一个元组，其中包含一个计数（从 0 开始）和通过迭代获得的值iterable。在这里，iterable是我们的字典G，并且迭代G相当于在 Python 中迭代它的键。

然后我们进入主循环。在每次迭代中，我们在图中的所有节点上执行一个循环，并为每个节点计算它收到的票数：

    for it in range(max_iterations):print("======= Iteration", it)# create a copy of the labels computed in previous iterationold_labels = dict(labels)for node, neighbors in G.items():# counting the number of votes from each neighbors:votes = Counter([old_labels[n] for n in neighbors])

为了找到多数票，我们可以使用以下代码，它将遍历收到的票，并在每次找到高于当前最大值的值时更新新标签的值：

            max_vote = -9999new_label = old_labels[node]for label, vote  in votes.items():if vote > max_vote:max_vote = votenew_label = labelelif vote == max_vote:  # deterministic rule to disentangle equality votes (arbitrary)if label > new_label:new_label = labellabels[node] = new_label

为了区分两个标签具有相同投票数的情况，我们使用完全任意的规则来选择具有最高值的标签。

一旦所有标签都更新了，我们可以通过检查自上次迭代以来没有标签发生变化来检查算法的收敛性：

        end = Truefor node in G:if old_labels[node] != labels[node]:# if at least one node's label has changed, go to next iterationend = Falsebreakif end:return labels

在本节开头定义的图 G 上运行此代码，我们得到以下结果：

{'A'：3，'B'：3，'C'：3，'D'：6，'E'：6，'F'：6，'G'：6}

确定了两个社区：第一个社区被标记3并包含节点A、B和C，而第二个社区被标记6并包含节点Dto G。请记住，标签本身是没有意义的，因为它们只是来自图形定义中的节点位置。不同的实现会为标签返回不同的值，但会保留社区结构。

Label Propagation 不能保证收敛，我们最终可能会出现振荡，其中给定节点的标签不稳定并且在每次迭代时在两个值之间振荡，从而导致收敛失败。

完整代码可在 GitHub 上的https://github.com/PacktPublishing/Hands-On-Graph-Analytics-with-Neo4j/ch7/label_propagation/label_propagation.py 获得。我们鼓励您复制和修改它以帮助您了解它的工作原理。例如，更新代码以考虑节点和关系权重。请注意，实现保持尽可能简单，以允许您利用您对 Python 的先验知识。例如，如果您已经了解networkx和numpy，您可以尝试修改此代码以使其适用于netwokx图形或使用矩阵公式（参见前一章，第 6 章，节点重要性）。

使用 GDS 中的标签传播算法

标签传播算法是生产质量算法的一部分，这意味着它经过了很好的测试和针对大型图的优化。我们将在我们在弱连接组件部分研究的图上测试运行标签传播算法。创建它的 Cypher 代码可在https://github.com/PacktPublishing/Hands-On-Graph-Analytics-with-Neo4j/ch7/test_graph.cql获得。

让我们创建一个无向投影图：

CALL gds.graph.create("projected_graph", "Node", {LINKED_TO: {type: "LINKED_TO", orientation: "UNDIRECTED"}}
)

要在该图上执行标签传播算法，我们可以使用以下查询：

CALL gds.labelPropagation.stream("projected_graph")
YIELD nodeId, communityId
RETURN gds.util.asNode(nodeId).name AS nodeName, communityId
ORDER BY communityId

结果如下：

╒══════════╤═════════════╕
│"nodeName"│"communityId"│
╞══════════╪═════════════╡
│"A"       │39           │
├──────────┼─────────────┤
│"B"       │39           │
├──────────┼─────────────┤
│"C"       │39           │
├──────────┼─────────────┤
│"D"       │42           │
├──────────┼─────────────┤
│"E"       │42           │
├──────────┼─────────────┤
│"F"       │42           │
├──────────┼─────────────┤
│"G"       │42           │
├──────────┼─────────────┤
│"Y"       │46           │
├──────────┼─────────────┤
│"Z"       │46           │
└──────────┴─────────────┘

已经确定了三个社区：两个类似于我们在上一节中确定的社区，加上一个包含节点Y和的额外社区Z，这些社区没有包含在我们之前的研究中。

同样，的确切值communityId可能会有所不同；它与nodeId财产有关。但是同一社区中的所有节点将始终具有相同的communityId.

使用种子

为了测试我们的算法，我们首先需要向图中添加一个新属性，该属性将保持我们对节点社区成员身份的先验信念—— knownCommunity：

MATCH (A:Node {name: "A"}) SET A.knownCommunity = 0;
MATCH (B:Node {name: "B"}) SET B.knownCommunity = 0;
MATCH (F:Node {name: "F"}) SET F.knownCommunity = 1;
MATCH (G:Node {name: "G"}) SET G.knownCommunity = 1;

对于某些节点，我们添加了一个名为的属性knownCommunity，它存储了我们关于每个节点所属社区的先验知识（或信念）。

然后，我们可以创建命名的投影图。该图将包含带有Node标签的所有节点以及带有类型的所有关系LINKED_TO。为了以半监督的方式使用该算法，我们还需要明确告诉 GDS 将knownCommunity节点属性存储在投影图中。最后，我们会将我们的图视为无向图，这是通过orientation: "UNDIRECTED"在关系投影中指定参数来实现的：

CALL gds.graph.create("projected_graph_with_properties", { // node projection:Node: {label: "Node",properties: "knownCommunity"}}, { // relationship projection:LINKED_TO: {type: "LINKED_TO",orientation: "UNDIRECTED"}
})

现在我们可以在这个命名的投影图上运行标签传播算法，并使用以下内容流式传输结果：

CALL gds.labelPropagation.stream("projected_graph_with_properties", {seedProperty: "knownCommunity"
})
YIELD nodeId, communityId
RETURN gds.util.asNode(nodeId).name AS nodeName, communityId
ORDER BY communityId

您可以从结果中看到已识别的社区相似，但是communityId现在反映了通过给出的值seedProperty。

将结果写入图表

要使用我们在上一节中编写的代码在浏览器中可视化结果，我们需要将结果存储在图形中，这可以通过以下gds.labelPropagation.write过程来实现：

CALL gds.labelPropagation.write("projected_graph_with_properties", {seedProperty: "knownCommunity",writeProperty: "lp"}
)

诸如标签传播之类的算法是一个很好的例子，说明图算法已经被用于更经典的机器学习模型中。事实上，标签传播用于机器学习中的分类和回归，其中传播是通过相似矩阵（而不是前一章讨论的邻接矩阵）执行的。

现在，我们将关注另一个重要的社区检测算法：Louvain 算法。

了解Louvain算法

鲁汶算法是由比利时鲁汶大学的研究人员于 2008 年提出的，该算法因此得名。它依赖于与其他节点的连接相比，社区内连接密度的度量。这个度量被称为模块化，它是我们首先要理解的变量。

定义模块化

与不同社区中节点之间的链接相比，模块化是量化同一社区中节点内链接密度的度量。

从数学上讲，它的定义如下：

Q = 1/(2m) * Σ ij [ A ij – k i k j / (2m)] δ(c i , c j )

在哪里：

如果节点i和j连接，则A ij为 1，否则为 0。
k i是节点i的度数。
m是边缘携带的所有权重的总和。我们也有关系Σ i k i = 2m，因为所有节点的总和将对每条边计算两次。
c i是算法分配给节点i的社区。
δ(x, y)是 Kronecker delta 函数，如果x=y则等于 1 ，否则等于 0。

为了理解这个等式的含义，让我们分别关注每个术语。具有k i个边的节点i有k i个机会连接到图中的任何其他节点。所以两个节点i和j有k i xk j机会相互连接。因此，术语k i k j / (2m)对应于节点i和j相互连接的概率。

在等式的另一边，A ij是i和j之间的真实连接状态。因此，sigma 符号下的项量化了同一社区（在随机图中）的两个节点之间的实际边数和预期边数之间的差异。

同一个社区中的两个节点应该比平均值更频繁地连接，因此A ij > k i k j / (2m)。Louvain 算法就是基于这个性质，并试图最大化模块化Q。

这种模块化的定义也适用于加权图。在这种情况下，A ij是i和j之间关系的权重。

在继续讨论算法本身之前，让我们研究一下特殊的图分区以及模块化对它们的价值。可以使用https://github.com/PacktPublishing/Hands-On-Graph-Analytics-with-Neo4j/ch7/louvain/modularity.py上的简单 Python 实现来挑战结果。

在本节的其余部分，为了简单起见，我们将使用与前一节类似的图表，不包括节点Y和Z，以便处理单个组件。

所有节点都在自己的社区中

如果所有节点都在自己的社区中，则δ(c i , c j )始终为 0，因为c i始终不同于c j，除非i=j的情况。由于我们的图没有自环（连接到自身的节点），因此 A ii始终等于 0，并且仅保留和中的负项。所以在那种特殊情况下，模块化Q是负的。在下文中，我们将其写为Q diag，它在我们的图表中的值为Q diag =-0.148。

所有节点都在同一个社区

在另一个极端情况下，所有节点都在同一个社区中，δ(c i , c j )始终为 1。因此模块化如下：

Q = 1/(2m) * Σ ij [ A ij – k i k j / (2m)]

Aij项的所有节点对的总和对应于所有边的权重总和，计算两次（对于ij和ji对）。所以，我们有以下内容：

Σ ij A ij = 2m

让我们重写方程的第二项：

Σ ij k i k j / (2m) = Σ i (k i (Σ j k j )) / 2m = Σ i (k i (2m) / 2m = Σ i k i = 2m

因此，在所有节点都在同一个社区中的特殊情况下，模块化Q=0。

最优分区

我们在本节中使用的简单图的最佳分区类似于使用连接组件或标签传播算法获得的分区：节点A、B和C在它们自己的分区中，而节点D到G在另一个社区中。

当 m = 9 时，这种情况下的模块性如下：

Q = 1/18 (
2 * (AAB – kAkB / 18 + AAC – kAkC / 18 + ABC – kBkC / 18)
+ 2 * (ADE – kDkE / 18 + ADG – kDkG / 18 + ADF – kDkF / 18 + AEF – kEkF / 18 + AEG – kEkG / 18 + AGF – kGkF / 18 )
) + Qdiag
= 1 / 18 * 2 * (
1 – 2 * 2 / 18 + 1 – 2 * 3 / 18 + 1 – 2 * 3 / 18
+ 1 – 3 * 3 / 18 + 1 – 3 * 3 / 18 + 0 – 3 * 2 / 18 + 1 – 3 * 2 / 18 + 1 – 3 * 3 / 18 + 1 – 3 * 2 / 18
) – 0.148
= 0.364 > 0

由于我们的图是无向的，我们可以将对应于 A 和 B ( ) 之间关系的项加倍A – B，而不是将项A -> B 和相加B -> A。

模块化也可以用来衡量另一种算法检测到的分区的质量。

现在我们对模块化有了更好的理解，在展示 Neo4j 和 GDS 的一些示例之前，我们将看看如何重现 Louvain 算法。

重现 Louvain 算法的步骤

Louvain 算法旨在最大化模块化，作为损失函数。从每个节点分配到自己的社区（Q=0）的图开始，算法将尝试将节点移动到其邻居的社区，并且仅当它使模块化增加时才保持此配置。

该算法在每次迭代中执行两个步骤。在第一个过程中，对所有节点执行迭代。对于每个节点n及其每个邻居k，该算法尝试将节点n移动到与k相同的社区。节点n被移动到导致模块化程度最高的社区。如果无法通过这样的操作增加模块性，则节点n的社区在此迭代中保持不变。

在第二步中，算法将属于同一社区的节点组合在一起以创建新节点，并将社区间边的权重相加以在它们之间创建新的加权边。

通过将单个节点从一个社区移动到另一个社区所引起的模块性变化可以计算而无需再次循环整个图。

GDS 中的 Louvain 算法

从 1.0 版开始，Louvain 算法是 Graph Data Science 库中生产质量实施的一部分。

句法

Louvian 算法的用法与其他算法类似。要流式传输结果，请使用gds.louvain.stream带有命名投影图作为参数的过程：

CALL gds.louvain.stream(<projectedGraphName>)

我们还可以使用等效的过程将结果保存在图中write：

CALL gds.louvain.write(<projectedGraphName>, {writeProperty: <newNodeProperty>})

在我们的图上使用 Louvain 算法会导致两个常见的分区，一侧是节点A、B和C ，另一侧是节点D到G。要查看这些算法之间的差异，我们将不得不转向稍大的图表。我们将在后面的章节中看到 Zachary 的空手道俱乐部的例子。

关系投影中的聚合方法

如果您改用该write过程，您会注意到它返回的信息包括最终的模块化。如果您在我们之前创建的投影图上运行此过程projected_graph，您会注意到与我们在上一节中获得的模块化值略有不同。解释来自我们的投影图。D存储在 Neo4j 中的初始图包含and之间的两个关系E（一个 from DtoE和一个 from Eto D）。当 GDS 创建投影图时，默认行为是存储这两种关系，这相当于增加了这条边的权重（A ij项）。因此，我们的投影图等价于以下内容：

    G = { 'A'：{'B'：1，'C'：1}，'B'：{'A'：1，'C'：1}，'C'：{'A'：1， 'B': 1, 'D': 1}, 'D': {'C': 1, 'E': 2, 'G': 1}, 'E': {'D': 2, 'F '：1，'G'：1}，'F'：{'E'：1，'G'：1}，'G'：{'D'：1，'E'：1，'F'： 1}, }

D和之间的边E的权重为 2 而不是 1。

如果我们希望投影图只包含两个节点之间的一个关系，我们必须向关系投影添加另一个属性：aggregation: "SINGLE"，这将强制每对节点通过给定类型的一个关系连接。以下查询将创建一个启用该属性的新投影图：

CALL gds.graph.create("projected_graph_single", "Node",{LINKED_TO: {type: "LINKED_TO", orientation: "UNDIRECTED", aggregation: "SINGLE"}}
)

使用以下语句在这个新投影图上运行 Louvain 算法：

CALL gds.louvain.write("projected_graph_single", {writeProperty: "louvain"})
YIELD nodePropertiesWritten, modularity
RETURN nodePropertiesWritten, modularity

您将再次找到相同的模块化值，大约为 0.36，如以下屏幕截图所示：

如果您查看gds.louvain程序的完整结果，您会发现另一个名为modularities. 它对应于在算法的每个阶段计算的模块化。

中间步骤

GDS 的一个有趣特性是它能够在算法的中间步骤存储社区。需要通过将配置参数设置为来启用此includeIntermediateCommunities选项true。例如，以下查询将为我们的投影图流式传输 Louvain 算法的结果，返回一个额外的列，其中包含每个节点在每次迭代时分配到的社区列表：

CALL gds.louvain.stream("projected_graph_single",{includeIntermediateCommunities: true}
)
YIELD nodeId, communityId, intermediateCommunityIds
RETURN gds.util.asNode(nodeId).name as name, communityId, intermediateCommunityIds
ORDER BY name

在我们的简单图表中，该intermediateCommunityIds列包含一个列表，其中包含一个与最终社区相对应的元素。这意味着一次迭代就足以收敛，鉴于图的尺寸非常小，这并不奇怪。在较大的图上使用此算法时，您将能够在每个步骤中看到图的状态。

如果intermediateCommuntiyIds与 write 过程一起使用，书面属性将包含与中间社区 ID 对应的 ID 列表，而不是仅对最终社区进行编码的单个整数。

Zachary 的空手道俱乐部图上的 Label Propagation 和 Louvain 之间的比较

到目前为止，使用我们使用的小型测试图，标签传播和 Louvain 算法产生相同的社区，但一般情况并非如此。Zachary 的空手道俱乐部图是一个稍大的图，也是图专家中最著名的图之一。它由芝加哥大学的教师韦恩·W·扎卡里 (Wayne W. Zachary) 收集。他观察了 1970 年代这所大学空手道俱乐部成员之间的不同联系。

下图显示了该图上标签传播（左）和 Louvain 算法（右）的结果，包含 34 个节点（学生）。虽然标签传播仅捕获两个社区，但 Louvain 算法能够检测到四个集群：

让我给你更多的背景来更好地理解这个结果。1970年左右，在芝加哥大学的空手道俱乐部，两名教练之间开始发生冲突，导致俱乐部分裂为两个实体。当时，双方都在努力吸引学生，每个导师和学生之间的互动很重要。Zachary 用图表对这些交互进行了建模，其中每个节点都是学生，它们之间的边表示他们在此期间是否进行了交互。所以这张图有一个很大的优势，就是拥有真实信息：扎卡里记录了每个成员在分裂后选择去俱乐部的哪个部分。

回到两种算法检测到的社区划分，Label Propagation 做对了，检测到两个与真实学生划分一致的社区。查看 Louvain 算法的结果，似乎又检测到了一个分区。但是，如果我们合并包含节点 17 的分区（顶部）和包含节点 2 的分区（中间），那么结果非常相似。唯一的区别是节点 10 将位于顶部社区，而在标签传播中，它位于底部社区。

像一些著名的数据科学数据集一样scikit-learn，Zachary 的空手道俱乐部包含在主要的 Python 包中，用于处理图形networkx： import networkx as nx G = nx.karate_club_graph()

我们现在对模块化和 Louvain 算法有了很多了解。在下一节中，我们将了解该算法的一些限制，以及已经提出的一些改进它的替代方案，即使它们（尚未）在 GDS 中实现。

超越 Louvain的重叠社区检测

与所有算法一样，Louvain 算法也有其局限性。了解它们非常重要，因此我们将在本节中尝试这样做。我们还将处理可能的替代方案。最后，我们还将讨论一些允许节点属于多个社区的算法。

Louvain算法的注意事项

与任何其他算法一样，Louvain 算法也有一些已知的缺点。主要的一个是分辨率限制。

分辨率限制

考虑下图，由每个具有七个节点的强连接 blob 组成，通过一条边彼此弱连接：

在此图上运行社区检测，您会期望每个 blob 形成一个社区。虽然这对于小图上的 Louvain 算法效果很好，但众所周知，它在大图上会失败。例如，当在一个结构类似于上图所示但有 100 个 blob 的图上运行时，Louvain 算法将仅识别 50 个社区。这个问题被称为分辨率限制问题：对于具有固定大小（节点数）和密度的边的图，Louvain 算法检测到的社区不能大于（或小于）给定节点数。这意味着该算法将无法在大型网络中发现小型社区（100 个 blob 的情况）。它也将无法检测小型网络中的大型社区。最后一个例子的一个特殊情况是小型网络中的无社区情况。

您可以尝试通过检查可以由 Louvain 算法的 GDS 实现返回的中间步骤来识别大型网络问题，如上一节所述。

另一个限制是模块化是一个全局度量的事实。因此，图表某一部分的更新可能会产生远离它的后果。例如，如果您在上图中的环中反复添加 blob，则在某些时候，社区会突然变得非常不同，即使图的只有一小部分发生了变化。

Louvain的替代品

已经提出了 Louvain 算法的许多替代方案。其中包括：

涉及分辨率参数γ的算法，以解决 Louvain 算法的分辨率限制。
Leiden 算法是 Louvain 算法的变体，它还能够拆分集群，而不仅仅是合并它们。通过这样做，Leiden 算法能够保证社区将连接良好，而 Louvain 算法则不是这种情况（请参阅进一步阅读部分以获取更深入该主题的资源链接）。

在上一节列出的案例中，这些算法已被证明比 Louvain 表现更好。但是，到目前为止，还没有解决的算法涵盖了其他两种情况：

重叠社区：给定节点可以属于多个社区的情况
动态网络：当网络随时间演变时社区如何变化（新边和/或新节点）

这两个主题将在接下来的两个小节中分别介绍。

重叠社区检测

到目前为止，我们研究的所有算法都有一个共同点：每个节点都分配给一个且只有一个社区。但这并不总是代表现实：朋友也可以是同事，同事也可以是家人。能够检测到属于多个社区的节点还可以提供有关图结构和社区边界的有趣信息，如下图所示。

重叠社区检测最著名的算法之一是Clique Percolation Method ( CPM )。图论中的派系是节点的子集，其中每个节点都连接到所有其他节点。k-clique是包含k个节点的clique。最简单的 clique 示例是3-clique，它是由三个完全连接的节点组成的三角形。CPM 算法基于相邻的k-clique定义社区，其中如果两个k -clique共享k-1个节点，则认为它们是相邻的，这使得第k个节点可以分配给多个社区。

动态网络

动态网络是随时间演化的图，其中可以添加、修改甚至删除节点和边。社区检测问题变得更加复杂，因为社区可以执行以下操作：

出现
生长
被减少
与另一个社区融合
分裂
消失

一个社区也可以保持不变，甚至暂时消失，只在稍后的某个时间再次出现。解决此类问题的一种技术包括在不同时间使用图形的快照。然后可以在每个快照上使用诸如本书中研究的静态算法。然而，当比较在两个连续快照中发现的社区时，将很难确定差异是由于真实的社区进化还是算法的不稳定性（想想 Louvain 算法的分辨率限制）。已经提出了许多解决方案来通过使用平滑技术来解决这个问题。例如，您可以构建一个算法，要求时间 t 的社区与时间t的社区在某种程度上相似t-1。有关此主题的更多详细信息，请参阅参考资料（请参阅进一步阅读部分）。

我们现在已经介绍了社区检测算法，了解它们是如何工作的，何时使用它们，以及如何在 Neo4j 中的 GDS 中使用它们。我们甚至超越了 GDS 并描述了一些用于重叠社区检测的技术。社区是将具有相似性的节点组合在一起：与图的其余部分（Louvain）相比，相似的邻域（标签传播）和相似的边密度。如果要量化两个节点之间的相似性，可以从检查它们是否属于同一个社区开始。但是存在更精确的指标，我们将在下一节中介绍。

测量节点之间的相似性

有几种技术用于量化节点之间的相似性。它们可以分为两类：

基于集合的度量：在全局范围内比较两个集合的内容。例如，集合 ( A , B , C ) 和 ( C , D , B ) 有两个共同的元素。
基于向量的度量：逐元素比较向量，这意味着每个元素的位置很重要。欧几里得距离是此类度量的一个示例。

让我们从基于集合的相似性开始更详细地了解这些指标。

基于集合的相似性

GDS 1.0 实现了我们将在此处介绍的基于集合的相似性的两种变体。

重叠

重叠相似度是衡量两个集合之间共同元素的数量，相对于最小集合的大小。

定义

该度量的数学定义如下：

O(A, B) = | A ∩ B | / 分钟(|A|, |B|)

A ∩ B是集合 A 和 B（公共元素）和|A|之间的交集表示集合 A 的大小。

GDS 在其 alpha 层中包含一个功能，可以让我们测试和理解这种相似性度量。我们通过以下方式使用它：

RETURN gds.alpha.similarity.overlap(<set1>, <set2>) AS similarity

以下语句返回O([1, 2, 3], [1, 2, 3, 4]) 的结果：

RETURN gds.alpha.similarity.overlap([1,2,3], [1,2,3,4]) AS similarity

集合 [1, 2, 3] 和 [1, 2, 3, 4] 之间的交集包含两个集合中的元素：1、2 和 3。它包含三个元素，因此它的大小为| A ∩ B | = 3。在分母上，我们需要找到最小集合的大小。在我们的例子中，最小的集合是 [ 1 , 2 , 3 ] 包含三个元素。所以重叠相似度的期望值为 1，也就是 GDS 函数返回的值。下表包含更多示例：

A	B	A ∩ B	\|A∩B\|	min(\|A\|, \|B\|)	O(A, B)
[1, 2, 3]	[1, 2, 3, 4]	[1, 2, 3]	3	3	1
[1, 2, 3]	[1, 2, 4]	[1, 2]	2	3	2/3≈0.67
[1, 2]	[3, 4]	[]	0	2	0

注意重叠相似度是对称的；交换A和B不会改变结果。

在 GitHub 图中量化用户相似度

我们将使用 Neo4j 社区 GitHub 图，其中包含以登录为特征的 GitHub 用户、Neo4j 拥有的存储库以及CONTRIBUTED_TO用户与他们贡献的存储库之间的类型关系。如果你还没有从本书的前面部分构建图表，数据和加载说明可以在本书的 GitHub 存储库中找到。

使用相似度算法的第一步是建立一组与每个用户相关的数据：

MATCH (user:User)-[:CONTRIBUTED_TO]->(repo:Repository)
WITH {item: user.login, categories: collect(repo.name)} as userData
RETURN userData

userData对于具有 login 的给定用户，包含以下内容j：

{"item": "j","categories": ["cypher-shell","neo4j-ogm","docker-neo4j","doctools"]
}

在这种情况下，计算两个用户之间的相似性意味着比较他们贡献的存储库（存储在categories密钥中）。为了能够被 GDS 使用，我们只需要将我们的用户登录名和存储库名称替换为 Neo4j 内部 ID：

MATCH (user:User)-[:CONTRIBUTED_TO]->(repo:Repository)
WITH {item: id(user), categories: collect(id(repo))} as userData
RETURN userData

userData然后可以用于馈送gds.alpha.overlap.stream过程：

MATCH (user:User)-[:CONTRIBUTED_TO]->(repo:Repository)
WITH {item:id(user), categories: collect(id(repo))} as userData
WITH collect(userData) as data
CALL gds.alpha.similarity.overlap.stream({nodeProjection: '*', relationshipProjection: 'CONTRIBUTED_TO', data: data}
)
YIELD item1, item2, count1, count2, intersection, similarity
RETURN *

该过程返回相似性，但也返回中间结果，例如两个类别集中的项目数和交集的大小。

item1并且item2是节点 ID。要检索节点对象，您可以使用该gds.util.asNode函数。例如，要获取与对应的用户登录item1，您可以编写gds.util.asNode(item1).login.

以下是从我们的结果中选择的一些行：

╒════════════════════╤═════════════════╤════════╤════════╤══════════════╤══════════════════╕
│"user1"             │"user2"          │"count1"│"count2"│"intersection"│"similarity"      │
╞════════════════════╪═════════════════╪════════╪════════╪══════════════╪══════════════════╡
│"systay"            │"nawroth"        │4       │13      │4             │1.0               │
├────────────────────┼─────────────────┼────────┼────────┼──────────────┼──────────────────┤
│"chrisvest"         │"systay"         │3       │4       │3             │1.0               │
└────────────────────┴─────────────────┴────────┴────────┴──────────────┴──────────────────┘

如您所见，即使对于相似度等于 1 的节点对。交集的大小之间存在很大差异：我们可能期望systay比更相似，因为贡献了chrisvest比多九个存储库，而差异存储库的数量只是和之间的一个。这可以通过我们将在下一段中看到的 Jaccard 相似性来解决。nawrothnavrothsystaysystaychrisvest

杰卡德相似度

Jaccard 相似度定义类似于重叠相似度，只是分母包含集合A和B的并集的大小：

J(A, B) = | A ∩ B | / |A ∪ B|

在分母中使用两个集合的并集对于识别用户将贡献给单个存储库的情况非常有用，其中有许多不同的贡献者。通过重叠相似度，该用户与所有其他贡献者的相似度为 1。使用 Jaccard 公式，相似度将取决于每个其他用户贡献的存储库数量，并且仅对于也为该单个存储库做出贡献的贡献者才等于 1。

在这个投影图上运行 Jaccard 相似度算法就像这样简单：

MATCH (u:User)
MATCH (v:User)
RETURN u, v, gds.alpha.similarity.jaccard(u, v) as score

您可以systay在此图中检查和其他用户之间的相似度，并注意到，现在，与的相似度chrisvest远高于与的相似度navroth。

这些相似性是基于节点所连接的元素之间的比较。在下一节中，我们将了解如何在 GDS 中使用基于向量的相似度度量，例如欧几里得距离或余弦相似度。即使它们不是特定于图表的，它们在数据分析方面也提供了有用的信息。

基于向量的相似性

基于向量的相似性类似于经典机器学习管道中遇到的相似性。他们比较两个包含有序数字列表的向量。

欧几里得距离

欧几里得距离是两点之间距离的度量。它是笛卡尔平面中距离度量的扩展，使用以下公式计算：

d(u, v) = √( (u 1 – v 1 ) 2 + (u 2 – v 2 ) 2 + … + (u n – v n ) 2 )

我们可以尝试量化他们的贡献向量之间的距离，而不是简单地计算每对用户共有的存储库数量。让我们通过一个例子更清楚地说明。我们将为某些关系添加一个新属性，以计算用户对给定存储库的贡献频率：

MATCH (u1:User {login: "systay"})-[ct1]->(repo)
SET ct1.nContributions = round(rand() * 10)

为简单起见，我在这里使用随机数，但这意味着您的结果可能会有所不同。如果我们为另一个用户做同样的事情，例如，chrisvest，我们可以创建每个用户对每个存储库的贡献向量：

MATCH (u1:User {login: 'chrisvest'})-[ct1]->(repo)
MATCH (u2:User {login: 'systay'})-[ct2]->(repo)
WITH collect(ct1.nContributions) as contrib1, collect(ct2.nContributions) as contrib2
RETURN contrib1, contrib2

该collect语句为每个用户创建了两个列表，其中包含该用户对每个存储库的贡献。要计算这两个向量之间的欧几里得距离，我们只需要调用gds.alpha.similarity.euclideanDistance函数：

MATCH (u1:User {login: 'chrisvest'})-[ct1]->(repo)
MATCH (u2:User {login: 'systay'})-[ct2]->(repo)
WITH collect(ct1.nContributions) as contrib1, collect(ct2.nContributions) as contrib2
RETURN gds.alpha.similarity.euclideanDistance(contrib1, contrib2) AS similarity

在我的情况下，这导致相似度接近 38。

与重叠相似度类似，GDS 还包含在投影图上运行并计算所有节点对之间的相似度的过程。

请记住，您可以通过以下内容找到您的 GDS 版本中可用的功能和过程的全名和签名：

CALL gds.list() YIELD name, signature
WHERE name =~ '.*euclidean.*'
RETURN *

余弦相似度

余弦相似度是众所周知的，尤其是在 NLP 社区中，因为它被广泛用于衡量两个文本之间的相似度。余弦相似度不是像欧几里得相似度那样计算两点之间的距离，而是基于两个向量之间的角度。考虑以下场景：

向量 A 和 C 之间的欧几里得距离为d AC，而θ AC表示余弦相似度。

同理， A和B的欧式距离用d AB线表示，但它们之间的夹角为 0，由于cos(0)=1，A和B的余弦相似度为 1——远高于余弦相似度在A和C之间。

要在 GitHub 贡献者的上下文中替换此示例，我们可以使用以下内容：

A对两个存储库R1和R2有贡献，对R1（x轴）有 5个贡献，对R2（y轴）有 10 个贡献。
B对相同存储库的贡献是：对R1的 1 个贡献和对R2的 2 个贡献，因此向量是对齐的。
C对R1的贡献更多，比如 8，但对R2的贡献更少（比如 8）。

仅从贡献总数来看，用户A和C比A和B更相似。然而，用户A和B的贡献分布更相似：他们每个人对R1的贡献是对R2的两倍。最后一个事实以余弦相似度编码，A和B之间的余弦相似度高于A和C之间的余弦相似度（见下表）。

GDS 的余弦相似度用法与欧几里得距离相同，使用以下名称：

一个函数，gds.alpha.similarity.cosine
两个程序，gds.alpha.similarity.cosine.stream和gds.alpha.similarity.cosine.write

下表显示了用户A、B和C之间的欧几里得和余弦相似度与前面给出的值的比较：

欧几里得

余弦

A/B

RETURN

gds.alpha.similarity.euclidean([5, 10], [1, 2])
~ 0.10

RETURN

gds.alpha.similarity.cosine([5, 10], [1, 2])
1.0

A/C

RETURN

gds.alpha.similarity.euclidean([5, 10], [8, 8])
~ 0.22

RETURN

gds.alpha.similarity.cosine([5, 10], [8, 8])
~ 0.95

这是我们专门讨论节点相似性的部分的结尾。我们将在接下来的章节中回到它，届时我们将使用我们在本章中发现的一些指标以及前面的指标作为机器学习模型中的特征。

概括

在本章中，我们讨论了很多测量节点之间相似度的方法，无论是在全球范围内通过将节点分组为社区还是使用更局部的相似度评估，例如使用 Jaccard 相似度度量。研究了几种算法——弱连接和强连接组件、标签传播算法和鲁汶算法。我们还使用了 GDS 提供的一项功能，该功能允许我们将算法的结果写入 Neo4j 以供将来使用。我们还使用了两个新工具来可视化图形以及在 GDS 中实现的图形算法的结果：neovis.js用于将 Neo4j 图形可视化嵌入到 HTML 页面中，以及 NEuler，它是图形算法游乐场，您可以从中使用无需编写代码即可运行图算法。

我们对 GDS (1.0) 中实现的算法的探索现已完成。在接下来的章节中，我们将学习如何在机器学习管道中使用图和这些算法来进行预测。首先，在下一章中，我们将构建一个机器学习管道并引入一个基于图形的特性来提高性能。

问题

连接组件：
如果您在无向投影图上运行强连通分量算法，您认为会发生什么？
如果我们添加从 D 到 C 的关系，测试图的社区结构将如何变化？或者如果我们删除从 D 到 E 的关系？
标签传播：
更新我们的算法实现以考虑种子，即关于节点社区的先验知识。

进一步阅读

社区检测技术在脑图上的应用：算法考虑和对神经功能的影响， JO Garcia 等人。, IEEE doi 论文集：10.1109/JPROC.2017.278671
一种分析复杂组织结构的方法，RS Weiss和E. Jacobson，美国社会学评论，卷。20，第 6 期，1955 年，第 661-668 页。doi:10.2307/2088670
Louvain算法：原论文：
https ://arxiv.org/abs/0803.0476
动态网络中的社区检测，一项调查，G. Rossetti和R. Cazabet，ACM 期刊（全文可在Community Discovery in Dynamic Networks: a Survey – Archive ouverte HAL获得）

🖍foreword

技术要求

社区检测及其应用介绍

识别节点集群

社区检测方法的应用

推荐引擎和有针对性的营销

欺诈识别

预测属性或链接

社区检测技术的简要概述

检测图形组件和可视化社区

弱连接组件

强连接组件

将 GDS 结果写入图表

使用 neovis.js 可视化图表

使用 NEuler，图形数据科学游乐场

用于社区检测可视化

运行标签传播算法

定义标签传播

加权节点和关系

半监督学习

在 Python 中实现标签传播

使用 GDS 中的标签传播算法

使用种子

将结果写入图表

了解Louvain算法

定义模块化

所有节点都在自己的社区中

所有节点都在同一个社区

最优分区

重现 Louvain 算法的步骤

GDS 中的 Louvain 算法

句法

关系投影中的聚合方法

中间步骤

Zachary 的空手道俱乐部图上的 Label Propagation 和 Louvain 之间的比较

超越 Louvain的重叠社区检测

Louvain算法的注意事项

分辨率限制

Louvain的替代品

重叠社区检测

动态网络

测量节点之间的相似性

基于集合的相似性

重叠

杰卡德相似度

基于向量的相似性

欧几里得距离

余弦相似度

概括

问题

进一步阅读

Published by

风君子

发表回复 取消回复

发表回复取消回复