复杂图算法

图平均距离估算(hyperANF)

图平均距离为图中所有的节点对之间的最短距离的平均值。采用hyperANF方法得出的是这一值的近似值,而非精确值。通常,当算法的迭代次数小于图中节点对的最短距离的最大值时,迭代次数越大计算结果越精确;迭代次数超过该最大值时,精度不随迭代次数变化。

图平均距离的理论值计算公式为:

hyperANF, 全称:Approximating the Neighbourhood Function of Very Large Graphs on a Budget,超大规模图最短邻居长度近似计算. 由意大利米兰大学信息科学系的 Paolo Boldi, Marco Rosa ,Sebastiano Vigna 于 2011 年提出。

图平均距离的[命令]为:algo(hyperANF)

图平均距离的[配置]为:

名称 类型 规范 描述
loop_num int >0,必填 迭代次数
register_num int [4, 30],必填 用HyperLogLog计算基数时所用到的幂运算的指数

k 最近邻(kNN)

邻近算法,或者说 K 最近邻(kNN,k-NearestNeighbor) ,通过计算得到图中和一个点最相似(例如 cosine 相似)的 k 个点, 并由这 k 个点的某个属性值得出该点的这一属性值。选取属性值出现次数最多的值作为该点的属性值:

上式中,K 为与该点 x 最相似的 k 个点的集合。如果出现次数最多的属性值有多个,则选取它们对应的点中和当前点最相似的点的属性值。算法返回该属性值和出现的次数,以及每个近邻的相似度。

针对 cosine 相似度的内容,请参阅后面的 cosine 相似度算法。

k 最近邻算法的 [命令] 为:algo(knn)

k 最近邻算法的 [配置] 为:

名称 类型 规范 描述
node_id int 必填 需要计算属性值的点
node_property_names []string 必填 参与相似度计算的属性名列表,至少填写两个属性,属性类型为数值
top_k int >0,必填 选取多少个相似节点进行属性计算
target_property_name string 必填 需要计算的目标属性名

示例,通过 点( id = 12 ) 的属性 age 和 grade ,来推算 属性 salary 的值

algo(knn).params({
  node_id: 12,
  node_property_names: ["age", "grade"],
  top: 10,
  target_property_name: "salary"
});

核心度 (k-core)

计算核心度不小于k的最大子图,即在该子图中所有节点的度均大于等于k。该算法是一个迭代剪枝过程,每次剪枝后重新计算剩余点的度,作为下一轮剪枝的依据,直至没有节点满足剪枝条件为止。

该算法返回 k-core 子图中的所有节点。k-core 可以作为图中紧密连通群组的识别标准。

运行 k-core 的[命令]为:algo(k_core)

运行 k-core 的[配置]为:

名称 类型 规范 描述
k int / 核心度 K

最小生成树(MST)

全称 Minimum Spanning Tree,即使用权重和最小的边连通图中所有节点的极小连通子图。一张图的极小连通子图可能有多个解,该算法从某一指定点出发,计算并返回一种解中的所有边。

对于不连通图,要遍历出完整的MST需要给图中每个连通分量都指定起点。算法从第一个起点开始,在当前连通分量中充分生成MST之后,再到下一起点,继续生成MST,直到所有起点都计算完毕。如果有多个起点属于同一连通分量,则仅最先被计算的起点有效;图中的孤点也无效。

注:对于连通图,其MST中包含的边数 等于图的节点数-1,即对于任意一张图,其MST中包含的边数 加上 连通分量个数 加上 孤点数 等于图的节点数。

最小生成树的 [命令] 为:algo(mst)

最小生成树的 [配置] 为:

名称 类型 规范 描述
ids []int >0,必填 起点的id,可为多个连通分量输入多个起点,后出现的重复连通分量的起点无效,孤点无效
edge_property_name string /,必填 作为权重的边属性的名称,属性类型为数值
limit int >0; -1 ,必填 需要返回的结果的条数,-1表示返回所有结果

示例,从点 id=[1,5,12] 出发,使用边的属性 distance 作为权重来生成最小生成树,即用真实场景中的 “最短距离” 连接所有点:

algo(mst).params({ ids: [1,5,12], edge_property_name: "distance", limit: -1 });

K 均值 (k-Means)

将所有点分成 k 类,使每个点到自己所属分类的质心(几何中心)的距离小于该点到其它分类的质心的距离。其中,距离最短的评判标准分为两种,1)欧几里得距离;2)cosine 相似度。

K 均值法是一种迭代算法,每次迭代都会根据当前质心对所有点进行分类,根据分类结果重新计算各类的质心;如果本次迭代后得到的新的质心和上一次相比,误差符合预设的精度要求,则迭代结束。如果达到了迭代次数限制也会结束。

使用欧几里得距离时,节点选择最近质心的计算公式如下,其中 d 为每个质心 m 到当前节点 x 的欧几里得距离,选择这些距离中最小值对应的质心为当前节点 x 的质心:

使用 cosine 相似度时,节点选择最近质心的计算公式如下,其中 s 为每个质心 m 到当前节点 x 的cosine 相似度,选择这些相似度中最大值对应的质心为当前节点 x 的质心:

注:初始质心的选择会影响最终分类结果;如果有多个初始质心的属性值相同,则仅其中一个质心有效,其余的质心会产生空集。

K 均值的 [命令] 为:algo(k_means)

K 均值的 [配置] 为:

名称 类型 规范 描述
k int > 0, 必填 分为 k 类
start_ids []int \ , 必填 指定 k 个节点作为起始分类的质心,属性值重复的质心会使其所代表的分类结果为空
node_property_names []string \ , 必填 参与距离计算的属性名,属性类型为数值,采用欧几里得距离时至少填一个属性,采用Cosine相似度时至少填两个属性
distance_type int 1|2, 必填 距离计算方法
1: 欧几里得距离
2:Cosine相似度
loop_num int > 0 , 必填 迭代次数,建议不要过大

示例:将全图通过 cosine 相似度 ,依据属性 age 和 salary 分为 3 类,以[1,2,6]为起始质心。执行 5 轮。

algo(k_means).params({
  k: 3,
  start_ids: [1,2,6],
  node_property_names: ["age", "salary"],
  distance_type: 2,
  loop_num: 5
});

局部聚集系数(Clustering Coefficient)

局部聚集系数,即一个点的所有邻居中,有边相连的邻居的对数,除以所有邻居的对数。

其中,E 代表点 x 的 某对邻居 i 和 j 之间的边的非空集合,分子为 E 的个数,k 为 点 x 的邻居数量,分母为 点 x 的邻居对数。显然,这一结果的范围在 0 到 1 之间。

在社交关系网中,局部聚集系数体现一个人的朋友之间彼此认识的程度,可以帮助区分社交群体类型,如果亲友、社团、代理等。

局部聚类系数的 [命令] 为:algo(clustering_coefficient)

局部聚类系数的 [配置] 为:

名称 类型 规范 描述
node_id int > 0,必填 node ID

示例:计算 node (id=12)的局部聚类系数

algo(clustering_coefficient).params({ node_id: 12 });

在 Ultipa-Manager 中计算局部聚类系数的结果如图所示: