中心性计算

本篇中前三个 接近中心性 的计算公用 相同的[配置]:

名称 类型 规范 描述
ids []int >0 需要计算的节点 id 列表,不设置表示计算所有节点
limit int >0或-1,必填 需要返回的结果的条数,-1表示返回所有结果

接近中心性(Closeness Centrality)

接近中心性,即指定某个点,在该点所在的连通分量中,计算该点到其它点的最短路径的和的倒数。 1950 年由 Bavelas 发明。

具体公式:

其中 d(x, y) 为该点 x 到其它某点 y 的最短路径的长度。由于此种算法得出的结果数值通常比较小,Ultipa 通过计算最短路径的 “平均值” 的倒数来提升结果的可读性:

具体公式:

由于需要计算全图从点 x 出发的所有最短路径,因此接近中心性将会消耗较多计算资源。Ultipa 在对点数超过10000的图集进行接近中心性计算时进行了采样,采样个数为以10为底的对数log(点数量)

计算节点接近中心性的[命令]为 : algo(closeness)

示例:计算点( id=1,2,3,4 ) 的接近中心性,返回所有结果

algo(closeness).params({ ids: [1,2,3,4], limit: -1 });

点出接近中心性(Out Closeness Centrality)

点出接近中心性,与接近中心性原理类似,计算指定点 到其他点最短路径的平均值的倒数。但最短路径的计算受边方向的影响,只计算由出方向(右向)的边构成的最短路径。

点出接近中心性的[命令]为:algo(out_closeness)

示例:计算点( id=1,2,3,4 ) 的点出接近中心性,返回所有结果

algo(out_closeness).params({ ids: [1,2,3,4], limit: -1 });

点入接近中心性(In Closeness Centrality)

点入接近中心性,计算指定点,到其他点最短路径的平均值的倒数。最短路径的计算中,只计算由入方向(左向)的边构成的最短路径。

点进接近中心性的[命令]为:algo(in_closeness)

示例:计算点( id=1,2,3,4 ) 的点入接近中心性,返回所有结果

algo(in_closeness).params({ ids: [1,2,3,4], limit: -1 });

图中心度(Graph Centrality)

图中心度,即针对某个点,在该点所在的连通分量中,找出该点与其他点的最短路径长度的最大值, 并求该值的倒数。计算的结果能够表示该点是否位于图的最中心。

图中心度的[命令]为:algo(graph_centrality)

图中心度的[配置]:

名称 类型 规范 描述
node_id int >0,必填 需要计算的节点 id

示例:计算 点(id = 12) 的图中心度

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

中介中心性(Betweenness Centrality)

按照 Freeman(1977)的定义,中介中心性是指在某节点 x 所在的连通分量中,首先计算任意两个其它节点之间的所有最短路径中,通过节点 x 的最短路径数量的占比,然后求出这些占比的平均值:

其中 σ 为任意两个其它节点 i 和 j 之间的所有最短路径的数量,σ(x) 为这些最短路径中通过点 x 的路径的数量,(k-1)(k-2)/2 为 i 和 j 的组合数量。

由于需要计算全图经过该点 x 的最短路径数量,因此中介中心性将会消耗较多计算资源。Ultipa在计算中介中心性时进行了采样,采样个数为以10为底的对数log(点数量),因此,计算结果会有波动,图集越大波动越小。

中介中心性的[命令]为:algo(betweenness_centrality)

中介中心性的[配置]:

名称 类型 规范 描述
limit int >0或-1,必填 需要返回的结果的条数,-1表示返回所有结果

示例:计算全图所有点的中介中心性,并返回6条结果:

algo(betweenness_centrality).params({ limit: 6 });