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.

Les problèmes combinatoires basés sur le partitionnement de graphe permettent de modéliser un grand nombre d'applications pratiques. On retiendra des exemples aussi variés que la reconstruction de " super-arbres " en phylogénie, la planification de missions, ou la construction de tournées de véhicules en logistique. Ces applications, bien que provenant de domaines différents, peuvent toutes se voir comme un problème de partitionnement de graphe par des patrons tels que des cycles, des chemins, ou des arbres. Cependant, les problèmes pratiques se résument rarement à des problèmes " pur " comme peuvent l'être le problème de chemin Hamiltonien ou le problème des K-chemins disjoints. En effet, ils combinent bien souvent le problème de partitionnement avec un ensemble de restrictions sur la topologie des sommets et des arcs. La diversité des contraintes opérationnelles misent en jeu constitue souvent une limite à leur résolution par des approches considérant de manière séparée le problème de partitionnement et les restrictions supplémentaires imposées. Cette thèse se concentre sur les problèmes de satisfaction de contraintes li !es au partitionnement de graphe par des arbres mettant en jeu un certain nombre de restrictions sur la topologie des partitions autorisées. Notre travail se focalise d'une part sur la compréhension des propriétés structurelles inhérentes aux contraintes de partitionnement par des arbres, et d'autre part sur l'étude des interactions existantes entre le problème de partitionnement et les restrictions classiques (telles que les relations de précédences ou d'incomparabilités entre les sommets du graphe à partitionner). Nous nous attachons plus particulièrement à montrer comment prendre en compte de manière globale un certain nombre de ces restrictions au sein d'une contrainte de partitionnement de graphes par des arbres. Un autre aspect essentiel porte sur la mise en œuvre d'une telle contrainte : nous montrons en quoi une gestion dynamique des structures de données permet de s'abstraire significativement d'un problème récurrent à la plupart des contraintes globales liées aux graphes : la sensibilité des algorithmes de graphes à la densité des graphes manipulés par la contrainte.

Nous détaillons dans cette thèse des algorithmes modérément exponentiels pour l'approximation du problème MAX SAT. Nous discutons d'une méthode générique pour la conception d'algorithmes exponentiels réalisant des schémas d'approximation dans un cadre plus général. Enfin, nous présentons des résultats paramétrés pour des problèmes de coupe à cardinalité contrainte.

Mémoire numérisé par la Division de la gestion de documents et des archives de l'Université de Montréal

L'analyse de réseaux (représentés par des graphes) est une composante importante dans la compréhension de systèmes complexes issus de nombreuses disciplines telles que la biologie, la géographie ou la sociologie. Nous nous intéressons dans cette thèse aux décompositions de ces réseaux. Ces décompositions sont utiles pour la compression des données, la détection de communautés ou la visualisation de graphes. Une décomposition possible est un partitionnement hiérarchique des sommets du graphe. Nous traitons de l'évaluation de la qualité de telles structures (leur capacité à bien capturer la topologie du graphe) par le biais de mesures de qualité. Nous discutons ensuite l'utilisation de ces mesures en tant que fonctions objectives à maximiser dans le cadre d'algorithmes de partitionnement. Enfin, nous nous intéressons à la définition de métaphores visuelles efficaces permettant de représenter différentes décompositions de graphes.

Un fasciagraphe de taille n et de fibre F est constitué de n copies consécutives du graphe F, chaque copie étant reliée à la suivante selon le même schéma. Les rotagraphes sont définis similairement, mais selon une structure circulaire. Dans cette thèse nous caractérisons un ensemble de problèmes combinatoires qui peuvent être résolus de façon efficace dans la classe des fasciagraphes et rotagraphes. Dans ce contexte, nous définissons les (d,q,w)-propriétés closes et stables, et présentons pour de telles propriétés un algorithme pour calculer une solution optimale en temps constant pour l'ensemble des fasciagraphes ou rotagraphes de fibre fixée. Nous montrons que plusieurs problèmes communément étudiés dans la théorie des graphes et NP-complets dans le cas général sont caractérisés par des (d,q,w)-propriétés closes ou stables. Dans une seconde partie de la thèse, nous adaptons cet algorithme générique à trois problèmes spécifiques caractérisés par des (d,q,w)-propriétés stables : le problème du code identifiant minimum, et deux problèmes proches, celui de dominant-localisateur minimum et celui du dominant-total-localisateur minimum. Nous présentons alors une implémentation de l'algorithme qui nous a permis de répondre à des questions ouvertes dans certains rotagraphes particuliers : les bandes circulaires de hauteur bornée. Nous en déduisons d'autres résultats sur les bandes infinies de hauteur bornée. Enfin, nous explorons le problème du code identifiant dans une autre classe de graphes à structure répétitive : les graphes fractals de cycle.

La décomposition modulaire apparait naturellement dans différents domaines de la combinatoire (et en particulier les graphes). Cette décomposition se révèle être un puissant outil de description d'objets discrets. Elle est aussi utilisée comme étape préliminaire à nombreux d'algorithmes.<br /><br />Dans ce mémoire, nous nous intéressons au calcul de la décomposition modulaire. Malgré la publication d'algorithmes linéaires au milieu des années 90, la recherche sur ce problème n'a pas cessée. Nous faisons le point sur les différentes avancées et techniques utilisées.

Cette thèse traite deux types de problèmes algorithmiques : des problèmes de triangularisation de matrices booléennes par permutation des lignes et des colonnes et des problèmes de découverte de structures secondaires d'ARN. Nous étudions des problèmes de triangularisation de matrices booléennes par permutation des lignes et des colonnes. Ce problème apparaît, par exemple, lorsque l'on souhaite calculer "en place" un système d'équations. Une façon naturelle d'aborder ce problème est de se placer dans le cadre général de la théorie des graphes et des graphes bipartis en particulier. Nous présentons de nombreux résultats de complexité - essentiellement de NP-complétude - liés à ce problème et introduisons quelques extensions dont nous précisons toujours la complexité. Certaines familles d'ARN sont très précisément définies par des motifs de séquence, et des contraintes structurelles secondaires et tertiaires. La plupart des outils ne sont pas adaptés puisqu'ils n'intègrent pas toutes les connaissances sur la molécule lors de l'exploration des banques de séquences. D'où l'intérêt d'algorithmes de recherche assurant une recherche en séquence et structure par le biais d'un descripteur défini par l'utilisateur intégrant l'ensemble des connaissances caractérisant l'ARN à détecter. Une nouvelle façon d'aborder ce problème consiste en l'étude de problèmes algorithmiques sur les graphes d'intersection d'un ensemble de 2-intervalles. Cette notion de 2-intervalles se trouve dans la lignée des études actuelles en matière d'algorithmique de graphes où l'on étudie de plus en plus les structures des graphes issues de modèles géométriques. Nous présentons plusieurs résultats de complexité et montrons en particulier que la recherche de motifs dans un ensemble de 2-intervalles est un problème NP-complet. Nous nous intéressons, plus particulièrement, à appliquer ces travaux pour la prédiction de motifs biologiques structurés. Plus spécifiquement, nous avons mis au point l'algorithme ORANGE pour la prédiction des introns auto-catalytiques de groupe 1 dans de grandes séquences génomiques. Cet algorithme est une amélioration de l'algorithme CITRON mis au point par F. Lisacek et F. Michel du point de vue de la rapidité d'exécution. De plus, une mise-en-œuvre de l'algorithme ORANGE est accessible en ligne sur Internet.

Dans ce manuscrit, nous proposons de concevoir et de mettre en oeuvre un environnement logiciel pour une "gestion guidée par les modèles" des changements dans les architectures des applications distribuées coopératives. Les aspects adaptabilité des applications, les aspects transformations de graphe et les aspects particuliers des applications distribuées coopératives sont étudiés. Une approche d'adaptation s'appuyant sur une modélisation par les graphes et un style architectural de type Poducteur/Consommateur est présentée pour des applications communicantes collaboratives sensibles au contexte. Une démarche de raffinement est proposée permettant de garantir un certain degré d'adaptabilité en faisant un compromis entre les différents paramètres du contexte. Ces travaux de recherche ont aussi permis de définir un cadre algorithmique générique de reconfiguration architecturale multi-niveaux pour la sélection des architectures de déploiement les plus adaptées à un contexte et aux situations associées. Ce cadre a été appliqué au cas de la communication et de la coopération de groupe. Elle a aussi permis de modéliser le style architectural Producteur/Consommateur pour une communication orientée évènement. Des règles d'adaptation ont été définies. Elles comportent une partie basée sur SWRL pour la description du contexte et des règles d'adaptation, et une partie basée sur les grammaires de graphes pour la transformation des configurations de déploiement

Pour modéliser au mieux les phénomènes linguistiques dans les systèmes de traitement automatique des langues (traduction, analyse, etc.), il faut disposer de ressources de qualité. Or, les ressources existantes sont souvent incomplètes et ne permettent pas de traiter correctement les données. Cette thèse s'intéresse à l'acquisition de connaissances linguistiques, plus précisément à leur extraction à partir de corpus. Nous étudions en particulier le problème des collocations, ces couples de termes dont l'un est choisi en fonction de l'autre pour exprimer un sens particulier (comme " pluie battante " où " pluie " exprime l'intensification). Pour permettre l'acquisition de données à grande échelle, il faut la rendre facile à réaliser de manière automatique, et simple à paramétrer par des linguistes aux connaissances limitées en programmation ; cela nécessite une modélisation adaptée et précise des données et des processus. Nous avons réalisé et décrivons MuLLinG, modèle de graphes linguistiques multiniveau, où chaque niveau représente l'information d'une manière différente,et les opérations de manipulation de ces graphes. Ce modèle permet de représenter et traiter divers types de ressources. En effet, les opérations associées ont été écrites pour être les plus génériques possibles : elles sont indépendantes de ce que peuvent représenter les nœuds et les arcs du graphe, et de la tâche à réaliser. Cela permet à notre modèle, mis en œuvre et utilisé pour plusieurs expérimentations (entre autres l'extraction de collocations), de voir un processus parfois complexe d'extraction de connaissances linguistiques comme une succession d'opérations simples de manipulation de graphes.