Vue d’ensemble

L'algorithme de propagation de label (LPA) est un algorithme de détection de communautés utilisant la propagation de labels. Chaque node est initialisé avec un label et à chaque itération de l'algorithme, chaque node met à jour son label vers celui qui est le plus prévalent parmi ses voisins. Ce processus itératif permet aux groupes de nodes densément connectés de converger vers un consensus de labels, les nodes partageant le même label formant alors une communauté.

LPA n'optimise aucune mesure spécifique de la force des communautés et ne nécessite pas que le nombre de communautés soit prédéfini. Il exploite plutôt la structure du réseau pour guider sa progression. Cette simplicité permet à LPA d'analyser efficacement des réseaux grands et complexes.

Matériel connexe de l'algorithme :

• U.N. Raghavan, R. Albert, S. Kumara, Algorithme en temps presque linéaire pour détecter les structures de communauté dans les réseaux à grande échelle (2007)

Concepts

Label

Le label d'un node est initialisé avec une valeur de propriété spécifiée, ou son UUID unique.

Les nodes qui ont le même label à la fin de l'algorithme indiquent leur affiliation à une communauté commune.

Dans LPA, tous les labels initiaux sont valides et capables de se propager. Si certains labels doivent être définis comme invalides, veuillez contacter l'équipe Ultipa pour une personnalisation.

Propagation de Label

Dans les paramètres les plus simples, à chaque itération de propagation, chaque node met à jour son label vers celui auquel appartiennent le plus grand nombre de ses voisins.

Comme l'exemple suivant le montre, le label du node bleu sera mis à jour de d à c.

Lors de la prise en compte des poids des nodes et des edges, le poids du label équivaut à la somme des produits des poids correspondants des nodes et des edges, chaque node met à jour son label vers celui avec le poids le plus élevé.

Comme les poids des nodes et des edges indiqués dans l'exemple ci-dessous, le label du node bleu sera mis à jour de d à a.

Propagation Multi-label

Dans la propagation multi-label, chaque node accepte plusieurs labels pendant la propagation. Dans ce cas, une probabilité de label proportionnelle à son poids est attribuée à chaque label d'un node, tandis que la somme des probabilités de labels de chaque node reste égale à 1.

Dans l'exemple ci-dessous, chaque node conserve 2 labels, les probabilités sont écrites à côté des labels, les labels du node bleu seront mis à jour de d, c à a, c avec des probabilités de labels P_a = 6.3/(6.3+1.85) = 0.77 et P_c = 1.85/(6.3+1.85) = 0.23.

Considérations

• LPA ignore la direction des edges mais les calcule comme des edges non dirigées.
• Un node avec des boucles se propage ses label(s) actuels à lui-même, et chaque boucle est comptée deux fois.
• LPA suit le principe de mise à jour synchrone lors de la mise à jour des labels des nodes. Cela signifie que tous les nodes mettent à jour leurs labels simultanément en fonction des labels de leurs voisins. Cependant, dans certains cas, des oscillations de labels peuvent se produire, en particulier dans les graphes bipartites. Pour résoudre ce problème, l'algorithme intègre un mécanisme d'interruption qui détecte et empêche les oscillations de labels excessives.
• En raison de facteurs tels que l'ordre des nodes, la sélection aléatoire des labels avec des poids égaux et les calculs parallèles, les résultats de division communautaire de LPA peuvent varier.

Syntaxe

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

Exemples

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

File Writeback

algo(lpa).params({
  k: 2,
  loop_num: 5,
  edge_weight_property: 'strength'
}).write({
  file:{
    filename: "lpa"
  }
})

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

algo(lpa).params({
  node_label_property: 'interest',
  edge_weight_property: '@connect.strength',
  k: 2,
  loop_num: 10
}).write({
  db:{
    property: "lab"
  }
})

Statistiques : label_count = 5
Résultats : Les labels et la probabilité correspondante de chaque node sont écrits dans de nouvelles propriétés lab_1, probability_1, lab_2 et probability_2 respectivement

Direct Return

algo(lpa).params({
  node_label_property: '@user.interest',
  node_weight_property: '@user.level'
}) as res
return res

Résultats : res

algo(lpa).params({
  node_label_property: 'interest',
  k: 2
}) as res, stats
return res, stats

Résultats : res et stats

Stream Return

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

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

Stats Return

algo(lpa).params({
  node_label_property: 'interest',
  edge_weight_property: 'strength',
  k: 1,
  loop_num: 5
}).stats() as count 
return count

Résultats : count