Cette thèse a pour objectif la réalisation d'un Système à Base de Connaissances pour les situations de crise. A travers le développement de ce système, deux principaux axes de recherche ont été entrepris : l'acquisition et la validation de connaissances. Pour l'étape d'acquisition de connaissances, nous avons intégré une méthodologie d'acquisition de connaissances et une technique d'apprentissage automatique. Dans un premier temps, la méthodologie d'acquisition de connaissances nous a permis de recueillir l'ensemble des connaissances descriptives et stratégiques du domaine, et de construire un langage de description des exemples d'apprentissage. Une technique d'apprentissage est ensuite utilisée pour construire incrémentalement un graphe de connaissances en utilisant des cas d'interventions sur des situations de crise fournis par les experts du domaine. Pour la phase d'exploitation du système, nous avons proposé deux procédures différentes. La première procédure consiste en l'utilisation interactive du graphe de connaissances construit et la deuxième procédure consiste en l'utilisation en déduction des connaissances contenues dans ce graphe. L'approche proposée pour la validation des connaissances s'appuie sur l'utilisation interactive du graphe de connaissances construit et sur un suivi des interventions des experts sur des cas de crise.

L'étude et l'analyse des réseaux sociaux attirent l'attention d'une variété de sciences (psychologie, statistiques, sociologie). Parmi elles, le domaine de la fouille de données offre des outils pour extraire automatiquement des informations utiles sur les propriétés de ces réseaux. Plus précisément, la fouille de graphes répond au besoin de modéliser et d'étudier les réseaux sociaux en particulier dans le cas des grandes communautés que l'on trouve habituellement dans les médias en ligne oú la taille des réseaux sociaux est trop grande pour les méthodes manuelles. La modélisation générale d'un réseau social est basée sur des structures de graphes. Les sommets du graphe représentent les individus et les arêtes des actions différentes ou des types de liens sociaux entre les individus. Une communauté est définie comme un sous-graphe (d'un réseau social) et se caractérise par des liens denses. Plusieurs mesures ont été précédemment proposées pour l'évaluation des divers aspects de la qualité de ces communautés mais la plupart d'entre elles ignorent diverses propriétés des interactions entre individus (par exemple l'orientation de ces liens). Dans la recherche présentée ici, le concept de "k-core" est utilisé comme un moyen d'évaluer les communautés et d'en extraire des informations. La structure de "k-core" mesure la robustesse d'un réseau non orienté en utilisant la dégénérescence du graphe. En outre, des extensions du principe de dégénérescence sont introduites pour des réseaux dont les arêtes possèdent plus d'informations que celles non orientées. Le point de départ est l'exploration des attributs qui peuvent être extraits des graphes non orientés (réseaux sociaux). Sur ce point, la dégénérescence est utilisée pour évaluer les caractéristiques d'une collaboration entre individus et sur l'ensemble de la communauté - une propriété non capturée par les métriques sur les sommets individuels ou par les métriques d'évaluation communautaires traditionnelles. Ensuite, cette méthode est étendue aux graphes pondérés, orientés et signés afin d'offrir de nouvelles mesures d'évaluation pour les réseaux sociaux. Ces nouvelles fonctionnalités apportent des outils de mesure de la collaboration dans les réseaux sociaux oú l'on peut attribuer un poids ou un orientation à une interaction et fournir des moyens alternatifs pour capturer l'importance des individus au sein d'une communauté. Pour les graphes signés, l'extension de la dégénérescence permet de proposer des métriques supplémentaires qui peuvent être utilisées pour modéliser la confiance. De plus, nous introduisons une approche de partitionnement basée sur le traitement du graphe de manière hiérarchique, hiérarchie fournie par le principe de "core expansion sequence" qui partitionne le graphe en différents niveaux ordonnés conformément à la décomposition "k-core". Les modèles théoriques de graphes sont ensuite appliqués sur des graphes du monde réel pour examiner les tendances et les comportements. Les jeux de données explorés incluent des graphes de collaborations scientifiques et des graphes de citations (DBLP et ARXIV), une instance de graphe interne de Wikipédia et des réseaux basés sur la confiance entre les individus (par exemple Epinions et Slashdot). Les conclusions sur ces ensembles de données sont significatives et les modèles proposés offrent des résultats intuitifs.

This thesis focuses on the extraction and analysis of Web data objects, investigated from different points of view: temporal, structural, semantic. We first survey different strategies and best practices for deriving temporal aspects of Web pages, together with a more in-depth study on Web feeds for this particular purpose. Next, in the context of dynamically-generated Web pages by content management systems, we present two keyword-based techniques that perform article extraction from such pages. Keywords, either automatically acquired through a Tf−Idf analysis, or extracted from Web feeds, guide the process of object identification, either at the level of a single Web page (SIGFEED algorithm), or across different pages sharing the same template (FOREST algorithm). We finally present, in the context of the deep Web, a generic framework which aims at discovering the semantic model of a Web object (here, data record) by, first, using FOREST for the extraction of objects, and second, by representing the implicit rdf:type similarities between the object attributes and the entity of the Web interface as relationships that, together with the instances extracted from the objects, form a labeled graph. This graph is further aligned to a generic ontology like YAGO for the discovery of the graph's unknown types and relations.

Aujourd'hui, les contenus et les applications Web sont devenus la principale interface pour effectuer toutes sortes de tâches de la vie quotidienne comme déclarer et payer les impôts, réserver des billets d'avion ou de train, planifier des vacances, effectuer des achats, gérer les comptes bancaires, etc. En conséquence, il devient de plus en plus important d'étudier leurs fondements, d'améliorer leurs capacités, de faciliter leur conception, de vérifier leur fonctionnement, de les optimiser automatiquement et les rendre plus souples et adaptables aux usages et aux différentes plateformes. Dans ce document, nous décrivons d'abord mes activités professionnelles, concernant les années 1998 à 2012. La première partie de ce document contient un résumé de mes activités de recherche, d'encadrement, d'enseignement et charges administrative et collective, ainsi qu'un résumé de mes principaux résultats scientifiques. Dans le reste du document, nous introduisons une logique de raisonnement sur les arbres finis, une procédure de décision correcte et complète pour vérifier la satisfaisabilité d'une formule de la logique ainsi que d'une mise en œuvre efficace en pratique. La logique est une variante du mu-calcul adaptée aux arbres finis et équipée avec des modalités arrières et des nominaux. Ensuite, nous considérons le problème de l'évolution des schémas XML. Dans le contexte en constante évolution du Web, les schémas XML changent continuellement afin de faire face à l'évolution naturelle des entités qu'ils décrivent. Les modifications de schémas peuvent avoir des conséquences importantes dans la mesure où les documents existants peuvent devenir invalides et la programmes les manipulant incorrectes. Nous proposons un cadre unificateur pour déterminer les effets de l'évolution des schémas XML à la fois sur la validité des documents et des requêtes contenues dans ces programmes. Dans la dernière partie du document, nous considérons une algèbre de type équipée de la récursivité, du produit cartésien, des fonctions, de l'intersection, de l'union, et du complément ainsi que des variables de type et une quantification universelle implicite sur ces variables. Nous considérons la relation de sous-typage récemment définie par Castagna et Xu sur des expressions de cette algèbre de type et montrons que le sous-typage peut être décidé avec une complexité EXPTIME et implémenté efficacement en pratique clôturant ainsi à une question ouverte dans la littérature.

Les services web gagnent de l'importance en tant que cadre facilitant l'intégration d'applications au sein et en dehors des frontières des entreprises. Il est accepté que la description d'un service ne devrait pas seulement inclure l'interface, mais aussi le protocole métier supporté par le service. Dans le cadre de ce travail, nous avons formalisé la catégorie des protocoles incluant des contraintes de temps (appelés protocoles temporisés) et étudié l'impact du temps sur l'analyse de compatibilité et de remplaçabilité. Nous avons formalisé les contraintes suivantes : les contraintes Clnvoke définissent des fenêtres de disponibilités tandis que les contraintes Mlnvoke définissent des délais d'expiration. Nous avons étendu les techniques pour l'analyse de compatibilité et de remplaçabilité entre protocoles temporisés à l'aide d'un mapping préservant la sémantique entre les protocoles temporisés et les automates temporisés, ce qui a défini la classe des automates temporisés de protocoles (PTA). Les PTA possèdent des transitions silencieuses qui ne peuvent pas être supprimées en général, et pourtant ils sont fermés par calcul du complément, ce qui rend décidable les différents types d'analyse de compatibilité et de remplaçabilité. Enfin, nous avons mis en oeuvre notre approche dans le cadre du projet ServiceMosaic, une plate-forme pour la gestion du cycle de vie des services web.

Les services Web sont des briques de bases logicielles s‟affranchissant de toute contrainte de compatibilité logicielle ou matérielle. Ils sont mis en oeuvre dans une architecture orientée service. A l‟heure actuelle, les travaux de recherche se concentrent principalement sur la découverte et la composition. Cependant, la complexité de la structure de l‟espace des services Web et son évolution doivent nécessairement être prises en compte. Ceci ne peut se concevoir sans faire appel à la science des systèmes complexes, et notamment à la théorie des réseaux complexes. Dans cette thèse, nous définissons un ensemble de réseaux pour la composition sur la base de services décrits dans des langages syntaxique (WSDL) et sémantique (SAWSDL). L‟exploration expérimentale de ces réseaux permet de mettre en évidence les propriétés caractéristiques des grands graphes de terrain (la propriété petit monde et la distribution sans échelle). On montre par ailleurs que ces réseaux possèdent une structure communautaire. Ce résultat permet d‟apporter une réponse alternative à la problématique de la classification de services selon les domaines d‟intérêts. En effet, les communautés regroupent non pas des services aux fonctionnalités similaires, mais des services qui ont en commun de nombreuses relations d‟interaction. Cette organisation peut être utilisée entre autres, afin de guider les algorithmes de recherche de compositions. De plus, en ce qui concerne la classification des services aux fonctionnalités similaires en vue de la découverte ou de la substitution, nous proposons un ensemble de modèles de réseaux pour les représentations syntaxique et sémantique des services, traduisant divers degrés de similitude. L‟analyse topologique de ces réseaux fait apparaître une structuration en composantes et une organisation interne des composantes autour de motifs élémentaires. Cette propriété permet une caractérisation à deux niveaux de la notion de communauté de services similaires, mettant ainsi en avant la souplesse de ce nouveau modèle d‟organisation. Ces travaux ouvrent de nouvelles perspectives dans les problématiques de l‟architecture orientée service.

L'application des mesures d'importance de type PageRank aux graphes du Web est le sujet de cette thèse, qui est divisée en deux parties. La première introduit une famille particulière de grands graphes, les graphes du Web. Elle commence par définir la notion de Web indexable, puis donne quelques considérations sur les tailles des portions de Web effectivement indexées. Pour finir, elle donne et utilise quelques constatations sur les structures que l'on peut observer sur les graphes induits par ces portions de Web. Ensuite, la seconde partie étudie en profondeur les mesures d'importance à la PageRank. Après un rappel sur la théorie des chaînes de Markov est présentée une classification originale des algorithmes de PageRank, qui part du modèle le plus simple jusqu'à prendre en compte toutes les spécificités liées aux graphes du Web. Enfin, de nouveaux algorithmes sont proposés. L'algorithme BackRank utilise un modèle alternatif de parcours du graphe du Web pour un calcul de PageRank plus rapide. La structure fortement clusterisée des graphes du Web permet quant à elle de décomposer le PageRank sur les sites Web, ce qui est réalisé par les algorithmes FlowRank et BlowRank.

Cette thèse, au croisement du Web Social et du Web Sémantique, vise à rapprocher folksonomies et représentations structurées de connaissances telles que les thesauri ou les ontologies informatiques. Les folksonomies, résultant de l'usage de plateformes de social tagging, souffrent d'un manque de précision qui les rend difficile à exploiter pour la naviguation. Cette thèse présente notre approche multi-points de vue de l'enrichissement sémantique des folksonomies. L'amorçage est assuré par des traitements automatiques qui permettent d'extraire des relations sémantiques entre tags grâce à la combinaison d'une méthode que nous avons mise au point et analysant les labels de tags, et de méthodes que nous avons adaptées et analysant la structure de folksonomies. Les contributions des utilisateurs sont décrites par notre modèle SRTag supportant les points de vue divergents, et capturées par une interface intégrant à la navigation des fonctionnalités de micro-édition de folksonomie. Les conflits entre points de vue sont détectés et solutionnés par un agent automatique dont les résultats sont ensuite exploités pour aider un utilisateur référent à maintenir une structuration globale et cohérente de la folksonomie, servant en retour pour enrichir chaque point de vue individuel avec les autres contributions tout en garantissant une cohérence locale. Notre méthode permet d'améliorer la navigation dans les systèmes de connaissances à base de tags, mais fournit aussi une base à des thesauri nourris par un processus bottom-up d'acquisition de connaissances.

Dans les architectures parallèles à mémoire distribuée, la communication entre processus est un des facteurs de performance les plus importants pour les applications. Le système qui en a la charge, i.e, le noyau de communication, doit intégrer une fonctionnalité essentielle pour de telles architectures : le routage des messages. Cette fonctionnalité est assurée par une composante spécifique du noyau de communication: le noyau de routage, dont le rôle est l'acheminement d'un message d'un noeud émetteur vers un noeud récepteur. L'acheminement des messages nécessite une stratégie de routage qui spécifie les chemins de communication pour toute paire de processeurs (source, destination) du réseau d'interconnexion. Une telle stratégie de routage doit satisfaire d'une part, des critères de correction et d'autres part, des critères d'efficacité. Le but de cette thèse est la conception de stratégies de routage pour les réseaux de processeurs qui satisfont à la fois, les critères de correction et les critères d'efficacité. Nous proposons une méthode de conception de stratégies de routage, permettant par une démarche incrément-ale, de satisfaire les deux types de critère: la communication multi-niveaux et le schéma de communication primaire associé. Pour mesurer l'efficacité de la méthode, nous l'appliquons à un réseau particulier : la grille torique. Les différents algorithmes de routage obtenus sont corrects et très efficaces. Nous proposons également une technique d'implantation de notre méthode de routage, permettant le calcul des tables de routage directement sur le réseau de processeurs. Cette technique permet ainsi l'obtention d'un système autoconstructif.

Nous proposons dans notre thèse une nouvelle méthodologie pour le développement des protocoles de communication et des applications réparties en explorant une approche de synthèse automatisée. Après avoir effectué un état de l'art sur les techniques de synthèse de protocoles, nous présentons, dans la première partie de la thèse, une nouvelle méthode de synthèse automatique de spécifications de protocoles à partir de spécifications de services dans un modèle de réseaux de Petri interprétés. Notre approche de synthèse est basée sur un nouveau concept de raffinement de réseaux de Petri qui assure la correction des protocoles construits de façon incrémentale. L'intérêt principal de cette méthode par rapport aux techniques classiques basées sur l'analyse est qu'elle évite la phase supplémentaire de validation du protocole qui passe souvent par une analyse exhaustive dont le problème fondamental est l'explosion combinatoire. De plus, le coût de construction des protocoles est considérablement diminué. Partant d'une description de service, notre technique de synthèse permet de dériver automatiquement au niveau protocole l'ensemble des fonctionnalités suivantes: (1) traitements répartis, (2) flot de contrôle, (3) flot de données, (4) contrôle de la cohérence des données, (5) et choix distribué. Elle constitue, de ce fait, un "bon" compromis entre le pouvoir de synthèse et le pouvoir d'expression des services relativement aux techniques existantes. Dans la deuxième partie de la thèse nous présentons une application réelle de notre méthode de synthèse à la conception du protocole de transport ISO de base (ISO 8073), le point de départ de la conception étant la spécification du service de transport ISO 8072. Dans la troisième partie de la thèse, nous présentons un ensemble d'outils logiciels pour la synthèse automatique de protocoles que nous appelons STEPS (Software Toolset for automatEd Protocol Synthesis). Nous avons développé cet ensemble d'outils afin de démontrer l'utilité et la faisabilité de l'approche de synthèse que nous proposons. La sémantique de notre modèle de spécification étant assez proche de celle du langage Estelle, nous proposons une extension de notre démarche pour la synthèse de spécifications de protocoles dans le langage Estelle. L'intérêt est que ces spécifications peuvent être directement exploitées par des outils existants afin de générer automatiquement du code exécutable ou d'effectuer des simulations et des évaluations de performances.