修改密码

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

搜索
    中文

      HANP

      概述

      HANP(Hop Attenuation & Node Preference,跳跃衰减和节点倾向性)算法是对标签传播算法(LPA)的扩展,它在 LPA 的基础上引入了标签分值衰减机制,并考虑了邻居节点的度对邻居标签权重的影响。该算法由 Ian X.Y. Leung 于 2009 年提出。

      算法的相关资料如下:

      基本概念

      标签分值

      标签分值代表标签的传播能力。HANP 算法给每个标签赋予的初始分值为 1,当节点从邻居节点选取新标签时(即标签跳跃一次),新标签传递到节点上的分值会有一定程度的衰减,这正是算法名称中 HA(Hop Attenuation,跳跃衰减)的来源。标签分值每次跳跃后衰减的幅度称为衰减因子,记作 δ,衰减因子能有效地避免大社区的形成。下图中,令 δ = 0.3,当绿色节点选取标签 a 时,标签 a 在绿色节点上的分值衰减为 2 - 0.3 = 1.7

      当选取的新标签来自多个邻居时,选取分值最高的进行衰减。

      节点度倾向性

      节点度倾向性指的是度越大的节点传播标签的能力越强;换句话说,一个节点会倾向于接受节点度较高的邻居的标签。HANP 算法名称中 NP 的全称 Node Preference(节点倾向性)指的就是这种对邻居节点的度的倾向性。

      如上图所示,作为绿色节点的邻居,红色节点的度为 6(自环边计算两次),黄色节点的度为 4,因此绿色节点更倾向于接受标签 a

      当然,也可以规定度较低的节点标签得到优先传播。因此,算法考虑标签所在节点的度的指数幂,当指数大于 0 时,节点度高的标签会得到优先传播;当指数小于 0 时,节点度低的标签会得到优先传播;当指数等于 0 时,节点度不影响标签传播的优先级。

      标签权重

      节点 j 的标签 l 向其邻居节点 i 传播时的权重 w(l) 等于标签 lj 上的分值 s(j)j 的度的幂函数、ij 之间的边权重和这三者的乘积;当 i 有多个邻居节点拥有标签 l 时,需要对来自所有邻居节点的标签 l 权重求和:

      上式中,d(j)j 的节点度,m 为幂指数,A(ij)ij 之间的边权重和。

      对于图中任意节点 ili 的邻居的标签,w(l)l 的权重,则 i 的新标签 l' 可表示为:

      s(l') 为新标签在原各个邻居节点上的分值,δ 为衰减因子,则新标签在 i 上的分值为:

      请注意,如果选取的新标签与节点当前的标签相同,则 δ = 0,即不进行分值衰减。

      HANP 算法的迭代过程与 LPA 类似。在算法开始时将所有点的标签分值设置为 1;在每轮迭代中,为每个节点计算是否能从其邻居节点中选取与现有标签不同标签,或比现有标签分值更高的相同标签;计算完所有节点后,对需要更新的节点进行更新。按此规则循环迭代至所有节点的标签和标签分值不再变化,或迭代轮数达到限制。

      与 LPA 不同的是,由于 HANP 算法引入了标签分值,杜绝了标签震荡的情况,因此不需要额外的中断机制。

      特殊处理

      孤点、不连通图

      对于不连通图,各孤点、连通分量之间没有邻边,不能相互传递标签,不含有相同初始标签的连通分量不会被划分为相同社区。

      自环边

      HANP 算法对自环边的处理与节点度算法 algo(degree) 相同,都是将每条自环边计算两次。

      有向边

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

      结果和统计值

      以下面的图为例,边的权重均为 1,节点内的字母是初始标签,节点 11 没有初始标签,运行 HANP 算法,迭代 10 次,幂指数 m 为 0.1,衰减因子 δ 为 0.2:

      算法结果:每个点最多保留一个标签,返回 _uuidlabel_1score_1 三列

      _uuid label_1 score_1
      1 A -0.200000
      2 F -0.200000
      3 F -0.200000
      4 F -0.200000
      5 F -0.200000
      6 A -0.200000
      7 A -0.200000
      8 A -0.200000
      9 A -0.200000
      10 J 1
      11

      算法统计值:标签数量 label_count

      label_count
      3

      命令和参数配置

      • 命令:algo(hanp)
      • params() 参数配置项如下:
      名称
      类型
      默认值
      规范
      描述
      loop_num int 5 >= 1 算法迭代轮数
      node_label_property @<schema>.<property> / 数值或字符串类的点属性,需LTE 作为标签的 schema 及属性名称;无该属性的点不参与计算;忽略时使用随机数作为节点的标签
      edge_weight_property @<schema>.<property> / 数值类的边属性,需LTE 边权重所在的 schema 及属性名称;无该属性的边不参与计算;忽略表示权重为 1
      m float / 必填 邻居节点度的幂指数,表示对邻居节点度的偏向性;m = 0 代表不考虑邻居的节点度,m > 0 代表偏向节点度高的邻居,m < 0 代表偏向节点度低的邻居
      delta float / (0,1);必填 传播中标签分值衰减因子
      limit int -1 >= -1 需要返回的结果条数,-1 或忽略表示返回所有结果

      示例:运行 HANP 算法,标签所在属性为 @default.label,边权重所在属性为 @default.level,幂指数为 0.1,标签分值衰减因子为 0.2,迭代 10 次

      algo(hanp).params({ 
        loop_num: 10,
        node_label_property: "@default.label", 
        edge_weight_property: "@default.level", 
        m: 0.1, 
        delta: 0.2 
      }) as a return a
      

      算法执行

      任务回写

      1. 文件回写

      配置项
      各列数据
      filename _id,label_1,score_1

      示例:运行 HANP 算法,标签所在属性为 @default.label,边权重所在属性为 @default.level,幂指数为 0.1,标签分值衰减因子为 0.2,迭代 10 次,将算法结果回写至名为 hanp 的文件

      algo(hanp).params({ 
        loop_num: 10,
        node_label_property: "@default.label", 
        edge_weight_property: "@default.level", 
        m: 0.1, 
        delta: 0.2 
      }).write({
        file:{
          filename: "hanp"
        }
      })
      

      2. 属性回写

      配置项
      回写内容
      类型
      数据类型
      property label_1,score_1 点属性 标签的数据类型为 string,标签分值的数据类型为 float

      示例:运行 HANP 算法,标签所在属性为 @default.label,所有边权重为 1,幂指数为 0.1,标签分值衰减因子为 0.2,迭代 10 次,将算法结果分别回写至名为 tag_1、score_1 的点属性

      algo(hanp).params({ 
        loop_num: 10,
        node_label_property: "@default.label", 
        m: 0.1, 
        delta: 0.2 
      }).write({
        db:{
          property: "tag"
        }
      })
      

      3. 统计回写

      统计项名称 数据类型 描述
      label_count int 标签个数

      标签个数是指算法结束时,图中剩余标签的个数;HANP 算法只为每个节点保留一个标签,因此标签个数即为社区个数。

      示例:运行 HANP 算法,标签所在属性为 @default.label,所有边权重为 1,幂指数为 0.1,标签分值衰减因子为 0.2,迭代 10 次,将算法统计值回写至任务信息

      algo(hanp).params({ 
        loop_num: 10,
        node_label_property: "@default.label", 
        m: 0.1, 
        delta: 0.2 
      }).write()
      

      直接返回

      别名序号
      类型
      描述 列名
      0 []perNode 点及其各标签、标签分值 _uuid, label_1, score_1
      1 KV 标签个数 label_count

      示例:运行 HANP 算法,标签所在属性为 @default.label,所有边权重为 1,幂指数为 0.1,标签分值衰减因子为 0.2,迭代 10 次,将算法结果和统计值分别定义为别名 results 和 count 并返回

      algo(hanp).params({ 
        loop_num: 10,
        node_label_property: "@default.label", 
        m: 0.1, 
        delta: 0.2 
      }) as results, count 
      return results, count
      

      流式返回

      别名序号
      类型
      描述 列名
      0 []perNode 点及其各标签、标签分值 _uuid, label_1, score_1

      示例:运行 HANP 算法,标签所在属性为 @default.label,所有边权重为 1,幂指数为 0.1,标签分值衰减因子为 0.2,迭代 10 次,返回结果并按照标签名称和点的 UUID 升序排列

      algo(hanp).params({ 
        loop_num: 10,
        node_label_property: "@default.label", 
        m: 0.1, 
        delta: 0.2 
      }).stream() as res 
      return res order by res.label_1, res._uuid
      

      实时统计

      别名序号
      类型
      描述 列名
      0 KV 标签个数 label_count

      示例:运行 HANP 算法,标签所在属性为 @default.label,所有边权重为 1,幂指数为 0.1,标签分值衰减因子为 0.2,迭代 10 次,返回社区数量

      algo(hanp).params({ 
        loop_num: 10,
        node_label_property: "@default.label", 
        m: 0.1, 
        delta: 0.2 
      }).stats() as count 
      return count
      

      结果一致性

      受节点顺序、同权重标签随机选取、并行计算等因素的影响,HANP 算法的社区划分结果可能会不同。

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