\《******从离线图计算到图数据库和图流计算》****

\背景介绍**

主题	从离线图计算到图数据库和图流计算	时间	2020年11月23日
地点	Bilibili图谱学苑	主讲人	陈文光	主讲人单位	清华大学

\讲座内容**

\1. 将图计算引入传统方法可能无法良好解决的现实问题中，如失联修复（公司丢失客户联系方式，通过相关社交媒体账号找回），恶意网络攻击(基于图计算的恶意网址检测），反信用卡团伙欺诈（通过图计算发现团伙欺诈之间的关联性，利用社区发现算法发现申请间的关联性等）。上述算法本身都不复杂，复杂在图的计算上，本讲座讲述了如何处理这些巨大的图。

\2. 随着Spark成为大数据处理的实际标准，但其在图的处理上是十分低效的，具体体现在计算时间和计算空间上的巨量空耗。为解决此问题，涌现了许多图计算系统，详细介绍了三个并行图计算系统：GridGraph（高效率单机外存图计算系统，处理规模：万亿边），Gemini(分布式内存图计算系统，处理规模：万亿边），shentu(极大规模分布式内存图计算系统，处理规模：数十万亿边）。并介绍了图计算模型的基本模型和原理，如以边为中心的图处理模型，GridGraph的起点终点二维划分，Streaming-apply模式的双滑动窗口，稠密-稀疏双模式的计算模型。

\3. 讲述了对图划分算法的改进，chunk划分保留了局部性，已经局部感知性的chunking，多层次分块划分和任务窃取对负载平衡进行全局调整。也通过搜狗全中文网页有12万亿条边的例子来描述大规模分布式处理的问题。

\4. 图数据库是目前发展的最快的数据库，产品化的图数据库TuGraph通过LDBC SNB测试程序进行测试的效果介绍。最后对是否可以合并图计算和图数据库形成一站式图系统的可能进行探讨。

\个人心得**

通过本次讲座，我系统了解到了图计算和图数据库的的相关知识，加深了从离线图计算到图数据图流计算的理解，对大规模图数据的同化计算有了新的认识，合并图计算与图数据库形成一站式图系统可能是未来一段时间图数据领域发展的重点，数据时代，图数据也发挥着越来越多的作用，可能对于越来越多的现实问题有了新的解决方法，分析节点和链接之间的关系，超大规模图计算的落地也将使大数据时代的复杂数据问题得到应有的解决。

\《******大规模时序图上最短路径查询》****

\背景介绍**

主题	大规模时序图上最短路径查询	时间	2020年11月23日
地点	Bilibili图谱学苑	主讲人	袁野	主讲人单位	北京理工大学计算机学院

\讲座内容**

本次讲座详细介绍了两种时序图模型，并介绍提出了一个更加通用的模型，可以普适性的解决时序图上的最短路径查询问题。袁老师线详细介绍了大图数据背景时序图的应用背景和基本定义，大图数据的计算分类为离线分析和在线查询，梳理了现有的时序图模型，然后从图查询处理帆帆，时序图管理系统等方面介绍了当前大规模时序图最短路径查询的详细研究工作。之后，详细讲解了大规模时序图上带约束的最短路径查询方法研究进展，给出了基于树分解的大图计算模型和相关应用的设计方案。就大图数据跨域计算进行了面向跨越的高效大图计算框架GeoGraph的相关扩展。最后，通过金融风险防控的实例讲解了图务实体经济上大图数据处理的应用。

\个人心得**

最短路径查询作为图论研究的核心问题之一，现实世界中很多问题都能转化为最短路径问题求解。随着网络规模的不断扩张，传统经典的最短路径查询方法已无法满足大规模图的查询需求，本次讲座中，袁野老师通过对两种时序图模型的介绍，接着提出了目前来说更加通用的模型，在涉及大规模时序图上最短路径查询应用时，传统场景中的数据预处理都会被用作来提高查询效率的重要手段。袁老师的大规模图改进于大规模图中近似最短路径查询，又能适用于更广泛的时序图上，作为总结，不仅能为后来研究此方向的人给出新的方向和思路，也能对图论中关于大规模图最短路径问题的快速求解做出新的推进。