WOW !! MUCH LOVE ! SO WORLD PEACE !
Fond bitcoin pour l'amélioration du site: 1memzGeKS7CB3ECNkzSn2qHwxU6NZoJ8o
  Dogecoin (tips/pourboires): DCLoo9Dd4qECqpMLurdgGnaoqbftj16Nvp


Home | Publier un mémoire | Une page au hasard

 > 

Agrégats de mots sémantiquement cohérents issus d'un grand graphe de terrain


par Christian Belbèze
Université Toulouse 1 Capitole - Doctorat en informatique 2012
  

précédent sommaire suivant

3.4 Méthode 3 : Rigidification Régulée

Cette méthode est une évolution notable de la Rigidification Simple. Elle est aussi inspirée par les travaux sur la rigidification de Hoffman et al. [Hoffman&al-1997]. Afin d'améliorer la qualité des agrégats nous avons fait évoluer les règles gérant l'opérateur d'extension et plus précisément les règles de maintien des liaisons entre les noeuds.

3.4 : Méthode 3 : Rigidification Régulée 101

Chapitre 3. Les méthodes d'agrégations proposées

3.4.1 Dans quel but une nouvelle méthode améliorée ? Apprentissage

Les deux méthodes précédentes sont avant tout présentées comme des moyens ayant permis de construire cette troisième proposition. L'expérimentation de l'algorithme de Rigidification Simple (voir chapitre 4) et une meilleure connaissance du graphe permettent de formuler quatre observations :

1. Il existe un seuil de rupture de la validité sémantique des agrégats ;

2. les valeurs de Val-Min-CFL et de Val-Activ-CFL sont délicates à déterminer ;

3. la suppression des mots vides et/ou très courants casse des structures ;

4. les mots rares jouent un rôle disproportionné dans la construction d'agrégats.

Il est primordial de bien comprendre ces quatre points pour mesurer l'évolution entre la Rigidification Simple et la Rigidification Régulée.

Seuil de rupture de la validité sémantique

La validation de la méthode précédente nous a apporté plusieurs informations. Mais la plus importante est ce que nous nommons le « seuil de rupture de validité sémantique ». Au-delà de ce seuil, et ceci d'un point de vue statistique, nous notons un très fort affaiblissement de la cohérence sémantique telle que nous la mesurons. Ce seuil se situe, pour nos graphes de test AOL 17/04/2006 et AOL 17/03/2006 entre 30 et 40 mots. Il peut être considéré, comme l'équivalent du nombre de Dunbar dans les réseaux sociaux [Dunbar-1992]. Dunbar a émis l'hypothèse en 1992 que le nombre de personnes avec qui un être humain pourrait entretenir des relations durables serait limité. À partir de travaux menés sur des primates, il a estimé ce nombre autour de 150. On peut aussi faire un parallèle avec le seuil d'expansion des requêtes en science de la recherche d'informations. Harman a démontré que les requêtes devenaient moins performantes si l'on ajoutait plus de 20 à 40 mots [Harman-1992]. Ce chiffre a été validé plus tard par Boughamen M. et Soulé-Dupuy C. [Boughamen-1997].

Les valeurs de Val-Min-CFL et de Val-Activ-CFL sont délicates à déterminer

La connaissance du seuil de rupture permet la conception d'un algorithme dans lequel il n'est pas nécessaire de fixer les valeurs de seuil Val-Min-CFL et de Val-Activ-CF de manière arbitraire et définitive. En effet ces seuils peuvent prendre des valeurs extrêmement différentes d'un agrégat à l'autre. L'utilisation de valeurs trop élevées fait perdre des agrégats et l'utilisation de valeurs trop faibles oblige à créer des agrégats de taille irréaliste. De plus, nous savons que statistiquement les agrégats d'une trop grande taille ont une faible cohérence sémantique. Il faut donc que l'algorithme adapte ces valeurs aux conditions locales, en limitant la taille des agrégats obtenus pour rester en deçà du seuil de rupture de la validité sémantique.

3.4 : Méthode 3 : Rigidification Régulée 102

Chapitre 3. Les méthodes d'agrégations proposées

La suppression des mots vides et/ou très courants casse des structures.

Dans les grands graphes de terrain la plupart des noeuds ont par nécessité fonctionnelle le besoin d'être connectés. Cela vaut aussi bien pour la distribution du courrier dans un village (réseau postal) que pour le fonctionnement d'un ordinateur (réseau internet). Pourtant certains noeuds n'utilisent pas ces liaisons simplement pour fonctionner mais deviennent des connecteurs. Ainsi le facteur du village ou le routeur sur le réseau ont pour rôle d'effectuer les liaisons dans le réseau. Il s'agit là d'une spécialisation fonctionnelle d'un noeud du graphe qui devient un noeud connecteur ou concentrateur.

On retrouve ce phénomène dans la plupart des grands graphes de terrain, dont les objets n'ont pas par nature une limitation du nombre de connexions. C'est une des explications que nous proposons à la grande disparité du nombre de liens connectés par noeud typique des grands graphes de terrain.

3.4 : Méthode 3 : Rigidification Régulée 103

Chapitre 3. Les méthodes d'agrégations proposées

a - Paris hub du réseau ferré français :
http://www.sncf.com

b - Les dix noeuds hubs les plus utilisés du graphe :
http://antipaedo.lip6.fr/Proceedings.pdf

 
 
 
 

c - Les hubs du trafic Internet 2006 : http://opte.org

d - Les personnages hubs du roman Les misérables de

V. Hugo :

http://networkdata.ics.uci.edu/data.php ?id=109

 
 
 

e - Les 1000 noeuds les moins utilisés qui sont en
diades avec le mot hub « sex » :
http://antipaedo.lip6.fr/Proceedings.pdf

f - Les hubs du réseau de vols commerciaux USA :
http://www.ce.berkeley.edu

 
 

Figure 3.7 : Quelques exemples ou extraits de graphes de terrains incorporant des noeuds hubs.

Un autre exemple possible serait celui d'un réseau de transport. Une grande ville comme Paris ne possède pas seulement des routes pour y accéder, mais elle est un hub important de connexions territoriales. Cela signifie que je vais passer à Paris alors que ce n'est

3.4 : Méthode 3 : Rigidification Régulée 104

précédent sommaire suivant