修改密码

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

修改昵称

当前昵称:
提交
搜索
v4.0
    v4.0

    接近中心性

    概述

    接近中心性(Closeness Centrality)用来衡量节点在其连通分量中到其它各点的最短距离的平均值。该概念可以帮助选出连通分量内距离各点最近的点,因而被广泛用于关键社交节点发现、功能性场所选址等应用场景。

    接近中心性的取值范围是 [0,1],数值越大越靠近中心。

    接近中心性在实际应用中有着多种定义,其原始概念是由 Alex Bavelas 于 1950 年提出的,相关资料如下:

    基本概念

    最短距离

    最短距离是指两个点之间的最短路径的边数。最短路径按照 BFS 原则进行搜索,如果将一个点看作起点,将另一个点看作起点的某个 K 邻,此时的 K 值即为起点到 K 邻的最短距离。关于 BFS 和 K 邻的介绍请阅读《全图 K 邻》一章。

    考察以上无向图中红、绿两点之间的最短距离。由于是无向图,无论是以红色节点为起点,还是以绿色节点为起点,两点均为对方的 2 步邻居,即两点的最短距离为 2。

    将前面的无向图修改为有向图后再次考察红、绿两点之间的最短距离,此时注意路径中边的方向。从红色节点到绿色节点的出方向最短距离为 4,入方向最短距离为 3。

    接近中心性

    本算法所计算的接近中心性是从原始概念引申而来的,具体定义为某点到能与其相连的各节点的最短距离的平均值的倒数:

    其中,x 为待计算的节点,yx 所能达到的任意一个节点(沿出边或入边,或忽略边的方向;不包含 x),d(x, y)xy 的最短距离,k-1y 的个数。

    计算上图中红色节点的入方向接近中心性。入方向上可连通蓝、黄、紫三个节点,故接近中心性为 3 / (2 + 1 + 2) = 0.6。注意,入边不可达的绿色、灰色节点不参与计算。

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

    特殊处理

    孤点、不连通图

    孤点不与任何其它节点相连,其接近中心性为 0,孤点也不会参与到任何接近中心性的计算中。

    一个连通分量内的节点一定不会参与其它连通分量内节点的接近中心性的计算中。对于不连通图,建议使用调和中心性算法。

    自环边

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

    有向边

    在不规定边的方向时计算接近中心性,边的方向将被忽略,此时起点所在连通分量中的所有节点都参与计算。

    结果和统计值

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

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

    _uuid _id centrality
    1 LA 1.0000000
    6 LF 1.0000000
    7 LG 1.0000000
    2 LB 0.66666669
    3 LC 0.66666669
    4 LD 0.57142860
    5 LE 0.57142860
    8 LH 0.0000000

    算法统计值:

    命令和参数配置

    • 命令:algo(closeness_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(closeness_centrality).params({ 
      uuids: [1,2,3,4]
    }).stream() as centrality
    return centrality
    

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

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

    算法执行

    任务回写

    1. 文件回写

    配置项 各列数据
    filename _id,centrality

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

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

    2. 属性回写

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

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

    algo(closeness_centrality).params().write({
      db:{ 
        property: "cc"
      }
    })
    

    3. 统计回写

    算法无统计值。

    直接返回

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

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

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

    流式返回

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

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

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

    实时统计

    算法无统计值。

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