15種算法玩轉(zhuǎn)Neo4j數(shù)據(jù)庫(kù)

圖表分析在企業(yè)決策中能夠發(fā)揮極大的價(jià)值，而好的圖形算法不僅易于使用，執(zhí)行速度快，而且能夠產(chǎn)生強(qiáng)大的結(jié)果。Neo4j包含一個(gè)不斷增長(zhǎng)的開放式高性能圖形算法庫(kù)，可以揭示連接數(shù)據(jù)中的隱藏模式和結(jié)構(gòu)。

本文將為大家介紹Neo4j中提供的諸多圖算法以及它們的功能。使用Neo4j圖形算法，用戶可以建模并預(yù)測(cè)復(fù)雜的動(dòng)態(tài)特性，例如資源或信息的流動(dòng)，傳染或網(wǎng)絡(luò)故障傳播的途徑，以及組的影響和彈性。

由于Neo4j是將原生圖平臺(tái)中的分析和事務(wù)操作結(jié)合在一起，用戶不僅可以揭示真實(shí)世界系統(tǒng)的內(nèi)在本質(zhì)，還可以更快地開發(fā)和部署基于圖形的解決方案，并具有易于使用、簡(jiǎn)化的工作流程。

遍歷和尋路算法

1.廣度優(yōu)先算法（BFS）

做什么：遍歷樹數(shù)據(jù)結(jié)構(gòu)，探索最近的鄰居和他們的次級(jí)鄰居。它用于定位連接，是許多其他圖算法的前身。

當(dāng)樹較不平衡或目標(biāo)更接近起點(diǎn)時(shí)，BFS是首選。它也可用于查找節(jié)點(diǎn)之間的最短路徑或避免深度優(yōu)先搜索的遞歸過程。

如何使用：廣度優(yōu)先搜索可用于定位像BitTorrent等對(duì)等網(wǎng)絡(luò)中的鄰居節(jié)點(diǎn)，GPS系統(tǒng)可精確定位附近的位置，社交網(wǎng)絡(luò)服務(wù)可在特定距離內(nèi)查找人員。

2.深度優(yōu)先算法（DFS）

做什么：遍歷樹數(shù)據(jù)結(jié)構(gòu)，通過在回溯之前盡可能探索每個(gè)分支。用于深層次的數(shù)據(jù)，是許多其他圖算法的前身。當(dāng)樹較平衡或目標(biāo)更接近端點(diǎn)時(shí)，深度優(yōu)先搜索是首選。

如何使用：深度優(yōu)先算法通常用于游戲模擬，其中每個(gè)選擇或動(dòng)作引發(fā)另一個(gè)操作，從而擴(kuò)展成可能性的樹形圖。它將遍歷選擇樹，直到找到最佳解決方案路徑（即勝利）。

3.單源最短路徑

做什么：計(jì)算節(jié)點(diǎn)與所有其他節(jié)點(diǎn)之間的路徑，以及其與所有其他節(jié)點(diǎn)的總和值（成本，距離，時(shí)間或容量等關(guān)系的權(quán)重）并得出總和最小。

如何使用：?jiǎn)卧醋疃搪窂酵ǔＳ糜谧詣?dòng)獲取物理位置之間的路線，例如通過Google地圖獲取駕車路線。在邏輯路由中也很重要，例如電話呼叫路由（最低成本路由）。

4.全源最短路徑

做什么：計(jì)算包含圖中節(jié)點(diǎn)之間所有最短路徑的最短路徑森林（組）。當(dāng)最短路徑被阻塞或變得次優(yōu)時(shí)，切換到新的最短路徑，通常用于備用路由。

如何使用：用于評(píng)估備用路由，例如高速公路備份或網(wǎng)絡(luò)容量。它也是為邏輯路由提供多路徑的關(guān)鍵，比如呼叫路由選擇。

5.最小生成樹（MWST）

做什么：計(jì)算與訪問樹中所有節(jié)點(diǎn)相關(guān)的最小值（如成本，時(shí)間或容量等關(guān)系的權(quán)重）的路徑，用于逼近一些NP難題，如旅行商問題和隨機(jī)或迭代舍入。

如何使用：最小生成樹廣泛用于網(wǎng)絡(luò)設(shè)計(jì)：成本最低的邏輯或物理路由，如鋪設(shè)電纜，最快的垃圾收集路線，供水系統(tǒng)容量，高效電路設(shè)計(jì)等等。它還可用于滾動(dòng)優(yōu)化的實(shí)時(shí)應(yīng)用程序，如化學(xué)煉油廠的過程或行駛路線修正。

Centrality Algorithms

6. PageRank

做什么：估計(jì)當(dāng)前節(jié)點(diǎn)對(duì)其相鄰節(jié)點(diǎn)的重要性，然后再?gòu)钠溧従幽抢铽@得節(jié)點(diǎn)的重要性。一個(gè)節(jié)點(diǎn)的排名來源于其傳遞鏈接的數(shù)量和質(zhì)量。PageRank雖然被谷歌拋棄了，但它還是被廣泛認(rèn)為是檢測(cè)任何網(wǎng)絡(luò)中有影響力的節(jié)點(diǎn)的常用方式。

如何使用：PageRank用于評(píng)估重要性和影響力，經(jīng)常的用法是推薦推特賬戶以及一般的情緒分析。

PageRank也用于機(jī)器學(xué)習(xí)，以確定最有影響的提取特征。在生物學(xué)中，它被用來識(shí)別食物網(wǎng)中哪些物種的滅絕會(huì)導(dǎo)致物種死亡的最大連鎖反應(yīng)。

7. Degree Centrality

做什么：測(cè)量節(jié)點(diǎn)（或整個(gè)圖表）所具有的關(guān)系數(shù)量，被分為流入和流出兩個(gè)方向，關(guān)系具有指向性。

如何使用：Degree Centrality著眼于用途的直接連通性，例如評(píng)估患者接近病毒或聽取信息的近期風(fēng)險(xiǎn)。在社會(huì)研究中，可以用來預(yù)估人氣或者其它情感。

8. Closeness Centrality

做什么：衡量一個(gè)節(jié)點(diǎn)對(duì)其集群內(nèi)所有鄰居的集中程度。假定到所有其他節(jié)點(diǎn)的路徑都是最短的，那么該節(jié)點(diǎn)就能夠以最快的速度到達(dá)整個(gè)組。

如何使用：Closeness Centrality適用于多種資源、交流和行為分析，尤其是當(dāng)交互速度顯著時(shí)。

在新公共服務(wù)中，被用于確定最大可訪問性的位置。

在社交網(wǎng)絡(luò)分析中，用于找到具有理想社交網(wǎng)絡(luò)位置的人，以便更快地傳播信息。

9. Betweenness Centrality

做什么：測(cè)量通過節(jié)點(diǎn)的最短路徑的數(shù)量（首先通過廣度優(yōu)先算法找到）。出現(xiàn)在最短路徑上次數(shù)最多的節(jié)點(diǎn)具有較高的介數(shù)中心性，并且是不同集群之間的橋梁。它通常與控制資源和信息的流動(dòng)有關(guān)。

如何使用：Betweenness Centrality適用于網(wǎng)絡(luò)科學(xué)中的各種問題，用于查明通信和交通網(wǎng)絡(luò)中的瓶頸或可能的攻擊目標(biāo)。在基因組學(xué)中，被用于了解控制某些基因在蛋白質(zhì)網(wǎng)絡(luò)中的改進(jìn)，例如更好的藥物/疾病靶向。

Betweenness Centrality也被用來評(píng)估多人在線游戲玩家和共享醫(yī)師專業(yè)知識(shí)的信息流。

社區(qū)發(fā)現(xiàn)算法

這個(gè)類別也被稱為聚類算法或分區(qū)算法。

10. Label Propagation

做什么：基于鄰域多數(shù)的標(biāo)簽作為推斷集群的手段。這種極其快速的圖形分割需要很少的先驗(yàn)信息，并且被廣泛地應(yīng)用于大規(guī)模的社區(qū)檢測(cè)網(wǎng)絡(luò)中。這是理解圖組織的一個(gè)關(guān)鍵方法，通常是其他分析的主要步驟。

如何使用：Label Propagation具有不同的應(yīng)用，例如了解社會(huì)團(tuán)體中的共識(shí)形成、識(shí)別在生物網(wǎng)絡(luò)的過程（功能模塊）中所涉及的蛋白質(zhì)集合等等。甚至還可以用于半監(jiān)督和無(wú)監(jiān)督的機(jī)器學(xué)習(xí)作為初始的預(yù)處理步驟。

11. Strongly Connected

做什么：定位節(jié)點(diǎn)組，其中每個(gè)節(jié)點(diǎn)可從同一組中的所有其他節(jié)點(diǎn)按照關(guān)系的方向到達(dá)，常被應(yīng)用于深度優(yōu)先算法。

如何使用：Strongly Connected通常用于在識(shí)別的集群上獨(dú)立運(yùn)行其他算法。作為有向圖的預(yù)處理步驟，它有助于快速識(shí)別不連通的集群。

在零售推薦中，它有助于識(shí)別具有強(qiáng)親和性的組，然后將向那些尚未購(gòu)買商品的群體推薦首選商品。

12. Union-Find/Connected Components/Weakly Connected

做什么：查找節(jié)點(diǎn)組，其中每個(gè)節(jié)點(diǎn)可從同一組中的任何其他節(jié)點(diǎn)到達(dá)，而不考慮關(guān)系的方向。它提供幾乎恒定的時(shí)間操作（獨(dú)立于輸入大?。﹣硖砑有碌慕M，合并現(xiàn)有的組，并確定兩個(gè)節(jié)點(diǎn)是否在同一組中。

如何使用：Union-find/connected 經(jīng)常與其他算法結(jié)合使用，特別是對(duì)于高性能分組。作為無(wú)向圖的預(yù)處理步驟，它有助于快速識(shí)別斷開的組。

13. Louvain Modularity

做什么：通過比較它的關(guān)系密度與適當(dāng)定義的隨機(jī)網(wǎng)絡(luò)來測(cè)量社團(tuán)分組的質(zhì)量（即假定的準(zhǔn)確性）。它通常用于評(píng)估復(fù)雜網(wǎng)絡(luò)的組織和社區(qū)層次結(jié)構(gòu)。這對(duì)于無(wú)監(jiān)督機(jī)器學(xué)習(xí)中的初始數(shù)據(jù)預(yù)處理也是有用的。

如何使用：Louvain用于評(píng)估Twitter，LinkedIn和YouTube上的社交結(jié)構(gòu);用于欺詐分析，以評(píng)估一個(gè)組織是只存在一些不良行為，還是背后一個(gè)連環(huán)欺詐。Louvain在比利時(shí)電信網(wǎng)絡(luò)中揭示了一個(gè)六級(jí)客戶層級(jí)。

14. Local Clustering Coefficient/Node Clustering Coefficient

做什么：對(duì)于一個(gè)特定的節(jié)點(diǎn)，量化了其到鄰居節(jié)點(diǎn)的距離， （每個(gè)節(jié)點(diǎn)都直接連接到其他節(jié)點(diǎn)）。例如，如果您的所有朋友都直接了解對(duì)方，那么您的本地集群系數(shù)將是1。集群的小值表明盡管存在一個(gè)分組，但節(jié)點(diǎn)之間并沒有緊密連接。

如何使用：Local cluster coefficient通過理解群體相關(guān)性或碎片化的可能性，對(duì)估計(jì)彈性具有重要意義。用這種方法對(duì)歐洲電網(wǎng)的分析發(fā)現(xiàn)，與稀疏連接的節(jié)點(diǎn)相比，集群更能抵御普遍的故障。

15. Triangle-Count and Average Clustering Coefficient

做什么：測(cè)量有多少節(jié)點(diǎn)具有三角形以及節(jié)點(diǎn)傾向于聚集在一起的程度。平均聚類系數(shù)為1時(shí)表明有一個(gè)分組，0時(shí)沒有連接。為使聚類系數(shù)有意義，它應(yīng)該明顯高于網(wǎng)絡(luò)中所有關(guān)系隨機(jī)的版本。

如何使用：平均聚類系數(shù)通常用于估計(jì)網(wǎng)絡(luò)是否可能展現(xiàn)基于緊密集群的“小世界”行為。這也是集群穩(wěn)定性和彈性的一個(gè)因素。流行病學(xué)家使用平均聚類系數(shù)來幫助預(yù)測(cè)不同社區(qū)的各種感染率。

結(jié)論

世界是由關(guān)系驅(qū)動(dòng)的，而Neo4j圖形分析揭示了圖形背后的意義，希望這些優(yōu)化的圖形算法能夠幫助你以更加有意義、更有效的方式來理解所連接的數(shù)據(jù)。