Structure d'un hypertexte sous forme matricielle

 

Position du problème

Le but est ici de passer des coefficients locaux à une représentation numérique globale. Pour cela on utilisera les représentations matricielles. L'exemple qui servira à fixer les idées est donné dans la figure 1.

Figure 1: un hypertexte constitué de cinq unités d'information et de trois concepts.

Un hypertexte est donné par les deux relations: document x descripteurs et documents x référents. Chacune de ces relations est donnée par une matrice, respectivement D et R.

Dans le cas de l'exemple:

La matrice du graphe "dérivé" constitué par les unités est (notée GU précédemment):

On sait que G*G donne les connexions constituées de chaînes de longueur 2. De même pour les puissances successives de G.

On notera que:

représente les référents que l'on peut obtenir à distance d'une unité. En particulier on voit que le concept c1 n'est pas accessible depuis aucune unité d'information.

Le but maintenant est de représenter la "probabilité" d'atteindre un certain type d'information, c'est-à-dire un concept c, à partir d'une unité u donnée.

Approche probabiliste

Si l'unité u possède c comme référent on donnera comme probabilité d'atteindre c via ce référent la valeur 1/D*(u). A cette valeur viendra s'ajouter la possibilité d'atteindre c via les unités d'informations liées. En formule:

Dans cette formule, u(c) vaut 1 si c est un "référent" de u et 0 sinon. Pour tenir compte du fait que l'information obtenue via d'autres unités d'information est moins accessible (et pour assurer la convergence de la suite en cas de boucle), on multipliera la somme par un facteur 1/2. C'est-à-dire:

 
(1)

Pour le calcul matriciel on introduit la matrice des référents où les coefficients d'une ligne sont divisés par le total de la ligne:

On fait de même pour D' (donc on pondère les lignes de R et les colonnes de D).

De même on considère la matrice du graphe pondérée:

La formule (1) devient:

et en utilisant la formule de la somme (1) de la série géométrique:

Dans le cas de l'exemple:

Son inverse vaut:

Cette matrice peut être interprétée comme une information de la circulation dans l'hypertexte et donc de sa structure. On la notera: S.

La matrice des coeffcients "référent" globaux sera:

Le coefficient de la ligne i et colonne j a pour interprétation la "facilité" (calculée à partir d'une probabilité) d'accès au je référent à partir de la ie unité d'information. Cette valeur dépend à la fois du nombre de référents contenus dans l'unité d'information et du nombre de "pas" à effectuer pour atteindre le concept donné. Notation: SR .

On peut faire de même du côté des descripteurs en calculant:

qui vaut dans le cas de l'exemple:

Le coefficient de la ligne i et de la colonne j indique la possibilité d'avoir atteint la ie unité d'information par le je concept. Notation: SD

Un autre exemple est donné par la figure 2.

Figure 2: un hypertexte constitué de trois unités d'information en boucle.

Dans ce cas on obtient le résultat suivant:

Un autre exemple est encore fourni par celui de la figure 3.

Figure 3: un hypertexte constitué de cinq unités d'information et de six concepts avec une "boucle".

Dans ce cas, on a les matrices associées suivantes:

La matrice de structure est:

et les matrices SR et SD sont:

En prenant 0.3 comme seuil, les trois matrices précédentes deviennent:

A partir de = (si,,j) il est possible de trouver des "composantes" de l'hypertexte et de mettre en évidence sa structure.

Les "composantes" de l'hypertexte

Pour chaque unité d'information Ui, on considère l'ensemble des unités d'information liées, c'est-à-dire les Uj telles que si,,j 0 ou si,,j 0.

Ensuite, il est possible de vérifier dans quelle mesure ces composantes sont disjointes par une technique du type analyse "cluster".

Structure de l'hypertexte

Le but est de visualiser les différents types d'unités d'information, sources, puits, etc. Pour cela, on passe en revue les unités d'information, ce qui revient à parcourir la diagonale de la matrice , et pour chaque unité U, à comptabiliser le nombre de valeurs nulles sur la ligne (nombre d'unités d'informations non atteintes depuis U) et le le nombre de valeurs nulles sur la colonne (nombre d'unités d'informations ne conduisant pas à U). Ces nombres permettent de définir des points (xU, yU) que l'on peut représenter sur un schéma cartésien.

Figure 4: représentation cartésienne des unités d'information d'un hypertexte avec M = |U| -1. Chaque unité d'information est placée en fonction de ses "coordonnées" (xU, yU) où: xU représente le nombre d'unités d'information non dépendantes de U et yU le nombre d'unités d'information ne conduisant pas à U. Les "puits" sont les unités d'informations sans descendant. Les "sources" sont les unités d'informations sans "ancêtre". Les unités d'information situées sur l'axe des x (yU = 0) sont des unités d'information qui proviennent de n'importe quelle autre. Les unités d'information situées sur l'axe vertical (xU = 0) sont celles qui conduisent à n'importe quelle autre. Les unités centrales sont celles qui, de façon équilibrée, ont "beaucoup" d'ancêtres et de descendants.

Dans le cas de l'hypertexte représenté dans la figure 3, avec la matrice calculée ci-dessus, ce schéma devient celui de la figure 5. Ces calculs peuvent facilement être automatisés.

Figure 5: représentation cartésienne des unités d'information de l'hypertexte de la figure 3.


xU yU
U1 3 4
U2 3 4
U3 3 1
U4 3 3
U5 3 3

 


1) est le produit de deux matrices dont la somme des de chaque ligne vaut 1. jouit donc de cette propriété. La somme de chacune de ses lignes vaut 1. (/ 2)' est donc la matrice d'une application contractante et la série des puissances converge. Ce résultat peut également être obtenu en notant que est la transposée d'une matrice de Markov.

 

   

(c) A. Favre, VisioSoft S.A. & L.-O. Pochon, IRDP, 2000