原文鏈接:https://tbgraph.wordpress.com/2017/10/28/neo4j-marvel-social-graph-analysis/
譯者言：原文篇副較長(zhǎng)，為了方便閱讀，這里先原文拆成上下兩篇。本文是下篇，主要介紹聚類系數(shù)，連通分量，加權(quán)連通分量幾種分析方法，總體而言還都是比較基礎(chǔ)的分析方法。好，閑話少說(shuō)，書接上回在Neo4j中對(duì)漫威社交網(wǎng)絡(luò)進(jìn)行初步分析。

三角形個(gè)數(shù)/聚類系數(shù)

在圖論中，聚類系數(shù)是用來(lái)描述圖中結(jié)點(diǎn)聚集程度的系數(shù)。在現(xiàn)實(shí)的網(wǎng)絡(luò)中，尤其是在特定社交網(wǎng)絡(luò)中，由于相對(duì)高密度連接關(guān)系，結(jié)點(diǎn)總是趨向于建立一組嚴(yán)密的組織關(guān)系。這種可能性往往比兩個(gè)結(jié)點(diǎn)之間隨機(jī)建立了一個(gè)連接的平均概率更大。這種相互關(guān)系可以利用聚類系數(shù)進(jìn)行量化表示(理論依據(jù)參看文章結(jié)尾[1][2]引用)。

聚類系數(shù)分為整體與局部?jī)煞N。整體聚類系數(shù)可以給出一個(gè)圖中結(jié)點(diǎn)整體的聚集程度的評(píng)估，而局部聚類系數(shù)則可以測(cè)量圖中每一個(gè)結(jié)點(diǎn)附近的聚集程度。

CALL algo.triangleCount('Hero', 'KNOWS',
{write:true, writeProperty:'triangles',
clusteringCoefficientProperty:'coefficient'})
YIELD nodeCount, triangleCount, averageClusteringCoefficient;

運(yùn)行這個(gè)算法，將會(huì)在每個(gè)Hero結(jié)點(diǎn)增加兩個(gè)屬性：局部三條形個(gè)數(shù)(triangles)和聚類系數(shù)(coefficient)。同時(shí)會(huì)返回整個(gè)圖的總?cè)切蝹€(gè)數(shù)和平均聚類系數(shù)。關(guān)于這個(gè)算法的更多信息請(qǐng)看文檔(https://neo4j.com/docs/graph-algorithms/current/algorithms/triangle-counting-clustering-coefficient/)

從上圖可以看到，平均聚類系數(shù)達(dá)到0.77，已經(jīng)非常高了。如果是1的話，就代表整個(gè)圖就是一個(gè)完整的類群，那樣的話，圖中每個(gè)人都是知道彼此的。而聚類系數(shù)如此之高也并不奇怪，因?yàn)槲覀儓D是連通的，只是大部分關(guān)系都弱連接而已。

連通分量

圖的連通性測(cè)試是每個(gè)圖算法最重要的一個(gè)預(yù)處理步驟，這就要求這種測(cè)試要簡(jiǎn)單且快速。即使看上去一個(gè)圖是連通的，但在執(zhí)行算法之間也要進(jìn)行一下連通性測(cè)試。因?yàn)楫?dāng)算法在非連通圖上運(yùn)行時(shí)，可能會(huì)有細(xì)微的且難以發(fā)現(xiàn)的錯(cuò)誤出現(xiàn)。

連通分量還有一些具體用處，如我們?cè)诜治鲆粋€(gè)社交網(wǎng)絡(luò)時(shí)，可以幫助我們發(fā)現(xiàn)圖中存在的所有孤立的群組。 關(guān)于更多信息請(qǐng)查閱文檔(https://neo4j.com/docs/graph-algorithms/current/algorithms/connected-components/)

CALL algo.unionFind.stream('Hero', 'KNOWS', {})
YIELD nodeId,setId
WITH setId,count(*) as communitySize
// filter our single node communities
WHERE communitySize > 1
RETURN setId,communitySize
ORDER BY communitySize DESC LIMIT 20

上面語(yǔ)句運(yùn)行時(shí)，可以看出，整個(gè)圖有22個(gè)群組成，且最大的群覆蓋了整個(gè)圖的99.5%。另外，還有18個(gè)單成員群，以及3個(gè)小群：分別有9個(gè)、7個(gè)、2個(gè)成員。

譯者言：看上面的語(yǔ)句和圖以及描述可能不太好理解，上面的語(yǔ)句把所有單成員群都屏蔽了。但是運(yùn)行下面的語(yǔ)句就可以容易理解：

CALL algo.unionFind.stream('Hero', 'KNOWS', {}) 
YIELD nodeId,setId
WITH setId,count(*) as communitySize
RETURN setId,communitySize
ORDER BY communitySize DESC

這里把所有群都列出來(lái)了，包括單成員群。

接下來(lái)我們看看這些小群里都有誰(shuí)

CALL algo.unionFind.stream('Hero', 'KNOWS', {})
YIELD nodeId,setId
WITH setId,collect(nodeId) as membersId,count(*) as communitySize
// skip the largest component
ORDER BY communitySize DESC SKIP 1 LIMIT 20
MATCH (h:Hero) WHERE id(h) in membersId
RETURN setId,collect(h.name) as members
ORDER BY length(members) DESC

我們通過(guò)返回的結(jié)點(diǎn)ID找到結(jié)點(diǎn)，再通過(guò)結(jié)點(diǎn)去獲取英雄的名稱。

?有18位英雄從沒(méi)有和其他英雄一起出現(xiàn)過(guò)，他們是RED WOLF II, RUNE, DEATHCHARGE 等。第二大群有9位英雄，看上去他們是ASHER的家人和朋友。

譯者言:非常抱歉，真的不知道這幾位英雄怎么稱呼了。

加權(quán)連通分量

現(xiàn)在我們想要把兩個(gè)英雄標(biāo)記為同事，但是只在一部漫畫中出現(xiàn)，不能稱之為同事，要在至少十部漫畫中一塊出現(xiàn)才算同事。要實(shí)現(xiàn)這個(gè)邏輯，這時(shí)就需要使用加權(quán)連通分量算法。

在algo.unionFind.stream方法的第三個(gè)參數(shù)中，有兩個(gè)選項(xiàng)可能用來(lái)定義權(quán)重和閾值。如果關(guān)系上weight值足夠高，大于閾值時(shí)，此時(shí)兩英雄之間的關(guān)系就會(huì)保留，代表這兩英雄是有聯(lián)系的，是同事，否則，這個(gè)關(guān)系就會(huì)被拋棄，這兩英雄也就沒(méi)有聯(lián)系，不是同事。

在我們的示例中，要求兩英雄至少在10部漫畫中一起出現(xiàn)過(guò)才代表他們之前有聯(lián)系，可以被標(biāo)記為同事。

CALL algo.unionFind.stream('Hero', 'KNOWS',
{weightProperty:'weight', threshold:10.0})
YIELD nodeId,setId
RETURN setId,count(*) as communitySize
ORDER BY communitySize DESC LIMIT 20;

注意 weightProperty 和 threshold.?

譯者言：上述語(yǔ)句有可能運(yùn)行失敗，那是因?yàn)槭褂玫陌姹静恢С植⑿杏?jì)算，可以使用如下語(yǔ)句:

CALL algo.unionFind.stream('Hero', 'KNOWS', 
{weightProperty:'weight', threshold:10.0,concurrency:1}) 
YIELD nodeId,setId
RETURN setId,count(*) as communitySize
ORDER BY communitySize DESC LIMIT 20;

如我們所料，最大一個(gè)群的英雄覆蓋率由之間的99.5%下降到18.6%。另外，通過(guò)調(diào)整閾值，我們可以發(fā)現(xiàn)一些潛在的英雄團(tuán)隊(duì)，包括他們之間更多的互動(dòng)，以及更久遠(yuǎn)的歷史等。

我們可以自行設(shè)置不同的閾值看看會(huì)怎樣。

另外，不僅群的人數(shù)有意思，群成員也很有趣。我們來(lái)看看這些群成員，先跳過(guò)第一大群，因?yàn)樵跒g覽器里顯示1200個(gè)名字可不太明智。

CALL algo.unionFind.stream('Hero', 'KNOWS',
{weightProperty:'weight', defaultValue:0.0, threshold:10.0})
YIELD nodeId,setId
WITH setId,collect(nodeId) as membersId,count(*) as communitySize
// skip the largest component
ORDER BY communitySize DESC SKIP 1 LIMIT 20
MATCH (h:Hero) WHERE id(h) in membersId
RETURN setId,collect(h.name) as members
ORDER BY length(members) DESC

第二大群已經(jīng)顯示出來(lái)，他們的名字看起來(lái)很酷，如Bodybag、China Doll 和 Scatter Brain。但是很抱歉，我對(duì)這個(gè)領(lǐng)域所知甚少，無(wú)法給出任何評(píng)價(jià)。

譯者言：我也不知道這第二大群都是些什么英雄，就直接貼出來(lái)吧。

結(jié)論

本文比較長(zhǎng)，但是我想在漫威英雄社交網(wǎng)絡(luò)上分析的遠(yuǎn)不至這些，所以，我會(huì)至少再寫一篇文章來(lái)介紹如何使用Cypher來(lái)進(jìn)行中心性判斷，以及使用Louvain和標(biāo)簽傳播算法來(lái)進(jìn)行群組識(shí)別。

好，希望今天這些對(duì)你有用。

引用

[1] https://en.wikipedia.org/wiki/Clustering_coefficient