1. 首頁 > 生活百科 > >

從零開始學Graph Database：什么是圖

生活百科

摘要：本文從零開始引導與大家一起學習圖知識 。希望大家可以通過本教程學習如何使用圖數據庫與圖計算引擎 。本篇將以華為云圖引擎服務來輔助大家學習如何使用圖數據庫與圖計算引擎 。
【從零開始學Graph Database：什么是圖】本文分享自華為云社區《從零開始學Graph Database（1）》，作者：弓乙。
基礎概念什么是圖？首先，我們需要明確圖 Graph的概念 。
這里的圖，是graph, 是graphical，而不是graphic 。即圖處理的是關系問題，而不是圖片 。我們解決是關系問題，而非視覺cv問題 。
從零開始學Graph Database：什么是圖

文章插圖
在離散數據中 ， 有專門研究圖的圖論 。包含子圖相關，染色，路徑，網絡流量等問題 。
在計算機科學中 ， 我們將圖抽象為一種數據結構，即由點,邊構成的集合 。我們可以將現實世界的任意一種包含關系的實體用圖來抽象概括 。
我們通常把圖的問題定義為G=(V,E,φ)：
V:是節點的集合E:是邊的集合φ: E->{(x,y) | (x,y)∈ V^2 ∪ x≠y }是一個關聯函數，它每條邊映射到一個有頂點組成的有序對上 。下圖是一個使用圖來描述的社交網絡 。點代表了人，邊代表了人和人之間為朋友關系 。在構建了這樣一個社交網絡以后，我們可以通過使用圖查詢和算法使得圖數據產生價值 。如利用k跳查詢,共同鄰居,node2vec等來為社交網絡中的用戶進行好友推薦 。
從零開始學Graph Database：什么是圖

文章插圖
// 好友推薦邏輯試想我們為李雷推薦好友 ， 思路是：向他推薦其好友的好友 。但是需要過濾掉本身李雷的好友 。如上圖，小明即是李雷的好友，也是李雷好友的好友 。所以在這種情況中，我們不需要再向李雷推薦小明了 。而是推薦 小霞和小剛 。這種稍微有點復雜的推薦思路，可以使用查詢語言進行 。以gremlin為例：g.V("李雷").repeat(out("friend").simplePath().where(without('1hop')).store('1hop')).times(2).path().by("name").limit(100)可以使用圖做什么？傳統上我們使用圖來解決一些數學問題 。比如圖論起源于著名的柯尼斯堡七橋問題, 該問題被歐拉推廣為：怎樣判斷是否存在著一個恰好包含了所有邊，且沒有重復的路徑 。即一筆畫問題 。
從零開始學Graph Database：什么是圖

文章插圖
歐拉證明了以下定理，并解決了一筆畫問題：
連通的無向圖G有歐拉路徑（一筆畫）的充要條件是：G中的奇點的數目等于0或2 。（奇點：連接邊數為奇數的頂點 。）我們可以用一筆畫問題來解決七橋問題，從模型可以看出來，七橋問題中的奇點數目為4個，顯然不滿足一筆畫的充要條件 。故七橋無法在所有橋都只能走一遍的前提下，把這個地方所有的橋都走遍 。
當然了，圖并非只能解決這類圖論經典問題(如 四色問題，馬的遍歷問題，郵遞員問題, 網絡流問題 )，只要能夠將研究對象表示為圖結構 ， 就能利用圖的特點來解決問題，甚至大部分情況下，并不需要使用到多么高深的算法 。
查詢與算法圖查詢這里的查詢一般指代使用原生圖查詢語言進行的圖上對象的查詢操作 。如neo4j的Cypher，tinkerpop的Gremlin等 。Cypher與Gremlin也是業界使用較多的查詢語言，Cypher是側重于pattern matching的聲明式語言，而Gremlin則是基于groovy的函數式編程語言，強調graph traversal的重要性 。
從零開始學Graph Database：什么是圖

文章插圖
如：
1、gremlin
g.V("李雷").outE('friend').has('age',gt(30)).otherV().where(out('friend').(hasId('李雷'))).limit(100)2、cypher
match (a)-[r1:friend]->(b)-[r2:friend]->(c) where a.mid='李雷' and r1.age>30 and a=c return id(b) limit 100以上兩種寫法等價，只是使用的圖查詢語言有區別 。
圖算法除了明確規則的查詢外，我們也可以利用圖算法對圖進行分析 。畢竟圖中蘊含的信息量遠比表面看上去多，這個時候我們希望通過圖算法揭示圖中更多的信息，如發現節點之間隱含關系，分析節點重要性 ， 對業務場景進行行為預測等 。
下表列出了目前不同類型具有代表性的圖算法：
從零開始學Graph Database：什么是圖

文章插圖
實際的場景中 ， 我們需要同時兼顧算法的效果和執行成本 。這也是很多使用場景所面臨的trade-off問題 。正如我們前面所說，大部分情況下不需要用到非常高深的圖算法，特別是在在線任務中 ， 我們更看重時延和效率 。

推薦閱讀