GSQL 图数据库算法库

图数据库的算法是一系列的函数，用于计算图，图内顶点及其相互关系的指标和特征。它可以从内部揭示出某个图中的各个实体之间的角色及其关联关系。例如：某个顶点的位置有多靠中间？这个顶点对其他顶点的影响力有多大？某些图算法会计算或识别全局特征：例如某个图中的自然社群的分组是什么？图中关联之间的密度是多少？

GSQL 图数据库算法库使用方法

GSQL图算法库包含了一系列性能卓越的GSQL查询。每个查询都可以实现某种标准的图算法。每种算法都可以作为一个独立的查询使用，也可作为某个更大的分析应用程序中的模块被调用。

TigerGraph平台上GSQL查询语句特别适用于图数据库的算法，原因在于它：

图灵完备：完全支持命令式编程和程序式编程，是算法运算的理想选择；
可并行和分布式处理：可在大型图上进行计算；
用户可自行扩充代码：由于算法基于GSQL规范编写并由用户自行编译，因此可以非常容易地修改和定制；
开源：用户可以通过示例学习不同的GSQL实现，并且也可将自行开发的代码提交到算法库中；

GSQL 图数据库算法库架构

用户可以从github下载该算法库 https://github.com/tigergraph/ecosys/tree/master/graph_algorithms

该算法库包含两个部分：算法和测试。算法（Algorithms）文件夹中包含了算法的模板和脚本，可帮助用户编写自定义代码并将其安装。测试（Tests）文件夹中包含了可用于验证算法的小型示例图形。我们在本文中也会使用这些示例图形来演示每种算法的预期输出结果。由于这些图型都很小，所以用户也可以手动计算结果，用于与算法输出结果进行对比。

安装一个算法查询

请记住，GSQL的图形算法本质上是GSQL查询。由于我们不知道用户到底要分析哪些顶点或边，也不知道用户希望如何输出结果，因此我们提供的算法都是算法的模板。用户需要运行脚本将其自定义为自己的版本，然后安装它们。

1、在Algorithms文件夹中有一个脚本，文件名为install.sh。当用户运行该脚本时，它将首先询问调用哪个图数据库纲目（schema）；

（TigerGraph平台支持多个图形并发运行）

2、然后它会要求用户从一系列可用的算法中选择一种；

3、在确认了图数据库纲目和对应算法之后，安装程序会为用户推荐合适的顶点类型和边缘类型。不过请注意，并不是图形中的所有顶点类型或边缘类型都必须选择。例如，用户可能拥有一个包含三类人群和五种关系类型的社交关系图形，但他可能决定只使用Member顶点和Guest顶点以及 Recommended边来计算“页面排名”（PageRank）；

4、随后，基于算法的不同输出形式，用户可以选择三种不同格式的输出结果：

以JSON格式流式输出，这是大多数GSQL查询的默认输出；
将输出值保存到CSV文件中。对于某些算法，可通过在查询命令中添加某个参数来实现文件输出，并允许用户设定输出结果的数量上限；
将输出存储为顶点或边的属性值。这些属性必须已存在于数据库纲目中，且安装程序将询问用户使用哪些属性

5、在查询创建完毕后，安装程序将返回初始菜单，用户可以继续选择新的算法

（即返回步骤2）；

6、当用户退出菜单时，安装程序会询问：是否要安装查询？安装这个动作一般发生在代码编译并绑定到查询引擎的时候。这通常需要几分钟时间。所以，推荐用户一次性创建完所有的自定义查询，然后将它们作为一个组（group）来安装

示例:

$ bash install.sh 
*** GSQL Graph Algorithm Installer ***
Available graphs:
  - Graph social(Person:v, Friend:e, Also_Friend:e, Coworker:e)
Graph name? social

Please enter the number of the algorithm to install:
1) EXIT
2) Closeness Centrality
3) Connected Components
4) Label Propagation
5) Community detection: Louvain
6) PageRank
7) Shortest Path, Single-Source, Any Weight
8) Triangle Counting(minimal memory)
9) Triangle Counting(fast, more memory)
#? 6
  pageRank() works on directed edges

Available vertex and edge types:
  - VERTEX Person(PRIMARY_ID id STRING, name STRING, score FLOAT, tag STRING) WITH STATS="OUTDEGREE_BY_EDGETYPE"
  - DIRECTED EDGE Friend(FROM Person, TO Person, weight FLOAT, tag STRING) WITH REVERSE_EDGE="Also_Friend"
  - DIRECTED EDGE Also_Friend(FROM Person, TO Person, weight FLOAT, tag STRING) WITH REVERSE_EDGE="Friend"
  - UNDIRECTED EDGE Coworker(FROM Person, TO Person, weight FLOAT, tag STRING)

Please enter the vertex type(s) and edge type(s) for running PageRank.
   Use commas to separate multiple types [ex: type1, type2]
   Leaving this blank will select all available types

Vertex types: Person
Edge types: Friend
The query pageRank is dropped.
The query pageRank_file is dropped.
The query pageRank_attr is dropped.

gsql -g social ./templates/pageRank.gsql
The query pageRank has been added!

gsql -g social ./templates/pageRank_file.gsql
The query pageRank_file has been added!

If your graph schema has appropriate vertex or edge attributes,
 you can update the graph with your results.
Do you want to update the graph [yn]? y
Vertex attribute to store FLOAT result (e.g. pageRank): score
gsql -g social ./templates/pageRank_attr.gsql
The query pageRank_attr has been added!
Created the following algorithms:
  - pageRank(float maxChange, int maxIter, float damping, bool display, int outputLimit) 
  - pageRank_attr(float maxChange, int maxIter, float damping, bool display) 
  - pageRank_file(float maxChange, int maxIter, float damping, bool display, file f) 


Please enter the number of the algorithm to install:
1) EXIT
2) Closeness Centrality
3) Connected Components
4) Label Propagation
5) Community detection: Louvain
6) PageRank
7) Shortest Path, Single-Source, Any Weight
8) Triangle Counting(minimal memory)
9) Triangle Counting(fast, more memory)
#? 1
Exiting
Algorithm files have been created. Do want to install them now [yn]? y
Start installing queries, about 1 minute ...
c
pageRank query: curl -X GET 'http://127.0.0.1:9000/query/social/pageRank?maxChange=VALUE&maxIter=VALUE&damping=VALUE&display=VALUE&outputLimit=VALUE'. Add -H "Authorization: Bearer TOKEN" if authentication is enabled.
pageRank_file query: curl -X GET 'http://127.0.0.1:9000/query/social/pageRank_file?maxChange=VALUE&maxIter=VALUE&damping=VALUE&display=VALUE&f=VALUE'. Add -H "Authorization: Bearer TOKEN" if authentication is enabled.
pageRank_attr query: curl -X GET 'http://127.0.0.1:9000/query/social/pageRank_attr?maxChange=VALUE&maxIter=VALUE&damping=VALUE&display=VALUE'. Add -H "Authorization: Bearer TOKEN" if authentication is enabled.

[======================================================================================================] 100% (3/3) 
$

当某个算法查询被安装完成后，你可以看到它们和其他GSQL查询列在一起。

GSQL > ls
...
Queries:
 - cc_subquery(vertex v, int numVert, int maxHops) (installed v2)
 - closeness_cent(bool display, int outputLimit) (installed v2)
 - closeness_cent_attr(bool display) (installed v2)
 - closeness_cent_file(bool display, file f) (installed v2)
 - conn_comp() (installed v2)
 - conn_comp_attr() (installed v2)
 - conn_comp_file(file f) (installed v2)
 - label_prop(int maxIter) (installed v2)
 - label_prop_attr(int maxIter) (installed v2)
 - label_prop_file(int maxIter, file f) (installed v2)
 - louvain() (installed v2)
 - louvain_attr() (installed v2)
 - louvain_file(file f) (installed v2)
 - pageRank(float maxChange, int maxIter, float damping, bool display, int outputLimit) (installed v2)
 - pageRank_attr(float maxChange, int maxIter, float damping, bool display) (installed v2)
 - pageRank_file(float maxChange, int maxIter, float damping, bool display, file f) (installed v2)
 - tri_count() (installed v2)
 - tri_count_fast() (installed v2)

不久之后我们将更新算法库，使得大多数数据库纲目的选择可以在算法查询运行的时候执行，从而避免在安装算法时就需要做选择。

运行一个算法查询

运行算法查询与运行GSQL查询的动作是相同的。例如，如果用户为页面排名算法选择了JSON格式输出，则它在GSQL里的命令如下：

GSQL > RUN QUERY pageRank(0.001, 25, 0.85, 10)

查询安装的同时还会创建一个REST端点。因此同样的查询也可以写成：

curl -X GET 'http://127.0.0.1:9000/query/alg_graph/pageRank?maxChange=0.001&maxIter=25&damping=0.85&outputSize=10'

GSQL允许用户从一个查询中调用另一个查询。这意味着用户可以将算法作为另一个更复杂的分析应用的模块。

算法库总览

目前可用算法分为三类：

路径（Path）
中心度（Centrality）
群体度（Community）

此外，每种算法都可能适用于/不适用于无向边（Undirected Edges）、有向边（Directed Edges）及带有权重赋值的边（Weighted Edges）。

“即将上线”表示该算法的实现形式即将由TigerGraph发布
“n/a”表示该算法一般不会被使用

算法

英文全称

分类

无向边

有向边

权重赋值的边

单起点最短路径

Single-Source Shortest Path

路径

适用

全顶点对最短路径

All Pairs Shortest Path

路径

适用

页面排名

PageRank

中心度

n/a

适用

即将上线

接近中心度

Closeness Centrality

中心度

适用

n/a

即将上线

中介中心度

Betweenness Centrality

中心度

即将上线

n/a

即将上线

弱连通组件

Weakly Connected Components

群体度

适用

n/a

强连通组件

Strongly Connected Components

群体度

n/a

即将上线

n/a

标签传播

Label Propagation

群体度

适用

n/a

鲁汶算法

Louvain Modularity

群体度

适用

n/a

三角计数

Triangle Counting

群体度

适用

n/a

计算的复杂度

计算复杂度是一个数学术语。它指在某种算法下，由于不同数据量或其他关键参数的值而导致的计算所需要时间的长短程度。对于图数据库来说，这样的关键参数有两个：

V（或n），顶点数目
E（或m），边数目

例如符号O（V ^ 2）表示当V变大时，计算所需要的时间与V 的平方成正比。

路径搜寻的算法

这些算法帮助用户找到最短路径或评估某条路径的可行性或质量。

单起点最短路径算法（Single-Source Shortest Path），无权重

该算法从图形中的某一个源顶点出发，并找到通往每个可能的目标顶点的最短路径，且路径未赋予权重值。也就是说，它总共可以找到n个路径。

如果用户只想知道某两个特定顶点S和T之间的最短无权重路径，可以参阅《GSQL演示案例》（GSQL Demo Examples）。

如果图形中包含带有权重的边，请参阅下一个算法。

算法简述和使用

如果某个图形包含未加权的边，则找到从一个顶点到另一个顶点的最短路径与找到最少跳路径的方法等价。六度分离理论和朋友的朋友理论都是基于这样的算法。未加权最短路径算法能够回答“你们两个如何关联起来？”的问题。并且这两个顶点实体可以不是人。最短路径算法在大量应用中都有广泛运用，例如用于估计事件影响，评估知识传播的方法，或者调查犯罪。

当图形未加权时，我们可以使用”贪婪算法”（greedy approach）来找到最短路径。在计算机科学中，贪婪算法根据当下正在等待选择的选项做出中间选择，然后再也不重新考虑这些选择。在这种情况下，一旦算法找到了通往顶点T的任何路径，就可以确定这条是最短路径。

格式定义

shortest_ss(VERTEX v, INT maxDepth, BOOL display)
shortest_ss_file(VERTEX v, INT maxDepth, BOOL display,STRING filepath)
shortest_ss_attr(VERTEX v, INT maxDepth, BOOL display)

特征

描述

输出结果

计算从顶点v到每个顶点T的最短距离（整数值）和最短路径（字符串值）

输出结果有三种形式：

• JSON格式流输出

• 写入一个表格类文件

• 保存为两个顶点属性值

输入参数

• v: 起始顶点的id

• maxDepth: 不搜索长度比maxDepth更大的路径。

如果maxDepth小于零则对搜索没有限制。

• display: 如果为true，则JSON输出包含图形的边，从而显示整个图形

• filepath (仅适用于文件输出): 输出文件的保存路径

结果大小

V = 顶点的数目

计算复杂度

O(E), E = 边的数目

图形类型

有向边，无向边，无权重边

示例

即将发布

单起点最短路径算法（Single-Source Shortest Path）, 含权重

算法简述和使用

在包含加权边的图形中查找最短路径在算法比在未加权图形中更难，因为仅仅找到了通往顶点T的路径，并不能确定它就是最短路径。如果权重总是正的，那么你必须继续尝试，直到遍历完包含所有T的入射边的路径为止。而如果权重可以是负数，那么它就更加困难了。用户必须考虑所有可能的路径。

带权重的最短路径算法最常见的应用方式，就是寻找从A地到B地的最短路径。（比如说GPS导航的路径规划）。普遍地来说，任何寻找更优路线的努力都可能应用了该算法。

格式定义

shortest_path_any_wt(VERTEX v, INT maxDepth, BOOL display)
shortest_path_any_wt_file(VERTEX v, INT maxDepth, BOOL display, STRING filepath)
shortest_path_any_wt_attr(VERTEX v, INT maxDepth, BOOL display)

特征

描述

输出结果

计算从顶点v到每个顶点T的最短距离（整数值）和最短路径（字符串值）

输出结果有三种形式：

• JSON格式流输出

• 写入一个表格类文件

• 保存为两个顶点属性值

输入参数

• v: 起始顶点的id

• maxDepth: 不搜索长度比maxDepth更大的路径。

如果maxDepth小于零则对搜索没有限制。

• display: 如果为true，则JSON输出包含图形的边，从而显示整个图形

• filepath (仅适用于文件输出): 输出文件的保存路径

结果大小

V = 顶点数目

计算复杂度

O(V*E), V = 顶点数目, E = 边数目

图形类型

有向边，无向边，有权重边

shortest_path_wt查询基于贝尔曼-福特（Bellman-Ford）算法。如果有多条路径拥有相同的总权重，则算法只返回其中一条。

示例

下图中的边即包含正权重和也包含负权重。从顶点A出发，得到从A到E的最短加权路径是A-D-C-B-E，累积得分为7-3-2-4 = -2。

单顶点对最短路径算法（Single-Pair Shortest Path）

单顶点对最短路径算法用于找到从顶点S和顶点T的最短路径。如果边缘为无权重边，则请参阅《GSQL演示案例》（GSQL Demo Examples）。

如果边是加权的，则请使用单起点最短路径算法。在最坏的情况下，找到某个单顶点对的最短路径所花费的时间等于找到从某个顶点S出发的所有顶点对的最短路径所花费的时间。原因在于，用户无法确定当前找到的路径是否为最短（最小权重）路径，除非遍历完整个图形。不过，如果权重均为正值，则存在一种更有效的算法。即当用户在每条目标顶点T的入射边上都找到对应路径之后，用户便可以停止搜索。

全顶点对最短路径算法（All-Pairs Shortest Path）

全顶点对最短路径算法对于大规模图形来说十分耗时，因为该算法的计算时间是O(V^3)并且输出结果大小是O(V^2)。所以，在大型图形上运行此操作时请务必谨慎。

全顶点对最短路径算法（APSP）会为整个图形上的所有顶点对计算最短路径。从原理上来说，该操作可以通过对每个顶点使用单起点最短路径算法（SSSP）来实现，例如，

CREATE QUERY all_pairs_shortest(
 Start = {Node.*};
 Start = SELECT s FROM Start:s
       POST-ACCUM
         shortest_ss_any_wt_file(s, -1, false, "/home/tigergraph/alg/apsp"+s)
  ;
}

该示例展现了GSQL的一个优势：查询可以被储存为一个步骤。其它查询动作可直接调用该步骤。

然而，对于大型图形来说（即包含百万级别或更多的顶点数的图形），该运算将会是一项极其艰巨的任务。虽然TigerGraph平台的大规模并行处理能力可以将该计算速度提高10倍甚至100倍，但如何报告和储存输出结果也会是一个头疼的问题。假设某个图形有100万个顶点，则该运算将会产生近1万亿个输出值。

当然，也有一些方法比n次简单调用单起点最短路径算法更加有效，例如弗洛伊德算法（Floyd-Warshall Algorithm），用其计算APSP将花费O(V^3)的时间。

我们的建议：

如果图形规模小（顶点数目在千级别或万级别）时，APSP算法较为适用。
如果图形规模庞大，请避免适用APSP算法。

衡量中心度（Centrality）的算法

中心度算法的目标是为了确定网络中某个顶点对于总体的重要性。

典型应用如下：

页面排名算法（PageRank）专为有向边设计。过去，这种算法是为了通过网页上的超链接找到最”重要”的页面，但现在它同样可以适用于其他类型的网络。这些网络中，节点之间会正向推介后跳转。

接近中心度算法（Closeness Centrality）和中介中心度算法（Betweenness Centrality）都可以用来解释“位置有多靠中心？”这样的问题。

页面排名算法（PageRank）

算法简述和使用

页面排名算法测量每个顶点对于每个其他顶点的影响力。该影响力是递归方式定义的：一个顶点的影响力是基于引用它的其他顶点的影响力。如果（1）引用某个顶点的其他顶点越多（2）或引用该顶点的其他顶点具有更高的影响力，则该顶点的影响力更大。它和个人在社交网络中的社会影响力大小是类似的。

解释PageRank值的常用方法是借助随机网络冲浪模型（Random Network Surfer model）。某个顶点的pageRank分数与随机浏览者在任何给定时间正好访问该顶点的概率成正比。即pageRank分数越高，则该顶点越经常被访问。上述结论的前提是，假设浏览者根据以下方式随机地访问顶点：

假设浏览者在网络中按照网络拓扑一个节点一个节点地访问并跳转节点，并重复许多轮次。
浏览者可以从任意起点开始其浏览动作。这个“任意起点”的特性是页面排名算法的魔力之一，这意味着PageRank分数成为了该图形结构本身的基础属性。
每个轮次中，浏览者在当前顶点上可能的出发路径中随机选择一条，并重复该随机选择动作许多轮次。
但同时，浏览者并不总是遵循网络的顺序浏览。存在一种可能（确切地说是一阻尼（1-damping）），浏览者将忽略网络节点顺序，而神奇地跳转到某个随机的顶点。

格式定义

pageRank(FLOAT maxChange, INT maxIter, FLOAT damping, BOOL display, INT maxOutput)
pageRank_file(FLOAT maxChange, INT maxIter, FLOAT damping, BOOL display, STRING filepath)
pageRank_attr(FLOAT maxChange, INT maxIter, FLOAT damping, BOOL display)

特征

描述

输出结果

计算每一个节点的PageRank 值 (FLOAT类型)

输出结果有三种形式：

• JSON格式流输出

• 写入一个表格类文件

• 保存为两个顶点属性值

输入参数

• maxChange: 当顶点的当前分数与之前的分数的差距最大值小于等于maxChange时，算法迭代停止。

它意味着，分数变化趋于稳定，迭代之间的变化小于maxChange值。

建议将该值设定为0.001或更小。

• maxIter: 最大迭代次数，建议值：10~100。

• damping: 当前顶点分数和相邻顶点分数的比值。

每个顶点都有一个最低值即1-damping。建议值：0.85•

• display: 如果为true，则JSON输出包含图形的边，从而显示整个图形

• filepath (仅适用于文件输出): 输出文件的保存路径

• outputLimit (仅适用于JSON格式输出): 输出的顶点值的最大数目。

顶点值中的最大值会优先保存。

结果大小

V = 顶点数目

计算复杂度

O(E*k), E = 边的数目, k = 迭代次数

迭代次数基于数据量。但用户也可以设定最大值。

并行计算能够减少计算时间。

图形类型

有向边

示例

我们在test10图形（使用Friend边）上运行页面排名算法，其中包含以下参数值：damping = 0.85，maxChange = 0.001，maxIter = 25。从图中我们可以看到顶点Ivy（最下方）的pageRank得分最高（1.12）。这是有道理的，因为有3个相邻顶点指向顶点Ivy，比其他的任何顶点都要多。同时，顶点Eddie和顶点Justin的得分恰好为1，这是因为它们不向外射出任何边。这是为了演示算法而特别设计出来的。同样，顶点Alex的得分为0.15，即（1-damping），因为没有边射向Alex。

接近中心度算法（Closeness Centrality）

在生活中我们总是会提到某人的家、办公室或者店铺“靠近市中心”；接近中心度算法可以帮助我们精确地衡量它到底“多靠中心”。下面列出了计算顶点v中心度的步骤：

步骤描述

数学公式

1. 计算从顶点v到其他每个顶点距离的平均值。

$d{avg}(v) = \sum{u \ne v} dist(v,u)/(n-1)$

2. 取平均值的倒数，得到v的平均临近值。

$CC(v) = 1/d_{avg}(v)CC(v)=1/davg(v)$

对图中每个顶点重复上述动作

格式定义

closeness_cent(BOOL display, INT maxOutput)
closeness_cent_file(BOOL display, STRING filepath)
closeness_cent_attr(BOOL display)

特征

描述

输出结果

对每个顶点计算接近中心度值（浮点数格式），输出结果可以有以下三种格式：

• JSON格式流输出

• 写入一个表格类文件

• 保存为两个顶点属性值

输入参数

display: 如果为true，则JSON输出包含图形的边，从而显示整个图形

filepath: (仅适用于文件输出): 输出文件的保存路径

maxOutput: (仅适用于JSON文件格式输出): 输出顶点值的最大数目。

按照倒叙排列。

结果大小

V = 顶点数目

计算复杂度

O(E*k), E = 边的数目, k = 迭代次数

迭代次数基于数据量。但用户也可以设定最大值。并行计算能够减少计算时间。

图形类型

有向边，无向边，无权重边

示例

无论是有向边（即从顶点v到其他顶点的边）还是无向边。都可以计算它们的接近中心度值。然而，有向图可能看起来比无向图复杂一些。假设从顶点Alex到顶点Bob的值为1，并不代表从Bob到Alex的值也为1。

在我们的示例中，我们想要使用Likes图，但又要包含无向边。所以我们通过使用Friend边和Also_Friend边（两者互为反向）来模拟无向图型。

衡量群体度（Community）的算法

群体度算法用于评估一个网络结构中个体组合或分裂的程度，同时也能够得到网络的组织程度正在加强或削弱的趋势。

连通分量算法（Connected Components）

算法简述和使用

一个“分量”（Component）是指互相连通的一组顶点和边的最大范围。也就是说，在分量内，我们可以从一个顶点到达任何另一个顶点。例如在下面的示例中，共有三个分量。

该算法是为无向边设计的。但如果将其应用于有向边（即每个顶点都可以到达其他任何一个顶点），则该组件称为强连通分量（Strongly Connected Component）。若虽为有向边，但忽略其方向（允许在任一方向上的遍历），则算法找到的是弱连同分量（Weakly Connected Components）。

格式定义

conn_comp()
conn_comp_file(STRING filepath)
conn_comp_attr()

特征

描述

输出结果

对每个顶点赋值一个分量ID（component id）（整数值），同一个分量中的顶点的组件号相同。

输出结果可以有以下三种格式：

• JSON格式流输出

• 写入一个表格类文件

• 保存为两个顶点属性值

输入参数

filepath (仅适用于文件输出): 输出文件的保存路径

结果大小

V = 顶点数目

计算复杂度

O(E*d), E = 边的数目, d = 分量直径的最大值

图形类型

无向边

示例

在示例中，很容易可以看出，算法将正确顶点分组。

Alex，Bob和Justin都拥有相同的社区ID = 2097152
Chase，Damon和Eddie都拥有相同的社区ID = 5242880
Fiona，George，Howard和Ivy都拥有相同的社区ID = 0

该算法使用TigerGraph引擎内部使用的顶点ID; 所以它们具体的值无法预知。

标签传播算法（Label Propagation）

算法简述和使用

标签传播算法是一种启发性算法，用于确定社群（Community）。该算法的逻辑很简单：如果某个顶点的大多数相邻顶点都带有社群标签X，那么它也应该将自己标记为X的成员。该算法从每一个顶点开始运行，且每个顶点最初都有自己的唯一标签。然后，我们基于上述逻辑不停地更新标签。而且关键点在于更新标签的顺序是随机的。该算法因其高效和易用而备受青睐，但它不能保证每次都产生相同的结果。

在改良版本中，我们可以在最初就将一组顶点划归某个社群。这样，如果这些顶点彼此联系紧密，它们会倾向于保留自己的社群标签，并同时影响周边的顶点。

格式定义

label_prop(INT maxIter)
label_prop_file(INT maxIter, FILE filepath)
label_prop_attr(INT maxIter)

特征

描述

输出结果

对每个顶点赋值一个分量ID（component id）（整数值），同一个分量中的顶点的组件号相同。

输出结果可以有以下三种格式：

• JSON格式流输出

• 写入一个表格类文件

• 保存为两个顶点属性值

输入参数

• maxIter: 最大迭代次数.

• filepath (仅适用于文件输出): 输出文件的保存路径•

结果大小

V = 顶点数量

计算复杂度

O(E*k), E = 边的数量, k =迭代次数

图形类型

无向边

示例

该图与在连通分量算法的示例中使用的图相同，但结果不同。Fiona，George，Howard和Ivy这四人被分为两组，且两两对称：

（George和Ivy）每个人都与（Fiona和Howard）相连。
（Fiona和Howard）每个人都与（George和Ivy）相连，但彼此不相连。

标签传播算法尝试在连接分量中查找自然形成的组合部分与分离部分。也就是说，它着眼于连接的质量和方式。连通分量算法关心是或否的问题：即“这两个顶点是否连通？”的问题

我们将maxIter设置为10，但算法在三次迭代后便能够达到稳定的状态。

基于鲁汶算法（Louvain Modularity）的社区发现

算法简述和使用

在一个图中，某个小分区的模块度分数（modularity score）用于评估分区内和分区间链路密度的差异。通常情况下，一个优秀的分区方法将会使得分区内部的密度值高于分区与分区之间。

此外，我们还可以通过模块度分数来优化分区方法。也就是说，我们可以先按照计划分区并测量其模块度。随后，我们对分区方式进行改进并通过模块度的增加来确认改进的确有效。

计算模块度最为有效的方法是由鲁汶大学的一群研究人员设计的，该方法被称为鲁汶算法，它使用了凝聚和分层优化的理念：

优化小型局部社群的模块度。
将每个优化过的局部社群视为个体，并对这些个体的组合重复优化操作。

格式定义

louvain()
louvain_file(FILE filepath)
louvain_attr()

特征

描述

输出结果

对每个顶点赋值一个分量ID（component id）（整数值），同一个分量中的顶点的组件号相同。

输出结果可以有以下三种格式：

• JSON格式流输出

• 写入一个表格类文件

• 保存为两个顶点属性值

输入参数

filepath (仅适用于文件输出): 输出文件的保存路径

结果大小

V = 顶点数目

计算复杂度

O(V log V), V = 顶点数目

图形类型

无向边

示例

本算法的结果与在便签传播算法示例中的结果相同。这并不奇怪，因为它们具有相同的最终目标：即在图中找到自然形成的社群。不过，如果图形更大，更复杂的话，则两者的结果可能会有一定差异。

三角计数算法（Triangle Counting）

算法简述和使用

为什么要计量三角形呢？我们通过一个社交网络的例子来解释：

如果A认识B也认识C，那么如果B也认识C，则我们就可以画出一个三角关系图。如果在一个社群中，若这种情况越常见，则表明该社群中的交互越频繁。
每个关系三角实际上是就是一个最小规模的多边”完整子图”，其中每个顶点都与其他所有顶点相连。

三角形的数量（即密度）是可用于度量一个社群的群体度和连通度。尤其它解决了传递关系的问题：即“如果A点可以通向B点，而B点可以通向C点，那么A点可以通向C的可能性是多少？”这样的问题。

请注意，该算法计算的是一个数字：即此图形中共有多少个三角形。而不是图形中社群的数量。

一般情况下，我们不在有向图中计算三角形数量，尽管它也是可以计算的。如果你选择这样做，那你必须明确方向的意义：在有向图中，如果存在A - > B和B - > C，那么

如果A - > C，我们有一个”捷径”。
如果C - > A，那么我们有一个反馈循环（feedback loop）

格式定义

共有两种不同的算法来计算三角形个数。第一个是tri_count()，即经典的边迭代（edge-iterator）算法。对于每个边缘及其两个端点顶点S和T，计算S的相邻顶点和T的相邻顶点的重叠部分。

tri_count()
tri_count_file(FILE filepath)
tri_count_attr()

边迭代算法比较简单，但它的一个缺陷在于它会计算三角形的三条边。所以最终计数也需要除以3，且这意味着我们的工作量比之后要介绍的算法多3倍。 tri_count_fast()是一种效率更好的算法，它会两次经过同一条边。第一次经过时，我们标记两个端点顶点中的哪一个的相邻顶点较少。在第二次经过时，我们仅计算标记过的顶点中重合的部分。它可以帮助我们减少1/3的邻域匹配工作量（减少了最慢的那1/3的工作量），而代价仅仅是一部分额外的内存消耗。

tri_count_fast()
tri_count_fast_file(FILE filepath)
tri_count_fast_attr()

特征

描述

输出结果

返回图形中的三角形数量

输入参数

无

结果大小

一个整数

计算复杂度

O(V * E), V = 顶点数目, E = 边的数目

图形类型

无向边

示例

{
  "error": false,
  "message": "",
  "version": {
    "schema": 0,
    "api": "v2"
  },
  "results": [
    {"num_triangles": 4}
  ]
}

衡量相似度（Similarity）的算法

衡量两点之间相似程度的方法有很多，但它们都能总结为三个类别：（1）要么比较两点的自身属性，（2）要么比较两点各自的关联关系，（3）要么是前两种方法的混合体。本章中，我们将使用一个叫做电影（movie）的图来演示我们的相似度算法。

邻点的余弦相似度算法（Cosine Similarity），单起点

算法简述和使用

两点间余弦相似度的计算方法为：首先，将这两个点的各自属性定义为一个向量。（举个例子：一个Person点的属性向量可能包含多个元素，例如年龄、身高、体重等）；然后，将这两个向量代入余弦函数进行计算。

向量A与向量B的余弦相似度被定义为：

$cos(A,B)=\frac{A\cdot B}{||A||\cdot ||B||} = \frac{\sum_iA_i B_i}{\sqrt{\sum_iA^2_i}\sqrt{\sum_iB^2_i}}$

若A和B完全相同，则cos(A, B)的结果等于1。事实上，余弦相似度与Person点之间的相关系数紧密相关。

对于该函数来说，属性向量是这两点以及它们与各自邻点间的一系列边权重的组合。

在Movie图中有两个点类——Person点和Movie点。每个Person都可能会给某些Movie打分。所打的分数会作为权重值保存在两者之间的Like边上。例如在下图中，观众Alex给名叫“Free Solo”的电影打了10分。

格式定义

cosine_nbor_ss(VERTEX source, INT topK)
cosine_nbor_ss_file(VERTEX source, INT topK, FILE filepath)
cosine_nbor_ss_attr(VERTEX source)

特征

描述

输出结果

相似度打分最高的K个点，以及它们的相似度分数

输出结果有三种形式：

JSON格式流输出
写入一个表格类文件
保存为两个顶点属性值

输入参数

source: 初始起点
topK: 结果个数
filepath: (仅适用于文件输出): 输出文件的保存路径

结果大小

topK

计算复杂度

O(D^2), D = 点v的外部度数（outdegree）

图形类型

有向边，无向边，有权重边

输出结果的个数永远是K（如果K<=N），因此如果存相同的相似度分数的话，算法可能会在相同分数的点对中任意选择。

示例

首先，我们先确定一个目标点（即某个人）且此人给某组电影打过分数。然后我们使用余弦相似度算法，计算出给同样电影打过分数的其他人与此人的相似度分数：

还是前面那个例子：这次我们假设起始点为Alex，topK参数设为5；然后我们计算他与Jing以及Kevin之间的余弦相似度。在JSON格式的结果中，相似度最高的k个点以及它们各自的相似度分数从高到低依次显示出来。虽然我们限制最多输出5个点，但这次的结果中只有2个点符合条件。

[
  {
    "@@result_topk": [
      {
        "vertex1": "Alex",
        "vertex2": "Jing",
        "score": 0.42173
      },
      {
        "vertex1": "Alex",
        "vertex2": "Kevin",
        "score": 0.14248
      }
    ]
  }
]

然而，如果选择通过文件格式输出，则结果并不会按照从大到小排列。文件内容会显示为：

Vertex1,Vertex2,Similarity
Alex,Kevin,0.142484
Alex,Jing,0.421731

若选择通过属性值输出，则系统会自动插入一条边（前提是相似度分数大于零），并且将相似度分数作为该边的属性；结果如下：

邻点的余弦相似度算法（Cosine Similarity），All Pairs

算法简述和使用

该算法的计算过程与单起点余弦相似度算法(即cosine_nbor_ss)相同，区别在于它会对图中所有的点对（或用户选中的点类和边类）进行计算。所以通常来说这样的计算会需要花费更长的时间。如果图特别大或者深度特别深，则执行该运算将可能不是一个好的选择。

格式定义

cosine_nbor_ap(INT topK)
cosine_nbor_ap_file(INT topK, FILE filepath)
cosine_nbor_ap_attr(INT topK)

特征

描述

输出结果

相似度打分最高的K个点，以及它们的相似度分数

输出结果有三种形式：

JSON格式流输出
写入一个表格类文件
保存为两个顶点属性值

输入参数

topK: 输出点对的数量
filepath: (仅适用于文件输出): 输出文件的保存路径

结果大小

topK

计算复杂度

O(E^2 / V), V = 点的个数, E = 边的个数

图形类型

有向边，无向边，有权重边

示例

在movie图上执行全体点对的余弦相似度计算，并找到相似度打分最高的5个点对：cosine_nbor_ap(5)；以下为结果的JSON格式输出：

[
  {
    "@@total_result": [
      {
        "vertex1": "Kat",
        "vertex2": "Neol",
        "score": 0.67509
      },
      {
        "vertex1": "Jing",
        "vertex2": "Neol",
        "score": 0.46377
      },
      {
        "vertex1": "Kevin",
        "vertex2": "Neol",
        "score": 0.42436
      },
      {
        "vertex1": "Jing",
        "vertex2": "Alex",
        "score": 0.42173
      },
      {
        "vertex1": "Kat",
        "vertex2": "Kevin",
        "score": 0.3526
      }
    ]
  }
]

文件格式的输出结果与cosine_nbor_file的结果类似。

属性值输出的结果将创建k条边：

邻点的杰卡德相似度算法（Jaccard Similarity），单起点

算法简述和使用

杰卡德指数（Jaccard index）用于评估两组数据的重合程度。如果要计算两个点的杰卡德相似度，需要首先对每一个点选取一系列的值；例如，对于一个Person选取的值，可以是他居住的城市。随后，便可以针对这两个值进行杰卡德相似度计算。

A和B的杰卡德指数定义如下：

$Jaccard(A,B)=\frac{|A \cap B|}{|A \cup B|}$

结果的范围在0到1之间。如果A和B完全相同，则Jaccard(A, B)的结果为1。如果A和B都为空，则结果为0。

格式定义

当前定义如下：

jaccard_nbor_ss(VERTEX source, INT topK)
jaccard_nbor_ss_file(VERTEX source, INT topK, FILE filepath)
jaccard_nbor_ss_attr(VERTEX source, INT topK)

特征

描述

输出结果

相似度打分最高的K个点，以及它们的相似度分数

输出结果有三种形式：

格式流输出
写入一个表格类文件
保存为两个顶点属性值

输入参数

source:初始起点
topK: 结果个数
filepath: (仅适用于文件输出): 输出文件的保存路径

结果大小

topK

计算复杂度

O(D^2), D = 点v的外部度数（outdegree）

图形类型

有向边，无向边，无权重边

输出结果的个数永远不会超过是K个，因此如果存相同的相似度分数的话，算法可能会在相同分数的点对中任意选择。

示例

在movie图上，我们执行计算：jaccard_nbor_ss("Neol", 5)：

[
  {
    "@@result_topK": [
      {
        "vertex1": "Neol",
        "vertex2": "Kat",
        "score": 0.5
      },
      {
        "vertex1": "Neol",
        "vertex2": "Kevin",
        "score": 0.4
      },
      {
        "vertex1": "Neol",
        "vertex2": "Jing",
        "score": 0.2
      }
    ]
  }
]

如果起始点Person没有和其他任何Person拥有共同的Movie邻点（例如本例中的Elena），则计算结果为空集：

[
  {
    "@@result_topK": []
  }
]

邻点的杰卡德相似度算法（Jaccard Similarity），All Pairs

算法简述和使用

本算法的计算过程与杰卡德单起点相似度算法（即jaccard_nbor_ss）相同，区别在于本算法会对图内的所有点（或用户选择的点类或边类）进行杰卡德相似度计算。所以通常来说这样的计算会需要花费更长的时间。如果图特别大或者深度特别深，则执行该运算将可能不是一个好的选择。

格式定义

jaccard_nbor_ap(INT topK)
jaccard_nbor_ap_file(INT topK, FILE filepath)
jaccard_nbor_ap_attr(INT topK)

特征

描述

输出结果

相似度打分最高的K个点，以及它们的相似度分数

输出结果有三种形式：

JSON格式流输出
写入一个表格类文件
保存为两个顶点属性值

输入参数

topK: 点的个数
filepath: (仅适用于文件输出): 输出文件的保存路径

结果大小

topK

计算复杂度

O(E^2 / V), V = 点的个数, E = 边的个数

图形类型

有向边，无向边，有权重边

输出结果的个数永远不会超过是K个，因此如果存相同的相似度分数的话，算法可能会在相同分数的点对中任意选择。

示例

在Movie图上，执行杰卡德全体点对相似度运算并找到相似度打分前五名的点对：jaccard_nbor_ap(5)；以下为JSON格式的结果输出：

[
  {
    "@@total_result": [
      {
        "vertex1": "Kat",
        "vertex2": "Neol",
        "score": 0.5
      },
      {
        "vertex1": "Kevin",
        "vertex2": "Neol",
        "score": 0.4
      },
      {
        "vertex1": "Jing",
        "vertex2": "Alex",
        "score": 0.25
      },
      {
        "vertex1": "Kat",
        "vertex2": "Kevin",
        "score": 0.25
      },
      {
        "vertex1": "Jing",
        "vertex2": "Neol",
        "score": 0.2
      }
    ]
  }
]

PreviousTigerGraph 版本比较 Next版本发布, 功能变更

Last updated 5 years ago