2.1. Graphe d’adjacence

10Ce graphe est représenté sur la figure 1. Les graphes sont des « modèles abstraits de dessins de réseaux reliant des objets » ; « Ces modèles sont constitués par la donnée de sommets (aussi appelés nœuds ou points, en référence aux polyèdres), et d’arêtes (aussi appelées liens ou lignes) entre ces sommets » [4].

Figure 1

Graphe d’adjacence de sec

Graphe d’adjacence de sec

11La vedette et chacun de ses synonymes sont représentés par un cercle bleu avec un diamètre plus ou moins grand en fonction du nombre de synonymes que chacun possède : c’est la valeur affichée à côté du cercle. Le rond bleu représentant sec est central et a le plus grand diamètre puisque sec a 67 synonymes. Nous observons aussi que dur, rude et sévère ont respectivement un diamètre de cercle proportionnel aux nombres 29, 22 et 19. Ces nombres représentent le nombre de liens synonymiques que le sommet de la vedette a avec les autres sommets.

12Ceci nous permet déjà de déduire que, dans le DES, sec est très fortement connecté avec certains synonymes qui sont liés entre eux et qui ont par conséquent beaucoup de synonymes en commun avec la vedette : outre dur, rude et sévère que nous avons cités, nous pouvons facilement déduire aussi que bourru, aride, maigre, désagréable, insensible, ingrat et pauvre sont fortement reliés à sec puisque la densité d’arêtes qui les entourent est importante.

13L’emplacement des sommets entre eux nous renseigne sur leur relation. Le calcul automatique réalisé par le système pour placer les sommets va rapprocher ceux qui ont beaucoup de liens et éloigner ceux qui en ont moins de façon à rendre le graphique le plus lisible possible. En effet, dur, rude, sévère, désagréable et bourru sont disposés à droite de la vedette, alors que aride, maigre, ingrat et pauvre sont à gauche : ils n’ont donc pas ou peu de liens entre eux. Insensible occupe une position médiane en haut.

14De plus, nous remarquons que les traits de couleur grise ont des largeurs différentes : ces dernières reflètent la force de la relation entre les synonymes, deux à deux.

15La force d’une relation est proportionnelle au calcul du nombre minimum de liens à supprimer dans le graphe pour que l’un des sommets ne soit plus accessible à partir de l’autre et inversement, autrement dit c’est le nombre de liens à supprimer pour obtenir deux graphes disjoints [5]. Plus le nombre de liens à supprimer est important, plus cela signifie que ces deux sommets ont de nombreux autres synonymes en commun. L’exemple simple de la figure 1b va nous permettre de comprendre. Pour ne plus pouvoir atteindre le sommet U2 à partir du sommet U7, nous devons enlever quatre arêtes (en pointillé bleu). De même entre les sommets U7 et U8, nous ne devons enlever que deux arêtes (tirets verts). Nous voyons ainsi que la relation entre U7 et U2 est plus forte que celle entre U7 et U8 [6].

Figure 1b

Force d’une relation selon la méthode Edge_connectivity de la librairie igraph

Force d’une relation selon la méthode Edge_connectivity de la librairie igraph

16Cela nous permet d’ajouter, en complément des déductions précédentes, que dur, rude, sévère, abrupt sont très liés puisqu’ils sont proches (sur la droite du graphe) et les liens entre eux sont forts. De même maigre, aride, pauvre et stérile à gauche du graphe sont assez proches les uns des autres.

2.2. Vision lexicographique

17Sec est répertorié dans le Trésor de la langue française (TLF) avec plus de 30 sens différents. Mais nous pouvons regrouper les sens en six acceptions principales comme le proposent Jacquet et al. (2005) et Venant (2004) :

18

1. qui ne contient pas d’eau : « la route était sèche » ;
2. maigre, décharné : « un vieil homme sec et ridé » ;
3. stérile, improductif : « rester sec à un examen » ;
4. insensible, sévère, égoïste : « un homme au cœur sec » ;
5. brusque, abrupt : « donner un coup sec » ;
6. simple, seul : « avoir un atout sec dans son jeu ».

19L’ensemble des sens est décrit comme une « ressemblance de famille » avec six sens qui se recouvrent en partie. Nous voyons bien que l’étude du graphe d’adjacence nous apporte des informations qui confortent la représentation lexicographique donnée dans le dictionnaire puisque nous y retrouvons comme synonymes les plus représentatifs : maigre, abrupt, insensible et sévère. Simple et seul en revanche apparaissent en bas du graphique avec peu de synonymes : ils ne sont donc pas visibles et c’est pourtant une signification de sec à souligner.

20En comparaison, Le Grand Robert [7] propose quatre catégories : I avec la notion de concret, II avec la notion d’abstrait, III en tant que nom et IV en tant qu’adverbe. Dans la catégorie I (concret), nous avons neuf subdivisions :

21

• qui n’est pas ou peu imprégné de liquide ;
• qui n’est plus mouillé ou humide ;
• déshydraté, séché (suite à un traitement) : « fruits secs » ;
• qui n’est pas accompagné du liquide auquel il est généralement associé : « mur de pierres sèches », « toux sèche » ;
• non accompagné d’un autre élément : « pain sec » ;
• qui est peu charnu, qui a peu de graisse : « corps sec » ;
• qui est peu étoffé, manque d’ampleur : « contours très précis, secs » ;
• tissu, lainage sec, à tissage bien marqué ;
• vins secs, peu sucrés.

22Dans la catégorie II (abstrait) :

23

• froid, indifférent, insensible, pincé ;
• aigre, désobligeant, glacial ;
• rébarbatif, rebutant, revêche.

24Dans la catégorie III (en tant que nom) :

25

• sécheresse : le sec et l’humide.

26Dans la catégorie IV (en tant qu’adverbe) :

27

• brutalement, rapidement, rudement, sèchement : « qui claque sec », « laisser tomber tout sec ».

28Dans le graphe d’adjacence, nous remarquons que sec en tant qu’adverbe n’est pas représenté mais les autres catégories du Grand Robert le sont. Cela peut sembler surprenant étant donné que le DES ne fait pas de distinction de catégorie grammaticale.

29Nous allons maintenant étudier l’espace sémantique de sec tel qu’il se présente à ce jour dans le DES.

2.3. La création des cliques et l’espace sémantique

30Comprendre l’espace sémantique en 2D accessible en ligne [8] peut paraître difficile dans un premier temps. Pour cela, nous avons réalisé une présentation détaillée du calcul (voir Chardon 2020) et un tutoriel proposant une méthode d’investigation en prenant comme exemple l’adjectif curieux [9].

31Le calcul se fonde sur la publication de Ploux & Victorri (1998) qui détaille la métrique du χ². En effet, nous partons de la matrice d’appartenance des mots aux cliques. Les cliques sont des sous-ensembles du graphe dont les sommets sont tous reliés entre eux. L’algorithme utilisé dans le cadre de l’espace sémantique du DES est celui de Bron-Kerbosch (Bernard & Seba 2018).

32Cet algorithme récursif [10] se présente ainsi :

• algorithm BronKerbosch1(R, P, X) is
  • if P and X are both empty then
    • report R as a maximal clique
  • for each vertex v in P do
    • BronKerbosch1(R ⋃ {v}, P ⋂ N(v), X ⋂ N(v))
    • P := P \ {v}
    • X := X ⋃ {v}

33

• L’ensemble R contient la clique partielle à un instant t.
• L’ensemble P contient les nœuds candidats pour agrandir la clique partielle.
• L’ensemble X contient les nœuds ayant déjà été visités pour la construction de la clique.

34Tant que P et X ne sont pas vides, un candidat potentiel (v) est sélectionné dans P et l’algorithme est relancé avec R auquel on ajoute l’élément v et avec P et X tenant compte des voisins de v (N(v)). Une fois l’ensemble des cliques calculé, la matrice d’appartenance des mots aux cliques se présente comme nous le montre la figure 2.

Figure 2

Matrice d’appartenance des mots aux cliques

Matrice d’appartenance des mots aux cliques

35Cette matrice M est composée des coefficients C_iM_j égaux à 0 ou 1 selon si le mot M_j appartient à la clique C_i. Ensuite une nouvelle matrice Q composée des coefficients X_ij est calculée en fonction de ces coefficients C_iM_j divisés par la somme totale, X, et les racines carrées des sommes marginales selon la formule de la figure 3.

Figure 3

Calcul des coefficients de la matrice Q selon la métrique du χ² [11]

Calcul des coefficients de la matrice Q selon la métrique du χ² [11]

36Cette matrice Q est ensuite décomposée en valeurs singulières [12] correspondant aux produits de trois matrices qui vont servir à calculer les coordonnées des mots et des cliques dans un espace à deux dimensions (voir Chardon 2020).

37Un espace sémantique (Poudat & Landragin 2017 : 103-121) est une représentation graphique issue d’une réduction des données de départ. L’objectif est de déformer le moins possible ces dernières de façon à mieux rendre compte de leur structure. Dans notre exemple, les données de départ sont regroupées dans la matrice d’appartenance montrant l’appartenance de sec et de ses synonymes aux différentes cliques comme indiqué ci-dessus. Elles sont réduites en plusieurs facteurs dont les deux principaux, qui vont donner le maximum d’information des données initiales, sont représentés par les axes X et Y.

38Pour chaque axe, on va en premier lieu repérer les points qui s’opposent le plus, c’est-à-dire ceux qui sont les plus éloignés du centre, parce qu’ils vont permettre au mieux d’apprécier les contrastes. Dans la figure 4, nous avons d’un côté de l’axe Y mais assez proches du centre rude, dur, bourru et sévère et de l’autre, plus éloignés, maigre, osseux et squelettique. Nous voyons également que, partant de maigre vers le centre, nous avons aride, pauvre, ingrat. Cet axe Y met en opposition les sens concrets et les sens abstraits de sec.

Figure 4

Espace sémantique de sec

Espace sémantique de sec

39L’axe X, de son côté, met en évidence un autre sens concret de sec : simple, seul (vin ou vol sec). Les points les plus proches du centre (rude, dur, bourru et sévère) sont les plus proches de la « moyenne » : ils s’attirent et sont fortement corrélés. Ils représentent les synonymes les plus nombreux, fortement reliés entre eux par les cliques.

40Ce qui compte donc pour comprendre un espace sémantique est d’observer l’emplacement des points par rapport aux axes (éloignés, proches du centre) et les regroupements de points qui vont mettre en évidence des rapprochements de sens.

41Poudat & Landragin (2017 : 111) signalent toutefois que la représentation en 2D pose un problème, qui peut être partiellement réglé par une représentation en 3D :

42

C’est donc en observant la position des points sur les axes qu’on peut commencer à interpréter les facteurs. Pourtant un problème majeur se pose à ce stade : la position des points sur un plan factoriel peut être trompeuse.
En effet, on doit garder à l’esprit que la localisation des points sur un plan ne permet pas d’évaluer la distance réelle entre ces points. La visualisation des variables sur les axes linéaires de l’ACP [analyse en composantes principales] entraîne potentiellement des biais : deux variables proches, voire presque recouvertes, quand elles sont projetées sur deux axes peuvent en effet s’avérer très éloignées l’une de l’autre dans l’espace.
Observer les descripteurs dans un espace à trois dimensions peut visuellement apporter davantage d’information sans toutefois résoudre le problème.

43Nous avons récemment mis en place une version test 3D [13] dans le DES. Celle-ci apporte une vision enrichie et affiche quatre « groupes de sens » :

44

1. sans-cœur, indifférent, insensible ;
2. blessant, abrupt, désagréable ;
3. désertique, stérile, aride ;
4. maigre, squelettique, émacié.

45On constate cependant que le groupe représenté par simple et seul n’est pas aussi clairement visible : cet espace sémantique apparaît entre celui de blessant d’un côté et celui de désertique de l’autre sans toutefois être distinctement délimité.

46Nous souhaitons maintenant passer en revue d’autres méthodes de regroupement (ou clustering) réalisées directement sur le graphe d’adjacence afin de les comparer avec celle de l’espace sémantique du DES.

3.1. L’algorithme Multilevel

48Cet algorithme est issu de la publication de Blondel et al. (2008). Il est également appelé l’algorithme de Louvain (les auteurs étant rattachés à l’université de Louvain en Belgique).

49

La méthode permet d’effectuer le partitionnement d’un réseau en optimisant la modularité. La modularité est une valeur comprise entre -1 et 1 qui mesure la densité d’arêtes à l’intérieur des communautés (regroupements de sens) comparée à celle des arêtes reliant les communautés entre elles [16].

50Il s’agit d’un algorithme ascendant : au départ, chaque sommet appartient à une communauté distincte, et les sommets sont déplacés entre les communautés de manière itérative de façon à maximiser la contribution locale des sommets au score global de modularité. Lorsqu’un consensus est atteint (c’est-à-dire qu’aucun mouvement n’augmenterait le score de modularité), chaque communauté dans le graphique original est réduite à un seul sommet (tout en conservant le poids total des arêtes adjacentes) et le processus se poursuit au niveau suivant. L’algorithme s’arrête lorsqu’il n’est plus possible d’augmenter la modularité après avoir réduit les communautés aux sommets.

51On dit que cet algorithme fonctionne presque en temps linéaire sur des graphiques clairsemés.

52Sur sec, cela donne le résultat de la figure 5.

Figure 5

Regroupements des nœuds du graphe de sec avec l’algorithme Multilevel

Regroupements des nœuds du graphe de sec avec l’algorithme Multilevel

53Nous remarquons six clusters différents :

54

1. en vert autour de dur, sévère, rude, aigre, bourru, brusque ;
2. en bleu foncé avec maigre, décharné, squelettique ;
3. en bleu clair représenté par aride, pauvre, ingrat, stérile, asséché ;
4. en rouge avec désagréable, blessant, rebutant, déplaisant, acerbe ;
5. en jaune avec insensible, froid, indifférent ;
6. en magenta avec pur, simple et seul.

55On retrouve de façon assez prononcée les mêmes catégories de sens que celles citées à la section 2.2 « Vision lexicographique ». Deux remarques s’imposent toutefois :

56

• l’absence d’eau (« la route était sèche ») apparaît dans le cluster 3 mais elle est peu représentative de ce dernier (asséché et séché ont peu de relations) ;
• le cluster 4 (désagréable, blessant…) et le cluster 5 (insensible, froid, indifférent) se retrouvent dans la catégorie 4 de Jacquet et al. (2005) et Venant (2004), laquelle est représentée par l’exemple « un homme au cœur sec » (voir section 2.2).

3.2. L’algorithme Infomap

57Cet algorithme se fonde sur deux publications, l’une de Rosvall & Bergstrom (2008) et l’autre de Rosvall et al. (2009), et le lien sur son implémentation dans la librairie igraph est donné dans la sitographie.

58L’idée de base derrière l’algorithme Infomap [17] est d’utiliser l’image d’une personne se déplaçant aléatoirement d’un sommet à un autre. Par analogie avec une carte routière, la probabilité de rester longtemps, après un certain nombre de choix, dans une communauté sera d’autant plus grande que les sommets dans cette communauté sont fortement connectés. De même que, sur un chemin ou une route, un marcheur aventureux aura plus de chance de voyager à l’intérieur d’une région où les villes et villages sont très connectés entre eux. Si le graphe est aléatoire, aucune communauté ne sera détectée puisque le marcheur se déplacera au hasard des chemins rencontrés qui ne seront pas plus nombreux à un endroit qu’à un autre.

59Chaque sommet est codé à différents niveaux à l’aide de préfixes. Un préfixe est un terme utilisé dans plusieurs domaines [18]. Nous l’utilisons ici dans le domaine des réseaux informatiques dans le sens de routage [19]. Par analogie à une adresse postale, un numéro de rue n’a de sens que par rapport au nom de cette rue qui elle-même n’a de sens que par rapport à un arrondissement (dans les grandes villes) lui-même identifié par le nom de la ville dans laquelle il est, ville qui elle-même se situe dans un pays donné.

60Une optimisation est nécessaire : lorsque les sommets ne sont codés qu’à un seul niveau, alors il y a trop peu de communautés. Si, au contraire, les sommets sont codés avec de nombreux préfixes, les communautés sont trop nombreuses. Nous devons donc trouver une partition optimale qui assigne des nœuds aux communautés de façon à réduire au minimum l’information nécessaire pour comprimer le mouvement de nos marcheurs aléatoires.

61L’algorithme Infomap et celui fondé sur la modularité (Multilevel) sont deux exemples de méthodes optimales de détection de communauté : ils ont chacun une fonction de qualité et recherchent ensuite dans l’espace des partitions graphiques pour trouver la partition qui optimise cette fonction de qualité. La différence réside dans la fonction de qualité : Infomap se concentre sur les informations nécessaires pour comprimer le mouvement de la marche aléatoire, tandis que Multilevel définit les communautés en fonction de la densité des arêtes (une communauté contient un nombre d’arêtes supérieur au nombre dû au hasard [20]).

62À nouveau, dans la figure 6, nous obtenons six clusters :

63

1. dur, rude, sévère, aigre, insensible, froid, indifférent en rouge ;
2. aride, pauvre, ingrat, stérile en bleu foncé ;
3. maigre, décharné, squelettique en vert ;
4. fauché, désargenté, impécunieux en bleu clair ;
5. séché, desséché, racorni en jaune ;
6. simple, seul, pur en magenta.

Figure 6

Regroupement des nœuds du graphe de sec avec l’algorithme Infomap

Regroupement des nœuds du graphe de sec avec l’algorithme Infomap

64Le cluster 4 avec désagréable, blessant, rebutant, déplaisant, acerbe de l’algorithme Multilevel a laissé sa place à fauché, désargenté et impécunieux. Les autres clusters sont similaires entre les deux méthodes.

3.3. L’algorithme Fastgreedy

65Cet algorithme se fonde sur la publication de Clauset et al. (2004) et le lien sur son implémentation dans la librairie igraph est donné dans la sitographie.

66Il fusionnera deux communautés actuelles de manière itérative, dans le but d’obtenir le maximum de gain de modularité au niveau local optimal. Il regroupe donc les nœuds individuels en communautés d’une manière qui maximise le plus (greedily = « goulûment ») le score de modularité du graphique [21].

67Cela donne le dendrogramme (c’est-à-dire une représentation sous forme d’arbre) de la figure 7.

Figure 7

Regroupement des nœuds du graphe de sec avec l’algorithme Fastgreedy

Regroupement des nœuds du graphe de sec avec l’algorithme Fastgreedy

68Les rectangles colorés montrent bien les six clusters qui sont relativement proches des deux précédemment étudiés.

69L’inconvénient de cette méthode est que les petites communautés vont être regroupées avec les plus grandes même si elles sont bien formées. Et c’est effectivement ce que l’on voit : l’algorithme renvoie un nombre optimal de clusters de trois. Or les deux clusters, pur-seul-simple d’un côté et impécunieux-fauché-désargenté-pauvre de l’autre, sont très vite « absorbés » dans les autres clusters et passent quasiment inaperçus.

70D’autre part, on remarque que les synonymes avec peu de relations (pincé : 1 ; séché : 2 ; et aussi asséché, essuyé et desséchant : 1…) ne sont pas traités : ils sont raccordés bien en aval, vers la fin du dendrogramme de façon incohérente.

71Si nous souhaitons avoir une vue sous forme de six regroupements et non de dendrogramme hiérarchique, nous obtenons le graphique de la figure 8 :

Figure 8

Graphe de sec avec l’algorithme Fastgreedy avec six clusters

Graphe de sec avec l’algorithme Fastgreedy avec six clusters

72Nous y voyons bien les quatre principaux regroupements :

73

1. bleu : désagréable, blessant, rebutant ;
2. vert : dur, sévère, rude ;
3. rouge : pauvre, simple, désargenté ;
4. jaune : aride, desséché, maigre.

74Les deux derniers regroupements sont plus difficiles à déceler puisqu’ils contiennent un seul sommet :

75

5. racorni en magenta (en bas et légèrement à gauche dans le graphique) ;
6. séché en bleu clair (en bas et légèrement à droite dans le graphique) [22].

76Cela correspond parfaitement à une coupe droite verticale dans le graphique du dendrogramme à l’endroit où l’on coupe six lignes horizontales.

3.4. L’algorithme Walktrap

77Cette méthode issue de la publication de Pons & Latapy (2005) est une approche fondée sur une marche aléatoire. L’idée générale [23] est que si vous effectuez une marche aléatoire dans le graphique, en choisissant sur chaque sommet un des chemins vers un autre sommet de façon arbitraire, alors votre marche est plus susceptible de rester dans la même communauté parce qu’il n’y a que quelques chemins qui mènent en dehors de celle-ci.

78Cet algorithme est donc fondé sur le principe de la marche aléatoire comme l’algorithme Infomap. Mais ici on va se focaliser sur la probabilité pour chaque sommet d’être le passage obligé du marcheur s’il est très connecté aux autres sommets (son degré est élevé). Au départ, chaque sommet est une communauté, qui sont ensuite regroupées étape par étape jusqu’à former une seule communauté. Puis la mesure de la modularité permet de couper le dendrogramme pour obtenir la partition la plus adaptée.

79Walktrap fait de courtes marches aléatoires de 3-4-5 pas (selon l’un de ses paramètres) et utilise les résultats de ces marches aléatoires pour fusionner des communautés séparées d’une manière ascendante comme Fastgreedy.

80L’algorithme détecte de façon optimale six clusters (champ « optimal_count ») représentés sur la figure 9 ci-dessous assez représentatifs de la vision lexicographique développée précédemment (voir section 2.2) :

81

1. qui ne contient pas d’eau (« la route était sèche ») : cluster bleu foncé ;
2. maigre, décharné (« un vieil homme sec et ridé ») : cluster vert ;
3. stérile, improductif (« rester sec à un examen ») : à nouveau le cluster bleu foncé ;
4. insensible, sévère, égoïste (« un homme au cœur sec ») : cluster jaune (sauf sévère) ;
5. brusque, abrupt (« donner un coup sec ») : cluster rose ;
6. simple, seul (« avoir un atout sec dans son jeu ») : cluster magenta.

Figure 9

Regroupement des nœuds du graphe de sec avec l’algorithme Walktrap

Regroupement des nœuds du graphe de sec avec l’algorithme Walktrap

82Les 1^er et 3^e groupes de sens sont réunis dans le cluster bleu foncé. Le sens de impécunieux, fauché, désargenté en bleu clair qui est aussi un sens de sec (manquer d’argent = « être sec ») n’apparaît pas dans l’analyse lexicographique.

83Nous pouvons mieux visualiser les six regroupements dans le graphique ci-dessous (figure 10).

Figure 10

Graphe de sec avec les six clusters de l’algorithme Walktrap

Graphe de sec avec les six clusters de l’algorithme Walktrap

3.5. L’algorithme Spinglass

84Cette méthode exposée dans la publication de Reichardt & Bornholdt (2006) est fondée sur la recherche des graphes hamiltoniens, du nom de son concepteur William Rowan Hamilton, astronome royal en Irlande au XIX^e siècle. « […] un chemin hamiltonien d’un graphe orienté ou non orienté est un chemin qui passe par tous les sommets une fois et une seule » [24]. Une analogie peut être proposée avec la tournée d’un facteur pour distribuer le courrier qui s’arrête une et une seule fois devant chaque boîte aux lettres. « Un cycle hamiltonien est un chemin hamiltonien qui est un cycle », c’est-à-dire que le sommet d’arrivée est celui de départ. « Un graphe hamiltonien est un graphe qui possède un cycle hamiltonien » [25].

85On va donc rechercher tous les sous-graphes dans lesquels il existe un chemin qui passe par tous les nœuds une seule fois avant de revenir à son point de départ. Autrement dit, ces sous-graphes représentent des communautés, des groupes de nœuds fortement interconnectés qui ne sont que faiblement connectés au reste du réseau. Le calcul part donc du principe qu’il faut regrouper ce qui est lié et séparer ce qui ne l’est pas. Il doit donc : a) récompenser les bords internes entre les nœuds d’un même groupe (dans le même état de rotation) et b) pénaliser les bords manquants (les non-liens) entre les nœuds d’un même groupe. En outre, il devrait c) pénaliser les arêtes existantes entre différents groupes (nœuds dans différents états de rotation) et d) récompenser les non-liens entre différents groupes.

86Dans notre exemple, nous obtenons le résultat de la figure 11 :

Figure 11

Regroupement des nœuds du graphe de sec avec l’algorithme Spinglass

Regroupement des nœuds du graphe de sec avec l’algorithme Spinglass

87Nous obtenons six clusters sensiblement identiques aux méthodes précédentes.

88

1. simple, pur et seul en bleu clair ;
2. sévère, dur, rude en gris ;
3. ingrat, aride, pauvre, stérile en vert ;
4. désagréable, blessant, rebutant, acerbe en rouge ;
5. insensible, froid, glacial en magenta ;
6. maigre, décharné, desséché en bleu foncé.

89On remarque toutefois un minuscule cluster en jaune avec concis difficilement compréhensible.

3.6. L’algorithme Edge_betweenness

90Il s’agit d’un partitionnement issu de Girvan & Newman (2002) et fondé sur l’intermédiarité des liens. À chaque itération, l’intermédiarité des liens est calculée. Ceux ayant le score le plus élevé sont supprimés. L’opération est répétée jusqu’à rendre le graphe non connexe [26].

91L’intermédiarité est « égale au nombre de fois que ce sommet est sur le chemin le plus court entre deux autres nœuds quelconques du graphe. Un nœud possède une grande intermédiarité s’il a une grande influence sur les transferts de données dans le réseau, sous l’hypothèse que ces transferts se font uniquement par les chemins les plus courts » [27].

92C’est un processus de décomposition hiérarchique où les arêtes sont supprimées dans l’ordre décroissant de leur intermédiarité. Ceci est motivé par le fait que les arêtes reliant les différents groupes sont plus susceptibles d’être contenues dans de multiples chemins les plus courts simplement parce que, dans de nombreux cas, elles sont la seule option pour passer d’un groupe à un autre. Cette méthode donne de bons résultats, mais elle est très lente en raison de la complexité des calculs d’entre-distance et parce que les scores d’entre-distance doivent être recalculés après chaque enlèvement d’arête. Les graphes à traiter avec cette méthode ne doivent pas dépasser environ 700 sommets et 3 500 arêtes : c’est la limite supérieure de la taille des graphiques qu’il est possible d’analyser avec cette approche [28].

93Avec cette méthode, nous obtenons le graphique de la figure 12 :

Figure 12

Regroupement des nœuds du graphe de sec avec l’algorithme Edge_betweenness

Regroupement des nœuds du graphe de sec avec l’algorithme Edge_betweenness

94De façon optimale, quinze clusters sont détectés. En réalité, en étudiant ce résultat, on se rend compte que cinq de ces clusters, colorés sur l’image, correspondent à la classification des sens décrite dans la section 2.2 telle que proposée par Venant (2004) et Jacquet et al. (2005). Les deux groupes de synonymes non colorés n’ont pas été pris en compte correctement :

95

• d’une part, déplaisant, désobligeant, endurci, indifférent, sans-cœur, égoïste devraient plutôt rejoindre le cluster rose et ce dernier aurait dû être séparé en deux, insensible, sévère, égoïste d’une part et brusque, abrupt de l’autre ;
• d’autre part, en bas du graphique :
  • simple aurait dû rejoindre le cluster magenta,
  • racorni, séché, essuyé, desséchant et asséché auraient dû rejoindre le cluster bleu foncé,
  • enfin, concis et pincé le cluster rose (insensible, sévère…).

96Parmi ces synonymes en bas du graphique, certains n’ont qu’une, voire deux, liaisons synonymiques (sur la figure 12, « séché 2 » veut dire que séché n’a que deux liaisons synonymiques, « asséché 1 » veut dire qu’asséché n’en a qu’une seule). Cela explique en partie du moins le traitement moins efficace réalisé par cette méthode.

97Comme pour les dendrogrammes des algorithmes Fastgreedy et Walktrap, si nous coupons le dendrogramme Edge_betweenness avec une ligne verticale de façon à produire six clusters, nous obtenons le graphique de la figure 13 :

Figure 13

Graphe de sec avec les six clusters de l’algorithme Edge_betweenness

Graphe de sec avec les six clusters de l’algorithme Edge_betweenness

98Le graphique montre :

99

• un regroupement principal en rouge qui comprend quasiment tous les mots et tous les sens de sec : rude, maigre, bref, indifférent sans distinction ;
• cinq autres regroupements représentés par un seul mot chacun : asséché, desséchant, essuyé, pincé et concis.

100Ce découpage ne peut pas ainsi être représentatif des différentes définitions de sec de la section 2.2.

3.7. L’algorithme Eigenvector

101Cette méthode se fonde sur la publication de Newman (2006). Elle utilise la notion de vecteurs propres pour détecter la structure de la communauté. Cependant, elle ne fonctionne pas bien sur des graphes dégénérés. « Un graphe est k-dégénéré si tout sous-graphe contient un nœud de degré inférieur ou égal à k, et la dégénérescence d’un graphe est le plus petit k tel qu’il est k-dégénéré » [29]. Dans les graphes d’adjacence du DES pour une vedette, nous avons une proportion non négligeable de graphes 1-dégénérés c’est-à-dire qu’un synonyme est relié uniquement à la vedette.

102Effectivement, comme nous pouvons le constater dans la figure 14, même si nous précisons un nombre de clusters de six, nous n’en obtenons que deux, pas suffisamment représentatifs de la classification lexicographique de Venant (2004) et Jacquet et al. (2005).

Figure 14

Regroupements des nœuds du graphe de sec avec l’algorithme Eigenvector

Regroupements des nœuds du graphe de sec avec l’algorithme Eigenvector

3.8. L’algorithme de modularité optimale

103Cette fonction, qui s’appuie sur Good et al. (2010), utilise le « GNU Linear Programming Kit » (GLPK) pour résoudre un problème d’optimisation de grands entiers afin de trouver le score de modularité optimal et la structure de communauté correspondante. Le GLPK est un solveur libre et open source constitué d’un ensemble d’outils et de méthodes utilisables à partir d’un langage de programmation (C, Java, Python) pour trouver la solution de problèmes complexes. Dans cet algorithme, nous cherchons à calculer les clusters par lesquels la modularité, qui mesure la qualité du partitionnement, sera optimale [30]. Cet algorithme fonctionne pour des graphiques de moins de 100 sommets car son exécution est longue [31].

104Sur notre exemple qui possède moins de 100 sommets et après plusieurs minutes d’exécution, nous obtenons le résultat de la figure 15 :

Figure 15

Regroupement des nœuds du graphe de sec avec l’algorithme de modularité maximale

Regroupement des nœuds du graphe de sec avec l’algorithme de modularité maximale

105Nous obtenons un résultat assez proche de l’algorithme de Louvain :

106

1. dur, sévère, rude de couleur verte ;
2. maigre, décharné, squelettique en rouge ;
3. aride, pauvre, ingrat, stérile en jaune ;
4. désagréable, blessant, rebutant en bleu foncé ;
5. insensible, froid, indifférent en magenta ;
6. simple, seul et pur en bleu ciel.

107Ce résultat caractérise dans son ensemble les différents sens de sec donnés dans le dictionnaire TLF.