修改密码

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

      标签传播算法

      ✓ 文件回写 ✓ 属性回写 ✓ 直接返回 ✓ 流式返回 ✓ 统计值

      概述

      标签传播算法(LPA, Label Propagation Algorithm)是一种基于标签传播的社区识别算法。每个节点初始化标签后,在算法的每次迭代中,每个节点都会将其标签更新为在其邻居中最普遍的标签。这个迭代过程会使连接密集的节点拥有同一标签,有相同标签的节点继而形成一个社区。

      LPA不要求预先设定要划分的社区数量,也不将任何用于衡量社区划分优劣的标准作为目标,相反,它仅利用网络结构来引导其进程,这使得LPA能够有效地在大型和复杂的网络中运行。

      算法的相关资料如下:

      基本概念

      标签

      指定的一个属性值或UUID对节点标签进行初始化。算法结束时,拥有相同标签的节点属于同一社区。

      在LPA中,所有的初始标签都是有效的,即能够进行传播。如果需要将某些标签指定为无效,请联系嬴图团队定制算法。

      标签传播

      在最简单的场景中,每次迭代传播时,每个节点都会将其标签更新为其最多邻居拥有的标签。

      如下例所示,蓝色节点的标签将从d更新为c

      考虑节点和边权重时,标签权重则等于相应节点和边权重的乘积之和,每个节点将其标签更新为权重最大的那一个。

      以下的示例中包含节点和边的权重,蓝色节点的标签将从d更新为a

      多标签传播

      在多标签传播中,每个节点在传播过程中会保留多个标签。在这种情况下,节点的每个标签会关联一个与其权重成正比的标签概率,而每个节点的标签概率总和保持为1。

      在下面的示例中,每个节点保留2个标签,其概率写在标签旁,蓝色节点的标签将从d, c更新为a, c,标签概率为Pa = 6.3/(6.3+1.85) = 0.77和Pc = 1.85/(6.3+1.85) = 0.23。

      特殊说明

      • LPA忽略边的方向,按照无向边进行计算。
      • 具有自环边的节点能将自身当前的标签传播给自身,并且每条自环边计算两次。
      • LPA在更新节点标签时遵循同步更新原则,即所有节点会根据其邻居的标签同时更新其标签。但在某些情况下可能会发生标签振荡,这多见于二分图中。为了解决这个问题,LPA包含一个中断机制,可以检测并防止标签过度振荡。
      • 受节点顺序、同权重标签的随机选取以及并行计算等因素的影响,标签传播算法的社区划分结果可能会不同。

      语法

      • 命令:algo(lpa)
      • 参数:
      名称
      类型
      规范
      默认
      可选
      描述
      node_label_property @<schema>?.<property> 数值/字符串类型,需LTE / 用于初始化节点标签的点属性,无该属性的点不参与标签传播;不设置时使用节点的UUID作为标签
      node_weight_property @<schema>?.<property> 数值类型,需LTE / 作为节点权重的点属性
      edge_weight_property @<schema>?.<property> 数值类型,需LTE / 作为边权重的边属性
      loop_num int ≥1 5 传播的迭代次数
      k int ≥1 1 最多为每个节点保留的标签数量(按照标签概率从大到小排序)

      示例

      示例图如下,节点的Schema为user,边的Schema为connect,属性@connect.strength的值已标注在图中:

      文件回写

      配置项
      回写内容
      filename _id,label_1,probability_1,...label_k,probability_k
      algo(lpa).params({
        k: 2,
        loop_num: 5,
        edge_weight_property: 'strength'
      }).write({
        file:{
          filename: "lpa"
        }
      })
      

      统计值:label_count = 7
      结果:文件lpa

      O,1,0.599162,2,0.400838,
      N,1,0.634582,2,0.365418,
      M,1,0.610834,2,0.389166,
      L,1,0.607434,2,0.392566,
      K,1,0.619842,2,0.380158,
      J,14,0.655975,8,0.344025,
      I,14,0.546347,8,0.453653,
      H,9,0.690423,7,0.309577,
      G,14,0.569427,8,0.430573,
      F,9,0.784132,7,0.215869,
      E,9,0.519003,12,0.480997,
      D,14,0.781072,9,0.218928,
      C,12,0.540345,9,0.459655,
      B,9,0.559427,14,0.440573,
      A,14,0.768171,12,0.231829,
      

      属性回写

      配置项
      回写内容
      类型
      数据类型
      property label_1, probability_1, ... label_k, probability_k 点属性 标签:string,标签概率:float
      algo(lpa).params({
        node_label_property: 'interest',
        edge_weight_property: '@connect.strength',
        k: 2,
        loop_num: 10
      }).write({
        db:{
          property: "lab"
        }
      })
      

      统计值:label_count = 5
      结果:每个节点的标签和对应的概率分别回写至名为lab_1、probability_1、lab_2和probability_2的点属性下

      直接返回

      别名序号
      类型
      描述 列名
      0 []perNode 点及其各标签、标签占比 _uuid, label_1, probability_1, ... label_k, probability_k
      1 KV 标签个数 label_count
      algo(lpa).params({
        node_label_property: '@user.interest',
        node_weight_property: '@user.level'
      }) as res
      return res
      

      结果:res

      _uuid label_1 probability_1
      15 novel 1.000000
      14 swimming 1.000000
      13 novel 1.000000
      12 novel 1.000000
      11 novel 1.000000
      10 violin 1.000000
      9 badminton 1.000000
      8 piano 1.000000
      7 badminton 1.000000
      6 badminton 1.000000
      5 piano 1.000000
      4 piano 1.000000
      3 piano 1.000000
      2 piano 1.000000
      1 piano 1.000000
      algo(lpa).params({
        node_label_property: 'interest',
        k: 2
      }) as res, stats
      return res, stats
      

      结果:res和stats

      _uuid label_1 probability_1 label_2 probability_2
      15 novel 0.642453 saxophone 0.357547
      14 swimming 0.577773 saxophone 0.422227
      13 novel 0.610180 swimming 0.389820
      12 saxophone 0.608193 novel 0.391807
      11 piano 0.536380 saxophone 0.463620
      10 piano 0.588276 movie 0.411724
      9 piano 0.595449 movie 0.404551
      8 piano 0.637065 movie 0.362935
      7 piano 0.554655 movie 0.445345
      6 piano 0.720096 movie 0.279904
      5 piano 0.502892 flute 0.497108
      4 piano 0.648339 flute 0.351661
      3 piano 0.520442 flute 0.479558
      2 piano 0.624170 flute 0.375831
      1 piano 0.670773 flute 0.329227
      label_count
      6

      流式返回

      别名序号
      类型
      描述 列名
      0 []perNode 点及其各标签、标签占比 _uuid, label_1, probability_1, ... label_k, probability_k
      algo(lpa).params({
        node_label_property: '@user.interest',
        node_weight_property: '@user.level',
        edge_weight_property: 'strength',
        loop_num: 10
      }).stream() as lpa
      group by lpa.label_1
      with count(lpa) as labelCount
      return table(lpa.label_1, labelCount) 
      order by labelCount desc
      

      结果:table(lpa.label_1, labelCount)

      lpa.label_1 labelCount
      piano 5
      swimming 3
      violin 2
      novel 2
      tennis 2

      统计返回

      别名序号
      类型
      描述 列名
      0 KV 标签个数 label_count
      algo(lpa).params({
        node_label_property: 'interest',
        edge_weight_property: 'strength',
        k: 1,
        loop_num: 5
      }).stats() as count 
      return count
      

      结果:count

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