修改密码

请输入密码
请输入密码 请输入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

v5.0
搜索
    v5.0

      调和中心性

      HDC

      概述

      调和中心性(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,这就是调和平均数,它根据每段距离所花费的时间进行了调整。

      调和中心性

      在本算法中,节点的调和中心性分值等于该点与其他各节点的最短距离调和平均值的倒数。计算公式为:

      其中,x为待计算的目标节点,y为图中除 x以外的所有节点,k-1y的个数,d(x,y)xy的最短距离,当xy不连通时,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

      调和中心性算法会消耗很多计算资源。在一个有V个节点的图中,建议当V>10000 时通过采样进行近似计算,推荐的采样个数是节点数以10为底的对数(log(V))。

      每次执行算法时,只进行一次采样,每个节点的中心性分值是基于该节点到所有样本节点的最短距离计算的。

      特殊说明

      • 孤点的调和中心性分值为0。

      示例图集

      创建示例图集:

      // 在空图集中逐行运行以下语句
      create().node_schema("user").edge_schema("vote")
      create().edge_property(@vote, "score", uint32)
      insert().into(@user).nodes([{_id:"A"},{_id:"B"},{_id:"C"},{_id:"D"},{_id:"E"},{_id:"F"},{_id:"G"},{_id:"H"}])
      insert().into(@vote).edges([{_from:"A", _to:"B", score:2}, {_from:"A", _to:"E", score:3}, {_from:"B", _to:"B", score:4}, {_from:"B", _to:"C", score:2}, {_from:"C", _to:"A", score:3}, {_from:"D", _to:"A", score:1}, {_from:"F", _to:"G", score:1}])
      

      创建HDC图集

      将当前图集全部加载到HDC服务器hdc-server-1上,并命名为 hdc_hc

      CALL hdc.graph.create("hdc-server-1", "hdc_hc", {
        nodes: {"*": ["*"]},
        edges: {"*": ["*"]},
        direction: "undirected",
        load_id: true,
        update: "static",
        query: "query",
        default: false
      })
      

      hdc.graph.create("hdc_hc", {
        nodes: {"*": ["*"]},
        edges: {"*": ["*"]},
        direction: "undirected",
        load_id: true,
        update: "static",
        query: "query",
        default: false
      }).to("hdc-server-1")
      

      参数

      算法名:harmonic_centrality

      参数名
      类型
      规范
      默认值
      可选
      描述
      ids []_id / / 通过_id指定参与计算的点;若未设置则计算所有点
      uuids []_uuid / / 通过_uuid指定参与计算的点;若未设置则计算所有点
      direction String in, out / 指定最短路径中所有边的方向,in表示仅包含入边,out表示仅包含出边
      edge_schema_property []"<@schema.?><property>" / / 作为权重的数值类型边属性,权重值为所有指定属性值的总和;不包含指定属性的边将被忽略
      impl_type String dijkstra, delta_stepping, spfa, beta beta 指定由算法DijkstraDelta-SteppingSPFA或嬴图默认最短路径算法beta计算的加权最短路径。仅当使用edge_schema_property时生效
      sample_size Integer -1, -2, [1, |V|] -2 指定采样策略;设置为-1时,采样log(|V|)个点;设置为[1, |V|]区间内的一个数字,采样指定数量的点(|V|是图中总点数);设置为-2时,不进行采样。该选项仅当所有点参与计算时生效
      return_id_uuid String uuid, id, both uuid 在结果中使用_uuid_id或同时使用两者来表示点
      limit Integer ≥-1 -1 限制返回的结果数;-1返回所有结果
      order String asc, desc / 根据harmonic_centrality分值对结果排序

      文件回写

      CALL algo.harmonic_centrality.write("hdc_hc", {
        params: {
          return_id_uuid: "id",
          order: "desc"
        },
        return_params: {
          file: {
            filename: "harmonic"
          }
        }
      })
      

      algo(harmonic_centrality).params({
        projection: "hdc_hc",
        return_id_uuid: "id",
        order: "desc"
      }).write({
        file: {
          filename: "harmonic"
        }
      })
      

      结果:

      _id,harmonic_centrality
      A,0.571429
      B,0.428571
      C,0.428571
      D,0.357143
      E,0.357143
      F,0.142857
      G,0.142857
      H,0
      

      数据库回写

      将结果中的harmonic_centrality值写入指定点属性。该属性类型为float

      CALL algo.harmonic_centrality.write("hdc_hc", {
        params: {},
        return_params: {
          db: {
            property: 'hc'
          }
        }
      })
      

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

      完整返回

      CALL algo.harmonic_centrality("hdc_hc", {
        params: {
          return_id_uuid: "id",
          ids: ["A", "B"],
          edge_schema_property: "score"
        },
        return_params: {}
      }) YIELD hc
      RETURN hc
      

      exec{
        algo(harmonic_centrality).params({
          return_id_uuid: "id",
          ids: ["A", "B"],
          edge_schema_property: "score"
        }) as hc
        return hc
      } on hdc_hc
      

      结果:

      _id harmonic_centrality
      A 0.309523
      B 0.219048

      流式返回

      CALL algo.harmonic_centrality("hdc_hc", {
        params: {
          direction: "in",
          return_id_uuid: "id"
        },
        return_params: {
        	stream: {}
        }
      }) YIELD hc
      FILTER hc.harmonic_centrality = 0
      RETURN hc
      

      exec{
        algo(harmonic_centrality).params({
          direction: "in",
          return_id_uuid: "id"
        }).stream() as hc
        where hc.harmonic_centrality == 0
        return hc
      } on hdc_hc
      

      结果:

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