概述

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