Les méthodes d'apprentissage semi-supervisé constituent une catégorie de méthodes d'apprentissage automatique qui combinent points étiquetés et données non labellisées pour construire le classifieur. Dans la première partie de la thèse, nous proposons un formalisme d'optimisation général, commun à l'ensemble des méthodes d'apprentissage semi-supervisé et en particulier aux Laplacien Standard, Laplacien Normalisé et PageRank. En utilisant la théorie des marches aléatoires, nous caractérisons les différences majeures entre méthodes d'apprentissage semi-supervisé et nous définissons des critères opérationnels pour guider le choix des paramètres du noyau ainsi que des points étiquetés. Nous illustrons la portée des résultats théoriques obtenus sur des données synthétiques et réelles, comme par exemple la classification par le contenu et par utilisateurs des systèmes pair-à-pair. Cette application montre de façon édifiante que la famille de méthodes proposée passe parfaitement à l’échelle. Les algorithmes développés dans la deuxième partie de la thèse peuvent être appliquées pour la sélection des données étiquetées, mais également aux autres applications dans la recherche d'information. Plus précisément, nous proposons des algorithmes randomisés pour la détection rapide des nœuds de grands degrés et des nœuds avec de grandes valeurs de PageRank personnalisé. A la fin de la thèse, nous proposons une nouvelle mesure de centralité, qui généralise à la fois la centralité d'intermédiarité et PageRank. Cette nouvelle mesure est particulièrement bien adaptée pour la détection de la vulnérabilité de réseau. / Semi-supervised learning methods constitute a category of machine learning methods which use labelled points together with unlabeled data to tune the classifier. The main idea of the semi-supervised methods is based on an assumption that the classification function should change smoothly over a similarity graph. In the first part of the thesis, we propose a generalized optimization approach for the graph-based semi-supervised learning which implies as particular cases the Standard Laplacian, Normalized Laplacian and PageRank based methods. Using random walk theory, we provide insights about the differences among the graph-based semi-supervised learning methods and give recommendations for the choice of the kernel parameters and labelled points. We have illustrated all theoretical results with the help of synthetic and real data. As one example of real data we consider classification of content and users in P2P systems. This application demonstrates that the proposed family of methods scales very well with the volume of data. The second part of the thesis is devoted to quick detection of network central nodes. The algorithms developed in the second part of the thesis can be applied for the selections of quality labelled data but also have other applications in information retrieval. Specifically, we propose random walk based algorithms for quick detection of large degree nodes and nodes with large values of Personalized PageRank. Finally, in the end of the thesis we suggest new centrality measure, which generalizes both the current flow betweenness centrality and PageRank. This new measure is particularly well suited for detection of network vulnerability.

Les méthodes d'apprentissage semi-supervisé constituent une catégorie de méthodes d'apprentissage automatique qui combinent points étiquetés et données non labellisées pour construire le classifieur. Dans la première partie de la thèse, nous proposons un formalisme d'optimisation général, commun à l'ensemble des méthodes d'apprentissage semi-supervisé et en particulier aux Laplacien Standard, Laplacien Normalisé et PageRank. En utilisant la théorie des marches aléatoires, nous caractérisons les différences majeures entre méthodes d'apprentissage semi-supervisé et nous définissons des critères opérationnels pour guider le choix des paramètres du noyau ainsi que des points étiquetés. Nous illustrons la portée des résultats théoriques obtenus sur des données synthétiques et réelles, comme par exemple la classification par le contenu et par utilisateurs des systèmes pair-à-pair. Cette application montre de façon édifiante que la famille de méthodes proposée passe parfaitement à l'échelle. Les algorithmes développés dans la deuxième partie de la thèse peuvent être appliquées pour la sélection des données étiquetées, mais également aux autres applications dans la recherche d'information. Plus précisément, nous proposons des algorithmes randomisés pour la détection rapide des nœuds de grands degrés et des nœuds avec de grandes valeurs de PageRank personnalisé. A la fin de la thèse, nous proposons une nouvelle mesure de centralité, qui généralise à la fois la centralité d'intermédiarité et PageRank. Cette nouvelle mesure est particulièrement bien adaptée pour la détection de la vulnérabilité de réseau.

Le programme de réplication d’environ la moitié du génome des mammifères est caractérisé par des U/N-domaines de réplication de l’ordre du méga-base en taille. Ces domaines sont bordés par des origines de réplication maitresses (MaOris) correspondantes à des régions (~200 kb) de chromatine ouverte favorables à l’initiation précoce de la réplication et de la transcription. Grâce au développement récent de technologies à haut débit de capture de conformations des chromosomes (Hi-C), des matrices de fréquences de co-localisation 3D entre toutes les paires de loci sont désormais déterminées expérimentalement. Il est apparu que les U/N-domaines sont reliés à l’organisation du génome en unités structurelles. Dans cette thèse, nous avons effectué une analyse combinée de données de Hi-C de lignées cellulaires humaines et de profils de temps de réplication pour explorer davantage les relations structure/fonction dans le noyau. Cela nous a conduit à décrire de nouveaux domaines de réplication de grande tailles (>3 Mb) : les split-U-domaines aussi bordés par des MaOris; à démontrer que la vague de réplication initiée aux MaOris ne dépend que du temps pendant la phase S et de montrer que le repliement de la chromatine est compatible avec un modèle d’équilibre 3D pour les régions euchromatiniennes à réplication précoces et un modèle d’équilibre 2D pour les régions heterochromatiniennes à réplication tardives associées à la lamina nucléaire. En représentant les matrices de co-localisation issues du Hi-C en réseaux d’interactions structurelles et en déployant des outils de la théorie des graphes, nous avons aussi démontré que les MaOris sont des hubs interconnectés à longue portée dans le réseau structurel, fondamentaux pour l’organisation 3D du génome et nous avons développé une méthodologie multi-échelle basée sur les ondelettes sur graphes pour délimiter objectivement des unités structurelles à partir des données Hi-C. Ce travail nous permet de discuter de la relation entre les domaines de réplication et les unités structurelles entre les différentes lignées cellulaires humaines. / The replication program of about one half of mammalian genomes is characterized by megabase-sized replication U/N-domains. These domains are bordered by master replication origins (MaOris) corresponding to ~200 kb regions of open chromatin favorable for early initiation of replication and transcription. Thanks to recent high-throughput chromosome conformation capture technologies (Hi-C), 3D co-localization frequency matrices between all genome loci are now experimentally determined. It appeared that U/N-domains were related to the organization of the genome into structural units. In this thesis, we performed a combined analysis of human Hi-C data and replication timing profiles to further explore the structure/function relationships in the nucleus. This led us to describe novel large (>3 Mb) replication timing split-U domains also bordered by MaOris, to demonstrate that the replication wave initiated at MaOris only depends of the time during S phase and to show that chromatin folding is compatible with a 3D equilibrium in early-replicating euchromatin regions turning to a 2D equilibrium in the late-replicating heterochromatin regions associated to nuclear lamina. Representing Hi-C co-localization matrices as structural networks and deploying graph theoretical tools, we also demonstrated that MaOris are long-range interconnected hubs in the structural network, central to the 3D organization of the genome and we developed a novel multi-scale methodology based on graph wavelets to objectively delineate structural units from Hi-C data. This work allows us to discuss the relationship between replication domains and structural units across different human cell lines.

Cette thèse fournit au lecteur un recueil d'applications de la théorie des graphes ; à ce but, des outils sur mesure, adaptés aux applications considérées, ont été conçus et mis en œuvre de manière inspirée par les données.Dans la première partie, une nouvelle métrique de centralité, nommée “bridgeness”, est présentée, basée sur une décomposition de la centralité intermédiaire (“betweenness centrality”) standard. Une composante, la “connectivité locale”, correspondante approximativement au degré d'un noeud, est différenciée de l'autre, qui, en revanche, évalue les propriétés structurelles à longue distance. En effet, cette dernière fournit une mesure de l'efficacité de chaque noeud à “relayer” parties faiblement connectées d'un réseau ; une caractéristique importante de cette métrique est son agnosticisme en ce qui concerne la structure de la communauté sous jacente éventuelle.Une deuxième application vise à décrire les caractéristiques dynamiques des graphes temporels qui apparaissent au niveau mésoscopique. L'ensemble de données de choix comprend 40 ans de publications scientifiques sélectionnées. L'apparition et l'évolution dans le temps d'un domaine d'étude spécifique (les ondelettes) sont capturées, en discriminant les caractéristiques persistantes des artefacts transitoires résultants du processus de détection des communautés, intrinsèquement bruité, effectué indépendamment sur des instantanées statiques successives. La notion de “flux laminaire”, sur laquelle repose le “score de complexité” que nous cherchons à optimiser, est présentée.Dans le même ordre d'idées, un réseau d'investisseurs japonais a été construit, sur la base d'un ensemble de données qui comprend des informations (indirectes) sur les filiales étrangères en copropriété. Une question très débattue dans le domaine de l'économie industrielle, l'hypothèse de Miwa-Ramseyer, a été démontrée de manière concluante comme fausse, du moins sous sa forme forte. / This thesis provides the reader with a compendium of applications of network theory; tailor-madetools suited for the purpose have been devised and implemented in a data-driven fashion. In the first part, a novel centrality metric, aptly named “bridgeness”, is presented, based on adecomposition of the standard betweenness centrality. One component, local connectivity, roughlycorresponding to the degree of a node, is set apart from the other, which evaluates longer-rangestructural properties. Indeed, the latter provides a measure of the relevance of each node in“bridging” weakly connected parts of a network; a prominent feature of the metric is its agnosticism with regard to the eventual ground truth community structure.A second application is aimed at describing dynamic features of temporal graphs which are apparent at the mesoscopic level. The dataset of choice includes 40 years of selected scientific publications.The appearance and evolution in time of a specific field of study (“wavelets”) is captured,discriminating persistent features from transient artifacts, which result from the intrinsically noisy community detection process, independently performed on successive static snapshots. The concept of “laminar stream”, on which the “complexity score” we seek to optimize is based, is introduced.In a similar vein, a network of Japanese investors has been constructed, based on a dataset which includes (indirect) information on co-owned overseas subsidiaries. A hotly debated issue in the field of industrial economics, the Miwa-Ramseyer hypothesis, has been conclusively shown to be false, at least in its strong form.