修改密码

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

搜索
    中文

      中介中心性

      概述

      中介中心性(Betweenness Centrality)用来衡量点处于其它任意两点间最短路径之中的概率。该概念由 Linton C. Freeman 于 1977 年提出,能有效地计算出在图的多个部分间起重要桥梁、媒介作用的点。

      中介中心性的取值范围是 [0,1],数值越大中介作用越强。

      相关资料如下:

      基本概念

      中介概率

      本算法中的中介是指一个点通过最短路径到达另一个点时途经的各点。

      上图中红、绿节点间的最短路径经过了蓝、黄两个节点,蓝、黄节点均为其中介点。

      中介概率是指某点在某个节点对的所有最短路径中出现的概率。

      上图中红、绿节点对之间有三条步数为 3 的最短路径,其中两条有黄色节点出现,因此黄色节点对于红绿节点对的中介概率为 2 / 3 = 0.6667

      对于两个不连通的节点,任何其他一个节点针对他们的中介概率都是 0。

      中介中心性

      计算中介中心性,需要先列出全图除该点外的所有节点对,计算该点对于每个节点对的中介概率,再对这些概率求平均值:

      其中,x 为待计算的节点,ij 为图中不同于 x 且互异的任意两节点,ij 配对不重复,σij 间的所有最短路径的数量,σ(x) 为这些最短路径中包含点 x 的路径的数量,σ(x)/σ 就是 x 对于 ij 的中介概率(ij 不连通时为 0),k 为图中的节点数量,即 (k-1)(k-2)/2ij 节点对的数量。

      计算上图中红色节点的中介中心性。根据找出的各节点对的最短路径算出红色节点对他们的中介概率,取平均值后得到中介中心性为 (1/2 + 1 + 2/3) / 6 = 0.3611

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

      特殊处理

      孤点、不连通图

      孤点不与任何其它节点相连,其中介中心性为 0;但孤点参与点对的构成,影响节点对的数量。

      对于不连通图中的两个不连通的节点,任何其他一个节点针对他们的中介概率都是 0。

      自环边

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

      有向边

      对于有向边,中介中心性算法会忽略边的方向,按照无向边进行计算。

      结果和统计值

      以下面的 7 人小型社交网络为例,针对所有点运行中介中心性算法:

      算法结果:为每个点计算中介中心性,根据算法执行方式,返回 _idcentrality 两列或 _uuidcentrality 两列

      _uuid _id centrality
      1 Sue 0.0000000
      2 Dave 0.33333334
      3 Ann 0.13333334
      4 Mark 0.13333334
      5 May 0.066666670
      6 Jay 0.066666670
      7 Billy 0.0000000

      算法统计值:

      命令及配置项

      • 命令:algo(betweenness_centrality)
      • params() 参数配置项如下:
      名称
      类型
      默认值
      规范
      描述
      sample_size int -1 -1,-2 或 (0,节点总数] 随机采样的点个数,-1 表示采样 log(<全图点数量>) 个点进行计算,-2 或忽略表示不采样,用所有点进行精确计算
      limit int -1 >=-1 需要返回的结果条数,-1 或忽略表示返回所有结果
      order string / ASC/DESC,大小写不敏感 对返回结果进行排序;忽略表示不排序

      示例:计算所有点的中介中心性,进行精确不采样计算,并返回 6 条结果

      algo(betweenness_centrality).params({ 
        limit: 6, 
        sample_size: -2 
      }) as bc
      return bc
      

      算法执行

      任务回写

      1. 文件回写

      配置项 各列数据
      filename _id,centrality

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

      algo(betweenness_centrality).params().write({
        file:{ 
          filename: "cen"
        }
      })
      

      2. 属性回写

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

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

      algo(betweenness_centrality).params().write({
        db:{ 
          property: "bc"
        }
      })
      

      3. 统计回写

      算法无统计值。

      直接返回

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

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

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

      流式返回

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

      示例:计算图中中介中心性为 0 的节点数量

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

      实时统计

      算法无统计值。

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