阿里云：图计算及其应用（2022）（69页）.pdf

1、封面页（此页面将由下图全覆盖，此为编辑稿中的示意，将在终稿 PDF 版中做更新）卷首语 近年来，基于图数据的计算（图计算）得到了学术界和工业界越来越多的关注，被认为是人工智能发展的一个重要方向。本专场围绕图计算系统、应用及前沿学术研究问题，首先介绍阿里巴巴开源的一站式图计算系统 GraphScope 的设计思想、基础能力以及未来发展方向；另外，邀请来自学术界和工业界的大咖，分享图计算最前沿的学术和技术热点；同时，邀请在业务中应用图计算技术的客户，分享图计算在真实业务场景中的应用案例及效果。目录 一、图计算发展的回顾与展望.5 二、GraphScope：人人可用的一站式图计算.15 三、Grap

2、h+Insight 在关联数据中发现商业价值.32 四、小图撬动大图：千亿规模用户群体网络的子图挖掘与应用.48 五、图计算在全域数据融合场景的实践.60 一、图计算发展的回顾与展望 5 一、图计算发展的回顾与展望 摘要：本文整理自上海交通大学安泰经济与管理学院数据与商务智能系讲席教授、数据与商务智能系系主任、欧洲科学院院士、IEEE Fellow 林学民，在云栖大会“图计算及其应用”分论坛的分享。本篇内容主要分为四个部分：1)子图罗列 Subgraph Enumeration 2)内聚子图 Cohesive Subgraphs 3)网络弹性 Network Resilience 4)二分图

3、Bipartite Graph 什么是图？这个图不是我们平时说的图形或者图像，这个图是点和边。点代表事物，边表示他们之间的关系。我们最早知道图是欧拉定理和格尼斯堡七桥问题，然后翻山越岭，经过历史的长河，我们来到了本世纪初的图数据库和大图计算。一、图计算发展的回顾与展望 6 现在各行各业都需要图，比如：Web Graph，Social Network、Protein Interaction Network 等等。下图是一个图的应用场景，左边是各种各样的应用，应用可以分解出基本算子，然后基本算子再分解出最基本算子，所以做系统就要把最基本算子处理好。1.子图罗列 Subgraph Enumerati

4、on 左边 P 是模式图，中间 G 是数据图，通常模式图比较小，可能就是几个点，数据图有可能非常大。下面是从 G 中找到所有和 P 同构的子图实例的三个样例。所以能想象，在实际应用中这种映射有可能会有成千上万，甚至上亿的量。下面来分享一下子图罗列在各行各业中的应用。1)实时周期检测 下图是几年前和阿里合作的实时周期检测项目，主要用于欺诈检测和洗钱检测。一、图计算发展的回顾与展望 7 2)检测指定社区 3)单 CPU 解决方案 一、图计算发展的回顾与展望 8 4)分布式技术 在分布式技术中没有哪一个算法是最好的，需要我们根据数据分布选择适合的算法。2.内聚子图 Cohesive Subgraph

5、s 下图是曾经和阿里合作的一个项目，目的是抓住刷单的水军。这个问题我们是怎么解决的呢？其实就是将问题转化成抓 Bi-Clique 就可以了。所谓的 Clique 就是每两个点之间都有一条边，那么如何把所有的 Clique 或者最大的 Clique 找出来呢？这里就会有一个很大的难点。因为 Clique 和 Clique 之间是可以重叠的，这样就会使数目变得非常大。一、图计算发展的回顾与展望 9 在数据库他们会做各种各样的变种，比如 Quasi-Clique，那么如何定义他们呢？比如 clique 的边数是|v|(|v|)-1，那么 Quasi-Clique 就是|v|(|v|)-1。K-Ple

6、x 在 Clique 里它的度数等于 n-1，那么 K-Plex 每个点的度数就会大于等于 n-k。一、图计算发展的回顾与展望 10 K-clique 是子图中任意两个顶点之间的距离小于等于 k，K-club 同样也是任意两个顶点之间的距离小于等于 k，但是它的两点是指子群中两点的距离。K-Core 是指子图中每个点的度数大于等于 k。这个就比较简单，比如现在这个图里找一度数最小的点，如果度数等于或者大于 k 就 finish 了。小于 k 的，我们就把它除掉，再 update 度数。K-Truss 是 K-Core 的加强版，每条边上三角形的个数要大于等于 k-2。那么为什么说 K-Trus