Communautés dans les réseaux sémantiques pairs-à-pairs, Communities in semantic peer-to-peer networks

Anis Ismail

Description

Sous la direction de Mohamed Quafalou, Mohammad Hajjar
Thèse soutenue le 13 juillet 2010: Aix Marseille 2
La première partie de cette thèse est dédiée à l’état de l’art sur les réseaux pair-à-pair, la recherche d’information dans de tels réseaux et la problématique de la fouille des données dans le contexte pair-à-pair en se focalisant plus particulièrement sur les méthodes de regroupement (clustering) et les arbres de décision.La seconde partie traite des réseaux où les pairs disposent de leurs propres schémas de données. On y analyse plus particulièrement les fondements et le fonctionnement du système SenPeer. On propose alors une architecture supportant une organisation communautaire des réseaux pair-à-pairs sémantiques. Cela nous permet alors de construire des réseaux pair-à-pair sémantiques structurés en communautés appelés cSON (CommunitySemantic Overlay Network).Ce qui pose alors les questions concernant l’explicitation des communautés et leur exploitation pour améliorer les performances (temps de réponse, nombres de messages, précision et le rappel). Pour construire les communautés, nous étudions deux alternatives différentes : (1) Médiation sémantique : la construction des communautés se base sur les liens sémantiques entre les super-pairs et la confiance qu’ils ont les uns envers les autres et (2) Clustering : un algorithme de clustering basé sur l’analyse des requêtes traitées par les super-pairs est à la base de construction des communautés. Ensuite, nous proposons deux méthodes pour calculer des caractérisations des communautaires en se plaçant dans les deux champs de recherche suivants : (1) Data mining: on cherche à caractériser chaque communauté à l’aide d’une connaissance extraite des requêtes traitées par ses super-pairs d’une même communauté CK (Communauty Knowledge) et (2) Hypergraphes : A l’inverse de la méthode précédente, notre objectif maintenant est de caractériser collectivement les communautés. On formalise ce problème comme la recherche des MCS (minimal covering shortcuts) qui sont des raccourcis, entre les super pairs,minimaux couvrants toutes les communautés. Nous développons ensuite deux méthodes de routages de requêtes CK-rooting et MCS-rooting en utilisant respectivement la connaissance communautaire et les MCS afin d’identifier les super-pairs susceptibles de traiter une requête donnée.Dans la troisième partie, nous présentons le simulateur développé pour supporter l’approche cSON. Nous présentons alors les résultats empiriques résultant de simulations et qui montrent une amélioration significative des performances de l’approche basée uniquement sur la médiation sémantique. Cette partie se termine avec la description d’une application de recherche d’information basée sur le partage de documents scientifiques enrichis.
-Pair-à-pair
-Communautés
-Simulation
-Hypergraphes
The first part of this thesis is dedicated to the state of the art on the peer-to-peer networks, the information retrieval in such networks, and the problematic of data mining in the peer-to-peer context more particularly on clustering methods and decision trees.The second part deals with networks where peers have their own data schemas. We examine more particularlythe fundamentals and functioning of the system “SenPeer”. Then, we propose an architecture supporting acommunity organization of semantic peer-to-peer networks. This allows us to build peer-to-peer semantic structured communities called cSON (Communauty Semantic Overlay Network).This raises many questions concerning the explanation of communities and their operating to improve performances (response time, number of messages, precision and recall). To build communities, we study two different alternatives: (1) Semantic Mediation: the building of communities is based on semantic links between super-peers and the confidence that they have between them and (2) Clustering: a clustering algorithm, based onthe analysis of queries processed by the super-peers, is the base of community building. Then, we propose twomethods to calculate the characterizations of communities in the two research fields: (1) Data mining: we try to characterize each community using knowledge extracted from applications processed by his super-peers of the same community CK (Community Knowledge) and (2) Hypergraphs: Unlike the previous method, our goal nowis to characterize the communities collectively. We formalize this problem as the research of the MCS (minimalcovering shortcuts) which are shortcuts between the super-peers, minimum shortcuts covering all communities.Then, we develop two methods of queries routing CK-rooting and MCS-rooting respectively using community knowledge and MCS to identify the super-peers may process a given query.In the third section, we present the simulator developed to support the cSON approach. We present the empirical results representing the simulations and which show a significant improvement of performance of the approachonly based on semantic mediation.This part ends with a description of an application of information retrieval based on sharing enriched scientific documents.
-Peer-to-peer
-Communities
-Clustering
-Data minig
-P2p
Source: http://www.theses.fr/2010AIX22057/document

Sujets

• Pair à pair
• Communauté
• Simulation
• Hypergraphe
• Clustering

Informations

• Publié par: Thesee
• Nombre de lectures: 59
• Langue: Français
• Poids de l'ouvrage: 1 Mo

Extrait

UNIVERSITÉ DE LA MEDITERRANEE AIX-MARSEILLE II
TITRE :
Communautés dans les réseaux sémantiques pairs-à-pairs
THÈSE
Pour obtenir le grade de
DOCTEUR DE L'UNIVERSITÉ DE LA MEDITERRANEE AIX-MARSEILLE II
Faculté des Sciences et Techniques
Discipline :
École Doctorale en Mathématiques et Informatique de Marseille (ED184)
Présentée par
Anis Ismail
Le 13 JUILLET 2010
JURY
M. Patrick Gallinari Pr., Université Paris 6 Rapporteur
Kokou Yetongnon Pr., Université de Bourgogne Rapporteur
Bruno Defude Pr., TELECOM SudParis Examinateur
Omar Boucelma Pr., Université Paul Cézanne Examinateur
Gilles Nachouki MC., Université de Nantes Examinateur
Mohammad Hajjar Pr., Université Libanaise Co-encadrant
Mohamed Quafafou Pr., Université de la méditerranée Directeur


ANNÉE : 2010





















2





à mes parents,
à ma Femme,
à mes amis.











3
Remerciements

Je tiens tout d’abord à exprimer ma profonde gratitude envers M. Mohamad
Quafafou et M. Mohammed Hajjar qui ont accepté de diriger cette thèse et l’ont
fait de manière constante, avec une disponibilité totale. Leur patience devant
mes difficultés à trouver « le mot juste » et leurs précieux conseils auront permis
l’achèvement de ce travail.

Je suis également reconnaissant à M. Patrick Gallinari, professeur à l’université de
Paris 6 et M. Kokou Yetongnon, professeur à l’université de Bourgogne, pour avoir
accepté d’être rapporteurs et membres de ce jury.

Je tiens à exprimer mes plus vifs remerciements à M. Gilles Nachouki qui m’a aidé à
faire cette thèse. Merci infiniment pour la disponibilité, la patience, les remarques et
suggestions pertinentes durant toute la thèse.

Merci également à M. Bruno Defude, professeur à l’université de TELECOM SudParis et
M. Omar Boucelma professeur de l’université Paul Cézanne et professeur, pour avoir
accepté d’examiner ce travail et faire partie de mon jury de thèse.

Je ne pourrais finir sans inclure dans ces remerciements les personnes les plus chères
pour leur soutien matériel et moral : mes parents, mes frères et ma femme.

4 Sommaire

LISTE DES FIGURES ......................................................................................................................................... 8
LISTE DES TABLEAUX ..................................................................................................................................... 9
LISTE DES ABREVIATIONS .......................................................................................................................... 10
CHAPITRE 1. INTRODUCTION.................................................................................................................... 13
1. MOTIVATIONS ............................................................................................................................................. 13
2. CONTRIBUTION........................................................................................................................................... 14
3. ORGANISATION DU RAPPORT ................................................................................................................ 15
PARTIE I - FONDEMENTS ET ETAT DE L’ART........................................................................................ 19
CHAPITRE 2. RECHERCHE D’INFORMATION DANS LES RESEAUX P2P ....................................... 21
1. INTRODUCTION........................................................................................................................................... 21
2. TYPES DE RESEAUX ................................................................................................................................... 22
3. RESEAUX SEMANTIQUES SUPERPOSES............................................................................................... 24
3.1. RESEAUX SUPERPOSES STRUCTURES ET NON STRUCTURES.......................................................................... 25
3.2. RESEAUX SUPERPOSES SEMANTIQUES ......................................................................................................... 27
4. SYSTEMES DE GESTION DE DONNEES P2P ......................................................................................... 28
5. RECHERCHE D’INFORMATION DANS LES COMMUNAUTES DE PAIRS ..................................... 29
5.1. RECHERCHE D’INFORMATION...................................................................................................................... 30
5.1.1. Généralités .......................................................................................................................................... 30
5.1.2. Contexte .............................................................................................................................................. 30
5.1.3. Profils.................................................................................................................................................. 31
5.1.4. Profils et filtrage ................................................................................................................................. 31
5.2. RECHERCHE D’INFORMATION DANS LES SYSTEMES P2P.............................................................................. 32
5.2.1. Recherche aveugle .............................................................................................................................. 32
5.2.2. Recherche informée............................................................................................................................. 33
5.2.3. Recherche sémantique......................................................................................................................... 35
5.3. COMMUNAUTES DANS LES P2P ................................................................................................................... 39
5.3.1. Construction de communautés ............................................................................................................ 39
5.3.2. Recherche d’information dans les communautés ................................................................................ 41
5.4. CRITERES D’EVALUATION ........................................................................................................................... 41
5.4.1. Critères qualitatifs .............................................................................................................................. 41
5.4.2. Critères quantitatifs ............................................................................................................................ 42
6. CONCLUSION................................................................................................................................................ 42
CHAPITRE 3. FOUILLE DE DONNEES DANS LES RESEAUX P2P....................................................... 44
1. INTRODUCTION.......................................................................................................................................... 44
2. FOUILLE DE DONNEES DANS LE P2P.................................................................................................... 44
3. ARBRE DE DECISION ................................................................................................................................ 46
5 4. CLASSIFICATION NON SUPERVISEE (CLUSTERING)....................................................................... 50
4.1. METHODES DE PARTITIONNEMENT ............................................................................................................. 50
4.2. METHODES HIERARCHIQUES ....................................................................................................................... 54
4.3. METHODES BASEES SUR LES MOTIFS ET LA NOTION DE FREQUENCE ............................................................ 57
4.4. CLASSIFICATION CONCEPTUELLE ................................................................................................................ 61
5. CONCLUSION................................................................................................................................................ 65
PARTIE 2 - APPROCHE COMMUNAUTAIRE POUR LA RECHERCHE D’INFORMATION DANS
LES RESEAUX P2P ........................................................................................................................................... 67
CHAPITRE 4. APPROCHE SEMANTIQUE .................................................................................................. 69
1. INTRODUCTION.......................................................................................................................................... 69
2. ARCHITECTURE GENERALE.................................