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

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

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

遍歷和尋路算法

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

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

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

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

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

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

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

3.單源最短路徑

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

如何使用：單源最短路徑通常用于自動獲取物理位置之間的路線，例如通過Google地圖獲取駕車路線。在邏輯路由中也很重要，例如電話呼叫路由（最低成本路由）。

4.全源最短路徑

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

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

5.最小生成樹（MWST）

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

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

Centrality Algorithms

6. PageRank

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

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

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

7. Degree Centrality

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

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

8. Closeness Centrality

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

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

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

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

9. Betweenness Centrality

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

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

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

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

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

10. Label Propagation

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

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

11. Strongly Connected

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

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

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

12. Union-Find/Connected Components/Weakly Connected

做什么：查找節(jié)點組，其中每個節(jié)點可從同一組中的任何其他節(jié)點到達(dá)，而不考慮關(guān)系的方向。它提供幾乎恒定的時間操作（獨立于輸入大小）來添加新的組，合并現(xiàn)有的組，并確定兩個節(jié)點是否在同一組中。

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

13. Louvain Modularity

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

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

14. Local Clustering Coefficient/Node Clustering Coefficient

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

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

15. Triangle-Count and Average Clustering Coefficient

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

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

結(jié)論

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