修改密码

请输入密码
请输入密码 请输入8-64长度密码 和 email 地址不相同 至少包括数字、大写字母、小写字母、半角符号中的 3 个
请输入密码
提交

修改昵称

当前昵称:
提交

申请证书

证书详情

Please complete this required field.

  • Ultipa Graph V4

Standalone

Please complete this required field.

Please complete this required field.

服务器的MAC地址

Please complete this required field.

Please complete this required field.

取消
申请
ID
产品
状态
核数
申请天数
审批时间
过期时间
MAC地址
申请理由
审核信息
关闭
基础信息
  • 用户昵称:
  • 手机号:
  • 公司名称:
  • 公司邮箱:
  • 地区:
  • 语言:
修改密码
申请证书

当前未申请证书.

申请证书
Certificate Issued at Valid until Serial No. File
Serial No. Valid until File

Not having one? Apply now! >>>

ProductName CreateTime ID Price File
ProductName CreateTime ID Price File

No Invoice

搜索
    中文

      调和中心性

      概述

      调和中心性(Harmonic Centrality)算法是接近中心性算法的变种。接近中心性衡量的是节点在其连通分量中到其它各点的平均最短距离,显然在不连通图中就无法体现节点在全图的中心性;调和中心性提出的“平均最短距离”则是对这些最短距离的倒数求和,这使它可以处理非连通图中会出现的无限值。调和中心性算法首先是由 M. Marchiori 和 V. Latora 于 2000 年提出的,然后由 A. Dekker 和 Y. Rochat 分别于 2005 年和 2009 年提出。

      调和中心性的取值范围是 [0,1],数值越大中心性越大。

      算法的相关资料如下:

      基本概念

      最短距离

      最短距离是指两个点之间的最短路径的边数。具体可参看章节《接近中心性》。

      调和平均数

      调和平均数(Harmonic Mean)是平均数的一种,与算术平均数不同,它是变量倒数的算术平均数的倒数,所以又称为倒数平均数。算数平均数 A 和调和平均数 H 的计算公式如下:

      调和平均数应用的经典案例是以不同的速度通过相同的距离。假设有一个往返行程,去程速度为 30 km/h,回程速度为 10 km/h,整个行程的平均速度是多少?

      也许有人不假思索地使用算数平均数计算 A = (30+10)/2 = 20 km/h,但这个结果不太合理。由于去程速度快,行驶时间少,而回程行驶时间多,整个行程大部分时间的速度是 10 km/h,因而平均速度应该更接近于 10 km/h。

      假设单程距离为 1,考虑行驶时间而计算的平均值为 2/(1/30+1/10) = 15 km/h,这就是调和平均数,这才是真正的平均速度,它根据每段距离所花费的时间进行了调整。

      调和中心性

      节点的调和中心性定义为该点到图中其他所有点的最短距离的调和平均数的倒数:

      其中,i 为待计算节点,j 为图中除 i 以外的所有节点,n-1j 的个数,d(i,j)ij 的最短距离,当 ij 之间没有边相连时,d(i,j) = +∞,则有 1/d(i,j) = 0

      计算上图点 a 的调和中心性为 (1 + 1/2 + 1/+∞ + 1/+∞) / 4 = 0.375,点 d 的调和中心性为 (1/+∞ + 1/+∞ + 1/+∞ + 1) / 4 = 0.25

      由于需要计算全图从某个点出发的所有最短路径,调和中心性算法会消耗较多的计算资源。在进行调和中心性的计算时,可对点的数量大于 10,000 的图集进行采样计算,建议采样个数为以 10 为底的对数 log(点数量);可通过配置项决定是否采样。

      特殊处理

      孤点、不连通图

      节点的调和中心性是考虑了全图节点——包括孤点与不同连通分量内的节点——的结果。

      自环边

      调和中心性计算的是节点之间的最短距离,自环边不构成最短路径,因此不参与计算。

      有向边

      在不规定边的方向时计算调和中心性,边的方向将被忽略。此时图中的所有节点都参与计算。

      结果和统计值

      以下面包含 8 个节点的图为例,针对所有节点运行调和中心性算法:

      算法结果:忽略边的方向,计算每个点的调和中心性,根据算法执行方式,返回 _idcentrality 两列或 _uuidcentrality 两列

      _uuid _id centrality
      1 LA 0.5714286
      2 LB 0.4285714
      3 LC 0.4285714
      4 LD 0.3571429
      5 LE 0.3571429
      6 LF 0.1428571
      7 LG 0.1428571
      8 LH 0.0000000

      算法统计值:

      命令和参数配置

      • 命令:algo(harmonic_centrality)
      • params() 参数配置项如下:
      名称
      类型
      默认值
      规范
      描述
      ids 或 uuids []_id 或 []_uuid / / 待计算节点的 ID 或 UUID,指定点后 sample_size 设置无效;忽略表示计算全部点,此时 sample_size 设置有效
      direction string / in/out,大小写不敏感 路径中边的方向;忽略表示忽略方向
      sample_size int -1 -1,-2 或 (0,节点总数] 随机采样的点个数,-1 表示采样 log(<全图点数量>) 个点进行计算,-2 或忽略表示不采样,用所有点进行精确计算
      limit int -1 >=-1 需要返回的结果条数,-1 或忽略表示返回所有结果
      order string / ASC 或 DESC,大小写不敏感 对返回结果进行排序,忽略表示不排序

      示例:计算点 UUID = 1,2,3,4 的调和中心性

      algo(harmonic_centrality).params({ 
        uuids: [1,2,3,4]
      }).stream() as centrality
      return centrality
      

      示例:采样计算全图点的出方向调和中心性,返回 5 条结果

      algo(harmonic_centrality).params({ 
        limit: 5, 
        direction: "out",
        sample_size: -1 
      }) as out
      return out
      

      算法执行

      任务回写

      1. 文件回写

      配置项 各列数据
      filename _id,centrality

      示例:计算所有点的调和中心性,将算法结果回写至名为 centrality 的文件

      algo(harmonic_centrality).params().write({
        file:{ 
          filename: "centrality"
        }
      })
      

      2. 属性回写

      配置项 回写内容 类型 数据类型
      property centrality 点属性 float

      示例:计算所有点的调和中心性,将调和中心性回写至名为 hc 的点属性

      algo(harmonic_centrality).params().write({
        db:{ 
          property: "hc"
        }
      })
      

      3. 统计回写

      算法无统计值。

      直接返回

      别名序号 类型 描述 列名
      0 []perNode 点及其调和中心性 _uuid, centrality

      示例:计算所有点的调和中心性,将算法结果定义为别名 results 并返回中心性最大的三个结果

      algo(harmonic_centrality).params({
        order: "desc",
        limit: 3
      }) as results
      return results
      

      流式返回

      别名序号 类型 描述 列名
      0 []perNode 点及其调和中心性 _uuid, centrality

      示例:计算所有点的调和中心性,将算法结果定义为别名 results,返回中心性为 0 的结果

      algo(harmonic_centrality).params().stream() as results
      where results.centrality == 0
      return results
      

      实时统计

      算法无统计值。

      请完成以下信息后可下载此书
      *
      公司名称不能为空
      *
      公司邮箱必须填写
      *
      你的名字必须填写
      *
      你的电话必须填写
      *
      你的电话必须填写