當(dāng)前位置：首頁 > 编程资源 > 综合教程 >内容正文

综合教程

【Neo4j】第 7 章：社区检测和相似性措施

發(fā)布時(shí)間：2023/12/4 综合教程 30 生活家

生活随笔收集整理的這篇文章主要介紹了【Neo4j】第 7 章：社区检测和相似性措施小編覺得挺不錯(cuò)的,現(xiàn)在分享給大家,幫大家做個(gè)參考.

?🔎大家好，我是Sonhhxg_柒，希望你看完之后，能對(duì)你有所幫助，不足請(qǐng)指正！共同學(xué)習(xí)交流🔎

📝個(gè)人主頁－Sonhhxg_柒的博客_CSDN博客?📃

🎁歡迎各位→點(diǎn)贊👍 + 收藏⭐️ + 留言📝?

📣系列專欄 - 機(jī)器學(xué)習(xí)【ML】?自然語言處理【NLP】? 深度學(xué)習(xí)【DL】

??

?🖍foreword

✔說明?本人講解主要包括Python、機(jī)器學(xué)習(xí)（ML）、深度學(xué)習(xí)（DL）、自然語言處理（NLP）等內(nèi)容。

如果你對(duì)這個(gè)系列感興趣的話，可以關(guān)注訂閱喲👋

文章目錄

技術(shù)要求

社區(qū)檢測及其應(yīng)用介紹

識(shí)別節(jié)點(diǎn)集群

社區(qū)檢測方法的應(yīng)用

推薦引擎和有針對(duì)性的營銷

欺詐識(shí)別

預(yù)測屬性或鏈接

社區(qū)檢測技術(shù)的簡要概述

檢測圖形組件和可視化社區(qū)

弱連接組件

強(qiáng)連接組件

將 GDS 結(jié)果寫入圖表

使用 neovis.js 可視化圖表

使用 NEuler，圖形數(shù)據(jù)科學(xué)游樂場

用于社區(qū)檢測可視化

運(yùn)行標(biāo)簽傳播算法

定義標(biāo)簽傳播

加權(quán)節(jié)點(diǎn)和關(guān)系

半監(jiān)督學(xué)習(xí)

在 Python 中實(shí)現(xiàn)標(biāo)簽傳播

使用 GDS 中的標(biāo)簽傳播算法

使用種子

將結(jié)果寫入圖表

了解Louvain算法

定義模塊化

所有節(jié)點(diǎn)都在自己的社區(qū)中

所有節(jié)點(diǎn)都在同一個(gè)社區(qū)

最優(yōu)分區(qū)

重現(xiàn) Louvain 算法的步驟

GDS 中的 Louvain 算法

句法

關(guān)系投影中的聚合方法

中間步驟

Zachary 的空手道俱樂部圖上的 Label Propagation 和 Louvain 之間的比較

超越 Louvain的重疊社區(qū)檢測

Louvain算法的注意事項(xiàng)

分辨率限制

Louvain的替代品

重疊社區(qū)檢測

動(dòng)態(tài)網(wǎng)絡(luò)

測量節(jié)點(diǎn)之間的相似性

基于集合的相似性

重疊

杰卡德相似度

基于向量的相似性

歐幾里得距離

余弦相似度

概括

問題

進(jìn)一步閱讀

現(xiàn)實(shí)世界的圖既不是規(guī)則的也不是完全隨機(jī)的網(wǎng)格。它們的邊緣密度不均勻，因此我們最終找到了一些有趣的模式。中心性算法利用一些節(jié)點(diǎn)可以比其他節(jié)點(diǎn)擁有更多連接的事實(shí)來評(píng)估節(jié)點(diǎn)重要性（參見第 6 章，節(jié)點(diǎn)重要性）。在本章中，我們將發(fā)現(xiàn)一種新型算法，其目標(biāo)是識(shí)別彼此高度連接的節(jié)點(diǎn)組并形成社區(qū)或集群。其中一些社區(qū)檢測算法已經(jīng)在 GDS 中實(shí)現(xiàn)：組件算法、標(biāo)簽傳播算法和 Louvain 算法。?本章是我們使用 JavaScript 構(gòu)建社區(qū)圖形表示并發(fā)現(xiàn) NEuler（由 Neo4j 開發(fā)的圖形算法游樂場應(yīng)用程序）的機(jī)會(huì)。最后，我們還將了解 GDS 中實(shí)現(xiàn)的不同指標(biāo)，以在本地測量兩個(gè)節(jié)點(diǎn)之間的相似性。

本章將涵蓋以下主題：

社區(qū)檢測及其應(yīng)用介紹
檢測圖形組件和可視化社區(qū)
運(yùn)行標(biāo)簽傳播算法
了解Louvain算法
超越 Louvain 的重疊社區(qū)檢測
測量節(jié)點(diǎn)之間的相似性

技術(shù)要求

在本章中，我們將使用以下工具：

Neo4j 圖形數(shù)據(jù)庫列出了以下縮進(jìn)擴(kuò)展：
插件：圖形數(shù)據(jù)科學(xué)庫
Neo4j 桌面應(yīng)用程序
用于圖形可視化的 NEuler
您還需要一個(gè)瀏覽器來打開 HTML 和我們將為圖形可視化構(gòu)建的 JavaScript 文件。
Python（推薦≥3.6）運(yùn)行一些算法的示例實(shí)現(xiàn)。
本章使用的代碼可在本書的 GitHub 存儲(chǔ)庫中找到，網(wǎng)址為
https://github.com/PacktPublishing/Hands-On-Graph-Analytics-with-Neo4j/ch7

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

社區(qū)檢測及其應(yīng)用介紹

社區(qū)檢測收集已開發(fā)用于理解圖結(jié)構(gòu)并從中提取信息的技術(shù)。這種結(jié)構(gòu)隨后可以用于許多應(yīng)用中，例如推薦引擎、欺詐檢測、屬性預(yù)測和鏈接預(yù)測。

在本章中，我將使用community、cluster或partition來指代一組共享公共屬性的節(jié)點(diǎn)。

識(shí)別節(jié)點(diǎn)集群

下圖顯示了我們?cè)诘?2 章“?Cypher 查詢語言”中構(gòu)建的 Neo4j GitHub 用戶圖表。社區(qū)檢測算法能夠識(shí)別幾個(gè)社區(qū)：

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

在本章結(jié)束時(shí)，您將能夠重現(xiàn)此圖像。需要進(jìn)一步分析以了解紫羅蘭社區(qū)用戶的共同屬性。對(duì)該圖的更深入分析告訴我們，紫羅蘭社區(qū)中的用戶顯然從人群中脫穎而出，并且大部分都為獨(dú)特的存儲(chǔ)庫做出了貢獻(xiàn)。

在深入每個(gè)算法的技術(shù)細(xì)節(jié)之前，我們首先要更多地討論知道節(jié)點(diǎn)屬于哪個(gè)社區(qū)的優(yōu)勢。雖然我們?cè)谶@里談?wù)摰氖怯捎脩艚M成的社區(qū)，但這可以應(yīng)用于許多其他領(lǐng)域。我們將在本節(jié)的其余部分介紹其中的一些。

社區(qū)檢測方法的應(yīng)用

社區(qū)檢測和圖聚類有很多應(yīng)用。例如，它們可用于以下領(lǐng)域：

生物學(xué)：蛋白質(zhì)-蛋白質(zhì)相互作用網(wǎng)絡(luò)模擬細(xì)胞內(nèi)的蛋白質(zhì)相互作用。屬于同一群落的蛋白質(zhì)更有可能參與相同的功能。
神經(jīng)科學(xué)：研究人員將人腦建模為圖形，其中每個(gè)節(jié)點(diǎn)都是少量細(xì)胞。事實(shí)證明，了解該圖的社區(qū)結(jié)構(gòu)對(duì)于了解大腦的不同部分如何相互協(xié)調(diào)特別有用。
公共衛(wèi)生：我們可以使用人口的社區(qū)結(jié)構(gòu)來嘗試和預(yù)測疾病的演變和傳播。

接下來的部分將重點(diǎn)介紹一些更有可能對(duì)您直接有用的應(yīng)用程序。

欺詐識(shí)別

欺詐檢測在前一章（第 6 章，節(jié)點(diǎn)重要性）中討論過。我們討論了欺詐者創(chuàng)建犯罪團(tuán)伙并相互合作以避免被發(fā)現(xiàn)的方式。這種組織很難通過傳統(tǒng)方法檢測到，但由于其基于關(guān)系的原生結(jié)構(gòu)，圖表是打擊所有類型欺詐的非常有用的工具。假設(shè)欺詐者之間會(huì)進(jìn)行更多互動(dòng)，例如在假用戶共享相同電話號(hào)碼或地址的情況下，圖表可以形成一個(gè)社區(qū)并且更容易識(shí)別。

預(yù)測屬性或鏈接

社區(qū)檢測和上述大多數(shù)應(yīng)用的基本思想之一是屬于同一社區(qū)的節(jié)點(diǎn)共享一些屬性。這可用于根據(jù)圖的社區(qū)結(jié)構(gòu)進(jìn)行預(yù)測。讓我們從下圖所示的子圖開始：

它包含三個(gè)節(jié)點(diǎn)A、B和C，以及兩條邊（（A，B）和（A，C））。這可能是具有更多輸出邊的更大圖的一部分。節(jié)點(diǎn)A和B有一個(gè)值為 1 的屬性。這可能是某些用戶的年齡類別，這并不總是可用的。用戶A和B填寫了該字段，表明他們?cè)?21 到 30 之間。最重要的是，一些社區(qū)檢測算法已經(jīng)設(shè)法將所有三個(gè)節(jié)點(diǎn)聚集到同一個(gè)社區(qū)中。直觀地說，我們可以說節(jié)點(diǎn)C的概率隨著有關(guān)圖結(jié)構(gòu)的新知識(shí)，也屬于 21-30 歲年齡段。

類似地，如果我們?cè)噲D測量B和C之間的邊在我們不知道或?qū)沓霈F(xiàn)的情況下存在的概率，那么對(duì)于同一社區(qū)中的節(jié)點(diǎn)來說它會(huì)更高。

社區(qū)檢測技術(shù)的簡要概述

最早的圖結(jié)構(gòu)研究之一是由 Weiss 和 Jacobson 進(jìn)行的，并于 1955 年發(fā)表。從那時(shí)起，已經(jīng)使用不同類型的規(guī)則研究和實(shí)現(xiàn)了幾種類型的算法。

至于節(jié)點(diǎn)重要性問題，在社區(qū)檢測問題的情況下，首先要考慮的是定義度量或目標(biāo)函數(shù)，它將量化圖分區(qū)的好壞。社區(qū)最常見的定義指出，社區(qū)是一組節(jié)點(diǎn)，其社區(qū)內(nèi)連接（同一社區(qū)中的節(jié)點(diǎn)之間的邊更多）比社區(qū)間連接（兩個(gè)不同社區(qū)中的節(jié)點(diǎn)之間的邊）多。但是即使有了這個(gè)定義，也有幾種可能的方法可以實(shí)現(xiàn)令人滿意的分區(qū)。

已經(jīng)提出了許多算法，使用不同的度量。例如，層次聚類使用一些規(guī)則來創(chuàng)建樹狀圖，從而創(chuàng)建聚類的層次結(jié)構(gòu)。Girvan-Newman 算法是層次聚類的一個(gè)例子，它使用了通常用于節(jié)點(diǎn)到邊的中介中心性的擴(kuò)展：具有最高中介中心性的邊是圖中兩對(duì)節(jié)點(diǎn)之間的最短路徑中最常涉及的邊。其他層次聚類算法使用相似性度量而不是拓?fù)涠攘俊Ｔ诒菊碌淖詈?#xff08;在測量節(jié)點(diǎn)之間的相似性部分），我們將學(xué)習(xí)如何測量節(jié)點(diǎn)之間的相似性。

在本書中，我們將重點(diǎn)介紹 Neo4j 中實(shí)現(xiàn)的一些算法：

連接組件，它允許我們檢測斷開連接的子圖。
標(biāo)簽傳播，顧名思義，通過基于多數(shù)投票規(guī)則的圖傳播社區(qū)標(biāo)簽，以將每個(gè)節(jié)點(diǎn)分配給其新社區(qū)。
Louvain 算法優(yōu)化了模塊化，定義為社區(qū)內(nèi)連接數(shù)與社區(qū)間連接數(shù)之間的差異。

即使尚未在 GDS 中實(shí)現(xiàn)，我們也會(huì)討論這些算法的一些改進(jìn)建議，尤其是 Leiden 算法，該算法旨在解決 Louvain 算法的一些問題。我們還將簡要解決上述算法未涵蓋的重疊社區(qū)問題。

現(xiàn)在讓我們使用連接組件算法開始我們的社區(qū)檢測之旅。在下一節(jié)中，我們將學(xué)習(xí)組件算法。我們還將發(fā)現(xiàn)以圖形格式可視化檢測到的社區(qū)的工具，這對(duì)于理解中圖的結(jié)構(gòu)至關(guān)重要。

檢測圖形組件和可視化社區(qū)

圖形組件具有明確的數(shù)學(xué)定義。在給定的組件中，兩個(gè)節(jié)點(diǎn)始終通過路徑相互連接，但不連接到組件外的任何其他節(jié)點(diǎn)。有兩個(gè)版本的連接組件：

強(qiáng)連接組件：這些確保同一組件中的兩個(gè)節(jié)點(diǎn)之間的路徑存在于兩個(gè)方向。
弱連接組件：對(duì)于弱連接組件，單個(gè)方向就足夠了。

讓我們看看 Neo4j 中的一個(gè)例子。在本節(jié)中，我們還將在本書中首次使用寫入過程將算法結(jié)果存儲(chǔ)在 Neo4j 中。我們還將引入一個(gè)新的 JavaScript 庫來自定義大圖的可視化。

讓我們從以下有向圖開始：

用于創(chuàng)建圖表的 Cypher 代碼可在 GitHub (?https://github.com/PacktPublishing/Hands-On-Graph-Analytics-with-Neo4j/blob/master/ch7/test_graph.cql?) 上獲得。

在視覺上，我們可以說這個(gè)圖中至少有兩個(gè)組件。節(jié)點(diǎn)Y和Z與圖中的任何其他節(jié)點(diǎn)完全斷開連接，因此從這兩個(gè)節(jié)點(diǎn)到圖中的任何其他節(jié)點(diǎn)都沒有任何路徑。讓我們看看如何從 GDS 中實(shí)現(xiàn)的算法中學(xué)習(xí)這些信息。

我們將使用以下投影圖：

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

此投影圖包含帶有標(biāo)簽的所有節(jié)點(diǎn)Node以及與自然方向上的類型的所有關(guān)系LINKED_TO（如使用 Cypher 創(chuàng)建它們時(shí)定義的那樣，如上圖所示），它們沒有附加任何屬性。

弱連接組件

我們將在這里學(xué)習(xí)的第一個(gè)算法是弱連接組件或聯(lián)合查找。

弱連接組件，連同我們將在本章后面介紹的 Louvain 和標(biāo)簽傳播算法，都是 GDS 1.0 版中的生產(chǎn)就緒算法。

要查看使用弱連接組件進(jìn)行圖分區(qū)的結(jié)果，請(qǐng)使用以下查詢：

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

這是我們的結(jié)果：

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

如您所見，該算法成功識(shí)別出兩個(gè)組件：

此示例中標(biāo)記的組件7，包含節(jié)點(diǎn)Y和Z
另一個(gè)標(biāo)記為的組件0，包含所有其他節(jié)點(diǎn)

用于標(biāo)記社區(qū)的確切數(shù)字不相關(guān)；這取決于 GDS 的內(nèi)部功能。根據(jù)您的圖表的創(chuàng)建方式，您獲得的數(shù)字可能會(huì)有所不同，但應(yīng)該檢測到相同的社區(qū)。

考慮到圖是無向的，弱連接組件告訴我們，我們的圖中有兩個(gè)不連接的分區(qū)。如果關(guān)系方向很重要，例如在道路網(wǎng)絡(luò)中，那么我們將不得不使用強(qiáng)連通分量算法。

強(qiáng)連接組件

在強(qiáng)連接的組件中，關(guān)系的方向很重要。組件中的每個(gè)節(jié)點(diǎn)都必須能夠在兩個(gè)方向上連接同一組件中的任何其他節(jié)點(diǎn)。關(guān)注節(jié)點(diǎn)A到G，通過弱連通分量算法將它們分組在同一個(gè)社區(qū)中，您可以看到并非總是可以從一個(gè)節(jié)點(diǎn)到另一個(gè)節(jié)點(diǎn)在兩個(gè)方向上。例如，從D到A是可能的（通過C），但從A到D是不可能的。

要查看使用此更強(qiáng)規(guī)則標(biāo)識(shí)的組件，我們可以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

以下是前面代碼的結(jié)果：

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

這一次，確定了三個(gè)組件：雖然節(jié)點(diǎn)Y和Z仍在它們自己的組件中，但節(jié)點(diǎn)A、B和C現(xiàn)在與D、E、F和斷開連接G。

連通分量對(duì)于理解我們的圖結(jié)構(gòu)是非常有用的算法。一些算法，如 PageRank（參見第 6 章，節(jié)點(diǎn)重要性）可能會(huì)在具有多個(gè)組件的圖上導(dǎo)致意外結(jié)果。在圖形數(shù)據(jù)分析的數(shù)據(jù)探索部分運(yùn)行連接組件算法是一種很好的做法。

在繼續(xù)研究其他社區(qū)檢測算法之前，我們將討論一些允許我們以更好的格式可視化社區(qū)的工具。其中一些將要求社區(qū)編號(hào) (?componentID) 是節(jié)點(diǎn)屬性。這就是為什么我們現(xiàn)在要解決 GDS 的一個(gè)功能，我們目前還沒有利用：在 Neo4j 圖中寫入算法結(jié)果的可能性，而不是將它們流回給用戶并讓他們決定如何處理它們.

將 GDS 結(jié)果寫入圖表

在第 4 章，圖形數(shù)據(jù)科學(xué)庫和路徑查找中，我們介紹了 GDS 的寫入功能，允許我們將算法的結(jié)果存儲(chǔ)在 Neo4j 中。此功能適用于 GDS 中實(shí)現(xiàn)的幾乎所有算法。基本上，不提供此選項(xiàng)的算法是返回矩陣的算法，例如All Pairs 最短路徑算法或我們將在本章末尾介紹的一些相似性算法。

讓我們看一下使用連接組件算法的寫入過程的應(yīng)用。

寫入過程的語法與流一非常相似。主要區(qū)別在于它接受另一個(gè)配置參數(shù) ，writeProperty它允許我們配置將添加到每個(gè)節(jié)點(diǎn)的屬性的名稱。

以下查詢會(huì)將弱連接組件算法的結(jié)果寫入wcc每個(gè)節(jié)點(diǎn)的屬性中：

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

這里，返回的結(jié)果包含有關(guān)算法運(yùn)行時(shí)間和圖結(jié)構(gòu)的信息：

但是要查看每個(gè)節(jié)點(diǎn)所屬的分區(qū)，我們將不得不使用另一個(gè) Cypher 查詢：

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

使用強(qiáng)連接的組件也可以實(shí)現(xiàn)相同的目標(biāo)：

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

在其之上name，每個(gè)節(jié)點(diǎn)現(xiàn)在還包含另外兩個(gè)名為wccand的屬性scc，其中包含根據(jù)弱連接和強(qiáng)連接組件算法該節(jié)點(diǎn)所屬的組件的 ID。在這里，您可以看到 node 的內(nèi)容D：

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

當(dāng)圖非常大時(shí)，將結(jié)果寫入圖有時(shí)是唯一的解決方案（我們將在第 12 章，Neo4j at Scale中更多地討論大數(shù)據(jù)的情況）。但它在其他情況下也很有用。我們現(xiàn)在將討論其中之一。

到目前為止，我們只使用了非常小的圖表，通過從表格中讀取結(jié)果很容易理解它們。但這不是圖算法最常見的用例，它主要用于中型和大型圖。在這些情況下，以圖形格式可視化社區(qū)檢測算法的結(jié)果對(duì)于理解圖形的結(jié)構(gòu)可能更為重要。在下一節(jié)中，我們將發(fā)現(xiàn)兩種根據(jù)屬性繪制不同大小或顏色的節(jié)點(diǎn)的方法：第一種是neovis.js用于將圖形可視化嵌入 HTML 頁面的 JavaScript 庫，第二種是 NEuler，Graph Algorithms Playground，一個(gè)基于此包的 Neo4j 桌面應(yīng)用程序。

使用 neovis.js 可視化圖表

當(dāng)涉及到社區(qū)時(shí)，有一種方法來可視化節(jié)點(diǎn)分類和它們之間的關(guān)系總是有用的。圖形可視化本身就是一個(gè)研究領(lǐng)域，并且存在許多用于良好可視化的軟件包。例如，用于數(shù)據(jù)可視化的最完整的 JavaScript 庫之一d3.js，也具有繪制圖形的功能。但是，在使用時(shí)d3.js，必須管理與 Neo4j 的連接、數(shù)據(jù)檢索和格式化。這就是為什么在本節(jié)和本章的其余部分中，我們將使用開源neovis.jsJavaScript 庫的原因。它非常易于使用，因?yàn)榕c Neo4j 的連接是在內(nèi)部管理的，我們不需要任何有關(guān) Neo4j JavaScript 驅(qū)動(dòng)程序的知識(shí)就可以使其工作。neovis.js還創(chuàng)建了非常漂亮的可視化，就像本章第一張圖展示的 Neo4j GitHub 社區(qū)一樣，它有很多可自定義的參數(shù)。

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

使用以下命令從 GitHub 存儲(chǔ)庫導(dǎo)入庫：

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

最小的 HTML 代碼如下：

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

加載body后會(huì)調(diào)用前面draw的函數(shù)，將圖形繪制到div函數(shù)中id="graph"。主函數(shù)是draw函數(shù)，包含配置參數(shù)和渲染方法：

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();}

您需要更新圖表的連接參數(shù)：?server_url、server_user和server_password。server_password對(duì)應(yīng)于在 Neo4j Desktop 中添加新圖形時(shí)要求您創(chuàng)建的密碼。

可以使用您喜歡的瀏覽器打開該文件graph_viz.html，以查看我們圖中的不同社區(qū)，由強(qiáng)連通分量算法（scc屬性）標(biāo)識(shí)。生成的圖像應(yīng)如下圖所示：

如果需要，您還可以通過在draw函數(shù)中指示節(jié)點(diǎn)配置的大小參數(shù)以及包含其重要性的節(jié)點(diǎn)的屬性來可視化節(jié)點(diǎn)重要性；例如：

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

要使此代碼正常工作，您需要在投影圖上使用寫入過程運(yùn)行 PageRank 算法：
CALL gds.pageRank("simple_projected_graph", {writeProperty: "pagerank"})

但請(qǐng)記住，PageRank 可能會(huì)在圖不連貫的情況下產(chǎn)生意想不到的結(jié)果。

neoviz.js如果您想將圖形嵌入到 HTML 頁面中，它是一個(gè)強(qiáng)大而有趣的工具。但是，如果您只需要測試算法的結(jié)果，則存在一個(gè)更簡單的解決方案：NEuler。

使用 NEuler，圖形數(shù)據(jù)科學(xué)游樂場

NEuler 是集成在 Neo4j Desktop 中的開源應(yīng)用程序，其代碼可在 GitHub 上的GitHub - neo4j-devtools/neuler: Playground for Neo4j Graph Algorithms上找到。

它是一個(gè)非常強(qiáng)大的工具，允許我們測試 GDS 中實(shí)現(xiàn)的所有算法，從路徑查找（第 4 章，圖形數(shù)據(jù)科學(xué)庫和路徑查找）和中心性（第 5 章，節(jié)點(diǎn)重要性）到社區(qū)檢測和相似性。它還可以使用基于neoviz.js.

本書的 GitHub 存儲(chǔ)庫中提供了安裝說明。

用于社區(qū)檢測可視化

以下屏幕截圖所示的主屏幕是您可以選擇要運(yùn)行的算法類型的地方：

選擇社區(qū)檢測算法后，您可以從上方菜單中選擇要嘗試的算法。對(duì)于這個(gè)例子，我們將使用強(qiáng)連通分量算法。單擊其名稱后，您可以從右側(cè)欄中配置投影圖和算法參數(shù)。以下屏幕截圖中所示的配置將執(zhí)行以下操作：

在包含節(jié)點(diǎn)標(biāo)簽Node和關(guān)系類型LINKED_TO的投影圖上運(yùn)行算法orientation=UNDIRECTED。

將結(jié)果存儲(chǔ)在名為的屬性中scc。

????????????????????????????????????????

????????

單擊“運(yùn)行”按鈕將調(diào)用正確的 Cypher 程序，您可以通過“代碼”選項(xiàng)卡進(jìn)行檢查：

最后，您可以在“可視化”選項(xiàng)卡中可視化結(jié)果。在那里，您可以自定義將用于為它們著色的節(jié)點(diǎn)屬性，就像我們?cè)谏弦还?jié)中所做的那樣neovis.js：

這將關(guān)閉我們關(guān)于連接組件的部分。我們已經(jīng)了解了弱連接和強(qiáng)連接組件算法如何幫助我們識(shí)別圖中不連接的社區(qū)。我們還發(fā)現(xiàn)了兩種不同的可視化社區(qū)檢測算法結(jié)果的方法。我們將在以下部分繼續(xù)使用它們，我們將在其中發(fā)現(xiàn)新型社區(qū)檢測算法：標(biāo)簽傳播和 Louvain 算法，它們都是 GDS 生產(chǎn)質(zhì)量層的一部分。

運(yùn)行標(biāo)簽傳播算法

標(biāo)簽傳播是社區(qū)檢測算法的另一個(gè)例子。于 2017 年提出，其優(yōu)勢在于可以為已知節(jié)點(diǎn)設(shè)置一些標(biāo)簽，并以半監(jiān)督的方式從中導(dǎo)出未知標(biāo)簽。它還可以考慮關(guān)系和節(jié)點(diǎn)權(quán)重。在本節(jié)中，我們將通過 Python 中的簡單實(shí)現(xiàn)來詳細(xì)介紹該算法。

定義標(biāo)簽傳播

存在標(biāo)簽傳播的幾種變體。主要思想如下：

標(biāo)簽被初始化，使得每個(gè)節(jié)點(diǎn)都位于自己的社區(qū)中。
標(biāo)簽根據(jù)多數(shù)投票規(guī)則迭代更新：每個(gè)節(jié)點(diǎn)接收其鄰居的標(biāo)簽，并將其中最常見的標(biāo)簽分配給節(jié)點(diǎn)。當(dāng)最常見的標(biāo)簽不是唯一的時(shí)，就會(huì)出現(xiàn)沖突。在這種情況下，需要定義一個(gè)規(guī)則，它可以是隨機(jī)的或確定性的（就像在 GDS 中一樣）。
重復(fù)迭代過程，直到所有節(jié)點(diǎn)都有固定的標(biāo)簽。

最佳解決方案是連接具有不同標(biāo)簽的兩個(gè)節(jié)點(diǎn)的邊數(shù)最少的分區(qū)。讓我們考慮下圖：

經(jīng)過一些迭代，算法將節(jié)點(diǎn)A和B分配給一個(gè)社區(qū)（我們稱之為CR），將節(jié)點(diǎn)E和G分配給另一個(gè)社區(qū)（CG）。根據(jù)多數(shù)投票規(guī)則，在下一次迭代中，節(jié)點(diǎn)C將被分配到CR社區(qū)，因?yàn)檫B接到C的兩個(gè)節(jié)點(diǎn)已經(jīng)屬于這個(gè)分區(qū)，而只有一個(gè)節(jié)點(diǎn) (?D?) 屬于另一個(gè)集群。同樣，節(jié)點(diǎn)D將分配給CG社區(qū)。生成的圖表如下圖所示：

加權(quán)節(jié)點(diǎn)和關(guān)系

為了考慮節(jié)點(diǎn)或關(guān)系的權(quán)重，我們可以更新多數(shù)投票規(guī)則，使其不僅計(jì)算具有給定標(biāo)簽的節(jié)點(diǎn)數(shù)，而且計(jì)算它們的權(quán)重。所選標(biāo)簽將是權(quán)重總和最高的標(biāo)簽。

讓我們考慮下圖所示的上圖的加權(quán)版本：

這一次，為了選擇節(jié)點(diǎn)D的標(biāo)簽，我們必須考慮連接到D的每條邊的權(quán)重：

CR社區(qū)的權(quán)重= 1 (C) + 8 (D) = 9
CG社區(qū)的權(quán)重= 1 (E) + 2 (G) = 3

因此，在該圖的加權(quán)版本中，節(jié)點(diǎn)D將屬于CR社區(qū)。

半監(jiān)督學(xué)習(xí)

標(biāo)簽傳播的另一個(gè)有趣的方面是它考慮先驗(yàn)知識(shí)的能力。?如果您已經(jīng)知道某些節(jié)點(diǎn)的社區(qū)，則可以在初始化階段使用此信息，而不是設(shè)置隨機(jī)初始值。這種技術(shù)被稱為半監(jiān)督學(xué)習(xí)，因?yàn)橹挥幸恍┕?jié)點(diǎn)被標(biāo)記為他們的社區(qū)。

在 Python 中實(shí)現(xiàn)標(biāo)簽傳播

在本節(jié)中，我們將實(shí)現(xiàn)標(biāo)簽傳播的簡化版本，考慮到種子標(biāo)簽只能取兩個(gè)不同的值：0 或 1。

我們將使用與前幾章相同的圖形表示，基于 Python 字典。我們將使用的圖形由以下對(duì)象表示：

    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},}

它告訴我們節(jié)點(diǎn)A連接到節(jié)點(diǎn)B和C，兩條邊的權(quán)重都等于 1。

現(xiàn)在讓我們開始算法。在初始化階段，我們用唯一值初始化所有標(biāo)簽。查找唯一值的一種方法是在循環(huán)中使用它們的索引來遍歷的鍵G，這可以在 Python 中通過以下方式實(shí)現(xiàn)：

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

該enumerate(iterable)函數(shù)返回一個(gè)元組，其中包含一個(gè)計(jì)數(shù)（從 0 開始）和通過迭代獲得的值iterable。在這里，iterable是我們的字典G，并且迭代G相當(dāng)于在 Python 中迭代它的鍵。

然后我們進(jìn)入主循環(huán)。在每次迭代中，我們?cè)趫D中的所有節(jié)點(diǎn)上執(zhí)行一個(gè)循環(huán)，并為每個(gè)節(jié)點(diǎn)計(jì)算它收到的票數(shù)：

    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])

為了找到多數(shù)票，我們可以使用以下代碼，它將遍歷收到的票，并在每次找到高于當(dāng)前最大值的值時(shí)更新新標(biāo)簽的值：

            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

為了區(qū)分兩個(gè)標(biāo)簽具有相同投票數(shù)的情況，我們使用完全任意的規(guī)則來選擇具有最高值的標(biāo)簽。

一旦所有標(biāo)簽都更新了，我們可以通過檢查自上次迭代以來沒有標(biāo)簽發(fā)生變化來檢查算法的收斂性：

        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

在本節(jié)開頭定義的圖 G 上運(yùn)行此代碼，我們得到以下結(jié)果：

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

確定了兩個(gè)社區(qū)：第一個(gè)社區(qū)被標(biāo)記3并包含節(jié)點(diǎn)A、B和C，而第二個(gè)社區(qū)被標(biāo)記6并包含節(jié)點(diǎn)Dto?G。請(qǐng)記住，標(biāo)簽本身是沒有意義的，因?yàn)樗鼈冎皇莵碜詧D形定義中的節(jié)點(diǎn)位置。不同的實(shí)現(xiàn)會(huì)為標(biāo)簽返回不同的值，但會(huì)保留社區(qū)結(jié)構(gòu)。

Label Propagation 不能保證收斂，我們最終可能會(huì)出現(xiàn)振蕩，其中給定節(jié)點(diǎn)的標(biāo)簽不穩(wěn)定并且在每次迭代時(shí)在兩個(gè)值之間振蕩，從而導(dǎo)致收斂失敗。

完整代碼可在 GitHub 上的https://github.com/PacktPublishing/Hands-On-Graph-Analytics-with-Neo4j/ch7/label_propagation/label_propagation.py 獲得。我們鼓勵(lì)您復(fù)制和修改它以幫助您了解它的工作原理。例如，更新代碼以考慮節(jié)點(diǎn)和關(guān)系權(quán)重。請(qǐng)注意，實(shí)現(xiàn)保持盡可能簡單，以允許您利用您對(duì) Python 的先驗(yàn)知識(shí)。例如，如果您已經(jīng)了解networkx和numpy，您可以嘗試修改此代碼以使其適用于netwokx圖形或使用矩陣公式（參見前一章，第 6 章，節(jié)點(diǎn)重要性）。

使用 GDS 中的標(biāo)簽傳播算法

標(biāo)簽傳播算法是生產(chǎn)質(zhì)量算法的一部分，這意味著它經(jīng)過了很好的測試和針對(duì)大型圖的優(yōu)化。我們將在我們?cè)?em>弱連接組件部分研究的圖上測試運(yùn)行標(biāo)簽傳播算法。創(chuàng)建它的 Cypher 代碼可在https://github.com/PacktPublishing/Hands-On-Graph-Analytics-with-Neo4j/ch7/test_graph.cql獲得。

讓我們創(chuàng)建一個(gè)無向投影圖：

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

要在該圖上執(zhí)行標(biāo)簽傳播算法，我們可以使用以下查詢：

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

結(jié)果如下：

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

已經(jīng)確定了三個(gè)社區(qū)：兩個(gè)類似于我們?cè)谏弦还?jié)中確定的社區(qū)，加上一個(gè)包含節(jié)點(diǎn)Y和的額外社區(qū)Z，這些社區(qū)沒有包含在我們之前的研究中。

同樣，的確切值communityId可能會(huì)有所不同；它與nodeId財(cái)產(chǎn)有關(guān)。但是同一社區(qū)中的所有節(jié)點(diǎn)將始終具有相同的communityId.

使用種子

為了測試我們的算法，我們首先需要向圖中添加一個(gè)新屬性，該屬性將保持我們對(duì)節(jié)點(diǎn)社區(qū)成員身份的先驗(yàn)信念——?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;

對(duì)于某些節(jié)點(diǎn)，我們添加了一個(gè)名為的屬性knownCommunity，它存儲(chǔ)了我們關(guān)于每個(gè)節(jié)點(diǎn)所屬社區(qū)的先驗(yàn)知識(shí)（或信念）。

然后，我們可以創(chuàng)建命名的投影圖。該圖將包含帶有Node標(biāo)簽的所有節(jié)點(diǎn)以及帶有類型的所有關(guān)系LINKED_TO。為了以半監(jiān)督的方式使用該算法，我們還需要明確告訴 GDS 將knownCommunity節(jié)點(diǎn)屬性存儲(chǔ)在投影圖中。最后，我們會(huì)將我們的圖視為無向圖，這是通過orientation: "UNDIRECTED"在關(guān)系投影中指定參數(shù)來實(shí)現(xiàn)的：

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

現(xiàn)在我們可以在這個(gè)命名的投影圖上運(yùn)行標(biāo)簽傳播算法，并使用以下內(nèi)容流式傳輸結(jié)果：

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

您可以從結(jié)果中看到已識(shí)別的社區(qū)相似，但是communityId現(xiàn)在反映了通過給出的值seedProperty。

將結(jié)果寫入圖表

要使用我們?cè)谏弦还?jié)中編寫的代碼在瀏覽器中可視化結(jié)果，我們需要將結(jié)果存儲(chǔ)在圖形中，這可以通過以下gds.labelPropagation.write過程來實(shí)現(xiàn)：

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

諸如標(biāo)簽傳播之類的算法是一個(gè)很好的例子，說明圖算法已經(jīng)被用于更經(jīng)典的機(jī)器學(xué)習(xí)模型中。事實(shí)上，標(biāo)簽傳播用于機(jī)器學(xué)習(xí)中的分類和回歸，其中傳播是通過相似矩陣（而不是前一章討論的鄰接矩陣）執(zhí)行的。

現(xiàn)在，我們將關(guān)注另一個(gè)重要的社區(qū)檢測算法：Louvain 算法。

了解Louvain算法

魯汶算法是由比利時(shí)魯汶大學(xué)的研究人員于 2008 年提出的，該算法因此得名。它依賴于與其他節(jié)點(diǎn)的連接相比，社區(qū)內(nèi)連接密度的度量。這個(gè)度量被稱為模塊化，它是我們首先要理解的變量。

定義模塊化

與不同社區(qū)中節(jié)點(diǎn)之間的鏈接相比，模塊化是量化同一社區(qū)中節(jié)點(diǎn)內(nèi)鏈接密度的度量。

從數(shù)學(xué)上講，它的定義如下：

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

在哪里：

如果節(jié)點(diǎn)i和j連接，則A?ij為 1，否則為 0。
k?i是節(jié)點(diǎn)i的度數(shù)。
m是邊緣攜帶的所有權(quán)重的總和。我們也有關(guān)系Σ?i?k?i?= 2m，因?yàn)樗泄?jié)點(diǎn)的總和將對(duì)每條邊計(jì)算兩次。
c?i是算法分配給節(jié)點(diǎn)i的社區(qū)。
δ(x, y)是 Kronecker delta 函數(shù)，如果x=y則等于 1?，否則等于 0。

為了理解這個(gè)等式的含義，讓我們分別關(guān)注每個(gè)術(shù)語。具有k?i個(gè)邊的節(jié)點(diǎn)i有k?i個(gè)機(jī)會(huì)連接到圖中的任何其他節(jié)點(diǎn)。所以兩個(gè)節(jié)點(diǎn)i和j有k?i?xk?j機(jī)會(huì)相互連接。因此，術(shù)語k?i?k?j?/ (2m)對(duì)應(yīng)于節(jié)點(diǎn)i和j相互連接的概率。

在等式的另一邊，A?ij是i和j之間的真實(shí)連接狀態(tài)。因此，sigma 符號(hào)下的項(xiàng)量化了同一社區(qū)（在隨機(jī)圖中）的兩個(gè)節(jié)點(diǎn)之間的實(shí)際邊數(shù)和預(yù)期邊數(shù)之間的差異。

同一個(gè)社區(qū)中的兩個(gè)節(jié)點(diǎn)應(yīng)該比平均值更頻繁地連接，因此A?ij?> k?i?k?j?/ (2m)。Louvain 算法就是基于這個(gè)性質(zhì)，并試圖最大化模塊化Q。

這種模塊化的定義也適用于加權(quán)圖。在這種情況下，A?ij是i和j之間關(guān)系的權(quán)重。

在繼續(xù)討論算法本身之前，讓我們研究一下特殊的圖分區(qū)以及模塊化對(duì)它們的價(jià)值。可以使用https://github.com/PacktPublishing/Hands-On-Graph-Analytics-with-Neo4j/ch7/louvain/modularity.py上的簡單 Python 實(shí)現(xiàn)來挑戰(zhàn)結(jié)果。

在本節(jié)的其余部分，為了簡單起見，我們將使用與前一節(jié)類似的圖表，不包括節(jié)點(diǎn)Y和Z，以便處理單個(gè)組件。

所有節(jié)點(diǎn)都在自己的社區(qū)中

如果所有節(jié)點(diǎn)都在自己的社區(qū)中，則δ(c?i?, c?j?)始終為 0，因?yàn)?em>c?i始終不同于c?j，除非i=j的情況。由于我們的圖沒有自環(huán)（連接到自身的節(jié)點(diǎn)），因此 A?ii始終等于 0，并且僅保留和中的負(fù)項(xiàng)。所以在那種特殊情況下，模塊化Q是負(fù)的。在下文中，我們將其寫為Q?diag，它在我們的圖表中的值為Q?diag?=-0.148。

所有節(jié)點(diǎn)都在同一個(gè)社區(qū)

在另一個(gè)極端情況下，所有節(jié)點(diǎn)都在同一個(gè)社區(qū)中，δ(c?i?, c?j?)始終為 1。因此模塊化如下：

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

Aij項(xiàng)的所有節(jié)點(diǎn)對(duì)的總和對(duì)應(yīng)于所有邊的權(quán)重總和，計(jì)算兩次（對(duì)于ij和ji對(duì)）。所以，我們有以下內(nèi)容：

Σ?ij?A?ij?= 2m

讓我們重寫方程的第二項(xiàng)：

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

因此，在所有節(jié)點(diǎn)都在同一個(gè)社區(qū)中的特殊情況下，模塊化Q=0。

最優(yōu)分區(qū)

我們?cè)诒竟?jié)中使用的簡單圖的最佳分區(qū)類似于使用連接組件或標(biāo)簽傳播算法獲得的分區(qū)：節(jié)點(diǎn)A、B和C在它們自己的分區(qū)中，而節(jié)點(diǎn)D到G在另一個(gè)社區(qū)中。

當(dāng) m = 9 時(shí)，這種情況下的模塊性如下：

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

由于我們的圖是無向的，我們可以將對(duì)應(yīng)于 A 和 B ( ) 之間關(guān)系的項(xiàng)加倍A - B，而不是將項(xiàng)A -> B?和相加B -> A。

模塊化也可以用來衡量另一種算法檢測到的分區(qū)的質(zhì)量。

現(xiàn)在我們對(duì)模塊化有了更好的理解，在展示 Neo4j 和 GDS 的一些示例之前，我們將看看如何重現(xiàn) Louvain 算法。

重現(xiàn) Louvain 算法的步驟

Louvain 算法旨在最大化模塊化，作為損失函數(shù)。從每個(gè)節(jié)點(diǎn)分配到自己的社區(qū)（Q=0）的圖開始，算法將嘗試將節(jié)點(diǎn)移動(dòng)到其鄰居的社區(qū)，并且僅當(dāng)它使模塊化增加時(shí)才保持此配置。

該算法在每次迭代中執(zhí)行兩個(gè)步驟。在第一個(gè)過程中，對(duì)所有節(jié)點(diǎn)執(zhí)行迭代。對(duì)于每個(gè)節(jié)點(diǎn)n及其每個(gè)鄰居k，該算法嘗試將節(jié)點(diǎn)n移動(dòng)到與k相同的社區(qū)。節(jié)點(diǎn)n被移動(dòng)到導(dǎo)致模塊化程度最高的社區(qū)。如果無法通過這樣的操作增加模塊性，則節(jié)點(diǎn)n的社區(qū)在此迭代中保持不變。

在第二步中，算法將屬于同一社區(qū)的節(jié)點(diǎn)組合在一起以創(chuàng)建新節(jié)點(diǎn)，并將社區(qū)間邊的權(quán)重相加以在它們之間創(chuàng)建新的加權(quán)邊。

通過將單個(gè)節(jié)點(diǎn)從一個(gè)社區(qū)移動(dòng)到另一個(gè)社區(qū)所引起的模塊性變化可以計(jì)算而無需再次循環(huán)整個(gè)圖。

GDS 中的 Louvain 算法

從 1.0 版開始，Louvain 算法是 Graph Data Science 庫中生產(chǎn)質(zhì)量實(shí)施的一部分。

句法

Louvian 算法的用法與其他算法類似。要流式傳輸結(jié)果，請(qǐng)使用gds.louvain.stream帶有命名投影圖作為參數(shù)的過程：

CALL gds.louvain.stream(<projectedGraphName>)

我們還可以使用等效的過程將結(jié)果保存在圖中write：

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

在我們的圖上使用 Louvain 算法會(huì)導(dǎo)致兩個(gè)常見的分區(qū)，一側(cè)是節(jié)點(diǎn)A、B和C?，另一側(cè)是節(jié)點(diǎn)D到G。要查看這些算法之間的差異，我們將不得不轉(zhuǎn)向稍大的圖表。我們將在后面的章節(jié)中看到 Zachary 的空手道俱樂部的例子。

關(guān)系投影中的聚合方法

如果您改用該write過程，您會(huì)注意到它返回的信息包括最終的模塊化。如果您在我們之前創(chuàng)建的投影圖上運(yùn)行此過程projected_graph，您會(huì)注意到與我們?cè)谏弦还?jié)中獲得的模塊化值略有不同。解釋來自我們的投影圖。D存儲(chǔ)在 Neo4j 中的初始圖包含and之間的兩個(gè)關(guān)系E（一個(gè) from?DtoE和一個(gè) from?Eto?D）。當(dāng) GDS 創(chuàng)建投影圖時(shí)，默認(rèn)行為是存儲(chǔ)這兩種關(guān)系，這相當(dāng)于增加了這條邊的權(quán)重（A?ij項(xiàng)）。因此，我們的投影圖等價(jià)于以下內(nèi)容：

    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的權(quán)重為 2 而不是 1。

如果我們希望投影圖只包含兩個(gè)節(jié)點(diǎn)之間的一個(gè)關(guān)系，我們必須向關(guān)系投影添加另一個(gè)屬性：aggregation: "SINGLE"，這將強(qiáng)制每對(duì)節(jié)點(diǎn)通過給定類型的一個(gè)關(guān)系連接。以下查詢將創(chuàng)建一個(gè)啟用該屬性的新投影圖：

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

使用以下語句在這個(gè)新投影圖上運(yùn)行 Louvain 算法：

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

您將再次找到相同的模塊化值，大約為 0.36，如以下屏幕截圖所示：

如果您查看gds.louvain程序的完整結(jié)果，您會(huì)發(fā)現(xiàn)另一個(gè)名為modularities.?它對(duì)應(yīng)于在算法的每個(gè)階段計(jì)算的模塊化。

中間步驟

GDS 的一個(gè)有趣特性是它能夠在算法的中間步驟存儲(chǔ)社區(qū)。需要通過將配置參數(shù)設(shè)置為來啟用此includeIntermediateCommunities選項(xiàng)true。例如，以下查詢將為我們的投影圖流式傳輸 Louvain 算法的結(jié)果，返回一個(gè)額外的列，其中包含每個(gè)節(jié)點(diǎn)在每次迭代時(shí)分配到的社區(qū)列表：

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列包含一個(gè)列表，其中包含一個(gè)與最終社區(qū)相對(duì)應(yīng)的元素。這意味著一次迭代就足以收斂，鑒于圖的尺寸非常小，這并不奇怪。在較大的圖上使用此算法時(shí)，您將能夠在每個(gè)步驟中看到圖的狀態(tài)。

如果intermediateCommuntiyIds與 write 過程一起使用，書面屬性將包含與中間社區(qū) ID 對(duì)應(yīng)的 ID 列表，而不是僅對(duì)最終社區(qū)進(jìn)行編碼的單個(gè)整數(shù)。

Zachary 的空手道俱樂部圖上的 Label Propagation 和 Louvain 之間的比較

到目前為止，使用我們使用的小型測試圖，標(biāo)簽傳播和 Louvain 算法產(chǎn)生相同的社區(qū)，但一般情況并非如此。Zachary 的空手道俱樂部圖是一個(gè)稍大的圖，也是圖專家中最著名的圖之一。它由芝加哥大學(xué)的教師韋恩·W·扎卡里 (Wayne W. Zachary) 收集。他觀察了 1970 年代這所大學(xué)空手道俱樂部成員之間的不同聯(lián)系。

下圖顯示了該圖上標(biāo)簽傳播（左）和 Louvain 算法（右）的結(jié)果，包含 34 個(gè)節(jié)點(diǎn)（學(xué)生）。雖然標(biāo)簽傳播僅捕獲兩個(gè)社區(qū)，但 Louvain 算法能夠檢測到四個(gè)集群：

讓我給你更多的背景來更好地理解這個(gè)結(jié)果。1970年左右，在芝加哥大學(xué)的空手道俱樂部，兩名教練之間開始發(fā)生沖突，導(dǎo)致俱樂部分裂為兩個(gè)實(shí)體。當(dāng)時(shí)，雙方都在努力吸引學(xué)生，每個(gè)導(dǎo)師和學(xué)生之間的互動(dòng)很重要。Zachary 用圖表對(duì)這些交互進(jìn)行了建模，其中每個(gè)節(jié)點(diǎn)都是學(xué)生，它們之間的邊表示他們?cè)诖似陂g是否進(jìn)行了交互。所以這張圖有一個(gè)很大的優(yōu)勢，就是擁有真實(shí)信息：扎卡里記錄了每個(gè)成員在分裂后選擇去俱樂部的哪個(gè)部分。

回到兩種算法檢測到的社區(qū)劃分，Label Propagation 做對(duì)了，檢測到兩個(gè)與真實(shí)學(xué)生劃分一致的社區(qū)。查看 Louvain 算法的結(jié)果，似乎又檢測到了一個(gè)分區(qū)。但是，如果我們合并包含節(jié)點(diǎn) 17 的分區(qū)（頂部）和包含節(jié)點(diǎn) 2 的分區(qū)（中間），那么結(jié)果非常相似。唯一的區(qū)別是節(jié)點(diǎn) 10 將位于頂部社區(qū)，而在標(biāo)簽傳播中，它位于底部社區(qū)。

像一些著名的數(shù)據(jù)科學(xué)數(shù)據(jù)集一樣scikit-learn，Zachary 的空手道俱樂部包含在主要的 Python 包中，用于處理圖形networkx： import?networkx?as?nx?G?=?nx.karate_club_graph()

我們現(xiàn)在對(duì)模塊化和 Louvain 算法有了很多了解。在下一節(jié)中，我們將了解該算法的一些限制，以及已經(jīng)提出的一些改進(jìn)它的替代方案，即使它們（尚未）在 GDS 中實(shí)現(xiàn)。

超越 Louvain的重疊社區(qū)檢測

與所有算法一樣，Louvain 算法也有其局限性。了解它們非常重要，因此我們將在本節(jié)中嘗試這樣做。我們還將處理可能的替代方案。最后，我們還將討論一些允許節(jié)點(diǎn)屬于多個(gè)社區(qū)的算法。

Louvain算法的注意事項(xiàng)

與任何其他算法一樣，Louvain 算法也有一些已知的缺點(diǎn)。主要的一個(gè)是分辨率限制。

分辨率限制

考慮下圖，由每個(gè)具有七個(gè)節(jié)點(diǎn)的強(qiáng)連接 blob 組成，通過一條邊彼此弱連接：

在此圖上運(yùn)行社區(qū)檢測，您會(huì)期望每個(gè) blob 形成一個(gè)社區(qū)。雖然這對(duì)于小圖上的 Louvain 算法效果很好，但眾所周知，它在大圖上會(huì)失敗。例如，當(dāng)在一個(gè)結(jié)構(gòu)類似于上圖所示但有 100 個(gè) blob 的圖上運(yùn)行時(shí)，Louvain 算法將僅識(shí)別 50 個(gè)社區(qū)。這個(gè)問題被稱為分辨率限制問題：對(duì)于具有固定大小（節(jié)點(diǎn)數(shù)）和密度的邊的圖，Louvain 算法檢測到的社區(qū)不能大于（或小于）給定節(jié)點(diǎn)數(shù)。這意味著該算法將無法在大型網(wǎng)絡(luò)中發(fā)現(xiàn)小型社區(qū)（100 個(gè) blob 的情況）。它也將無法檢測小型網(wǎng)絡(luò)中的大型社區(qū)。最后一個(gè)例子的一個(gè)特殊情況是小型網(wǎng)絡(luò)中的無社區(qū)情況。

您可以嘗試通過檢查可以由 Louvain 算法的 GDS 實(shí)現(xiàn)返回的中間步驟來識(shí)別大型網(wǎng)絡(luò)問題，如上一節(jié)所述。

另一個(gè)限制是模塊化是一個(gè)全局度量的事實(shí)。因此，圖表某一部分的更新可能會(huì)產(chǎn)生遠(yuǎn)離它的后果。例如，如果您在上圖中的環(huán)中反復(fù)添加 blob，則在某些時(shí)候，社區(qū)會(huì)突然變得非常不同，即使圖的只有一小部分發(fā)生了變化。

Louvain的替代品

已經(jīng)提出了 Louvain 算法的許多替代方案。其中包括：

涉及分辨率參數(shù)γ的算法，以解決 Louvain 算法的分辨率限制。
Leiden 算法是 Louvain 算法的變體，它還能夠拆分集群，而不僅僅是合并它們。通過這樣做，Leiden 算法能夠保證社區(qū)將連接良好，而 Louvain 算法則不是這種情況（請(qǐng)參閱進(jìn)一步閱讀部分以獲取更深入該主題的資源鏈接）。

在上一節(jié)列出的案例中，這些算法已被證明比 Louvain 表現(xiàn)更好。但是，到目前為止，還沒有解決的算法涵蓋了其他兩種情況：

重疊社區(qū)：給定節(jié)點(diǎn)可以屬于多個(gè)社區(qū)的情況
動(dòng)態(tài)網(wǎng)絡(luò)：當(dāng)網(wǎng)絡(luò)隨時(shí)間演變時(shí)社區(qū)如何變化（新邊和/或新節(jié)點(diǎn)）

這兩個(gè)主題將在接下來的兩個(gè)小節(jié)中分別介紹。

重疊社區(qū)檢測

到目前為止，我們研究的所有算法都有一個(gè)共同點(diǎn)：每個(gè)節(jié)點(diǎn)都分配給一個(gè)且只有一個(gè)社區(qū)。但這并不總是代表現(xiàn)實(shí)：朋友也可以是同事，同事也可以是家人。能夠檢測到屬于多個(gè)社區(qū)的節(jié)點(diǎn)還可以提供有關(guān)圖結(jié)構(gòu)和社區(qū)邊界的有趣信息，如下圖所示。

重疊社區(qū)檢測最著名的算法之一是Clique Percolation Method?(?CPM?)。圖論中的派系是節(jié)點(diǎn)的子集，其中每個(gè)節(jié)點(diǎn)都連接到所有其他節(jié)點(diǎn)。k-clique是包含k個(gè)節(jié)點(diǎn)的clique。最簡單的 clique 示例是3-clique，它是由三個(gè)完全連接的節(jié)點(diǎn)組成的三角形。CPM 算法基于相鄰的k-clique定義社區(qū)，其中如果兩個(gè)k?-clique共享k-1個(gè)節(jié)點(diǎn)，則認(rèn)為它們是相鄰的，這使得第k個(gè)節(jié)點(diǎn)可以分配給多個(gè)社區(qū)。

動(dòng)態(tài)網(wǎng)絡(luò)

動(dòng)態(tài)網(wǎng)絡(luò)是隨時(shí)間演化的圖，其中可以添加、修改甚至刪除節(jié)點(diǎn)和邊。社區(qū)檢測問題變得更加復(fù)雜，因?yàn)樯鐓^(qū)可以執(zhí)行以下操作：

出現(xiàn)
生長
被減少
與另一個(gè)社區(qū)融合
分裂
消失

一個(gè)社區(qū)也可以保持不變，甚至?xí)簳r(shí)消失，只在稍后的某個(gè)時(shí)間再次出現(xiàn)。解決此類問題的一種技術(shù)包括在不同時(shí)間使用圖形的快照。然后可以在每個(gè)快照上使用諸如本書中研究的靜態(tài)算法。然而，當(dāng)比較在兩個(gè)連續(xù)快照中發(fā)現(xiàn)的社區(qū)時(shí)，將很難確定差異是由于真實(shí)的社區(qū)進(jìn)化還是算法的不穩(wěn)定性（想想 Louvain 算法的分辨率限制）。已經(jīng)提出了許多解決方案來通過使用平滑技術(shù)來解決這個(gè)問題。例如，您可以構(gòu)建一個(gè)算法，要求時(shí)間 t 的社區(qū)與時(shí)間t的社區(qū)在某種程度上相似t-1。有關(guān)此主題的更多詳細(xì)信息，請(qǐng)參閱參考資料（請(qǐng)參閱進(jìn)一步閱讀部分）。

我們現(xiàn)在已經(jīng)介紹了社區(qū)檢測算法，了解它們是如何工作的，何時(shí)使用它們，以及如何在 Neo4j 中的 GDS 中使用它們。我們甚至超越了 GDS 并描述了一些用于重疊社區(qū)檢測的技術(shù)。社區(qū)是將具有相似性的節(jié)點(diǎn)組合在一起：與圖的其余部分（Louvain）相比，相似的鄰域（標(biāo)簽傳播）和相似的邊密度。如果要量化兩個(gè)節(jié)點(diǎn)之間的相似性，可以從檢查它們是否屬于同一個(gè)社區(qū)開始。但是存在更精確的指標(biāo)，我們將在下一節(jié)中介紹。

測量節(jié)點(diǎn)之間的相似性

有幾種技術(shù)用于量化節(jié)點(diǎn)之間的相似性。它們可以分為兩類：

基于集合的度量：在全局范圍內(nèi)比較兩個(gè)集合的內(nèi)容。例如，集合 (?A?,?B?,?C?) 和 (?C?,?D?,?B?) 有兩個(gè)共同的元素。
基于向量的度量：逐元素比較向量，這意味著每個(gè)元素的位置很重要。歐幾里得距離是此類度量的一個(gè)示例。

讓我們從基于集合的相似性開始更詳細(xì)地了解這些指標(biāo)。

基于集合的相似性

GDS 1.0 實(shí)現(xiàn)了我們將在此處介紹的基于集合的相似性的兩種變體。

重疊

重疊相似度是衡量兩個(gè)集合之間共同元素的數(shù)量，相對(duì)于最小集合的大小。

定義

該度量的數(shù)學(xué)定義如下：

O(A, B) = |?A ∩ B |?/ 分鐘(|A|, |B|)

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

GDS 在其 alpha 層中包含一個(gè)功能，可以讓我們測試和理解這種相似性度量。我們通過以下方式使用它：

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

以下語句返回O([1, 2, 3], [1, 2, 3, 4]) 的結(jié)果：

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

集合 [1, 2, 3] 和 [1, 2, 3, 4] 之間的交集包含兩個(gè)集合中的元素：1、2 和 3。它包含三個(gè)元素，因此它的大小為|?A ∩ B |?= 3。在分母上，我們需要找到最小集合的大小。在我們的例子中，最小的集合是 [?1?,?2?,?3?] 包含三個(gè)元素。所以重疊相似度的期望值為 1，也就是 GDS 函數(shù)返回的值。下表包含更多示例：

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

注意重疊相似度是對(duì)稱的；交換A和B不會(huì)改變結(jié)果。

在 GitHub 圖中量化用戶相似度

我們將使用 Neo4j 社區(qū) GitHub 圖，其中包含以登錄為特征的 GitHub 用戶、Neo4j 擁有的存儲(chǔ)庫以及CONTRIBUTED_TO用戶與他們貢獻(xiàn)的存儲(chǔ)庫之間的類型關(guān)系。如果你還沒有從本書的前面部分構(gòu)建圖表，數(shù)據(jù)和加載說明可以在本書的 GitHub 存儲(chǔ)庫中找到。

使用相似度算法的第一步是建立一組與每個(gè)用戶相關(guān)的數(shù)據(jù)：

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

userData對(duì)于具有 login 的給定用戶，包含以下內(nèi)容j：

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

在這種情況下，計(jì)算兩個(gè)用戶之間的相似性意味著比較他們貢獻(xiàn)的存儲(chǔ)庫（存儲(chǔ)在categories密鑰中）。為了能夠被 GDS 使用，我們只需要將我們的用戶登錄名和存儲(chǔ)庫名稱替換為 Neo4j 內(nèi)部 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 *

該過程返回相似性，但也返回中間結(jié)果，例如兩個(gè)類別集中的項(xiàng)目數(shù)和交集的大小。

item1并且item2是節(jié)點(diǎn) ID。要檢索節(jié)點(diǎn)對(duì)象，您可以使用該gds.util.asNode函數(shù)。例如，要獲取與對(duì)應(yīng)的用戶登錄item1，您可以編寫gds.util.asNode(item1).login.

以下是從我們的結(jié)果中選擇的一些行：

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

如您所見，即使對(duì)于相似度等于 1 的節(jié)點(diǎn)對(duì)。交集的大小之間存在很大差異：我們可能期望systay比更相似，因?yàn)樨暙I(xiàn)了chrisvest比多九個(gè)存儲(chǔ)庫，而差異存儲(chǔ)庫的數(shù)量只是和之間的一個(gè)。這可以通過我們將在下一段中看到的 Jaccard 相似性來解決。nawrothnavrothsystaysystaychrisvest

杰卡德相似度

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

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

在分母中使用兩個(gè)集合的并集對(duì)于識(shí)別用戶將貢獻(xiàn)給單個(gè)存儲(chǔ)庫的情況非常有用，其中有許多不同的貢獻(xiàn)者。通過重疊相似度，該用戶與所有其他貢獻(xiàn)者的相似度為 1。使用 Jaccard 公式，相似度將取決于每個(gè)其他用戶貢獻(xiàn)的存儲(chǔ)庫數(shù)量，并且僅對(duì)于也為該單個(gè)存儲(chǔ)庫做出貢獻(xiàn)的貢獻(xiàn)者才等于 1。

在這個(gè)投影圖上運(yùn)行 Jaccard 相似度算法就像這樣簡單：

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

您可以systay在此圖中檢查和其他用戶之間的相似度，并注意到，現(xiàn)在，與的相似度chrisvest遠(yuǎn)高于與的相似度navroth。

這些相似性是基于節(jié)點(diǎn)所連接的元素之間的比較。在下一節(jié)中，我們將了解如何在 GDS 中使用基于向量的相似度度量，例如歐幾里得距離或余弦相似度。即使它們不是特定于圖表的，它們?cè)跀?shù)據(jù)分析方面也提供了有用的信息。

基于向量的相似性

基于向量的相似性類似于經(jīng)典機(jī)器學(xué)習(xí)管道中遇到的相似性。他們比較兩個(gè)包含有序數(shù)字列表的向量。

歐幾里得距離

歐幾里得距離是兩點(diǎn)之間距離的度量。它是笛卡爾平面中距離度量的擴(kuò)展，使用以下公式計(jì)算：

d(u, v) = √( (u?1?- v?1?)?2?+ (u?2?- v?2?)?2?+ ... + (u?n?- v?n?)?2?)

我們可以嘗試量化他們的貢獻(xiàn)向量之間的距離，而不是簡單地計(jì)算每對(duì)用戶共有的存儲(chǔ)庫數(shù)量。讓我們通過一個(gè)例子更清楚地說明。我們將為某些關(guān)系添加一個(gè)新屬性，以計(jì)算用戶對(duì)給定存儲(chǔ)庫的貢獻(xiàn)頻率：

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

為簡單起見，我在這里使用隨機(jī)數(shù)，但這意味著您的結(jié)果可能會(huì)有所不同。如果我們?yōu)榱硪粋€(gè)用戶做同樣的事情，例如，chrisvest，我們可以創(chuàng)建每個(gè)用戶對(duì)每個(gè)存儲(chǔ)庫的貢獻(xiàn)向量：

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語句為每個(gè)用戶創(chuàng)建了兩個(gè)列表，其中包含該用戶對(duì)每個(gè)存儲(chǔ)庫的貢獻(xiàn)。要計(jì)算這兩個(gè)向量之間的歐幾里得距離，我們只需要調(diào)用gds.alpha.similarity.euclideanDistance函數(shù)：

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

在我的情況下，這導(dǎo)致相似度接近 38。

與重疊相似度類似，GDS 還包含在投影圖上運(yùn)行并計(jì)算所有節(jié)點(diǎn)對(duì)之間的相似度的過程。

請(qǐng)記住，您可以通過以下內(nèi)容找到您的 GDS 版本中可用的功能和過程的全名和簽名：

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

余弦相似度

余弦相似度是眾所周知的，尤其是在 NLP 社區(qū)中，因?yàn)樗粡V泛用于衡量兩個(gè)文本之間的相似度。余弦相似度不是像歐幾里得相似度那樣計(jì)算兩點(diǎn)之間的距離，而是基于兩個(gè)向量之間的角度。考慮以下場景：

????????????????????????????????

?向量 A 和 C 之間的歐幾里得距離為d?AC，而θ?AC表示余弦相似度。

同理， A和B的歐式距離用d?AB線表示，但它們之間的夾角為 0，由于cos(0)=1，A和B的余弦相似度為 1——遠(yuǎn)高于余弦相似度在A和C之間。

要在 GitHub 貢獻(xiàn)者的上下文中替換此示例，我們可以使用以下內(nèi)容：

A對(duì)兩個(gè)存儲(chǔ)庫R1和R2有貢獻(xiàn)，對(duì)R1（x軸）有 5個(gè)貢獻(xiàn)，對(duì)R2（y軸）有 10 個(gè)貢獻(xiàn)。
B對(duì)相同存儲(chǔ)庫的貢獻(xiàn)是：對(duì)R1的 1 個(gè)貢獻(xiàn)和對(duì)R2的 2 個(gè)貢獻(xiàn)，因此向量是對(duì)齊的。
C對(duì)R1的貢獻(xiàn)更多，比如 8，但對(duì)R2的貢獻(xiàn)更少（比如 8）。

僅從貢獻(xiàn)總數(shù)來看，用戶A和C比A和B更相似。然而，用戶A和B的貢獻(xiàn)分布更相似：他們每個(gè)人對(duì)R1的貢獻(xiàn)是對(duì)R2的兩倍。最后一個(gè)事實(shí)以余弦相似度編碼，A和B之間的余弦相似度高于A和C之間的余弦相似度（見下表）。

GDS 的余弦相似度用法與歐幾里得距離相同，使用以下名稱：

一個(gè)函數(shù)，gds.alpha.similarity.cosine
兩個(gè)程序，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

這是我們專門討論節(jié)點(diǎn)相似性的部分的結(jié)尾。我們將在接下來的章節(jié)中回到它，屆時(shí)我們將使用我們?cè)诒菊轮邪l(fā)現(xiàn)的一些指標(biāo)以及前面的指標(biāo)作為機(jī)器學(xué)習(xí)模型中的特征。

概括

在本章中，我們討論了很多測量節(jié)點(diǎn)之間相似度的方法，無論是在全球范圍內(nèi)通過將節(jié)點(diǎn)分組為社區(qū)還是使用更局部的相似度評(píng)估，例如使用 Jaccard 相似度度量。研究了幾種算法——弱連接和強(qiáng)連接組件、標(biāo)簽傳播算法和魯汶算法。我們還使用了 GDS 提供的一項(xiàng)功能，該功能允許我們將算法的結(jié)果寫入 Neo4j 以供將來使用。我們還使用了兩個(gè)新工具來可視化圖形以及在 GDS 中實(shí)現(xiàn)的圖形算法的結(jié)果：neovis.js用于將 Neo4j 圖形可視化嵌入到 HTML 頁面中，以及 NEuler，它是圖形算法游樂場，您可以從中使用無需編寫代碼即可運(yùn)行圖算法。

我們對(duì) GDS (1.0) 中實(shí)現(xiàn)的算法的探索現(xiàn)已完成。在接下來的章節(jié)中，我們將學(xué)習(xí)如何在機(jī)器學(xué)習(xí)管道中使用圖和這些算法來進(jìn)行預(yù)測。首先，在下一章中，我們將構(gòu)建一個(gè)機(jī)器學(xué)習(xí)管道并引入一個(gè)基于圖形的特性來提高性能。

問題

連接組件：
如果您在無向投影圖上運(yùn)行強(qiáng)連通分量算法，您認(rèn)為會(huì)發(fā)生什么？
如果我們添加從 D 到 C 的關(guān)系，測試圖的社區(qū)結(jié)構(gòu)將如何變化？或者如果我們刪除從 D 到 E 的關(guān)系？
標(biāo)簽傳播：
更新我們的算法實(shí)現(xiàn)以考慮種子，即關(guān)于節(jié)點(diǎn)社區(qū)的先驗(yàn)知識(shí)。

進(jìn)一步閱讀

社區(qū)檢測技術(shù)在腦圖上的應(yīng)用：算法考慮和對(duì)神經(jīng)功能的影響，?JO Garcia 等人。,?IEEE doi 論文集：10.1109/JPROC.2017.278671
一種分析復(fù)雜組織結(jié)構(gòu)的方法，RS Weiss和E. Jacobson，美國社會(huì)學(xué)評(píng)論，卷。20，第 6 期，1955 年，第 661-668 頁。doi:10.2307/2088670
Louvain算法：原論文：
https ://arxiv.org/abs/0803.0476
動(dòng)態(tài)網(wǎng)絡(luò)中的社區(qū)檢測，一項(xiàng)調(diào)查，G. Rossetti和R. Cazabet，ACM 期刊（全文可在Community Discovery in Dynamic Networks: a Survey - Archive ouverte HAL獲得）

總結(jié)

以上是生活随笔為你收集整理的【Neo4j】第 7 章：社区检测和相似性措施的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。

上一篇： Codeforces Round #58
下一篇： Educational Codeforc