Modélisation de parcours du Web

Les réseaux sociaux

Les graphes sont utilisés couramment en sciences sociales pour modéliser des interactions entre individus. Les sommets représentent alors les entités ou individus, et les arêtes ou arcs une relation ou interaction entre eux.
Les réseaux acteurs Le graphe des acteurs est un graphe dont les sommets sont des acteurs et deux acteurs sont reliés s’ils ont joué ensemble dans un film [16, 12]. En 2000, la taille du graphe d’acteurs étudié était de 449 913 sommets [88]. Les données sont disponibles grâce à Internet Movie DataBase
Les réseaux de citations Le graphe des citations est un graphe dont les sommets sont des publications scientifiques et deux publications u et v sont liées par l’arc (u,v) si la publication u a cité en références la publication v. Dans [95], des études ont été réalisées sur un graphe de 783 339 sommets issu du catalogue de l’Institute for Scientific Information et un graphe de 24 296 sommets issu des publications de la revue Physical Review D.
Les réseaux de co-auteurs Le graphe de co-auteurs est un graphe dont les sommets sont des auteurs scientifiques et deux auteurs sont reliés s’ils ont une publication commune [88, 84, 85, 15]. Les données sont issus de la recherche en physique, en informatique et en biomédicale entre 1995 et 1999 [88, 84, 85]. Barabasi et al. [15] ont utilisé des données issues des mathématiques et des neurosciences entre 1991 et 1998.
Les réseaux de connaissance Le graphe de connaissance est un graphe dont les sommets sont des personnes et deux personnes sont liés si elles se connaissent [77]. Bien entendu, une telle relation ne peut être définie de façon très formelle et le graphe ne peut être totalement construit.
Les réseaux d’appels téléphoniques Le graphes des appels téléphoniques est un graphe orienté dont les sommets représentent des numéros de téléphones et un arc signale qu’un numéro a au moins une fois appelé un autre [8].
Les réseaux de contacts sexuels Le graphe des contacts sexuels est un graphe dont les sommets sont des personnes et deux personnes sont liées si elles ont eu un rapport sexuel [71]. Notons que les données sont relativement difficiles à obtenir.

Les réseaux utilisés en biologie

Réseau d’interactions entre protéines Le réseau d’interactions entre protéines est modélisé par un graphe dans lequel les sommets sont des protéines et deux protéines sont reliées si elles réagissent l’une avec l’autre [57].
Les réseaux trophiques Les réseaux trophiques sont représentés par un graphe dans lequel un sommet est une espèce animale ou végétale et deux espèces sont reliées si une des deux espèces est un prédateur de l’autre.

Abondance de bicliques

Un graphe biparti est un graphe orienté G(V,E) dans lequel V peut être partitionné en deux ensembles V1 et V2 tel que (u,v) ∈ E implique que, soit u ∈ V1 et v ∈ V2, soit u ∈ V2 et v ∈ V1. En d’autres termes, tous les arcs passent entre les deux ensembles V1 et V2. Une biclique est un graphe biparti complet orienté K|V1|,|V2| où chaque sommet de V1 pointe (a un arc sortant) vers chaque sommet de V2. On peut tenter d’analyser la signification d’une biclique dans le Web. Des pages Web d’un ensemble l pointent toutes vers des pages Web d’un ensemble w. Cela signifierait que les pages Web de l et w partagent des informations sur un sujet particulier. Dans ce cas, on dit que les pages Web ont un intérêt commun. Les deux ensembles l et w forment ce que [60] définissent comme étant une communauté (voir figure 1.7). Kleinberg [60] considère deux qualités pour une page. Un annuaire (hub) pointe des pages intéressantes, tandis qu’une autorité (authority) est une page Web de référence pour un sujet donné. De manière récursive, un bon annuaire est une page Web qui pointe vers des page Web considérées comme des bons autorité et une page Web est considérée comme un bonne autorité si elle est pointée par des pages Web considérées comme des bons annuaires. Cette relation entre annuaire et autorité est appelée renforcement mutuel. l’ensemble des hubs et des fans peut être utilisée comme une définition d’une communauté sur le Web. Nous verrons (voir chapitre 5 page 79) qu’il existe d’autres définitions des communautés. Kumar et al. [64] ont montré empiriquement que le Web contient un grand nombre de bicliques de différentes tailles.

Le processus de crawl

Tous les moteurs de recherche disposent d’un programme qui parcourt le Web à la recherche de nouvelles pages Web, il est appelé crawler. Le processus de crawl (crawling) consiste à choisir une URL1 parmi l’ensemble des URLs à visiter. Ce choix dépend de la stratégie de parcours adoptée (voir figure 3.1). Il existe plusieurs stratégies de crawl, nous citons les plus classiques: le parcours en largeur (BFS) et le parcours en profondeur (DFS). Il existe aussi d’autres types de parcours, tels que le parcours suivant le degré entrant maximum (DEG), où à chaque étape le sommet le plus cité est choisi en premier, ou encore le parcours aléatoire (RAND) dans lequel, un sommet est choisi au hasard parmi tous les sommets déjà cités (un mélange entre le parcours en largeur et le parcours en profondeur). Après avoir choisi une URL parmi l’ensemble des URLs à visiter (suivant la stratégie adoptée), le crawler télécharge la ressource (page Web), extrait les liens hypertextes (sous forme d’URLs) de la page. Les URLs non encore visitées sont insérées dans la liste des pages Web à visiter. Ce processus est réitéré jusqu’à ce que la liste des URLs à visiter soit vide ou que le processus soit arrêté volontairement. Comme le Web est gigantesque, la liste des URLs à visiter n’est jamais vide. Par conséquent, c’est généralement la deuxième solution ; à savoir l’arrêt du crawler ; qui est adoptée. Le crawling permet donc de construire un graphe du Web généralement appelé crawl du Web. Ce dernier peut être modélisé par un graphe G(V,E). Dans le chapitre 1, nous avons étudié les propriétés de ce crawl. Notre but est de générer des graphes aléatoires avec les mêmes propriétés que les crawls du Web.

Le rapport de stage ou le pfe est un document d’analyse, de synthèse et d’évaluation de votre apprentissage, c’est pour cela chatpfe.com propose le téléchargement des modèles complet de projet de fin d’étude, rapport de stage, mémoire, pfe, thèse, pour connaître la méthodologie à avoir et savoir comment construire les parties d’un projet de fin d’étude.

Table des matières

Introduction
I Analyse et modélisation des réseaux d’interactions: application aux crawls du Web
1 Propriétés des réseaux d’interactions
1.1 Définitions et notations
1.2 Réseaux d’interactions
1.2.1 Modèles de réseaux issus de l’Internet
1.2.2 Les réseaux sociaux
1.2.3 Les réseaux utilisés en biologie
1.2.4 D’autres réseaux d’interactions
1.3 Propriétés communes aux réseaux d’interactions
1.3.1 Distribution des degrés en loi de puissance
1.3.2 Diamètre petit et distance moyenne faible
1.3.3 Densité faible
1.3.4 Coefficient de regroupement fort
1.3.5 Composante connexe géante
1.3.6 Abondance de bicliques
2 Modélisation des réseaux d’interactions
2.1 Modèle aléatoire d’Erdös et Rényi
2.2 Modélisation des graphes à invariance d’échelle
2.2.1 Distribution des degrés fixés
2.2.2 Modèle à base d’attachement préférentiel
2.2.3 Modèle de copie
2.2.4 Modèles petits mondes
2.2.5 Autres modèles
2.3 Comparaison des différents modèles
3 Un modèle de crawls aléatoires du Web
3.1 Le processus de crawl
3.2 Objectifs
3.3 Description du modèle
3.3.1 Les stratégies de crawls
3.3.2 Génération de crawl
3.4 Résultats
3.4.1 Crawls à caractère sans-échelle (Scale-Free)
3.4.2 Évolution de la distance moyenne et diamètre
3.4.3 Évolution du coefficient de regroupement
3.4.4 Taille des composantes SCC et OUT
3.4.5 Distribution du PageRank
3.4.6 Proportion de sommets revisités et puits
3.4.7 Énumération des bicliques
3.5 La visualisation de graphes
3.5.1 La décomposition en k-core
3.5.2 Description de l’outil de visualisation
3.5.3 Comparaison entre les réseaux
3.6 Conclusion
II Calcul et visualisation de communautés
4 Structure de liens hypertextes
4.1 Analyse de liens hypertexte
4.1.1 Collecte de pages Web
4.1.2 Tri des pages Web
4.2 Tri global : algorithme PageRank
4.2.1 PageRank simplifié
4.2.2 PageRank pratique
4.3 Tri local : algorithme HITS
5 Calcul de cyber-communautés par émergence
5.1 Quelques définitions des communautés
5.2 Les méthodes d’extraction de communautés
5.2.1 Le p-partitionnement
5.2.2 Les méthodes agglomératives
5.2.3 Les méthodes séparatives
5.3 Qualité d’un partitionnement
5.3.1 Modularité de Newman
5.3.2 Une nouvelle mesure de qualité
5.4 Le modèle gravitationnel
5.4.1 Modélisation de l’Univers
5.4.2 Modélisation des actions
5.4.3 Modélisation des transferts de masse
5.4.4 Implémentation
5.4.5 Résultats
5.5 Le modèle intentionnel
5.5.1 Description du modèle
5.5.2 Identification de l’objectif
5.5.3 Déplacement vers l’objectif
5.5.4 Forme de l’univers
5.5.5 Extraction de communautés
5.5.6 Condition d’arrêt
5.5.7 Résultats
5.6 Conclusion
Conclusion
Annexes
Annexe A : Historique du Web
Annexe B : Méthode de la puissance itérée
Annexe C : Une implémentation expérimentale d’un crawler
Table des algorithmes
Table des figures
Index
Bibliographie