Théorie des graphes et concepts relatifs aux diagrammes de liens

Il peut être utile de comprendre certains concepts liés à la théorie des graphes lorsque vous déterminez les méthodes à utiliser lors de la manipulation ou de l’analyse des diagrammes de liens qui incluent un contenu provenant d’un graphe de connaissances et lorsque vous évaluez les résultats de ces méthodes.

Le contenu d’un diagramme de liens est géré en tant que graphe. Les discussions sur la théorie des graphes font souvent référence à des nœuds ou des tronçons. Un nœud dans un graphe correspond à une entité dans le graphe de connaissances. Un tronçon dans un graphe correspond à une relation dans le graphe de connaissances.

Calculer le degré ou le degré réduit d’une entité

Le degré d’une entité correspond au nombre de relations auxquelles l’entité participe. Le degré d’une entité est calculé dans le contexte du diagramme de liens. En d’autres termes, seules les relations présentes dans le diagramme de liens sont utilisées pour calculer le degré d’une entité.

Contrairement au degré d’une entité, le degré réduit correspond au nombre d’entités auxquelles l’entité est liée. Examinez les scénarios ci-après.

De nombreuses relations existent entre deux entités. Par exemple, une entité nommée Employé A est connectée à une autre entité nommée Employé B par une relation TravaillePour et une relation ChefÉquipe. Le degré d’Employé A est deux. En revanche, le degré réduit pour Employé A est un. Dans le diagramme ci-dessous, les relations libellées A illustrent cet exemple.

Groupes de relations : dans l’exemple précédent, supposez que les relations TravaillePour et ChefÉquipe sont regroupées entre Employé A et Employé B. Les calculs du degré et du degré réduit traitent le groupe de relations comme s’il n’existait pas. Lorsque vous déterminez le degré d’Employé A, chaque relation dans le groupe est prise en compte individuellement et le degré est deux. Cependant, pour le degré réduit, le groupe de relations connecte uniquement Employé A à Employé B et le degré réduit est un. Dans le diagramme ci-dessous, les groupes de relations libellés Groupe (2) et Groupe (4) illustrent cet exemple.

Relations récursives : une relation récursive existe lorsqu’une entité est à la fois l’origine et la destination d’une relation. Par exemple, l’employé C est un chef de projet et travaille sur le projet ; par conséquent, il est son propre chef d’équipe. Le degré de l’entité Employé C est deux car elle participe à une relation sortante et à une relation entrante. Toutefois, le degré réduit de l’entité Employé C est zéro car elle n’est liée à aucune autre entité. Dans le diagramme ci-dessous, les relations libellées B illustrent cet exemple.

Dans le cas de relations classiques où une relation unique connecte deux entités, le degré d’une entité et son degré réduit sont identiques. Par exemple, une entité Employé A est connectée à une entité Employé B par une relation TravaillePour et est connectée à une entité Employé C par une relation ChefÉquipe. Le degré d’Employé A est deux et son degré réduit est également deux, car l’entité Employé B participe à deux relations et est liée à deux entités. Si les entités Employé B et Employé C sont regroupées dans le diagramme de liens, ce qui entraîne le regroupement des deux relations, le degré et le degré réduit d’Employé A sont identiques car les entités participent tout de même à deux relations individuelles et sont liées à deux entités individuelles.

Le diagramme ci-dessous présente le degré réduit (R:x) et le degré (D:y) de chaque entité dans un exemple de diagramme de liens. Les entités affichées en rose possèdent un degré réduit de 1 (R:1), les entités affichées en bleu possèdent un degré réduit de 2 (R:2) et les entités affichées en vert possèdent un degré réduit de 3 ou plus (R:x).

Degré réduit et degré des entités dans un exemple de diagramme de liens

Utiliser le degré ou le degré réduit d’une entité

Certaines opérations de diagramme de liens reposent sur le degré ou le degré réduit des entités qui sont traitées. Le degré d’une entité est pris en compte lors du calcul des scores de centralité suivants :

  • Degré
  • Degré entrant
  • Degré sortant

Le degré réduit d’une entité est pris en compte lorsque les méthodes suivantes sont utilisées avec un diagramme de liens :

  • Mise en page organique : lorsque vous changez la façon dont les entités et les relations sont affichées en appliquant une mise en page organique, les entités possédant un degré réduit de un, deux ou trois sont post-traitées.
  • Opération de troncature : la méthode de troncature est utilisée pour retirer les entités feuilles d’un diagramme de liens. Les entités feuilles sont définies en tant qu’entités avec un degré réduit de un.

Les mêmes entités de graphe de connaissances peuvent être ajoutées à des diagrammes de liens dans lesquels des relations différentes associées à ces entités sont incluses. Dans chaque diagramme de liens, le degré et le degré réduit d’une entité sont calculés spécifiquement pour le diagramme de liens, et non pour le graphe de connaissances sous-jacent.

Rubriques connexes