内置算法

GraphScope的图分析引擎(GAE)提供了许多内置算法，使用户能够以最小的努力分析其图数据。这些内置算法涵盖了广泛的应用场景，如最短路径、社区检测、聚类等。这些内置算法采用PIE编程模型实现，并经过高度优化以获得最佳性能，用户可以开箱即用地使用它们。

以下是支持的内置算法完整列表：

全对最短路径长度

该算法用于从给定的加权图中求解所有顶点对之间的最短路径问题。运行此算法后，它将计算出图中任一顶点到所有其他顶点的最小距离。

all_pairs_shortest_path_length()

计算图中所有顶点之间的最短路径长度。

属性同配性

图中的同配性指的是顶点倾向于与其他相似顶点而非不相似顶点相连的特性。属性同配性衡量的是具有相同属性的顶点相互连接的程度。

attribute_assortativity()

计算顶点属性的同配性。

平均度连通性

平均度连接性是指度数为k的顶点的平均最近邻度数。该算法返回图中连续k=0,1,2...时的k-平均度连接性列表。

average_degree_connectivity(source_degree_type, target_degree_type)

计算图的平均度连通性。

Parameters:

  • source_degree_type (str) – 对源顶点使用"入度"、"出度"或"入度+出度"

  • target_degree_type (str) – 使用"in"(入度)、"out"(出度)或"in+out"(入度+出度)作为目标顶点的度数类型

中介中心性

中介中心性是基于最短路径的图中中心性度量指标。顶点v的中介中心性是指所有顶点对最短路径中经过v的路径所占比例的总和。

betweenness_centrality(normalized, endpoints)

计算顶点间最短路径的介数中心性。

Parameters:

  • normalized (bool) – 结果是否应进行归一化处理

  • endpoints (bool) – 是否在最短路径计数中包含端点

CDLP

使用标签传播算法(LPA)评估社区检测。 参见 LPA

cdlp(max_round=10)

使用标签传播评估社区检测

Parameters:

max_round (int) – 最大轮数，默认为10

接近中心性

顶点v的原始接近中心性是其到所有n-1个可达节点的平均最短路径距离的倒数。Wasserman和Faust针对具有多个连通分量的图提出了改进公式。该结果是"从可达节点出发，组内可达参与者比例与平均距离之比"。

closeness_centrality(wf)

计算顶点的接近中心性。

Parameters:

wf (bool) – 是否使用Wasserman和Faust改进后的公式

聚类

聚类算法用于计算图中每个顶点的聚类系数。图中某个顶点的聚类系数量化了其邻居节点接近形成一个团（完全图）的程度。

clustering()

计算图中每个顶点的聚类系数。

度同配系数

与属性同配性类似，度同配系数衡量的是存在边(u,v)的倾向性，其中度(u)等于度(v)。

degree_assortativity_coefficient(source_degree_type, target_degree_type, weighted)

计算图的度同配系数。

Parameters:

  • source_degree_type (str) – 对源顶点使用"入度"、"出度"或"入度+出度"

  • target_degree_type (str) – 使用"in"（入度）、"out"（出度）或"in+out"（总度数）作为目标顶点的度数类型

  • weight (bool) – 表示权重的边属性数值。如果为False，则每条边的权重默认为1。顶点的度等于其相邻边权重的总和。

度中心性

顶点v的度中心性是指与其相连的节点所占的比例。如果是有向图，则定义了三种独立的度中心性度量，分别是入度、出度以及入度和出度。

degree_centrality(centrality_type)

计算顶点的度中心性。

Parameters:

centrality_type (str) – 应用in、out或both度

特征向量中心性

特征向量中心性用于衡量图中顶点的影响力。来自高分顶点的关系对顶点得分的贡献大于来自低分顶点的连接。高特征向量得分意味着一个顶点与许多自身也具有高得分的顶点相连。

eigenvector_centrality(tolerance, max_round)

计算该图的特征向量中心性。

Parameters:

  • tolerance (double) – 用于检查收敛性的误差容限

  • max_round (int) – 最大迭代次数

Katz中心性

Katz centrality通过测量直接邻居（一度顶点）的数量以及图中通过这些直接邻居连接到所考虑顶点的所有其他顶点，来计算顶点在图中的相对影响力。

katz_centrality(alpha, beta, tolerance, max_round, normalized)

计算图中各顶点的Katz中心性。

Parameters:

  • alpha (double) – 衰减因子

  • beta (double) – 赋予直接邻域的权重

  • tolerance (double) – 用于检查收敛性的误差容限

  • max_round (int) – 最大迭代次数

  • normalized (bool) - 是否需要对结果值进行归一化处理

K-核

该算法用于从原始图中寻找k-core，k-core是指包含度数为k或更高顶点的最大子图。通过递归修剪度数小于k的顶点来找到k-core。

kkore(k)

计算图的k核。

Parameters:

k (int) – 核心的阶数

K-Shell

k壳层是由核心数为k的顶点导出的子图。也就是说，k核中不属于(k+1)核的顶点。

kshell(k)

计算图的k-shell。

Parameters:

k (int) – 壳层的阶数

标签传播算法

标签传播算法（LPA）是一种用于在图中快速发现社区的算法。该算法通过在图结构中传播标签的方式，以迭代过程为未标记顶点分配标签。

lpa(max_round)

计算图中每个顶点的标签。

Parameters:

max_round (int) – 计算过程中的迭代次数

LCC

LCC旨在计算局部聚类系数，遵循LDBC的规范

lcc()

计算图中每个顶点的局部聚类系数。

PageRank

PageRank是一种衡量图中各顶点重要性的方法。PageRank算法存在多种变体，GAE中的PageRank遵循NetworkX的PageRank实现。

pagerank(alpha, max_round, tolerance)

计算图中每个顶点的PageRank值。

Parameters:

  • alpha (double) – PageRank算法的阻尼参数

  • max_round (int) – 最大迭代次数

  • tolerance (double) – 用于检查收敛性的误差容限

采样路径

该算法从根顶点开始，按照路径长度采样一组路径。

sampling_path(source_id, cutoff)

计算从根顶点出发的一组路径。

Parameters:

  • source_id (int) – 路径采样的源顶点

  • cutoff (int) - 路径的最大长度

单源最短路径

单源最短路径(SSSP)算法将一个顶点固定为"源"顶点，并计算从该源点到图中所有其他顶点的最短路径。

sssp(source)

计算图中从源顶点出发的最短路径。

Parameters:

source (int) – 最短路径的源顶点

VoteRank

VoteRank是一种基于投票方案来衡量图中顶点排名的算法。通过VoteRank，所有顶点会为其每个入邻居投票，并迭代选出得票数最高的顶点。

voterank(num_of_nodes)

使用VoteRank算法选择图中具有影响力的顶点列表。

Parameters:

num_of_nodes (int) – 要提取的排名顶点数量

WCC

计算弱连通分量

wcc()

计算图中的弱连通分量。