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

概述

HANP（Hop Attenuation & Node Preference，跳跃衰减和节点倾向性）算法在标签传播算法（LPA）的基础上引入了标签分值衰减机制，并考虑邻居节点的度对邻居标签权重的影响。HANP 的目标是提高网络中社区检测的准确性和鲁棒性。该算法由 Ian X.Y. Leung 等人于 2009 年提出：

• I.X.Y. Leung, P. Hui, P. Liò, J. Crowcroft, Towards real-time community detection in large networks (2009)

基本概念

跳跃衰减

HANP 算法赋予每个标签一个分值，该分值随着标签从其原点向远传播而逐渐降低。所有标签的初始分值均为 1。当某节点从其邻域采用一个新标签时，新标签在该节点上的分值会在原分值基础上减去一个跳跃衰减因子 δ（0 < δ < 1）的大小。

跳跃衰减机制限制标签只向附近的节点传播，能防止某标签在网络中传播得太广从而形成过大的社区。

节点倾向性

在计算新的最大标签时，HANP 包含基于节点度的倾向性。当节点 j ∈ N_i 将其标签 L 传播到节点 i 时，标签 L 的权重计算公式为：

其中，

• s_j(L) 是标签 L 在节点 j 上的分值。
• deg_j 是节点 j 的度。当 m > 0 时，倾向于度较大的节点；当 m < 0 时，倾向于度较小的节点；当 m = 0 时，对节点度没有倾向性。
• w_ij 是节点 i 和 j 之间所有边的权重和。

以下的示例中包含边权重，标签分值写在标签旁，设置 m = 2 以及 δ = 0.2，蓝色节点的标签将从 d 更新为 a，标签 a 在蓝色节点上的分值衰减至 0.6。

特殊说明

• HANP 忽略边的方向，按照无向边进行计算。
• 具有自环边的节点能将自身当前的标签传播给自身，并且每条自环边计算两次。
• 如果节点选择的标签与当前自身的标签一致，δ = 0。
• HANP 在更新节点标签时遵循同步更新原则，即所有节点会根据其邻居的标签同时更新其标签。由于引入了标签分值，HANP 通常不会出现标签振荡。
• 受节点顺序、同权重标签的随机选取以及并行计算等因素的影响，HANP 算法的社区划分结果可能会不同。

语法

• 命令：algo(hanp)
• 参数：

示例

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

文件回写

algo(hanp).params({ 
  loop_num: 10,
  edge_weight_property: 'strength',
  m: 2, 
  delta: 0.2 
}).write({
  file:{
    filename: 'hanp'
  }
})

统计值：label_count = 4
结果：文件 hanp

O,13,-0.600000,
N,6,-1.000000,
M,6,-1.000000,
L,13,-0.600000,
K,13,-0.600000,
J,1,-0.200000,
I,1,-0.200000,
H,1,-0.200000,
G,1,-0.200000,
F,14,-1.000000,
E,6,-0.200000,
D,6,-0.200000,
C,6,-0.200000,
B,6,-0.200000,
A,6,-0.400000,

属性回写

algo(hanp).params({ 
  node_label_property: '@user.interest',
  m: 0.1, 
  delta: 0.3
}).write({
  db:{
    property: 'lab'
  }
})

统计值：label_count = 3
结果：每个节点的标签和标签分值分别回写至名为 lab_1 和 score_1 的点属性下

直接返回

algo(hanp).params({ 
  loop_num: 12,
  node_label_property: '@user.interest',
  m: 1,
  delta: 0.2
}) as res, stats
return res, stats

结果：res 和 stats

流式返回

algo(hanp).params({ 
  loop_num: 12,
  node_label_property: '@user.interest',
  m: 1,
  delta: 0.2
}).stream() as hanp
group by hanp.label_1
with count(hanp) as labelCount
return table(hanp.label_1, labelCount) 
order by labelCount desc

结果：table(hanp.label_1, labelCount)

统计返回

algo(hanp).params({ 
  loop_num: 5,
  node_label_property: 'interest',
  m: 0.6,
  delta: 0.2
}).stats() as count
return count

结果：count