Vue d’ensemble

L'algorithme d'Allocation des Ressources fonctionne sous l'hypothèse que les nodes transmettent des ressources entre eux à travers leurs voisins communs, qui agissent comme des transmetteurs. Dans sa forme basique, nous considérons chaque transmetteur possédant une unité de ressource, qui est répartie uniformément parmi ses voisins. Par conséquent, la similarité entre deux nodes peut être mesurée par l'ampleur des ressources qu'un node transmet à l'autre. Ce concept a été introduit par Tao Zhou, Linyuan Lü, et Yi-Cheng Zhang en 2009 :

• T. Zhou, L. Lü, Y. Zhang, Predicting Missing Links via Local Information (2009)

Il est calculé en utilisant la formule suivante :

où N(u) est l'ensemble des nodes adjacents à u. Pour chaque voisin commun u des deux nodes, l'Allocation des Ressources calcule d'abord le réciproque de son degré |N(u)|, puis additionne ces valeurs réciproques pour tous les voisins communs.

Lors du calcul du degré des nodes dans le graphset:

• les edges connectant deux mêmes nodes seront comptés une seule fois;
• l'auto-boucle sera ignorée.

Des scores d'Allocation des Ressources plus élevés indiquent une plus grande similarité entre les nodes, tandis qu'un score de 0 indique une absence de similarité entre deux nodes.

Dans cet exemple, N(D) ∩ N(E) = {B, F}, RA(D,E) = $\frac{1}{\mathrm{|N(B)|}}$ + $\frac{1}{\mathrm{|N(F)|}}$ = $\frac{1}{4}$ + $\frac{1}{3}$ = 0.5833.

Considérations

• L'algorithme d'Allocation des Ressources ignore la direction des edges mais les calcule comme des edges non dirigés.

Syntaxe

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

Exemple

Le graph d'exemple est le suivant :

File Writeback

algo(topological_link_prediction).params({
  uuids: [3],
  uuids2: [1,5,7],
  type: 'Resource_Allocation'
}).write({
  file:{ 
    filename: 'ra'
  }
})

Résultats : Fichier ra

C,A,0.250000
C,E,0.500000
C,G,0.333333

Direct Return

algo(topological_link_prediction).params({
  ids: 'C',
  ids2: ['A','C','E','G'],
  type: 'Resource_Allocation'
}) as ra 
return ra 

Résultats : ra

Stream Return

find().nodes() as n
with collect(n._id) as nID
algo(topological_link_prediction).params({
  ids: 'C',
  ids2: nID,
  type: 'Resource_Allocation'
}).stream() as ra
where ra.num >= 0.3
return ra

Résultats : ra