尽管嬴图的图分析与算法已经支持了近百种经典、常用的图算法,我们仍然可以通过编写UQL来实现其中一些算法的计算效果。当然,这种尝试的前提是所选算法的计算过程,即每一步的计算结果能够设计成合理的数据流并在UQL语句的各个部分之间传递。像Jaccard相似性、全图K邻计算、三角形计算等算法,均可以用UQL来直接实现。
Jaccard相似度是针对图中某两个节点进行计算。Jaccard相似度的定义是两个集合的交集大小除以它们合集的大小,用公式表示则为:
其中,|A|为集合A的大小(元素的个数),|B|为集合B的大小,|A ∩ B|为A、B两集合交集的大小(共同元素的个数)。例如,下图中红、蓝节点的共同邻居数为2,所有邻居数为5,因此这两个节点的Jaccard相似度为2 / 5 = 0.4。
用UQL实现以上计算过程的步骤为:
- 分别查找点A、点B各自的邻居集合;
- 将两个邻居集合转换为两个数组的形式;
- 计算两个数组的长度,即得到|A|与|B|,计算两个数组的交集的长度,即得到|A ∩ B|;
- 按照公式计算出Jaccard相似度的数值。
以上步骤用UQL实现的示例:
以之前红、蓝节点图为例,将以上代码执行过程中所产生的数据流解析如下:
对于针对全图进行计算的算法,如三角形计算,也可以用UQL来实现,代码甚至比上面给出的Jaccard相似度的代码更为简单。按边计算三角形的UQL代码为:
如果需要按点计算三角形,可以对上面的代码进行改造,将三角形的三个点构成三元组以后去重即可: