工程師3 發表於 2018-05-03 15:01:00
圖表分析在企業決策中能夠發揮極大的價值，而好的圖形算法不僅易於使用，執行速度快，而且能夠產生強大的結果。Neo4j包含一個不斷增長的開放式高性能圖形算法庫，可以揭示連接數據中的隱藏模式和結構。
本文將為大家介紹Neo4j中提供的諸多圖算法以及它們的功能。使用Neo4j圖形算法，用戶可以建模並預測複雜的動態特性，例如資源或信息的流動，傳染或網絡故障傳播的途徑，以及組的影響和彈性。
由於Neo4j是將原生圖平臺中的分析和事務操作結合在一起，用戶不僅可以揭示真實世界系統的內在本質，還可以更快地開發和部署基於圖形的解決方案，並具有易於使用、簡化的工作流程。
1.廣度優先算法（BFS）
做什麼：遍歷樹數據結構，探索最近的鄰居和他們的次級鄰居。它用於定位連接，是許多其他圖算法的前身。
當樹較不平衡或目標更接近起點時，BFS是首選。它也可用於查找節點之間的最短路徑或避免深度優先搜索的遞歸過程。
如何使用：廣度優先搜索可用於定位像BitTorrent等對等網絡中的鄰居節點，GPS系統可精確定位附近的位置，社交網絡服務可在特定距離內查找人員。
2.深度優先算法（DFS）
做什麼：遍歷樹數據結構，通過在回溯之前儘可能探索每個分支。用於深層次的數據，是許多其他圖算法的前身。當樹較平衡或目標更接近端點時，深度優先搜索是首選。
如何使用：深度優先算法通常用於遊戲模擬，其中每個選擇或動作引發另一個操作，從而擴展成可能性的樹形圖。它將遍歷選擇樹，直到找到最佳解決方案路徑（即勝利）。
3.單源最短路徑
做什麼：計算節點與所有其他節點之間的路徑，以及其與所有其他節點的總和值（成本，距離，時間或容量等關係的權重）並得出總和最小。
如何使用：單源最短路徑通常用於自動獲取物理位置之間的路線，例如通過Google地圖獲取駕車路線。在邏輯路由中也很重要，例如電話呼叫路由（最低成本路由）。
4.全源最短路徑
做什麼：計算包含圖中節點之間所有最短路徑的最短路徑森林（組）。當最短路徑被阻塞或變得次優時，切換到新的最短路徑，通常用於備用路由。
如何使用：用於評估備用路由，例如高速公路備份或網絡容量。它也是為邏輯路由提供多路徑的關鍵，比如呼叫路由選擇。
5.最小生成樹（MWST）
做什麼：計算與訪問樹中所有節點相關的最小值（如成本，時間或容量等關係的權重）的路徑，用於逼近一些NP難題，如旅行商問題和隨機或迭代捨入。
如何使用：最小生成樹廣泛用於網絡設計：成本最低的邏輯或物理路由，如鋪設電纜，最快的垃圾收集路線，供水系統容量，高效電路設計等等。它還可用於滾動優化的實時應用程式，如化學煉油廠的過程或行駛路線修正。
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圖形分析揭示了圖形背後的意義，希望這些優化的圖形算法能夠幫助你以更加有意義、更有效的方式來理解所連接的數據。
打開APP閱讀更多精彩內容聲明：本文內容及配圖由入駐作者撰寫或者入駐合作網站授權轉載。文章觀點僅代表作者本人，不代表電子發燒友網立場。文章及其配圖僅供工程師學習之用，如有內容圖片侵權或者其他問題，請聯繫本站作侵刪。 侵權投訴