摘要:本文从零开始引导与大家一起学习图知识 。希望大家可以通过本教程学习如何使用图数据库与图计算引擎 。本篇将以华为云图引擎服务来辅助大家学习如何使用图数据库与图计算引擎 。【从零开始学Graph Database:什么是图】本文分享自华为云社区《从零开始学Graph Database(1)》,作者:弓乙。
基础概念什么是图?首先,我们需要明确图 Graph的概念 。
这里的图,是graph, 是graphical,而不是graphic 。即图处理的是关系问题,而不是图片 。我们解决是关系问题,而非视觉cv问题 。
文章插图
在离散数据中 , 有专门研究图的图论 。包含子图相关,染色,路径,网络流量等问题 。
在计算机科学中 , 我们将图抽象为一种数据结构,即由点,边构成的集合 。我们可以将现实世界的任意一种包含关系的实体用图来抽象概括 。
我们通常把图的问题定义为G=(V,E,φ):
V:是节点的集合E:是边的集合φ: E->{(x,y) | (x,y)∈ V^2 ∪ x≠y }是一个关联函数,它每条边映射到一个有顶点组成的有序对上 。下图是一个使用图来描述的社交网络 。点代表了人,边代表了人和人之间为朋友关系 。在构建了这样一个社交网络以后,我们可以通过使用图查询和算法使得图数据产生价值 。如利用k跳查询,共同邻居,node2vec等来为社交网络中的用户进行好友推荐 。
文章插图
// 好友推荐逻辑试想我们为李雷推荐好友 , 思路是:向他推荐其好友的好友 。但是需要过滤掉本身李雷的好友 。如上图,小明即是李雷的好友,也是李雷好友的好友 。所以在这种情况中,我们不需要再向李雷推荐小明了 。而是推荐 小霞和小刚 。这种稍微有点复杂的推荐思路,可以使用查询语言进行 。以gremlin为例:g.V("李雷").repeat(out("friend").simplePath().where(without('1hop')).store('1hop')).times(2).path().by("name").limit(100)可以使用图做什么?传统上我们使用图来解决一些数学问题 。比如图论起源于著名的柯尼斯堡七桥问题, 该问题被欧拉推广为:怎样判断是否存在着一个恰好包含了所有边,且没有重复的路径 。即一笔画问题 。
文章插图
欧拉证明了以下定理,并解决了一笔画问题:
连通的无向图G有欧拉路径(一笔画)的充要条件是:G中的奇点的数目等于0或2 。(奇点:连接边数为奇数的顶点 。)我们可以用一笔画问题来解决七桥问题,从模型可以看出来,七桥问题中的奇点数目为4个,显然不满足一笔画的充要条件 。故七桥无法在所有桥都只能走一遍的前提下,把这个地方所有的桥都走遍 。
当然了,图并非只能解决这类图论经典问题(如 四色问题,马的遍历问题,邮递员问题, 网络流问题 ),只要能够将研究对象表示为图结构 , 就能利用图的特点来解决问题,甚至大部分情况下,并不需要使用到多么高深的算法 。
查询与算法图查询这里的查询一般指代使用原生图查询语言进行的图上对象的查询操作 。如neo4j的Cypher,tinkerpop的Gremlin等 。Cypher与Gremlin也是业界使用较多的查询语言,Cypher是侧重于pattern matching的声明式语言,而Gremlin则是基于groovy的函数式编程语言,强调graph traversal的重要性 。
文章插图
如:
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以上两种写法等价,只是使用的图查询语言有区别 。
图算法除了明确规则的查询外,我们也可以利用图算法对图进行分析 。毕竟图中蕴含的信息量远比表面看上去多,这个时候我们希望通过图算法揭示图中更多的信息,如发现节点之间隐含关系,分析节点重要性 , 对业务场景进行行为预测等 。
下表列出了目前不同类型具有代表性的图算法:
文章插图
实际的场景中 , 我们需要同时兼顾算法的效果和执行成本 。这也是很多使用场景所面临的trade-off问题 。正如我们前面所说,大部分情况下不需要用到非常高深的图算法,特别是在在线任务中 , 我们更看重时延和效率 。
推荐阅读
- 咸鱼之王龙鱼义从怎么搭配
- 传奇祖玛阁怎么从6层下到5层(传奇怎么从祖玛阁去七层大厅)
- 你比从前快乐歌词 你比以前快乐
- 从SpringBoot启动,阅读源码设计
- 实用帖:从成都到稻城亚丁,最全自驾游攻略
- 从 C# 崩溃异常 中研究页堆布局
- [CG从零开始] 6. 加载一个柴犬模型学习UV贴图
- [CG从零开始] 5. 搞清 MVP 矩阵理论 + 实践
- 华为如何查看手机屏幕厂商_华为如何查看手机屏幕供应商
- 我的荣耀刚开始玩该怎么玩