共计 4105 个字符，预计需要花费 11 分钟才能阅读完成。
导语
图剖析引擎又称图计算框架，次要用来进行简单图剖析，是一种可能全量数据集运行疾速循环迭代的技术，实用场景包含社区发现、基因序列预测、重要性排名等，典型算法有 PageRank、WCC、BFS、LPA、SSSP。
TuGraph 图数据管理平台社区版已于 2022 年 9 月在 Github 开源，本文将对 TuGraph 图剖析引擎的技术进行分析。
（图 1.1 图剖析引擎）
1 TuGraph 图剖析引擎概览
TuGraph 的图剖析引擎，面向的场景次要是全图 / 全量数据分析类的工作。借助 TuGraph 的 C++ 图剖析引擎 API，用户能够对不同数据起源的图数据疾速导出一个待处理的简单子图，而后在该子图上运行诸如 BFS、PageRank、LPA、WCC 等迭代式图算法，最初依据运行后果做出相应的对策。
在 TuGraph 中，导出和计算过程均能够通过在内存中并行处理的形式进行减速，从而达到近乎实时的解决剖析，和传统办法相比，即防止了数据导出落盘的开销，又能应用紧凑的图数据结构取得计算的现实性能。
依据数据起源及实现不同，可分为 Procedure、Embed 和 Standalone 三种运行模式。其中 Procedure 模式和 Embed 模式的数据源是图存储中加载图数据，别离实用于 Client/Server 部署，以及服务端间接调用，后者多用于调试。
Standalone 模式的数据源是 TXT、二进制、ODPS 文件等内部数据源，可能独立于图数据存储间接运行剖析算法。
TuGraph 图计算零碎社区版内置 6 个根底算法，商业版内置了共 34 种算法。涵盖了图构造、社区发现、门路查问、重要性剖析、模式开掘和关联性剖析的六大类罕用办法，能够满足多种业务场景须要，因而用户简直不须要本人实现具体的图计算过程。
| 算法类型 | 中文算法名 | 英文算法名 | 程序名 |
| 门路查问 | 广度优先搜寻 | Breadth-First Search | bfs |
| 单源最短门路 | Single-Source Shortest Path | sssp | |
| 全对最短门路 | All-Pair Shortest Path | apsp | |
| 多源最短门路 | Multiple-source Shortest Paths | mssp | |
| 两点间最短门路 | Single-Pair Shortest Path | spsp | |
| 重要性剖析 | 网页排序 | Pagerank | pagerank |
| 介数核心度 | Betweenness Centrality | bc | |
| 置信度流传 | Belief Propagation | bp | |
| 间隔核心度 | Closeness Centrality | clce | |
| 个性化网页排序 | Personalized PageRank | ppr | |
| 带权重的网页排序 | Weighted Pagerank Algorithm | wpagerank | |
| 信赖指数排名 | Trustrank | trustrank | |
| sybil 检测算法 | Sybil Rank | sybilrank | |
| 超链接主题搜寻 | Hyperlink-Induced Topic Search | hits | |
| 关联性剖析 | 均匀会聚系数 | Local Clustering Coefficient | lcc |
| 独特街坊 | Common Neighborhood | cn | |
| 度数关联度 | Degree Correlation | dc | |
| 杰卡德系数 | Jaccard Index | ji | |
| 图构造 | 直径预计 | Dimension Estimation | de |
| K 核算法 | K-core | kcore | |
| k 阶团计数算法 | Kcliques | kcliques | |
| k 阶桁架计数算法 | Ktruss | ktruss | |
| 最大独立集算法 | Maximal independent set | mis | |
| 社区发现 | 弱连通重量 | Weakly Connected Components | wcc |
| 标签流传 | Label Propagation Algorithm | lpa | |
| EgoNet 算法 | EgoNet | en | |
| 鲁汶社区发现 | Louvain | louvain | |
| 强连通重量 | Strongly Connected Components | scc | |
| 监听标签流传 | Speaker-listener Label Propagation Algorithm | slpa | |
| 莱顿算法 | Leiden | leiden | |
| 带权重的标签流传 | Weighted Label Propagation Algorithm | wlpa | |
| 模式开掘 | 三角计数 | Triangle Counting | triangle |
| 子图匹配算法 | Subgraph Isomorphism | subgraph_isomorphism | |
| 模式匹配算法 | Motif | motif |
表 1.1 TuGraph 内置算法
2 性能介绍
2.1 图剖析框架
图剖析框架作为图剖析引擎的“骨架”，能够联结多种模块无效的耦合协同工作。个别分为预处理、算法过程、后果剖析三个阶段。
预处理局部用于读入数据及参数进行图构建及相干信息的存储统计，并整顿出算法过程所需的参数及数据。
算法过程会依据失去的数据通过特定的算法进行逻辑计算，并失去后果数据。
后果剖析局部依据失去的后果数据进行个性化解决（如取最值等），并将重要的信息写回和打印输出操作。
2.2 点边筛选器
点边筛选器作用于图剖析引擎中的 Procedure 和 Embed 模式。对于图存储数据源可依据用户须要和理论业务场景对图数据进行筛查，抉择无效的点边进行图构造的构建。
2.3 一致性快照
TuGraph 中的 Procedure 和 Embed 模式可能提供数据“快照”，即建设一个对指定数据集的齐全可用拷贝，该拷贝包含相应数据在某个工夫点（拷贝开始的工夫点）的镜像。因为 OLAP 的操作仅波及读操作而不波及写操作，OlapOnDB 会以一种更紧凑的形式对数据进行排布，在节俭空间的同时，进步数据拜访的局部性。
2.4 块状读写模块
块状读写模块作用于图剖析引擎中的 Standalone 模式，用于对不同内部数据源的数据进行高效读入，同时也蕴含对外部算法解决后的图数据后果写回。
2.5 参数模块
参数模块作用于剖析引擎中的 Standalone 模式，用于对图的个别信息（如数据起源，算法名称，数据输出、输入门路，顶点个数等）以及依据不同数据起源、不同算法所配置的不同信息参数进行承受和整顿，传输给图算法及各个模块，同时将最终后果模块化展现。
3 应用示例
由前文所述可知，图剖析引擎分为 Standalone、Embed 和 Procedure 模式，当初以 bfs 算法为例别离介绍他们的应用形式。
3.1 Procedure 模式
Procedure 模式次要用于 Client/Sever 的 TuGraph 运行时，图算法的加载和调用。
在 TuGraph/plugins 目录下执行 bash make_so.sh bfs 即可在 TuGraph/plugins 目录下的到 bfs.so 文件，将该文件以插件模式上传至 TuGraph-web，输出参数后即可执行。
示例：
在 TuGraph/plugins 编译.so 算法文件
bash make_so.sh bfs
将 bfs.so 文件以插件模式加载至 TuGraph-web 后，输出如下 json 参数：
即可失去返回后果。
输入内容解释：
- num_edges: 示意该图数据的边数量
- num_vertices: 示意该图数据顶点的数量
- prepare_cost: 示意预处理阶段所须要的工夫。预处理阶段的工作：加载参数、图数据加载、索引初始化等。
- core_cost: 示意算法运行所须要的工夫。
- found_vertices: 示意查找到顶点的个数。
- output_cost: 示意算法后果写回 db 所须要的工夫。
- total_cost: 示意执行该算法整体运行工夫。
3.2 Embed 模式
该种形式次要用于 TuGraph 在后台程序中对预加载的图存储数据进行算法剖析，多用于疾速调试。在 TuGraph/plugins 目录下对 embed_main.cpp 文件欠缺，补充数据名称、输出参数、数据门路等信息，示例如下：
保留后在 TuGraph/plugins 目录下执行 bash make_so.sh bfs 即可在 TuGraph/plugins/cpp 目录下的到 bfs_procedure 文件，bash make_embed.sh bfs
在 TuGraph/plugins 文件夹下执行./cpp/bfs_procedure 即可失去返回后果。
3.3 Standalone 模式
Standalone 模式能够独立于图存储运行，间接从文本文件或 ODPS 读取 Edgelist 模式的图数据。在 TuGraph/build 目录下执行 make bfs_standalone 即可失去 bfs_standalone 文件, 该文件生成与 TuGraph/build/output/algo 文件夹下。运行：在 TuGraph/build 目录下执行./output/algo/bfs_standalone -–type [type] –-input_dir [input_dir] -–vertices [vertices] –root [root] –-output_dir [output_dir]
- [type]：示意输出图文件的类型起源，蕴含 text 文本文件、BINARY_FILE 二进制文件和 ODPS 源。
- [input_dir]：示意输出图文件的文件夹门路，文件夹下可蕴含一个或多个输出文件。TuGraph 在读取输出文件时会读取 [input_dir] 下的所有文件，要求 [input_dir] 下只能蕴含输出文件，不能蕴含其它文件。参数不可省略。
- [vertices]：示意图的顶点个数，为 0 时示意用户心愿零碎自动识别顶点数量；为非零值时示意用户心愿自定义顶点个数，要求用户自定义顶点个数需大于最大的顶点 ID。参数可省略，默认值为 0。
- [root]：示意进行 bfs 的起始顶点 id。参数不可省略。
- [output_dir]：示意输入数据保留的文件夹门路，将输入内容保留至该文件中，参数不可省略。
示例：在 TuGraph/build 编译 standalone 算法程序
在 TuGraph/build/output 目录下运行 text 源文件
失去运行后果：
后果参数解释同上。
4 小结
综上，图剖析引擎能够高效、疾速的解决多种起源的数据，其并行的图构建形式保障了内存占用小的特点。此外，图剖析引擎也具备易于装置部署、灵活性高、耦合水平低、易于上手等对用户敌对个性，能够帮忙用户联合具体业务解决问题。
拜访 GitHub：
https://github.com/TuGraph-db
