Vue d’ensemble

L'algorithme k-Core identifie le sous-graphe maximal connecté où tous les nodes ont un degré minimum de k. Il est couramment utilisé pour extraire des groupes étroitement connectés dans un graph pour une analyse plus approfondie. L'algorithme est largement utilisé dans divers domaines de recherche, y compris le contrôle des risques financiers, l'analyse des réseaux sociaux et la biologie. L'un des principaux avantages de l'algorithme k-Core est sa faible complexité temporelle (linéaire), ce qui le rend efficace pour le traitement de graphes à grande échelle. De plus, les sous-graphes résultants ont une bonne interprétabilité intuitive, aidant à comprendre les motifs structurels et les relations du graph.

Le concept couramment accepté de k-core a été proposé pour la première fois par Seidman :

• S.B. Seidman, Network Structure And Minimum Degree. Soc Netw 5:269-287 (1983)

Concepts

k-Core

Le k-core d'un graph est obtenu grâce à un processus de réduction itératif. En commençant par le graph original, les nodes avec un degré inférieur à k sont successivement retirés jusqu'à ce qu'il ne reste que les nodes avec des degrés supérieurs ou égaux à k.

Ci-dessous se trouve le processus de réduction pour obtenir le 3-core de ce graph. Au premier tour, les nodes {a, d, f} avec un degré inférieur à 3 sont retirés, ce qui entraîne ensuite le retrait du node b au deuxième tour. Après le deuxième tour, tous les nodes restants ont un degré d'au moins 3. Par conséquent, le processus de réduction se termine, et le 3-core de ce graph est induit par les nodes {c, e, g, h}.

L'algorithme k-Core d'Ultipa identifie le k-core dans chaque composant connecté.

Considérations

• L'algorithme k-Core ignore les auto-boucles dans le graph. Toute auto-boucle présente n'est pas prise en compte lors du calcul du degré du node respectif.
• L'algorithme k-Core ignore la direction des edges mais les calcule comme des edges non dirigés.

Syntaxe

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

Exemples

Le graph d'exemple est le suivant :

File Writeback

algo(k_core).params({
  k: 3
}).write({
  file:{
    filename: '3-core'
  }
})

Résultats: Fichier 3-core

G
F
E
D

Direct Return

algo(k_core).params({
  k: 2
}) as k2 
return k2

Résultats: k2

Stream Return

algo(k_core).params({
  k: 2
}).stream() as k2 
find().nodes(k2) as nodes
return nodes{*}

Résultats: nodes