圖表分析在企業決策中能夠發揮極大的價值，而好的圖形算法不僅易于使用，執行速度快，而且能夠產生強大的結果。Neo4j包含一個不斷增長的開放式高性能圖形算法庫，可以揭示連接數據中的隱藏模式和結構。

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

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

遍歷和尋路算法

1.廣度優先算法(BFS)

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

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

如何使用：廣度優先搜索可用于定位像BitTorrent等對等網絡中的鄰居節點，GPS系統可精確定位附近的位置，社交網絡服務可在特定距離內查找人員。

2.深度優先算法(DFS)

做什么：遍歷樹數據結構，通過在回溯之前盡可能探索每個分支。用于深層次的數據，是許多其他圖算法的前身。當樹較平衡或目標更接近端點時，深度優先搜索是首選。

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

3.單源最短路徑

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

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

4.全源最短路徑

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

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

5.最小生成樹(MWST)

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

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

Centrality Algorithms

6. PageRank

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

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

PageRank也用于機器學習，以確定最有影響的提取特征。在生物學中，它被用來識別食物網中哪些物種的滅絕會導致物種死亡的最大連鎖反應。

7. Degree Centrality

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

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

8. Closeness Centrality

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

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

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

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

9. Betweenness Centrality

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

如何使用：Betweenness Centrality適用于網絡科學中的各種問題，用于查明通信和交通網絡中的瓶頸或可能的攻擊目標。在基因組學中，被用于了解控制某些基因在蛋白質網絡中的改進，例如更好的藥物/疾病靶向。

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

社區發現算法

這個類別也被稱為聚類算法或分區算法。

10. Label Propagation

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

如何使用：Label Propagation具有不同的應用，例如了解社會團體中的共識形成、識別在生物網絡的過程(功能模塊)中所涉及的蛋白質集合等等。甚至還可以用于半監督和無監督的機器學習作為初始的預處理步驟。

11. Strongly Connected

做什么：定位節點組，其中每個節點可從同一組中的所有其他節點按照關系的方向到達，常被應用于深度優先算法。

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

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

12. Union-Find/Connected Components/Weakly Connected

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

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

13. Louvain Modularity

做什么：通過比較它的關系密度與適當定義的隨機網絡來測量社團分組的質量(即假定的準確性)。它通常用于評估復雜網絡的組織和社區層次結構。這對于無監督機器學習中的初始數據預處理也是有用的。

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

14. Local Clustering Coefficient/Node Clustering Coefficient

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

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

15. Triangle-Count and Average Clustering Coefficient

做什么：測量有多少節點具有三角形以及節點傾向于聚集在一起的程度。平均聚類系數為1時表明有一個分組，0時沒有連接。為使聚類系數有意義，它應該明顯高于網絡中所有關系隨機的版本。

如何使用：平均聚類系數通常用于估計網絡是否可能展現基于緊密集群的“小世界”行為。這也是集群穩定性和彈性的一個因素。流行病學家使用平均聚類系數來幫助預測不同社區的各種感染率。

結論

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