原文鏈接：https://tbgraph.wordpress.com/2017/11/17/neo4j-marvel-social-graph-algorithms-community-detection/
譯者言：本文較長(zhǎng)，但內(nèi)容清晰，后面有動(dòng)手的東西，有興趣可以交流。

在本系列第一篇在Neo4j中構(gòu)建漫威世界的社交網(wǎng)絡(luò)中我們從英雄到漫畫的二分圖推導(dǎo)出英雄到英雄的一分圖。接著在第二篇在Neo4j中對(duì)漫威社交網(wǎng)絡(luò)進(jìn)行初步分析中得到一些基本的網(wǎng)絡(luò)信息以幫助我們了解正在處理的網(wǎng)絡(luò)情況。

在本篇中我將會(huì)在漫威英雄的網(wǎng)絡(luò)上使用Louvain算法和標(biāo)簽傳播算法(LPA)，發(fā)現(xiàn)一些有趣的社群。

本文中的可視化是使用Gephi來進(jìn)行呈現(xiàn)，關(guān)于Gephi的更多信息可以看我之前的文章《Neo4j?to?Gephi》(https://tbgraph.wordpress.com/2017/04/01/neo4j-to-gephi/)。關(guān)于社群可視化還可以使用neovis.js(https://github.com/johnymontana/neovis.js)。

圖映射

Neo4j圖算法一般是在圖的子集上進(jìn)行，而這個(gè)子集通常是一個(gè)虛擬圖，Neo4j圖算法加載這種圖有兩種辦法。第一種簡(jiǎn)單的辦法是通過指定結(jié)點(diǎn)的標(biāo)簽和關(guān)系的類型將其加載到圖算法中。

但是，如果我們要運(yùn)行的邏輯是在一個(gè)特定的子圖上，而僅使用結(jié)點(diǎn)標(biāo)簽和關(guān)系類型無法描述出這個(gè)子圖，同時(shí)也不想去修改實(shí)體圖，這時(shí)要怎么辦呢？

不用擔(dān)心，我們還可以使用Cypher語(yǔ)句來指定要加載的子圖。使用查詢結(jié)點(diǎn)的Cypher語(yǔ)句代替結(jié)點(diǎn)標(biāo)簽參數(shù)，使用查詢關(guān)系的Cypher語(yǔ)句來代替關(guān)系類型參數(shù)。

但是注意，在參數(shù)中一定要指明?graph:'cypher'。

如下示例：

CALL algo.unionFind(
//第一個(gè)Cypher語(yǔ)句指定了要加載的結(jié)點(diǎn)。
????'MATCH?(p:User)
WHERE p.property = 'import'
RETURN id(p) as id',
//第二個(gè)Cpyher語(yǔ)句指定要加載的關(guān)系
????'MATCH?(p1:User)-[f:FRIEND]->(p2:User)?
RETURN id(p1) as source, id(p2) as target,f.weight as weight',
{graph:'cypher',write:true})

通過Cypher語(yǔ)句映射和加載子圖，可以非常好的描述要運(yùn)行算法的子圖。不僅如此，我們還可以剔除一些關(guān)系，間接的映射一個(gè)虛擬圖用于運(yùn)行算法，而那些剔除的關(guān)系又并不會(huì)從實(shí)際圖中刪除。

Cpyher映射使用場(chǎng)景：

?* 過濾結(jié)點(diǎn)和關(guān)系

?* 加載間接關(guān)系

* 映射雙向圖

* 相似性閾值（后面詳情介紹）

社群識(shí)別

在對(duì)各種網(wǎng)絡(luò)的研究過程中，如計(jì)算機(jī)網(wǎng)絡(luò)、社交網(wǎng)絡(luò)以及生物網(wǎng)絡(luò)，我們發(fā)現(xiàn)了許多不同的特征，包括小世界特性，重尾分布以及聚類等等。另外，網(wǎng)絡(luò)都有一個(gè)共同的特征即社群結(jié)構(gòu)，也就是連通和分組。而現(xiàn)實(shí)網(wǎng)絡(luò)世界的連通并不是隨機(jī)或同質(zhì)的，而是存在著某種自然的聯(lián)系。

社群識(shí)別算法在一個(gè)全連通的圖上運(yùn)行，效果并不會(huì)很好。因?yàn)榇蠖鄶?shù)據(jù)結(jié)點(diǎn)都是緊密連接的，他們是屬于一個(gè)社群的。在這些的圖上運(yùn)行算法，最終結(jié)果就是：得到一個(gè)覆蓋圖大部分區(qū)域的大社群和一些邊邊角角小社群。

這時(shí)我們可以使用相似性閾值來進(jìn)行調(diào)控，將大于某個(gè)值的關(guān)系保留，而小于此值的關(guān)系將會(huì)剔除。而這個(gè)虛擬圖就可以通過Cypher語(yǔ)句輕松的映射出來了。

在本文中，我會(huì)將漫威社交網(wǎng)絡(luò)中KNOWS的weight作為閾值，將其設(shè)置到100，大于100的關(guān)系將會(huì)保留，小于100的關(guān)于將會(huì)剔除，這樣，得到的社群將會(huì)非常緊密。

連通分量

連通分量或并查集算法都是找到相互連接的結(jié)點(diǎn)集，或者稱之為島，而在這個(gè)集合中的所有點(diǎn)都是可以相互連通的。

在圖論中，無向圖的連通分量（或者僅分量）是一個(gè)子圖，其中此子圖任何兩個(gè)頂點(diǎn)通過路徑相互連接。

當(dāng)我遇到一個(gè)新的網(wǎng)絡(luò)時(shí)，我第一時(shí)間想知道是：這個(gè)網(wǎng)絡(luò)有多少個(gè)連通分量，以及他們每個(gè)都包含多少結(jié)點(diǎn)。在漫威英雄的網(wǎng)絡(luò)中，當(dāng)前我們已經(jīng)把KNOWS的weight閾值設(shè)置到100了，而前一篇文章的閾值是10，因此，本文得到的連接肯定要比前一篇文章()中的連接要少。

在下面的示例中，我們直接使用結(jié)點(diǎn)標(biāo)簽和關(guān)系類型，所有標(biāo)簽為Hero的結(jié)點(diǎn)和所有類型為KNOWS的關(guān)系都將被加載到算法中。由于我們將閾值設(shè)置到100，所以，當(dāng)前算法只考慮weight大于100的關(guān)系。

CALL algo.unionFind.stream('Hero', 'KNOWS',
{weightProperty:'weight',?defaultValue:0.0,?threshold:100.0,concurrency:1})?
YIELD nodeId,setId
RETURN setId as component,count(*) as componentSize
ORDER BY componentSize DESC LIMIT 10;

譯者言：原文查詢語(yǔ)句可能是基于老版本的alog庫(kù)，無法運(yùn)營(yíng)，當(dāng)前查詢語(yǔ)句已經(jīng)修復(fù)

正如我所料，漫威英雄網(wǎng)絡(luò)是一個(gè)稀疏圖，有1個(gè)大社群和6小社群組成，大社群有101個(gè)英雄，而小社群基本也就2~4個(gè)英雄。這表示，在6439個(gè)英雄中，有116個(gè)英雄至少一個(gè)KNOWS關(guān)系的weight值是大于100的。

如果想在瀏覽器中仔細(xì)瀏覽那個(gè)包含101英雄的大社群，會(huì)很容易發(fā)現(xiàn)隱藏在這里面的一些直觀的東西以及社群之間的橋梁結(jié)點(diǎn)。接下來我們將嘗試使用Louvain算法和標(biāo)簽傳播算法來看看這個(gè)116個(gè)英雄的子圖的社群結(jié)構(gòu)。

Louvain

社群就是網(wǎng)絡(luò)中結(jié)點(diǎn)集合，它們彼此之間的連接比其他節(jié)點(diǎn)更緊密。Modularity是一種度量刻度，被用于衡量社群發(fā)現(xiàn)算法結(jié)果的質(zhì)量，它能夠刻畫社區(qū)的緊密程度。在一個(gè)隨機(jī)的網(wǎng)絡(luò)中，將一個(gè)結(jié)點(diǎn)歸類到某一個(gè)社群，Modularity值就是會(huì)生變化，進(jìn)而給出這種分配后社區(qū)的質(zhì)量。Modularity即量化了此結(jié)點(diǎn)與社群中其他結(jié)點(diǎn)的連接緊密程度。社群識(shí)別的Louvain方法，是一種基于啟發(fā)式Modularity最大化的網(wǎng)絡(luò)社群檢測(cè)算法。

如前所述，我們將通過Cypher查詢來僅映射weight大于110的關(guān)系到算法中。

CALL algo.louvain.stream(
// load nodes
????'MATCH?(u:Hero)?RETURN?id(u)?as?id',?
// load relationships
????'MATCH?(u1:Hero)-[rel:KNOWS]-(u2:Hero)?
// similarity threshold
WHERE rel.weight > 100
RETURN id(u1) as source,id(u2) as target',
{graph:"cypher"})?
YIELD nodeId,community
MATCH?(n:Hero)?WHERE?id(n)=nodeId
RETURN community,
count(*) as communitySize,
collect(n.name) as members
order by communitySize desc limit 5

我使用Gephi進(jìn)行社群結(jié)果可視化，因?yàn)镚ephi的表現(xiàn)力比表格更好，更有洞察力。

結(jié)點(diǎn)顏色：代表Louvain社群?結(jié)點(diǎn)大小：代表PageRank值?名字大?。捍碇薪橹行男?/p>

我并不是漫威漫畫的專家，所以我只能根據(jù)數(shù)據(jù)來做一個(gè)簡(jiǎn)單的解釋。我們總共劃分出8個(gè)社群。最大的社群是紫色的社群，它由以美國(guó)隊(duì)長(zhǎng)為首的神盾局和復(fù)仇者聯(lián)盟組成。在左邊我們能看到神奇先生和神奇四俠也在紫色社群里。亮蘭色是蜘蛛俠團(tuán)隊(duì)，蜘蛛俠帕克是他們與外界聯(lián)系的唯一橋梁，其他人都是內(nèi)部交流，與外界并無聯(lián)系。深蘭色是阿斯加德人，他們也是比較封閉，他們僅僅和雷神托爾有聯(lián)系。哦？難以置信，綠巨人也是自己的社群（粉紅色），而綠巨人是這個(gè)社群唯一與外界有聯(lián)系的英雄。我們還看到野獸亨利是紫色社群與綠色社群的橋梁，位置特殊，而綠色是X-Men社群。

譯者言：野獸亨利，在X-Men中就是那個(gè)全身蘭色的家伙，但真沒有在復(fù)仇者聯(lián)盟系列電影中看到過他。

標(biāo)簽傳播算法（LPA)

標(biāo)簽傳播算法是由Raghavan等人于2007年首次提出，（譯者言：百度百科顯示此算法于2002年由Zhu等人提出）此算法是由每個(gè)結(jié)點(diǎn)使用其唯一標(biāo)識(shí)作為標(biāo)簽，然后根據(jù)大多數(shù)鄰居結(jié)點(diǎn)的標(biāo)簽為基礎(chǔ)進(jìn)行標(biāo)簽傳播，每個(gè)結(jié)點(diǎn)再?gòu)乃泥従咏Y(jié)點(diǎn)身上取出現(xiàn)次數(shù)最多的標(biāo)簽加到自己身上。LPA算法的具體步驟是這樣：結(jié)點(diǎn)X有一些鄰居結(jié)點(diǎn)，且每個(gè)鄰居結(jié)點(diǎn)都有一個(gè)標(biāo)簽，標(biāo)明他們所屬的社群。然后網(wǎng)絡(luò)中的每個(gè)結(jié)點(diǎn)都選擇加入其大多數(shù)鄰居所屬的那個(gè)社群，同時(shí)再隨機(jī)的斷開一些連接。在開始時(shí)，每個(gè)節(jié)點(diǎn)都用唯一標(biāo)簽進(jìn)行初始化，然后這些標(biāo)簽開始在網(wǎng)絡(luò)中進(jìn)行傳播，傳播的每一步，每個(gè)結(jié)點(diǎn)都會(huì)根據(jù)鄰居標(biāo)簽的情況更新自己的標(biāo)簽，隨著標(biāo)簽的傳播，最終連接緊密的結(jié)點(diǎn)集合將會(huì)達(dá)成一個(gè)共識(shí)，而他們身上的標(biāo)簽也將不再發(fā)生變化。

與Louvaint算法類似，我們也采用Cypher語(yǔ)句進(jìn)行圖映射，在映射時(shí)僅加載weight值大于KNOWS關(guān)系。同時(shí)會(huì)將對(duì)結(jié)點(diǎn)進(jìn)行回寫，導(dǎo)出結(jié)果到Gephi中進(jìn)行可視化展示。

CALL algo.labelPropagation(
// supports node-weights and defining
// initial communities using parameter value
????'MATCH?(u:Hero)?RETURN?id(u)?as?id,?1?as?weight,id(u)?as?value',
// load relationships
????'MATCH?(u1:Hero)-[rel:KNOWS]-(u2:Hero)?
// Similarity threshold
WHERE rel.weight > 100
RETURN id(u1) as source,id(u2) as target, rel.weight as weight',
'OUT',{graph:"cypher",partitionProperty:"lpa"?})?
YIELD computeMillis

最終我們得到21個(gè)社群，包括單點(diǎn)社群。復(fù)仇者聯(lián)盟（紫色）和神奇四俠（亮蘭色）被分為兩個(gè)社群了。蜘蛛俠（綠色），綠巨人（青綠色）和阿斯加德人（紅色）三個(gè)社群的結(jié)果與Louvain算法一致。我們還發(fā)現(xiàn)X-Man被劃分成兩個(gè)社群，加農(nóng)炮小組比Louvain的結(jié)果要稍微大點(diǎn)，同時(shí)也顯的不那么孤立。

結(jié)點(diǎn)顏色：代表LPA社群?結(jié)點(diǎn)大?。捍鞵ageRank值?名字大?。捍碇薪橹行男?/p>

譯者言：非常遺憾，我一直沒有使用LPA算法重現(xiàn)出那21個(gè)社群，而得到的都是當(dāng)結(jié)點(diǎn)社群，不知道作者是如何得到的，我已與作者進(jìn)行了聯(lián)系，如果有結(jié)果我會(huì)及時(shí)更新。另外，如果有朋友使用LPA推算出了任何結(jié)果，希望也給大家分享一下。當(dāng)前文章的數(shù)據(jù)可以通過本系統(tǒng)文章的第一篇在Neo4j中構(gòu)建漫威世界的社交網(wǎng)絡(luò)獲取。?我使用的查詢語(yǔ)句如下:

CALL algo.labelPropagation.stream(
????'MATCH?(u:Hero)?RETURN?id(u)?as?id,?1?as?weight,id(u)?as?value',
????'MATCH?(u1:Hero)-[rel:KNOWS]-(u2:Hero)?WHERE?rel.weight?>?100?RETURN?id(u1)?as?source,id(u2)?as?target,?rel.weight?as?weight',
{graph:"cypher",iterations:10,?partitionProperty?:?'lpa'})?
YIELD nodeId, label
with algo.getNodeById(nodeId) as node, label
return node.name , label

結(jié)論

你發(fā)現(xiàn)沒有？Neo4j圖算法庫(kù)真的很神奇，用起來也簡(jiǎn)單。通過與Cypher查詢語(yǔ)句結(jié)合進(jìn)行虛擬圖映射，可以簡(jiǎn)單有效的對(duì)圖進(jìn)行分析和理解。

本來，我打算在本文中介紹中心性算法的使用，但那樣本文將會(huì)非常長(zhǎng)，不便于閱讀，所以，?我后續(xù)將會(huì)再寫文章來介紹使用Cypher映射進(jìn)行中心性算法的示例。敬請(qǐng)期待吧。

譯者言：本文兩個(gè)算法的介紹很清晰，作者也考慮到讀者的心理負(fù)擔(dān)，幸好沒介紹中心性方面的算法，否則此文真的很長(zhǎng)。