原文鏈接: https://tbgraph.wordpress.com/2017/11/23/neo4j-marvel-social-graph-algorithms-centralities/
關(guān)于漫威英雄的社交網(wǎng)絡(luò)系列已寫(xiě)了好幾篇文章靴拱，是時(shí)候結(jié)束它了呐馆。作為本系列的最后一篇文章椅您，我們將來(lái)研究一下如何在cypher語(yǔ)句映射的虛擬圖上進(jìn)行中心性計(jì)算，我們將使用Neo4j和圖形算法庫(kù)來(lái)找出漫威英雄網(wǎng)絡(luò)中最有影響力的英雄或其他重要的英雄辟汰。
關(guān)于漫威社交網(wǎng)絡(luò)的研究已完成的文章有以下幾篇：
在Neo4j中構(gòu)建漫威社交網(wǎng)絡(luò)
在Neo4j中對(duì)漫威社交網(wǎng)絡(luò)進(jìn)行初步分析
Neo4j中基于三角形個(gè)數(shù)和連通分量的漫威英雄初步社群分析
Neo4j中使用Louvain和標(biāo)簽傳播算法對(duì)漫威英雄進(jìn)行客戶群分析
使用Cypher進(jìn)行虛擬圖映射
正如我在前面文章中說(shuō)過(guò)的，使用Cypher映射虛擬圖是真的好用弄企，他可以使我們簡(jiǎn)單快速的映射一個(gè)我們想要的虛擬圖货徙，我們簡(jiǎn)稱為“Cypher加載”。為了更好的理解這個(gè)神奇的功能晨仑，我們需要深入了解它是如何工作褐墅。
與直接使用結(jié)點(diǎn)標(biāo)簽和關(guān)系類型加載子圖不同，Cypher加載允許我們定義關(guān)系的方向洪己，通常是以下三種值“incoming”,"outgoing"或者"both"(雙向/無(wú)向)妥凳，但是Cypher加載不支持單條無(wú)向關(guān)系。
這看起來(lái)可不太友好答捕，但事實(shí)上逝钥，Cypher加載允許我們使用Cypher查詢語(yǔ)句映射各種虛擬圖去嘗試執(zhí)行圖像算法。我在之前的文章中也使用過(guò)噪珊，只是沒(méi)有詳細(xì)的介紹它而已晌缘。?
假設(shè)我們現(xiàn)在有兩個(gè)英雄結(jié)點(diǎn)以及在他們之間有一個(gè)單向的關(guān)系齐莲。將此圖加載為無(wú)向圖或者有向圖的唯一區(qū)別就是：在使用Cypher查詢語(yǔ)句映射時(shí)是否指定關(guān)系的方向痢站。當(dāng)我們?cè)诓樵儠r(shí)不指定方向，Cypher引擎會(huì)為每個(gè)關(guān)系返回兩個(gè)方向的結(jié)果选酗，這樣我們映射圖也就是雙向的阵难，你也可以稱他為無(wú)向的。
映射有向圖:?
MATCH (u1:Hero)-[rel:KNOWS]->(u2:Hero)
RETURN id(u1) as source, id(u2) as target映射無(wú)向圖:?
MATCH (u1:Hero)-[rel:KNOWS]-(u2:Hero)
RETURN id(u1) as source, id(u2) as target中心性
在圖論與網(wǎng)絡(luò)分析中芒填，中心性是用來(lái)表示網(wǎng)絡(luò)中結(jié)點(diǎn)重要性的指標(biāo)之一呜叫。在社交網(wǎng)絡(luò)中，其用來(lái)表明最有影響力的人殿衰。在互聯(lián)網(wǎng)朱庆、城市網(wǎng)絡(luò)甚至傳染病學(xué)中，用來(lái)表明關(guān)鍵結(jié)點(diǎn)闷祥。中心性概念最初應(yīng)用在社交網(wǎng)絡(luò)中娱颊，并且它的很多術(shù)語(yǔ)都可以反應(yīng)出其社會(huì)學(xué)起源，隨后中心性被推廣到其它類型網(wǎng)絡(luò)的分析中。[1]
Pagerank
Pagerank是因Google專有的搜索算法箱硕。它通過(guò)計(jì)算鏈接到頁(yè)面的鏈接數(shù)量和質(zhì)量來(lái)決定當(dāng)前頁(yè)面的重要性拴竹。其基本的假設(shè)是，重要的結(jié)點(diǎn)肯定會(huì)有許多的頁(yè)面鏈向它剧罩。關(guān)于Pagerank更多內(nèi)容可以看此文(https://neo4j.com/docs/graph-algorithms/3.5/algorithms/page-rank/)
我們使用Cypher加載來(lái)漫威網(wǎng)絡(luò)中最大社群的結(jié)點(diǎn)栓拜，并且設(shè)置關(guān)系的weight閾值為100.
call algo.pageRank.stream(
// 僅加載最大的社群。
'MATCH (u:Hero) WHERE u.component = 136 RETURN id(u) as id
','
MATCH (u1:Hero)-[k:KNOWS]-(u2:Hero)
// 近似性閾值
WHERE k.weight >= 100
RETURN id(u1) as source, id(u2) as target
',{graph:'cypher'}
) yield node,score
WITH node,score ORDER BY score DESC limit 10
return node.name as name, score;美國(guó)隊(duì)長(zhǎng)是Pagerank分?jǐn)?shù)最高的惠昔，他位于網(wǎng)絡(luò)的中心幕与，有24個(gè)關(guān)系，并且與其他重要英雄如雷神托爾镇防、蜘蛛俠纽门、鋼鐵俠都有聯(lián)系。如果我們仔細(xì)看一下與美國(guó)隊(duì)長(zhǎng)有聯(lián)系的英雄营罢，會(huì)發(fā)現(xiàn)一個(gè)有趣現(xiàn)象赏陵，他們因?yàn)榕c美國(guó)隊(duì)長(zhǎng)有聯(lián)系，而使得他們的pagerank分也比較高饲漾。
結(jié)點(diǎn)顏色由淺到深代表著Pagerank值由小到大蝙搔。
譯者言：上面的查詢語(yǔ)句中?
u.component = 136?代表著社群的ID，(如果你執(zhí)行上的語(yǔ)句沒(méi)有結(jié)果可以試試改成321考传，這是我計(jì)算是使用的社群ID)吃型。這個(gè)值可以在上一篇文章Neo4j中使用Louvain和標(biāo)簽傳播算法對(duì)漫威英雄進(jìn)行客戶群分析中看到。但我們的數(shù)據(jù)中Hero結(jié)點(diǎn)是沒(méi)有這個(gè)屬性的僚楞，為了將Hero結(jié)點(diǎn)上增加component屬性勤晚，需要先運(yùn)行下面的語(yǔ)句:CALL algo.unionFind('Hero', 'KNOWS',
{weightProperty:'weight', defaultValue:0.0, threshold:100.0,concurrency:1, write: true, writeProperty:'component'})
YIELD nodes, setCount, loadMillis, computeMillis, writeMillis此語(yǔ)句運(yùn)行之后就會(huì)在每個(gè)Hero結(jié)點(diǎn)上增加一個(gè)component屬性。
接近中心性
接近中心性定義了一個(gè)點(diǎn)到所有其他點(diǎn)最短距離的和泉褐，換句話說(shuō)赐写，要計(jì)算接近中心性，首先需要計(jì)算每對(duì)結(jié)點(diǎn)之間的最短路徑長(zhǎng)度膜赃。然后再對(duì)每個(gè)結(jié)點(diǎn)計(jì)算其到所有其他結(jié)點(diǎn)的最短路徑和挺邀。[2]
接近中心性可以理解為信息流到達(dá)網(wǎng)絡(luò)中任一點(diǎn)的所消耗的時(shí)間指標(biāo)。這個(gè)接近中心性分?jǐn)?shù)越高跳座，代表信息流從一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)所花的時(shí)間就越長(zhǎng)端铛。因此，我們可以認(rèn)為接近中心性代表著一個(gè)結(jié)點(diǎn)到達(dá)其他結(jié)點(diǎn)的潛在能力疲眷。關(guān)于更多信息可見(jiàn)文檔(https://neo4j.com/docs/graph-algorithms/3.5/algorithms/closeness-centrality/)
譯者言：這個(gè)接近中心性的介紹好生硬禾蚕，其實(shí)簡(jiǎn)單說(shuō)，接近中心性狂丝，計(jì)算的是一個(gè)點(diǎn)到其他所有點(diǎn)的距離的總和换淆，這個(gè)總和越小就說(shuō)明這個(gè)點(diǎn)到其他所有點(diǎn)的路徑越短虚倒，也就說(shuō)明這個(gè)點(diǎn)距離其他所有點(diǎn)越近，從而證明這個(gè)點(diǎn)的重要性产舞。
我們?nèi)詫⑹褂肅ypher加載漫威網(wǎng)絡(luò)中最大社群中的結(jié)點(diǎn)并將關(guān)系的weight閾值設(shè)置為100魂奥。對(duì)于接近中心性而言，最重要的是需要加載一個(gè)獨(dú)立社群易猫。
不幸的是耻煤，當(dāng)圖是非連通圖時(shí)，接近中心性是無(wú)法使用的准颓，因?yàn)樵诜沁B通圖中哈蝇，兩個(gè)點(diǎn)可能屬于不同的社群，則這兩個(gè)點(diǎn)是無(wú)法連接的攘已，這樣他們之間的距離就是無(wú)窮大炮赦。對(duì)于這樣的圖中的每一個(gè)點(diǎn)，都有屬于另一個(gè)社群的點(diǎn)與之無(wú)法連接样勃。因此圖中所有頂點(diǎn)的都是沒(méi)有用的吠勘，而接近中心性的計(jì)算也被限制在最大的社群中，其他社群中結(jié)點(diǎn)的作用是被忽略的峡眶。
CALL algo.closeness.stream(
// Match only the biggest component
'MATCH (u:Hero) WHERE u.component = 136 RETURN id(u) as id',
'MATCH (u1:Hero)-[k:KNOWS]-(u2:Hero)
// Similarity threshold
WHERE k.weight >= 100
RETURN id(u1) as source,id(u2) as target',
{graph:'cypher'}) YIELD nodeId, centrality
WITH nodeId,centrality
ORDER BY centrality DESC LIMIT 10
MATCH (h:Hero) where id(h)=nodeId
RETURN h.name as hero, centrality上圖中可以看出剧防，美國(guó)隊(duì)長(zhǎng)的位置非常特殊，事實(shí)上辫樱，在所有類型的中心性上峭拘，美國(guó)隊(duì)長(zhǎng)都是排第一。我們可以看到狮暑，在較緊密的社群里鸡挠，其結(jié)點(diǎn)的接近中心性的值相對(duì)較大，而在邊緣或較少連接的結(jié)點(diǎn)上搬男，其接近中心性的值也較小拣展。另外，我們還注意到圖中結(jié)點(diǎn)的分布也很重要止后，一般中間社群結(jié)點(diǎn)的接近中心性值要比周邊社群的高瞎惫。例如，鋼鐵俠和幻視要比蜘蛛俠的接近中心性高译株。但有意思的是蜘蛛俠的Pagerank值要比較他們大。
結(jié)點(diǎn)顏色由淺到深代表著接近中心性值由小到大挺益。
和諧中心性（值中心性）
從畢達(dá)哥拉斯和柏拉圖時(shí)代起歉糜，人們就知道，和諧就是“諧調(diào)和優(yōu)美的比率”的表述望众，后來(lái)匪补，音樂(lè)家用來(lái)表達(dá)規(guī)范音階伞辛，建筑學(xué)家描述建筑的完美比例。[4]
社交網(wǎng)絡(luò)分析是一門(mén)快速發(fā)展的且跨學(xué)科領(lǐng)域夯缺，它由社會(huì)學(xué)蚤氏、物理學(xué)、歷史學(xué)踊兜、數(shù)學(xué)竿滨、政治等多種學(xué)科共同發(fā)展而來(lái)∧缶常可能是由于缺少綜合性研究于游，造成其中有些方法存在著不足，但已被普遍所接受(Freeman, 1978; Faust & Wasserman, 1992)垫言，而接近中心性在非連通網(wǎng)絡(luò)的不適用性就是其一贰剥。和諧中心性也正是用來(lái)在非連通網(wǎng)絡(luò)中代替接近中心性的。實(shí)際情況顯示筷频，在真實(shí)環(huán)境下蚌成，我們解讀的結(jié)果發(fā)現(xiàn)其與接近中心性指標(biāo)一致，計(jì)算復(fù)雜度相同凛捏，但最重要的是它可用于非連通網(wǎng)絡(luò)笑陈！[3]
CALL algo.closeness.harmonic.stream(
'MATCH (u:Hero) WHERE u.component = 136 RETURN id(u) as id ',
'MATCH (u1:Hero)-[k:KNOWS]-(u2:Hero) WHERE k.weight >= 100 RETURN id(u1) as source,id(u2) as target',
{graph:'cypher'}) YIELD nodeId, centrality
WITH nodeId,centrality
ORDER BY centrality DESC LIMIT 10
MATCH (h:Hero) where id(h)=nodeId
RETURN h.name as hero, centrality因?yàn)楹椭C中心性是為了幫助接近中心性解決其在非連通圖上的問(wèn)題，所以葵袭，得到的結(jié)果也是相似的涵妥。?
譯者言：這個(gè)和諧中心性（Harmonic Centrality），完全沒(méi)有找到相應(yīng)的中文資料可參考坡锡。僅從官方文章中找到其計(jì)算公式為：?
結(jié)點(diǎn)原始和諧中心性 = sum(1 / 結(jié)點(diǎn)到其他點(diǎn)的距離)
歸一化后的結(jié)點(diǎn)和諧中心性 = sum(1 / 結(jié)點(diǎn)到其他點(diǎn)的距離)/(總結(jié)點(diǎn)數(shù)-1)
而接近中心性的計(jì)算公式為:
結(jié)點(diǎn)原始接近中心性 = 1/sum(結(jié)點(diǎn)到其他點(diǎn)的距離）
歸一化后的結(jié)點(diǎn)接近中心性 = (總結(jié)點(diǎn)數(shù)-1)/sum(結(jié)點(diǎn)到其他點(diǎn)的距離）
中介中心性
在圖論中蓬网，中介中心性是一種基于最短路徑的中心性指標(biāo)。在連通圖中鹉勒，每對(duì)點(diǎn)都存在著至少一條最短路徑帆锋，對(duì)于無(wú)權(quán)重圖，最短路徑是指路徑所包含的關(guān)系數(shù)最少禽额，對(duì)于權(quán)重圖锯厢，最短路徑是指路徑所含邊的權(quán)重之和最小。而每個(gè)點(diǎn)的中介中心性值就是通過(guò)這個(gè)點(diǎn)的最短路徑的條數(shù)脯倒。更多描述見(jiàn)(https://neo4j.com/docs/graph-algorithms/current/algorithms/betweenness-centrality/)
我們?nèi)匀皇褂肅ypher加載那個(gè)最大的社群并設(shè)置關(guān)系的weight閾值為100
CALL algo.betweenness.stream(
'MATCH (u:Hero) WHERE u.component = 136 RETURN id(u) as id',
'MATCH (u1:Hero)-[k:KNOWS]-(u2:Hero) WHERE k.weight >= 100 RETURN id(u1) as source,id(u2) as target',
{graph:'cypher'}) YIELD nodeId, centrality
WITH nodeId,centrality
ORDER BY centrality DESC LIMIT 10
MATCH (h:Hero) where id(h)=nodeId
RETURN h.name as hero, centrality美國(guó)隊(duì)長(zhǎng)仍然排在第一位实辑，但這次野獸排到了第二位，這并不奇怪藻丢，因?yàn)樗a(chǎn)中間和右邊社群的橋梁剪撬。蜘蛛俠和浩克扮演著與野獸相同的角色，但不同的是悠反，他們倆所關(guān)聯(lián)的社群較小残黑，所以馍佑，他們的中介中心性值也更低。
結(jié)點(diǎn)顏色由淺到深代表著接中介中心性值由小到大梨水。
引用文獻(xiàn)
[1] https://en.wikipedia.org/wiki/Centrality
[2] http://qualquant.org/wp-content/uploads/networks/2008+1-7-3.pdf
[3] https://infoscience.epfl.ch/record/200525/files/[EN]ASNA09.pdf?
[4] https://arxiv.org/pdf/cond-mat/0008357.pdf
[6] https://en.wikipedia.org/wiki/Betweenness_centrality
譯者言：總算翻譯完《漫威社交網(wǎng)絡(luò)分析》的這個(gè)系列了拭荤，接下來(lái)可以坐等《復(fù)仇者聯(lián)盟4》上映了。
