Détecter des communautés dans un diagramme de liens

Vous pouvez utiliser un diagramme de liens basé sur un graphe de connaissances pour détecter des communautés et rechercher des entités étroitement connectées entre elles et d'autres vaguement connectées aux entités d'autres communautés. Les communautés sont détectées à partir des entités actuellement présentes dans le diagramme de liens pas sur le contenu du graphe de connaissances dans son ensemble.

Les algorithmes de détection des communautés peuvent vous aider à visualiser des groupes d'entités étroitement liées qui ne seraient pas décelables avec d'autres méthodes d'analyse. Les communautés peuvent montrer des groupes d'influence sur les réseaux sociaux, dans des collaborations scientifiques et des structures de recherche, des individus susceptibles de se connaître entre eux du fait de leurs connexions communes, etc.

Une communauté peut avoir une entité comme membre. Votre analyse peut également identifier les entités isolées du reste du réseau.

Des méthodes de calcul des communautés, de personnalisation des paramètres méthodologiques et d'exploration des résultats sont décrites ci-dessous.

Méthodes de détection des communautés

Il existe six méthodes de détection des communautés disponibles pour les diagrammes de liens en fonction du graphe de connaissances : Louvain, Girvan-Newman, Biconnecté, Faiblement connecté, Fortement connecté et Propagation des étiquettes. Sélectionnez la méthode souhaitée dans la liste déroulante Detection Method (Méthode de détection) dans la vue tabulaire Community . Une seule méthode peut être utilisée à la fois.

Louvain

La méthode de détection Louvain est un algorithme d'agrégation hiérarchique qui détecte les communautés dans les réseaux étendus. Cette méthode évalue la densité des connexions entre les entités d'une communauté et compare ce résultat à la façon dont les entités seraient connectées dans un réseau aléatoire. Il s'agit de la méthode par défaut sélectionnée à l'ouverture de la table Community (Communauté).

Si les relations au sein d'une communauté sont plus denses qu'elles le seraient dans un réseau aléatoire, la modularité est positive. La modularité augmente en même temps que la densité des relations dans la communauté.

Cette méthode commence par détecter les petites communautés en optimisant la modularité. La modularité mesure la qualité de la division des nœuds dans les communautés. Si les relations dans une communauté sont plus denses qu'elles le seraient dans un réseau aléatoire, la modularité est positive et les entités sont placées dans une communauté. Plus les relations sont denses dans une communauté, plus le score de modularité est élevé.

Le processus est répété de façon itérative, évaluant les communautés de taille croissante avec des attributions communautaires aléatoires.

Girvan-Newman

La méthode de détection Girvan-Newman identifie les communautés en prenant en compte le niveau d'intermédiarité des relations qui connectent les communautés entre elles. Les chemins les plus courts sont calculés entre toutes les entités du graphe, et la centralité d’intermédiarité est calculée pour toutes les relations traversées. Les relations qui connectent des communautés distinctes ont la plus forte grande centrale d’intermédiarité car elles doivent être traversées plus souvent pour aller d'une communauté à une autre.

La relation présentant la centralité d’intermédiarité la plus grande est retirée du réseau. Au fur et à mesure que les relations centrales sont retirées, les communautés deviennent de plus en plus distinctes. Les relations sont retirées itérativement jusqu'à ce que toutes les relations restantes aient la même centralité d’intermédiarité.

Ce processus peut être relativement long pour les très gros diagrammes de liens.

Biconnecté

La méthode biconnectée recherche les communautés du réseau qui sont connectées entre elles. Deux entités connectées par une relation font partie de la même communauté. D'autres entités appartiennent à la même communauté si des relations vous permettent d'aller de l'une à l'autre et si cela reste vrai après le retrait d'une des relations dans la communauté. Chaque entité peut appartenir à plusieurs communautés.

Dans cet exemple, C fait partie de trois communautés car il a une relation avec des entités de chaque communauté. Les entités A, B et C forment une communauté car chacune d'elle est connectée à l'autre et qu'elles demeurent connectées lorsque l'une des relations entre elles est retirée. Lorsque la relation entre C et D, ou C et E, ou C et F est retirée, D, E et F, respectivement, ne sont plus connectées à A et B, et ne font donc plus partie de la communauté A, B et C.

Faiblement connecté

Une communauté est faiblement connectée lorsque toutes les entités sont connectées entre elles par un chemin. Le sens des relations entre les entités dans le diagramme de liens n'est pas prise en compte. En d'autres termes, le diagramme de liens est évalué en tant que graphe non orienté.

Dans cet exemple, il y a deux communautés faiblement connectées. A, B, C, D, E et F forment une communauté et X, Y et Z en forment une autre. Chacune de ces communautés ont des relations qui connectent toutes les entités. Aucune relation ne connecte la communauté X, Y, Z à la communauté A, B, C, D, E, F.

Si chaque entité du graphe est connecté à chacune des autres entités de quelconque manière, le graphe tout entier est faiblement connecté.

Fortement connecté

Une communauté est fortement connectée lorsque toutes les entités de la communauté sont connectées entre elles et que le sens de la relation est pris en compte. En d'autres termes, le diagramme de liens est évalué en tant que graphe orienté.

Cela signifie que si vous partez de n'importe où dans la communauté et tracez un chemin qui respecte le sens de chaque relation, vous pouvez rejoindre toutes les entités de la communauté.

Dans cet exemple, la communauté X, Y, Z et la communauté A, B, C D sont fortement connectées car vous pouvez partir de n'importe quelle entité dans l'une ou l'autre des communautés et suivre les relations orientées pour rejoindre chacune des entités.

E et F sont des communautés à elles seules car elles ne sont connectées à aucune autre entité. Vous pouvez rejoindre F à partir de la communauté A, B, C, D mais vous ne pouvez ensuite pas atteindre la communauté plus large depuis F. De même, vous pouvez rejoindre la communauté A, B, C, D à partir de E, mais vous ne pouvez atteindre E depuis la communauté plus large.

Propagation des étiquettes

La méthode de détection par propagation des étiquettes est un algorithme qui détermine les communautés en fonction de la façon dont les informations circule dans le graphe. Une étiquette est d'abord attribuée aux entités. Puis, une entité sélectionnée de façon aléatoire évalue ses voisins et détermine quelle est l'étiquette utilisée par la plupart d'entre eux. L'entité met alors à jour son étiquette pour qu'elle corresponde à celle qu'ont la plupart de ses voisins. Ce processus d'évaluation de ses voisins et de mise à jour de son étiquette par l'entité est répété encore et encore.

Au bout de plusieurs itérations, les étiquettes ont tendance à devenir dominantes dans les communautés densément connectées et ont du mal à traverser le graphe vers d'autres régions moins connectées. Plus le nombre d'itérations utilisé est grand, plus les étiquettes ont de chance de passer d'une communauté densément connectées à une communauté faiblement connectée. Lorsque chaque nœud a une étiquette que la plupart de ses voisins ont, l'algorithme prend fin même si le nombre d'itérations indiqué n'a pas été atteint.

La méthode Propagation des étiquettes peut produire des ensembles de communautés différents chaque fois qu'elle est utilisée selon les options utilisées pour effectuer l'analyse. Vous pouvez changer le nombre de valeurs initiales utilisé pour initialiser un générateur de nombres aléatoires utilisé par l'algorithme, le nombre de solutions générées et le nombre d'itérations utilisées par l'algorithme pour produire chaque solution.

La table Community (Communauté) présente une agrégation de toutes les solutions produites par plusieurs exécutions. Vous pouvez voir les résultats de chaque exécution en triant la table Community (Communauté) à l'aide du champ Solution. Par défaut, 20 solutions sont produites. Les résultats de la première exécution sont associés à la partition 0, ceux à partir de la vingtième exécution sont associés à la partition 19 de la table.

Des réglages vous permettent de déterminer certains paramètres de la méthode Propagation des étiquettes. Cliquez sur le bouton Options de la barre d'outils en haut de la table Community (Communauté), puis cliquez sur l'en-tête Label Propagation (Propagation des étiquettes).

Ouvrir la table Community (Communauté)

Dans un diagramme de liens, les communautés d'entités sont déterminées par défaut au moyen de la méthode de Louvain et décrites dans la table Community (Communauté) Utilisez la liste déroulante Detection Method (Méthode de détection) pour choisir une autre méthode pour évaluer les communautés. Toutes les lignes de la table sont alors mises à jour pour afficher les propriétés des nouveaux résultats des communautés.

La table comporte une ligne par communauté. Les propriétés de chaque communauté sont affichées dans différents champs de la table.

• Solution- Affiché pour la méthode Propagation des étiquettes uniquement si l’option Show solution column (Afficher la colonne de solution) est cochée (par défaut). Ce champ fournit un identifiant pour chaque solution produite par la méthode Propagation des étiquettes.
• Community- Pour toutes les méthodes de détection des communautés exceptée Propagation des étiquettes, ce champ affiche un identifiant pour la communauté et est utilisé par défaut pour trier les lignes de la table. Pour la méthode de propagation des étiquettes, cette colonne affiche une valeur qui identifie une communauté dans une solution produite par cette solution.
• Count- Nombre d'entités dans la communauté.
• Entity- Nom d'affichage de chaque entité dans la communauté. Les cinq premières entités sont répertoriées par défaut. Si la communauté comprend plus de cinq entités, vous pouvez afficher les suivantes en cliquant sur +More (+Plus) en bas de la liste. Cliquez sur -Less (-Moins) pour afficher moins d'entités.
• Type- Type d'entité de chaque entité de la communauté. Les types des cinq premières entités sont répertoriés par défaut. Lorsque d'autres entités sont affichées dans la liste, leur type apparait aussi dans la colonne Type. Cliquez sur +More (+Plus) en bas de la liste Type pour afficher les suivants. Cliquez sur -Less (-Moins) pour afficher moins de types d'entité.

Pour afficher les communautés des entités dans un diagramme de liens, procédez comme suit :

1. Dans l’onglet Link Chart (Diagramme de liens) du ruban, dans le groupe Analyze (Analyser), cliquez sur Community (Communauté).

   La table Community (Communauté) s'ouvre. Le nom qui apparaît dans l’onglet pour l’affichage de la table Community (Communauté) identifie le diagramme de liens pour lequel les communautés ont été calculées. La méthode de Louvain utilisée par défaut. Les lignes de la table sont triées à l’aide du champ Community par défaut.

   

2. Cliquez sur la liste déroulante Detection Method (Méthode de détection), puis sur une autre méthode d'évaluation des communautés.

   Les communautés du diagramme de liens sont réévaluées et les lignes de la table mises à jour pour représenter les résultats.

Inclure des documents

Par défaut, les entités Document ne sont pas prises en compte pendant la détection des communautés si elles sont présentes dans le diagramme de liens. Vous pouvez néanmoins choisir de les inclure dans le calcul. Par exemple, vous pouvez déterminer si les documents connectés à certaines entités appartiennent aussi à ces communautés.

1. Cochez ou décochez la case Include documents (Inclure des documents) dans la barre d’outils en haut de la table Community (Communauté).

   • Cochée : inclut les entités Document lors de la détection des communautés. Les documents sont pris en compte et inclus dans leurs communautés respectives conformément à la méthode choisie.

   • Décochée : exclut les entités Document lors de la détection des communautés. Les documents ne sont ni pris en compte ni inclus dans les communautés. Il s'agit de l'option par défaut.

La table Community (Communauté) est mise à jour automatiquement pour refléter les modifications apportées à ce paramètre. Des entités Document sont ajoutées ou retirées de la table et les communautés sont automatiquement recalculées.

Identifier des communautés dans un diagramme de liens

Lorsque vous sélectionnez une ou plusieurs lignes dans la table Community (Communauté), toutes les entités présentes dans la communauté définie par ces lignes sont sélectionnées dans le champ Entity de la table et du diagramme de liens associé. Cliquez sur le numéro de ligne ou sur les valeurs des champs Community, Count ou Solution pour sélectionner une ligne dans la table.

Vous pouvez cliquer sur une ou plusieurs entités individuelles dans le champ Entity pour le sélectionner. De même, si vous sélectionnez une entité dans le diagramme de liens, elle est sélectionnée dans le champ Entity de la table Community (Communauté) correspondante. Avec la méthode de détection par propagation d'étiquettes, une entité peut apparaître dans plusieurs lignes de la table Community (Commuanuté) et être sélectionnée dans toutes les lignes où elle apparaît.

Vous pouvez cliquer sur un type d'entité dans le champ Type pour sélectionner toutes les entités de ce type dans la communauté.

1. Cliquez sur une ligne dans la table Community (Communauté) pour sélectionner les entités dans cette communauté.

   Les entités correspondantes sont sélectionnées dans le champ Entity et dans le diagramme de liens.

   

2. Cliquez sur un type dans le champ Type pour sélectionner toutes les entités de ce type dans la communauté.

   Les entités correspondantes sont sélectionnées dans le champ Entity et dans le diagramme de liens.

   

3. Cliquez sur une entité appropriée dans le champ Entity pour le sélectionner.

   L'entité est sélectionnée dans le champ Entity et dans le diagramme de liens.

   

4. Cliquez sur +More (+Plus) en bas de la liste d'entités dans le champ Entity ou en bas de la liste des types dans le champ Type pour afficher toutes les entités et tous les types d'une communauté.
5. Cliquez sur -Less (-Moins) en bas de la liste d'entités dans le champ Entity ou en bas de la liste des types dans le champ Type pour afficher moins d'entités et de types dans une communauté.

Recherche une entité dans la table Community (Communauté)

Il n'est parfois pas évident de savoir à quelle communauté appartient une entité d'intérêt. Vous pouvez rechercher une entité et la sélectionner dans la vue tabulaire Community (Communauté).

1. Cliquez dans la zone de texte de recherche sur la barre d'outils en haut de la table Community (Communauté).
2. Saisissez le nom d'affichage d'une entité dans le diagramme de liens.

   Les lignes de la table Community (Communauté) sont automatiquement filtrées pour n'afficher que les entités dont le nom d'affichage correspond au nom que vous avez saisi. Seules les lignes qui représentent les entités filtrées sont affichées dans la table.

   

3. Sélectionnez la communauté qui contient l'entité qui vous intéresse.
4. Cliquez sur le bouton Delete (Supprimer) dans la zone de texte de recherche pour effacer la recherche et voir toutes les lignes de la table Community (Communauté).

   Toutes les entités de la communauté sont visibles et sélectionnées. Toutes les communautés sont visibles dans la table.

Faire un filtre sur les types d'entité de la table Community (Communauté)

Par défaut, la table Community (Communauté) inclut tous les types d'entité dans le diagramme de liens. Pour les diagrammes de liens volumineux, la table peut afficher trop d’informations à traiter. Vous pouvez filtrer les types affichés dans la table afin d’afficher uniquement des types d’entité spécifiques dans leurs communautés respectives.

1. Cliquez sur le bouton Types dans la barre d’outils en haut de la table Community (Communauté).

   Une liste déroulante apparaît. Elle inclut tous les types d’entité du graphe de connaissances, même si les entités de ce type ne se trouvent pas dans le diagramme de liens. Tous les types d’entité sont cochés par défaut.

2. Dans la liste déroulante, cochez les types d’entité que vous voulez afficher dans la table Community (Communauté). Décochez les types d’entité que vous ne voulez pas afficher dans la table. Saisissez le nom d’un type d’entité que vous ne voyez pas dans la liste ; la liste des types d’entité est automatiquement filtrée et vous pouvez cocher ou décocher les types d’entité dans la liste filtrée.

   Le nombre total de types d’entité sélectionnés apparaît dans la barre d’outils, en regard du bouton Types.

Les entités de la table Community (Communauté) sont mises à jour automatiquement. Les entités associées aux types cochés apparaissent dans la table. Les entités associées aux types sélectionnées décochés sont retirées de la table.

Recalculer les communautés

Lorsque vous ouvrez la table Community (Communauté) pour la première fois, les communautés sont détectées et un message indiquant que les communautés sont à jour apparaît au bas de la table,

Après ajout et suppression d'entités et de relations dans un diagramme de liens, les communautés détectées précédemment risquent de ne plus refléter le contenu du diagramme. La table Community (Communauté) affiche alors un message indiquant sur les communautés ne sont pas à jour en bas de la table.

1. En bas de la vue tabulaire Community (Communauté), cliquez sur le bouton Refresh (Actualiser).

   Toutes les lignes sont retirées de la table Community (Communauté) et les nouvelles communautés sont recalculées.

Le message affiché en bas de la table indique que les communautés sont à jour.

Définit les options de propagation des étiquettes

La méthode Propagation des étiquettes vous donne un certain contrôle sur la détection des communautés dans le diagramme de liens.

Vous pouvez déterminer le nombre de solutions générées par cette méthode et le nombre d'itérations utilisées pour développer chaque solution. En outre, une valeur initiale peut être fournie pour initialiser un générateur de nombres aléatoires utilisé par l'algorithme. Avec des valeurs initiales différentes, différentes solutions peuvent être produites.

Une fois les paramètres définis dans le volet Options, mettez à jour la table Community (Communauté) pour recalculer les communautés.

1. Cliquez sur le bouton Options dans la barre d’outils en haut de la table Community (Communauté).

   Le volet Options apparaît.

2. Dans le volet Options, cliquez sur l'en-tête Label Propagation (Propagation des étiquettes) pour afficher les paramètres disponibles.
3. Dans la zone de texte Seed for random number generator (Valeur initiale du générateur de nombres aléatoires), saisissez une valeur.

   Le paramètre par défaut est zéro.

4. Dans la zone de texte Number of solutions (Nombre de solutions), saisissez le nombre de fois que l'algorithme doit être exécuté pour générer un ensemble de communautés pour le diagramme de liens.

   Le paramètre par défaut est 1.

   Lorsque Number of solutions (Nombre de solutions) est égal à 1, un ensemble de communautés est généré pour le diagramme de liens. Ces communautés sont associées à la valeur zéro dans le champ Solution. Lorsque Number of solutions (Nombre de solutions) est égal à 10, 10 ensembles de communautés sont générés pour le diagramme de liens et les communautés de la dixième exécution sont associées à la valeur 9 dans le champ Solution.

5. Dans la zone de texte Number of iterations (Nombre d'itérations), saisissez le nombre maximal d'itérations utilisé pour déterminer l'ensemble final de communautés pour une solution produite par l'algorithme de propagation des étiquettes.

   Le paramètre par défaut est 1 000.

6. La case à cocher Show solution column (Afficher la colonne de solution) vous permet de choisir si les communautés détectées peuvent être triées pour évaluer la solution produite par chaque exécution de l’algorithme.
   • Cochée : affiche le champ Solution. Il s’agit de l’option par défaut.
   • Décochée : n’affiche pas le champ Solution.
7. Dans le coin inférieur droit de la table Community (Communauté), cliquez sur le bouton Refresh (Actualiser)  pour voir les résultats mis à jour.