Vue d’ensemble

L'algorithme de p-Cohésion identifie des groupes d'acteurs du réseau (nodes) très connectés entre eux, représentés par des sous-graphs cohésifs. Il fournit des informations précieuses sur le niveau de connectivité et d'interdépendance au sein de ces groupes, permettant une analyse approfondie de la structure du graph et de ses implications.

Le concept de p-cohésion a été proposé pour la première fois par S. Morris dans un modèle de contagion de l'interaction entre grandes populations :

• S. Morris, Contagion. The Review of Economic Studies, 67(1), 57–78 (2000)

Concepts

p-Cohésion

Une mesure naturelle de la 'cohésion' d'un groupe est la fréquence relative des liens parmi les membres du groupe comparée à celle des non-membres. Supposons que la cohésion soit une constante p ∈ (0,1), une p-cohésion est un sous-graph connecté dans lequel chaque node a, au moins, une proportion p de ses voisins à l'intérieur du sous-graph, c’est-à-dire, au plus, une proportion (1 − p) de ses voisins à l'extérieur.

Le modèle de p-Cohésion offre deux avantages distincts par rapport à d'autres modèles de sous-graph cohésif :

• Avec une valeur élevée de p, une p-cohésion assure non seulement une cohésion interne, mais aussi une rareté externe.
• Dans de nombreux scénarios, considérer le pourcentage de voisins plutôt qu'un nombre fixe de voisins (comme la valeur k dans k-Core) est plus approprié en raison des variations des degrés des nodes.

Ci-dessous figure un graph d’exemple. Supposons p = 0.6, une étiquette grise est placée à côté de chaque node indiquant le nombre minimum de voisins requis pour que le node reste dans une p-cohésion.

Ci-dessous sont présentés les sous-graphs de p-cohésion minimaux (en termes de nombre de nodes) incluant le node a et le node j respectivement.

L'algorithme de p-Cohésion d'Ultipa trouve le sous-graph p-cohésion minimal approximatif pour chaque node de requête et renvoie chaque sous-graph sous forme de son ensemble de nodes.

Considérations

• L'algorithme de p-Cohésion ignore la direction des edges mais les calcule comme des edges non orientés.

Syntaxe

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

Exemples

Le graph de l'exemple est le suivant :

File Writeback

algo(p_cohesion).params({
  ids: ['A', 'I'],
  p: 0.7
}).write({
  file: {
    filename: "cohesion"
  }
})

Statistiques : nombre de sous-graphs = 2
Résultats : Fichier cohesion

subgraph0:D,C,B,F,A,E,
subgraph1:D,C,F,B,H,E,A,I,