Vue d’ensemble

L'algorithme de Centralité de Degré est utilisé pour trouver les nodes importants dans le réseau, il mesure le nombre d'edges entrants et/ou sortants incidents au node, ou la somme des poids de ces edges. Le degré est l'algorithme de graph le plus simple et le plus efficace puisqu'il ne considère que le voisinage à 1 saut des nodes. Le degré joue un rôle vital dans le calcul scientifique, l'extraction de caractéristiques, la reconnaissance de super-nodes et d'autres domaines.

Concepts

Degré entrant et Degré sortant

Le nombre d'edges entrants qu'un node possède est appelé son degré entrant; de même, le nombre d'edges sortants est appelé degré sortant. Si la direction du edge est ignorée, c'est le degré.

Dans ce graph, le node rouge a un degré entrant de 4 et un degré sortant de 3, et son degré est de 7. Une boucle auto-dirigée est considérée comme un edge entrant et un edge sortant.

Degré Pondéré

Dans de nombreuses applications, chaque edge d'un graph a une valeur numérique associée, appelée poids. Dans un graph pondéré, le degré pondéré d'un node est la somme des poids de tous ses edges voisins. Le degré non pondéré équivaut à considérer tous les poids des edges comme étant 1.

Dans ce graph pondéré, le node rouge a un degré entrant pondéré de 0.5 + 0.3 + 2 + 1 = 3.8 et un degré sortant pondéré de 1 + 0.2 + 2 = 3.2, et son degré pondéré est de 3.2 + 3.8 = 7.

Considérations

• Le degré d'un node isolé ne dépend que de sa boucle auto-dirigée. S'il n'a pas de boucle auto-dirigée, le degré est 0.
• Chaque boucle auto-dirigée est comptée comme 2 edges attachés à son node. Une boucle auto-dirigée dirigée est vue comme un edge entrant et un edge sortant.

Syntaxe

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

Exemples

L'exemple est un réseau social, la propriété d'edge @follow.score peut être utilisée comme poids :

File Writeback

algo(degree).params().write({
  file:{ 
    filename: 'degree_all'
  }
})

Statistiques : total_degree = 20, average_degree = 2.25
Résultats : Fichier degree_all

Tim,0
Bill,1
Bob,2
Sam,2
Joe,3
Anna,5
Cathy,4
Mike,3

Property Writeback

algo(degree).params({
  edge_schema_property: '@follow.score'
}).write({
  db:{ 
    property: 'degree'
  }
})

Statistiques : total_degree = 40.4, average_degree = 5.05
Résultats : Le degré pour chaque node est écrit dans une nouvelle propriété nommée degree, les statistiques sont retournées en même temps

Direct Return

algo(degree).params({ 
  edge_schema_property: '@follow.score',
  order: 'desc' 
}) as degree, stats
return degree, stats

Résultats : degree et stats

Stream Return

Exemple : Trouver les voisins à 1 saut du node avec le degré le plus élevé, retourner toutes les informations de ces voisins

algo(degree).params({
  order: 'desc',
  limit: 1 
}).stream() as results
khop().src({_uuid == results._uuid}).depth(1) as neighbors
return neighbors{*}

Résultats : neighbors

Stats Return

algo(degree).params({
  direction: 'out'
}).stats() as stats
return stats

Résultats : stats