Vue d’ensemble

L'algorithme HANP (Hop Attenuation & Node Preference) étend l'algorithme de propagation d'étiquette (LPA) traditionnel en intégrant un mécanisme d'atténuation du score des étiquettes et en tenant compte de l'influence du degré des nodes voisins sur le poids de l'étiquette. Le but de HANP est d'améliorer la précision et la robustesse de la détection de communautés dans les réseaux, il a été proposé en 2009：

• I.X.Y. Leung, P. Hui, P. Liò, J. Crowcroft, Vers la détection en temps réel des communautés dans les grands réseaux (2009)

Concepts

Atténuation par Saut

HANP associe à chaque étiquette un score qui diminue à mesure qu'il se propage depuis son origine. Toutes les étiquettes reçoivent initialement un score de 1. Chaque fois qu'un node adopte une nouvelle étiquette de son voisinage, un nouveau score atténué sera attribué à cette nouvelle étiquette en soustrayant l’atténuation par saut δ (0 < δ < 1).

Le mécanisme d'atténuation par saut limite la propagation des étiquettes aux nodes proches et les empêche de se répandre trop largement dans le réseau.

Préférence de Node

Dans le calcul de la nouvelle étiquette maximale, HANP intègre la préférence de node basée sur le degré du node. Lorsque le node j ∈ N_i propage son étiquette L au node i, le poids de l'étiquette L est calculé par :

où,

• s_j(L) est le score de l'étiquette L dans j.
• deg_j est le degré de j. Lorsque m > 0, plus de préférence est accordée au node avec un degré élevé; m < 0, plus de préférence est accordée au node avec un faible degré; m = 0, aucune préférence de node n'est appliquée.
• w_ij est la somme des poids des edges entre i et j.

Comme les poids des edges et les scores des étiquettes indiqués dans l'exemple ci-dessous, fixer m = 2 et δ = 0.2, l'étiquette du node bleu sera mise à jour de d à a, et le score de l'étiquette a dans le node bleu sera atténué à 0.6.

Considérations

• HANP ignore la direction des edges mais les calcule comme des edges non dirigés.
• Un node avec des boucles se propage son étiquette(s) actuelle(s) à lui-même, et chaque boucle est comptée deux fois.
• Lorsque l'étiquette sélectionnée est égale à l'étiquette actuelle, laissez δ = 0.
• HANP suit le principe de mise à jour synchrone lors de la mise à jour des étiquettes des nodes. Cela signifie que tous les nodes mettent à jour leurs étiquettes simultanément en fonction des étiquettes de leurs voisins. Le mécanisme de score d'étiquette peut empêcher les oscillations d'étiquette.
• En raison de facteurs tels que l'ordre des nodes, la sélection aléatoire d'étiquettes avec des poids égaux et les calculs parallèles, les résultats de la division des communautés de HANP peuvent varier.

Syntaxe

• Commande : algo(hanp)
• Paramètres :

Exemples

Le graph de l'exemple est le suivant, les nodes sont de schema user, les edges sont de schema connect, la valeur de @connect.strength est montrée dans le graph :

File Writeback

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

Statistiques : label_count = 4
Résultats : Fichier 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,

Property Writeback

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

Statistiques : label_count = 3
Résultats : L'étiquette et le score de l'étiquette de chaque node sont écrits dans les nouvelles propriétés lab_1 et score_1

Direct Return

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

Résultats : res et stats

Stream Return

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

Résultats : table(hanp.label_1, labelCount)

Stats Return

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

Résultats : count