Vue d’ensemble

La similarité de Jaccard, ou indice de Jaccard, a été proposée par Paul Jaccard en 1901. C'est une mesure de similarité pour deux ensembles de données. Dans le graphe, en regroupant les voisins d'un node en un ensemble, deux nodes sont considérés similaires si leurs ensembles de voisinage sont similaires.

La similarité de Jaccard varie de 0 à 1 ; 1 signifie que deux ensembles sont exactement les mêmes, 0 signifie que les deux ensembles n'ont aucun élément en commun.

Concepts

Similarité de Jaccard

Étant donné deux ensembles A et B, la similarité de Jaccard entre eux est calculée comme suit :

Dans l'exemple suivant, l'ensemble A = {b,c,e,f,g}, l'ensemble B = {a,d,b,g}, leur intersection A⋂B = {b,g}, leur union A⋃B = {a,b,c,d,e,f,g}, donc la similarité de Jaccard entre A et B est 2 / 7 = 0.285714.

Lors de l'application de la Similarité de Jaccard pour comparer deux nodes dans un graph, nous utilisons l'ensemble de voisinage à 1 saut pour représenter chaque node cible. L'ensemble de voisinage à 1 saut :

• ne contient pas de nodes répétés ;
• exclut les deux nodes cibles.

Dans ce graph, l'ensemble de voisinage à 1 saut des nodes u et v est :

• N_u = {a,b,c,d,e}
• N_v = {d,e,f}

Ainsi, la similarité de Jaccard entre les nodes u et v est 2 / 6 = 0.333333.

En pratique, vous pouvez avoir besoin de convertir certaines propriétés de node en schemas de node afin de calculer l'indice de similarité basé sur les voisins communs, tout comme la Similarité de Jaccard. Par exemple, lors de la considération de la similarité entre deux applications, des informations telles que le numéro de téléphone, l'email, l'IP de l'appareil, etc., de l'application pourraient avoir été stockées en tant que propriétés du schema de node @application; elles doivent être conçues comme des nodes et incorporées dans le graph pour être utilisées pour la comparaison.

Similarité de Jaccard pondérée

La Similarité de Jaccard pondérée est une extension de la Similarité de Jaccard classique qui prend en compte les poids associés aux éléments dans les ensembles comparés.

La formule de la Similarité de Jaccard pondérée est donnée par :

Dans ce graph pondéré, l'union des ensembles de voisinage à 1 saut N_u et N_v est {a,b,c,d,e,f}. Fixez chaque élément de l'ensemble d'union à la somme des poids des edges entre le node cible et le node correspondant, ou 0 s'il n'y a pas d'edges entre eux :

Ainsi, la Similarité de Chevauchement Pondéré entre les nodes u et v est (0+0+0+0.5+0.5+0) / (1+1+1+1+1.6+1) = 0.151515.

Veuillez vous assurer que la somme des poids des edges entre le node cible et le node voisin est supérieure ou égale à 0.

Considérations

• L'algorithme de Similarité de Jaccard ignore la direction des edges mais les calcule comme des edges non dirigés.
• L'algorithme de Similarité de Jaccard ignore toute boucle auto-renforcée.

Syntaxe

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

L'algorithme a deux modes de calcul :

1. Couplage : lorsque ids/uuids et ids2/uuids2 sont configurés, coupler chaque node dans ids/uuids avec chaque node dans ids2/uuids2 (ignorer le même node) et calculer les similarités par paires.
2. Sélection : lorsque seul ids/uuids est configuré, pour chaque node cible dans celui-ci, calculer les similarités par paires entre lui et tous les autres nodes dans le graph. Les résultats retournés incluent tous ou un nombre limité de nodes ayant une similarité > 0 avec le node cible et sont ordonnés par similarité décroissante.

Exemples

Le graph exemple est le suivant :

File Writeback

algo(similarity).params({
  ids: 'userC',
  ids2: ['userA', 'userB', 'userD'],
  type: 'jaccard'
}).write({
  file:{ 
    filename: 'sc'
  }
})

Résultats : Fichier sc

userC,userA,0.25
userC,userB,0.5
userC,userD,0

algo(similarity).params({
  uuids: [1,2,3,4],
  type: 'jaccard'
}).write({
  file:{ 
    filename: 'list'
  }
})

Résultats : Fichier list

userA,userC,0.25
userA,userB,0.2
userA,userD:0.166667
userB,userC:0.5
userB,userD,0.25
userB,userA,0.2
userC,userB,0.5
userC,userA,0.25
userD,userB:0.25
userD,userA:0.166667

Direct Return

algo(similarity).params({ 
  uuids: [1,2], 
  uuids2: [2,3,4],
  type: 'jaccard'
}) as jacc
return jacc

Résultats : jacc

algo(similarity).params({
  uuids: [1,2],
  type: 'jaccard',
  top_limit: 1
}) as top
return top

Résultats : top

Stream Return

algo(similarity).params({ 
  uuids: [3], 
  uuids2: [1,2,4],
  type: 'jaccard'
}).stream() as jacc
where jacc.similarity > 0
return jacc

Résultats : jacc

algo(similarity).params({
  uuids: [1],
  type: 'jaccard',
  top_limit: 2
}).stream() as top
return top

Résultats : top