Search

Graph autoencoders (GAE) and variational graph autoencoders (VGAE) emerged as two powerful groups of unsupervised node embedding methods, with various applications to graph-based machine learning problems such as link prediction and community detection. Nonetheless, at the beginning of this Ph.D. project, GAE and VGAE models were also suffering from key limitations, preventing them from being adopted in the industry. In this thesis, we present several contributions to improve these models, with the general aim of facilitating their use to address industrial-level problems involving graph representations.Firstly, we propose two strategies to overcome the scalability issues of previous GAE and VGAE models, permitting to effectively train these models on large graphs with millions of nodes and edges. These strategies leverage graph degeneracy and stochastic subgraph decoding techniques, respectively. Besides, we introduce Gravity-Inspired GAE and VGAE, providing the first extensions of these models for directed graphs, that are ubiquitous in industrial applications. We also consider extensions of GAE and VGAE models for dynamic graphs. Furthermore, we argue that GAE and VGAE models are often unnecessarily complex, and we propose to simplify them by leveraging linear encoders. Lastly, we introduce Modularity-Aware GAE and VGAE to improve community detection on graphs, while jointly preserving good performances on link prediction.In the last part of this thesis, we evaluate our methods on several graphsextracted from the music streaming service Deezer. We put the emphasis on graph-based music recommendation problems. In particular, we show that our methods can improve the detection of communities of similar musical items to recommend to users, that they can effectively rank similar artists in a cold start setting, and that they permit modeling the music genre perception across cultures. At the end of this thesis, we present two additional models, recently deployed in production on the Deezer service to recommend music to millions of users. While being less directly linked to GAE and VGAE models, they provide a complementary perspective on music recommendation topics related to the ones we previously studied., Les autoencodeurs de graphes (GAE) et les autoencodeurs variationnels de graphes (VGAE) se sont imposés comme deux puissants groupes de méthodes permettant de construire des représentations vectorielles des nœuds d'un graphe de manière non-supervisée, avec des applications à divers problèmes d'apprentissage tels que la prédiction de liens manquants et la détection de communautés de nœuds. Néanmoins, au début de ce projet de thèse, les GAE et VGAE souffraient de limitations majeures. Ces dernières entravaient l'utilisation de ces modèles dans le cadre d'applications industrielles. Dans cette thèse, nous présentons plusieurs contributions permettant d'améliorer les GAE et VGAE afin de faciliter de telles utilisations.Tout d'abord, nous proposons deux stratégies permettant de surmonter les problèmes de passage à l'échelle des GAE et VGAE, et d'entraîner ces modèles sur des graphes ayant des millions de nœuds et d'arêtes. Ces stratégies exploitent respectivement des techniques de dégénérescence de graphes et de décodage stochastique de sous-graphes. Par ailleurs, nous présentons nos GAE et VGAE "inspirés de la gravité" (de l'anglais "Gravity-Inspired GAE and VGAE"), qui constituent les premières extensions de ces modèles destinées aux graphes dirigés, qui sont omniprésents dans les applications industrielles. Nous étudions également des extensions destinées aux graphes dynamiques. En outre, nous démontrons que les GAE et VGAE existants sont souvent inutilement complexes, et nous proposons donc de les simplifier en ayant recours à des encodeurs linéaires. Enfin, nous présentons nos GAE et VGAE "informés par la modularité'' (de l'anglais "Modularity-Aware GAE and VGAE"), qui permettent d'améliorer la détection de communautés de nœuds, tout en préservant de bonnes performances pour la prédiction de liens manquants.Dans la dernière partie de cette thèse, nous évaluons nos méthodes sur plusieurs graphes extraits du service de streaming musical Deezer. Nous nous concentrons sur des problèmes de recommandation musicale à partir de graphes. En particulier, nous montrons que nos méthodes permettent d'améliorer la détection de communautés d'entités musicales à recommander aux mêmes utilisateurs, mais aussi de mieux classer des artistes similaires dans un contexte de "démarrage à froid", et enfin de mieux modéliser la perception des genres musicaux à travers différentes cultures. Pour terminer, nous présentons également deux autres modèles, récemment déployés en production chez Deezer afin de recommander de la musique à des millions d'utilisateurs. Bien qu'étant moins directement liés aux GAE et VGAE, ils fournissent un point de vue complémentaire sur des sujets de recommandation musicale connexes à ceux étudiés précédemment.

This manuscript deals with inference problems on large, usually sparse, random graphs. We first focus on a planted tree problem, where a tree with known shape is planted inside a sparse Erdös-Rényi graph. When this tree is a path, we provide a complete characterization of the phase transition landscape, which differs from other related problems.We then move on to the problem of community detection, and the spectral algorithms designed to tackle this task. These algorithms are known for their sensitivity to adversarial noise in the graph. In contrast, we introduce a new spectral method based on a distance matrix and show that it performs equally well when the number of perturbed edges does not exceed a small power of n.Finally, we study several variations of the classical community detection: with edge labels, prescribed degree sequences, or directed edges. We introduce a general model that encompasses all those variants, and prove precise spectral results on the non-backtracking matrix of this model. This allows us to propose a general agnostic algorithm for all those variants as once.; On s'intéresse dans ce manuscrit à des problèmes d'inférence dans des graphes aléatoires de grande taille. Dans un premier temps, on étudie le problème des arbres plantés, où un arbre de forme connue est "caché" dans un graphe d'Erdös-Rényi peu dense. Dans le cas où l'arbre est un chemin, on détermine l'intégralité du paysage de transition de phase, qui a une forme inhabituelle par rapport à d'autres problèmes proches.On s'intéresse ensuite à la détection de communautés, et plus précisément aux algorithmes spectraux pour cette tâche. Ces algorithmes sont connus pour être peu robustes à des faibles perturbations du graphe. Malgré cela, on introduit un nouvel algorithme spectral basé sur une matrice différente, et l'on montre que cet algorithme est bien moins sensible aux perturbations: on peut rajouter ou enlever jusqu'à une petite puissance de n arêtes sans que sa performance ne soit affectée.Dans un troisième temps, on étudie des variantes du problème de détection de communautés : avec une distribution de degrés prescrite, des arêtes dirigées ou encore des étiques sur des arêtes. Toutes ces variantes font partie d'un modèle extrêmement général, sur lequel on prouve des résultats spectraux précis concernant la matrice non-rebroussante. Cela permet de proposer un algorithme à la fois très général et très performant pour tous ces problèmes à la fois.

The developement of new biotechnologies offers a large variety of biological datasets, extending the scope of biomedical research. These include genomic datasets, highly developed in statistical literature and metagenomic datasets, still relatively unknown, which require specific developments due to their special characteristics.The biological explored systems, represented using networks, enable us to model the functional relationships between its composing elements and to understand the underlying biological processes. In this context, this thesis provides mathematical studies of clustering algorithms and proper statistical tools to analyze these interactions. The first part of this thesis is dedicated to the development of a graph clustering algorithm, called CORE-clustering, to detect robustly representative variables, centers of specific variable clusters, within a high dimensional complex system. Specifically, we aim at highlighting these densely connected clusters, called CORE-clusters, forming major structures of the graph by only imposing, within each group, the minimal dimension and the minimal level of similarity. We then show through various applications the relevance of the CORE-clusters detected in the specific framework of genetic and road high dimensional networks.The second part of the thesis deals with the development of an extension of the spectral clustering algorithm which addresses the issue of identifying densely connected structures within a noisy graph, characteristic of real biological networks. Using the spectral clustering properties, this new variant, called l_1-spectral clustering enables to robustly bring out the natural hidden structure of the graph from the estimation of community indicators by imposing a lasso regularization. From a practical point of view, we show the stability of these estimators through various simulations, comparisons and biomedical applications. The third part of the thesis concerns the use of statistical tools, specifically adapted to the analysis of metagenomic datasets (intestinal microbiota genes). In the context of a clinical study conducted on patients suffering from liver pathologies at an early stage, we propose different strategies to identify the patients' clinical phenotypic profile and the microbial species involved in the development of the disease. To this end, we present a variety of exploratory, predictive and clustering methods used to identify groups of interacted bacteria and to understand the underlying mechanisms for the clinical trial. This information is the key to discover biomarkers, biological signatures categorizing patients in the disease. This clinical trial dealing with biomedical dataset from two diverse cohorts led us to develop fair learning approaches based on standard dimension reduction techniques to explain the total variabilities in the dataset while limiting the bias effect generated by the population's diversity, which is explored in the last part of the thesis.; L'essor de nouvelles biotechnologies permet actuellement de collecter une grande variété de données biologiques, élargissant ainsi le champ d'application de la recherche biomédicale. Parmi ces données, nous retrouvons notamment les données génomiques, dont la littérature dans le domaine statistique est très riche et les données métagénomiques, encore assez peu connues, qui nécessitent des développements particuliers dû à leur nature très différente. Les systèmes biologiques ainsi étudiés, représentés à partir de réseaux, permettent de modéliser les relations fonctionnelles entre les éléments qui les composent et d'en comprendre les processus biologiques sous-jacents. Dans ce contexte, cette thèse propose des développements autour de l'étude mathématique d'algorithmes de partitionnement et l'utilisation d'outils statistiques adaptés pour analyser ces interactions.La première partie de cette thèse est consacrée au développement d'un algorithme de clustering de graphe, appelé CORE-clustering, dédié à la détection robuste de variables représentatives, centres de clusters de variables spécifiques, au sein d'un système complexe de grande dimension. Plus précisément, nous cherchons à mettre en évidence ces clusters de variables très connectés, appelés CORE-clusters, formant des structures majeures du graphe en imposant seulement au sein de chaque groupe, d'une part, la dimension minimale et d'autre part, le niveau minimal de similarités. Nous montrons alors au travers de nombreuses applications la pertinence des CORE-clusters détectés notamment dans le cadre de réseaux génétiques et routiers de grandes dimensions.La deuxième partie de cette thèse concerne le développement d'une extension de l'algorithme du spectral clustering qui, traite de la problématique liée à l'identification de structures densément connectées au sein de graphes bruités, souvent caractéristiques des réseaux biologiques réels. En s'appuyant sur les propriétés du spectral clustering, cette nouvelle variante, appelée l_1-spectral clustering, permet de mettre en évidence les structures naturelles cachées du graphe au travers de l'estimation d'indicateurs de communautés en imposant une régularisation Lasso. D'un point de vue pratique, nous montrons la stabilité de ces estimateurs au travers de nombreuses simulations, comparaisons et applications biomédicales. La troisième partie concerne l'utilisation d'outils statistiques adaptés à l'analyse de données métagénomiques (gènes du microbiote intestinal). Dans le cadre d'une étude clinique réalisée sur des patients souffrant à un stade précoce, de pathologies hépatiques, nous proposons plusieurs stratégies afin d'identifier le profil phénotypique clinique type des patients ainsi que les espèces métagénomiques impliquées dans le développement de la maladie. Pour cela, nous proposons une variété de méthodes exploratoires, prédictives et de clustering de manière à mettre en évidence des groupements de bactéries présentant de fortes interactions et d'en comprendre les mécanismes sous-jacents pour l'étude de la pathologie. Cette information est essentielle pour la découverte de biomarqueurs, signatures biologiques classifiant les patients au sein de la maladie. Cette étude clinique, qui porte sur des données biomédicales issues de deux cohortes différentes, nous a amenés à développer dans cette dernière partie de la thèse, des méthodes statistiques adaptées. Nous proposons alors plusieurs approches d'apprentissage plus juste, basées sur des techniques de réduction de dimension standard afin de pouvoir expliquer l'ensemble des variabilités qui composent le jeu de données en limitant l'effet du biais engendré par la diversité des populations.

atlas.brussels est un outil de géovisualisation interactive en ligne qui permet de questionner l’extension spatiale et la fragmentation interne de l’aire métropolitaine bruxelloise. Pour ce faire, l’outil se focalise de manière originale sur des réseaux d’interaction spatiale appréhendés à la fois à l’échelle nationale et métropolitaine. Parmi les diverses composantes considérées figurent les déplacements de personnes (notamment domicile-travail), les communications (notamment les appels téléphoniques) ou encore les échanges économiques (notamment par le fret routier). atlas.brussels permet pour cela de rassembler, compléter, étendre et valoriser des travaux de recherche sur l’aire métropolitaine bruxelloise, et reste ouvert à l’intégration d’autres jeux de données. atlas.brussels is an interactive online geovisualization tool that questions the spatial extension and the internal fragmentation of the Brussels metropolitan area. To do this, the tool focuses in an original way on spatial interaction networks considered at both the national and the metropolitan scales. Among these networks appear movements of people (as home-to-work commuting), communications (as phone calls) and economic interactions (through the road freight interactions). Therefore, atlas.brussels combines, supplements, expands and promotes researches made on the metropolitan area of Brussels, and remains open to the integration of other datasets.

Graphs are mathematical tools for modelling relationships between entities. They are used in multiple scientific fields: in computer science for knowledge representation, in sociology for studying relationships between people, in chemistry for representing molecules and in many other fields. One specific type of relationships, that is of interest in this work, is the one that represents common membership of a set of entities to a set of groups. This relationship defines a multilayer network called the co-membership network where entities are represented by nodes and groups correspond to layers. Such relationship also has the property of transitivity which makes the layers of the co-membership network fully-connected. Moreover, in many cases, textual descriptions are associated to the groups and are represented in the co-membership network by layer attributes. The objective of this thesis if to develop community detection tools for co-membership networks using both the structural and semantic information they contain. The studied common membership relationship has various applications including the analysis of common attendancy of researchers to conferences and the representation of co-authorship of scientific publications. In social networks, this type of relationship is even more frequent and can be found in Twitter with common membership to lists. In this work, we give a formal definition of co-membership networks and underline the properties that distinguish them from the other multilayer networks. We present two algorithms for delimitting subgraphs that correspond to domains of interest of users. We also explain how to adapt data mining methods for the extraction of itemset and numeric patterns to the task of community detection in co-membership networks. Results are compared to those of state the art methods using two example networks from the social network Twitter and the collaborative encyclopedia Wikipedia., Les graphes sont considérés comme l’outil mathématique de prédilection pour la modélisation d'une relation entre des paires d’entités. Ils peuvent être utilisés pour modéliser une relation de connaissance entre des personnes, ou encore une relation de similarité entre des mots. Parmi ces relations, celle de l’appartenance commune d’un ensemble d’entités à un ensemble de groupes permet de définir un multigraphe de co-appartenance. Dans ce multigraphe, les entités correspondent aux nœuds, les relations aux liens et les groupes aux couches. Par ailleurs, la relation d’appartenance commune étant transitive, les nœuds d’une même couche forment une clique. Et dans plusieurs cas, des descriptions textuelles sont associées aux groupes et sont représentées par des attributs associés aux couches dans le multigraphe de co-appartenance. L’objectif de cette thèse est de développer des outils de détection de communautés de noeuds homogènes dans les multigraphes de co-appartenance en utilisant les informations structurelle et sémantique qui y sont contenues. La relation d’appartenance commune à des groupes, que nous étudions, se retrouve dans plusieurs situations réelles comme, par exemple, la participation d’un ensemble de chercheurs à des conférences ou la rédaction commune par des auteurs d’un ensemble d’articles. Dans les réseaux sociaux, cette relation est encore plus courante et nous la retrouvons, entre autres, dans le réseau social Twitter avec l’appartenance commune des utilisateurs aux listes. Dans ce travail, nous définissons formellement les multigraphes de co-appartenance et soulignons les propriétés qui les distinguent des multigraphes classiques. Nous présentons deux algorithmes pour y délimiter des sous-graphes qui correspondent à des domaines d’intérêt pour l’analyste utilisateur de l’outil de détection de communautés. Nous expliquons, aussi, comment adapter certaines méthodes de fouille de données pour l’extraction de motifs symboliques et numériques à la détection de communautés dans les multigraphes de co-appartenance. Les résultats obtenus sont comparés à ceux des méthodes de l’état de l’art en utilisant des exemples de multigraphes de co-appartenance issus du réseau social Twitter et de la plateforme collaborative Wikipedia.

Image segmentation has become an indispensable task that is widely employed in several image processing applications including object detection, object tracking, automatic driver assistance, and traffic control systems, etc. The literature abounds with algorithms for achieving image segmentation tasks. These methods can be divided into some main groups according to the underlying approaches, such as Region-based image segmentation, Feature-based clustering, Graph-based approaches and Artificial Neural Network-based image segmentation. Recently, complex networks have mushroomed both theories and applications as a trend of developments. Hence, image segmentation techniques based on community detection algorithms have been proposed and have become an interesting discipline in the literature. In this thesis, we propose a novel framework for community detection based image segmentation. The idea that brings social networks analysis domain into image segmentation quite satisfies with most authors and harmony in those researches. However, how community detection algorithms can be applied in image segmentation efficiently is a topic that has challenged researchers for decades. The contribution of this thesis is an effort to construct best complex networks for applying community detection and proposal novel agglomerate methods in order to aggregate homogeneous regions producing good image segmentation results. Besides, we also propose a content based image retrieval system using the same features than the ones obtained by the image segmentation processes. The proposed image search engine for real images can implement to search the closest similarity images with query image. This content based image retrieval relies on the incorporation of our extracted features into Bag-of-Visual-Words model. This is one of representative applications denoted that image segmentation benefits several image processing and computer visions applications. Our methods have been tested on several data sets and evaluated by many well-known segmentation evaluation metrics. The proposed methods produce efficient image segmentation results compared to the state of the art., La segmentation d’images est devenue une tâche indispensable largement utilisée dans plusieurs applications de traitement d’images, notamment la détection d’objets, le suivi d’objets, l’assistance automatique à la conduite et les systèmes de contrôle du trafic, etc. La littérature regorge d’algorithmes permettant de réaliser des tâches de segmentation d’images. Ces méthodes peuvent être divisées en groupes principaux en fonction des approches sous-jacentes, telles que la segmentation d'images basée sur les régions, la classification basée sur les caractéristiques de l'image, les approches basées sur les graphes et la segmentation d'images basée sur les réseaux de neurones. Récemment, l'analyse de réseaux sociaux a proposé de nombreuses théories et méthodologies. En particulier, des techniques de segmentation d’images basées sur des algorithmes de détection de communautés ont été proposées et forment une famille d'approches visible dans la littérature. Dans cette thèse, nous proposons un nouveau cadre pour la segmentation d'images basée sur la détection de communautés. Si l'idée de base d'utiliser le domaine de l'analyse des réseaux sociaux dans la segmentation de l'image est tout à fait séduisante, la manière dont les algorithmes de détection de communautés peuvent être appliqués efficacement à la segmentation d'images est un sujet qui continue à interroger. L’apport de cette thèse est un effort pour construire de manière pertinente des meilleurs réseaux complexes en fonction de l'application, des méthodes utilisées pour la détection de communautés et pour proposer de nouvelles méthodes pour agréger les régions homogènes afin de produire de bonnes segmentations d’images.Par ailleurs, nous proposons également un système de recherche d’images par le contenu (content-based image retrieval) utilisant les mêmes caractéristiques que celles obtenues par les processus de segmentation d’images. Le moteur de recherche d'images proposé fonctionne pour des images de scènes naturelles et permet de rechercher les images les plus similaires à l'image requête. Ce moteur de recherche d’images par le contenu repose sur l’utilisation des régions extraites comme mots visuels dans le modèle Bag-of-Visual-Words. Ceci permet de valider la généricité de notre approche de segmentation d’images à partir de réseaux complexes et son utilisation dans plusieurs domaines d'applications liés au traitement d’images et de vision par ordinateur. Nos méthodes ont été testées sur plusieurs jeux de données et évaluées en utilisant différentes mesures classiques de la qualité d'une segmentation. Les méthodes proposées produisent des segmentations d'image dont la qualité est supérieure à l'état de l'art.

The detection of block structures in matrices is an important challenge. First in data analysis where matrices are a key tool for data representation, as data tables or adjacency matrices. Indeed, for the first one, finding a co-clustering is equivalent to finding a row and column block structure of the matrix. For the second one, finding a structure of diagonal dominant blocks leads to a clustering of the data. Moreover, block structure detection is also usefull for the resolution of linear systems. For instance, it helps to create efficient Block Jacobi precoditioners or to find groups of rows that are strongly decorrelated in order to apply a solver such as Block Cimmino. In this dissertation, we focus our analysis on the detection of dominant diagonal block structures by symmetrically permuting the rows and columns of matrices. Lots of algorithms have been designed that aim to highlight such structures. Among them, spectral algorithms play a key role. They can be divided into two kinds. The first one consists of algorithms that first project the matrix rows onto a low-dimensional space generated by the matrix leading eigenvectors, and then apply a procedure such as a k-means on the reduced data. Their main drawbacks is that the knowledge of number of clusters to uncover is required. The second kind consists of iterative procedures that look for the k-th best partition into two subblocks of the matrix at step k. However, if the matrix structure shows more than two blocks, the best partition into two blocks may be a poor fit to the matrix groundtruth structure. Hence, we propose a spectral algorithm that deals with both issues described above. To that end, we preprocess the matrix with a doubly-stochastic scaling, which leverages the blocks. First we show the benefits of using such a scaling by using it as a preprocessing for the Louvain's algorithm, in order to uncover community structures in networks. We also investigate several global modularity measures designed for quantifying the consistency of a block structure. We generalise them to make them able to handle doubly-stochastic matrices, and thus we remark that our scaling tends to unify these measures. Then, we describe our algorithm that is based on spectral elements of the scaled matrix. Our method is built on the principle that leading singular vectors of a doubly-stochastic matrix should have a staircase pattern when their coordinates are sorted in the increasing order, under the condition that the matrix shows a hidden block structure. Tools from signal processing-that have been initially designed to detect jumps in signals-are applied to the sorted vectors in order to detect steps in these vectors, and thus to find the separations between the blocks. However, these tools are not specifically designed to this purpose. Hence procedures that we have implemented to answer the encountered issues are also described. We then propose three applications for the matrices block structure detection. First, community detection in networks, and the design of efficient Block Jacobi type preconditioners for solving linear systems. For these applications, we compare the results of our algorithm with those of algorithms that have been designed on purpose. Finally, we deal with the dialogue act detection in a discorsre, using the STAC database that consists in a chat of online players of " The Settlers of Catan ". To that end we connect classical clustering algorithms with a BiLSTM neural network taht preprocesses the dialogue unities. Finally, we conclude by giving some preliminary remarks about the extension of our method to rectangular matrices.; La détection de structures par blocs dans les matrices est un enjeu important. D'abord en analyse de données, où les matrices sont classiquement utilisées pour représenter des données, par exemple via les tables de données ou les matrices d'adjacence. Dans le premier cas, la détection d'une structure par blocs de lignes et de colonnes permet de trouver un co-clustering. Dans le second cas, la détection d'une structure par blocs diagonaux dominants fournit un clustering. En outre, la détection d'une structure par blocs est aussi utile pour la résolution de systèmes linéaires car elle permet, notamment, de rendre efficace des préconditionneurs type Block Jacobi, ou de trouver des groupes de lignes fortement décorrélés en vue de l'application d'un solveur type Block Cimmino. Dans cette thèse, nous centrons notre analyse sur la détection de blocs diagonaux dominants par permutations symétriques des lignes et des colonnes. De nombreux algorithmes pour trouver ces structures ont été créés. Parmi eux, les algorithmes spectraux jouent un rôle crucial, et se divisent en deux catégories. La première est composée d'algorithmes qui projettent les lignes de la matrice dans un espace de faible dimension composé des vecteurs propres dominants avant d'appliquer une procédure de type k-means sur les données réduites. Ces algorithmes ont le désavantage de nécessiter la connaissance du nombre de classes à découvrir. La deuxième famille est composée de procédures itératives qui, à chaque itération, cherchent la k-ième meilleure partition en deux blocs. Mais pour les matrices ayant plus de deux blocs, la partition optimale en deux blocs ne coïncide en général pas avec la véritable structure. Nous proposons donc un algorithme spectral répondant aux deux problèmes évoqués ci-dessus. Pour ce faire, nous prétraitons notre matrice via un équilibrage bi-stochastique permettant de stratifier les blocs. D'abord, nous montrons les bénéfices de cet équilibrage sur la détection de structures par blocs en l'utilisant comme prétraitement de l'algorithme de Louvain pour détecter des communautés dans des réseaux. Nous explorons aussi plusieurs mesures globales utilisées pour évaluer la cohérence d'une structure par blocs. En adaptant ces mesures à nos matrices bi-stochastiques, nous remarquons que notre équilibrage tend à unifier ces mesures. Ensuite, nous détaillons notre algorithme basé sur les éléments propres de la matrice équilibrée. Il est construit sur le principe que les vecteurs singuliers dominants d'une matrice bi-stochastique doivent présenter une structure en escalier lorsque l'on réordonne leurs coordonnées dans l'ordre croissant, à condition que la matrice ait une structure par blocs. Des outils de traitement du signal, initialement conçus pour détecter les sauts dans des signaux, sont appliqués aux vecteurs pour en détecter les paliers, et donc les séparations entre les blocs. Cependant, ces outils ne sont pas naturellement adaptés pour cette utilisation. Des procédures, mises en place pour répondre à des problèmes rencontrés, sont donc aussi détaillées. Nous proposons ensuite trois applications de la détection de structures par blocs dans les matrices. D'abord la détection de communautés dans des réseaux, et le préconditionnement de type Block Jacobi de systèmes linéaire. Pour ces applications, nous comparons les résultats de notre algorithme avec ceux d'algorithmes spécifiquement conçus à cet effet. Enfin, la détection des actes de dialogues dans un discours en utilisant la base de données STAC qui consiste en un chat de joueurs des "Colons de Catane" en ligne. Pour ce faire nous couplons des algorithmes de clustering non supervisés avec un réseau de neurones BiLSTM permettant de prétraiter les unités de dialogue. Enfin, nous concluons en entamant une réflexion sur la généralisation de notre méthode au cas des matrices rectangulaires.

In a global effort to achieve sustainable land management, regional and urban planning call for new adaptive datasets and methods to better grasp interactions between people and places. Understanding the moves of people, freight and information, and the relationships with the geographies of places are necessary knowledge for land use policies.Big-data currently offer a huge amount of information at very fine scales and in real-time. Analysing these data requires new techniques to obtain quick robust results. When dealing with origin and destination matrices resulting from big-data, community detection methods are useful to find how places are connected. The Louvain Method was applied on census or sensors datasets to define ‘interaction fields’. Analyses are performed on Belgium and Brussels.After a theoretical background, the second Part performs sensitivity analyses of the Louvain Method. The third part analyses moves of people. Results show that communities of commuting moves are much larger than those obtained by residential changes, and that administrative borders are serious constraints, confirmed by the study of train schedules requests. The fourth part uses GPS traces left by trucks as proxy of freight transportation. Diverting a dataset from its original fiscal objective requires pre-processing and conceptualisation that are time consuming. However, outcomes show that this dataset is a real opportunity to model goods transportation. Finally, the fifth part deals with mobile phone as proxy of moves of information. The very fine scale of the data and their variation in time lead to urban pulses but also to partitions varying in time and space. Big-data are a real opportunity to measure and understand space, but they need to be clearly understood and theoretically conceptualised.; Dans l’effort global d’atteindre une gestion durable du territoire, l’aménagement du territoire urbain et régional requièrent de nouvelles données et méthodes afin de mieux évaluer les interactions entre les personnes et les lieux. Comprendre les déplacements des personnes, du fret et de l’information, ainsi que leurs relations avec la géographie des lieux sont des connaissances nécessaires aux politiques d’aménagement du territoire.Les big-data offrent actuellement un déluge d’information en temps-réel à une échelle très fine, et l’analyse de celles-ci nécessite de nouvelles techniques pour obtenir rapidement des résultats robustes. Lorsque l’on manipule des matrices d’origines et de destinations résultant des big-data, les méthodes de détections de communautés sont efficaces pour mettre en évidence comment les lieux sont connectés. La Méthode de Louvain a été appliquée de nombreuses fois sur des données du census mais également sur des données provenant de senseurs afin de définir des ‘champs d’interactions’. Les analyses ont été appliquées à l’échelle de la Belgique et de Bruxelles.Après le développement du cadre théorique, la deuxième partie de cette thèse se concentre sur les analyses de sensibilité de la Méthode de Louvain. La troisième partie analyse quant à elle les mouvements des personnes. Les résultats montrent que les communautés de navettes ont une empreinte spatiale plus large que celles détectées dans les mouvements de changements de résidence, et que les frontières administratives sont de sérieuses contraintes, comme confirmé par l’étude des données portant sur les recherches des horaires de trains effectuées depuis internet. La quatrième partie utilise les traces GPS émises par la circulation des camions comme un proxy du transport de fret. Détourner un tel jeu de données de son objectif fiscal initial demande des traitements et des conceptualisations qui sont consommatrice de temps. Cependant, les résultats font de ces données une réelle opportunité de modélisation du transport de marchandise. Finalement, la cinquième partie se concentre sur les appels téléphoniques mobiles comme proxy des mouvements d’informations dans l’espace. L’échelle très fine des données, ainsi que leurs variations dans le temps mènent aux pulsations des villes mais également à des partitions spatiales qui varient dans le temps et l’espace. Les big-data sont donc une réelle opportunité de mesurer et de comprendre l’espace mais elles ont besoin d’être clairement comprises et théoriquement conceptualisées.

Most of the time, the first step to learn word embeddings is to build a word co-occurrence matrix. As such matrices are equivalent to graphs, complex networks theory can naturally be used to deal with such data. In this paper, we consider applying community detection, a main tool of this field, to the co-occurrence matrix corresponding to a huge corpus. Community structure is used as a way to reduce the dimensionality of the initial space. Using this community structure, we propose a method to extract word embeddings that are comparable to the state-of-the-art approaches., in French

The detection of communities in social networks has become a very important task. Indeed, as its role consists in partitioning the nodes of a network into subgroups having properties in common, this makes it possible to analyse the behaviour of the entities of the network and to predict the evolution of the latter in time.In social networks, information about nodes, links, and messages may be imperfect. From there, the analysis of such a type of network necessitates the use of a theory of uncertainty. In this thesis, we propose three contributions applied in the framework of the theory of belief functions:First, we were interested in showing the advantage of using evidential attributes in social networks. Indeed, we compared the results of the classification of nodes with uncertain attributes (numerical, probabilistic, evidential) generated according to the structure of the network. To do this, we considered two scenarios: attributes generated randomly and others sorted. We also performed the tests in the case of data that was noisy. In order to measure the quality of clustering results, we used normalised mutual information (NMI).The second contribution consists on the correction of noisy information in social networks. To do this, we proposed a model based on the comparison of the calculated distances between the triplets of the network and the coherent triplets defined initially. A triplet is composed of two nodes connected to each other by a link. In order to test the proposed approach, we first tested three cases: only the nodes are noisy, only the links are noisy and finally the nodes and the links are noisy simultaneously. Then we tested the method by varying several network parameters. In order to measure the quality of the obtained results, we calculated the accuracyThe third contribution is to detect which links are spammed in a social network. A link is considered spammed if its initial class changes accordingto the types of messages transiting on it. To do this, we used the theory of belief functions to combine the information of links and messages. In order to test our approach, we considered two cases: only the messages are noisy and the messages as well as the links are noisy simultaneously. The quality of the classication results was measured using accuracy, precision and recall measurements..; La détection de communautés dans les réseaux sociaux est devenue une tâche très importante. En effet, comme son rôle consiste à partitionner les nœuds d'un réseau en sous groupes ayant des propriétés en commun, ceci permet d'analyser le comportement des entités du réseau et de prédire l'évolution de ce dernier dans le temps.Dans les réseaux sociaux, les informations portant sur les nœuds, liens et messages peuvent être imparfaites. A partir de là, l'analyse d'un tel type de réseaux nécessite l'utilisation d'une théorie de l'incertain. Dans cette thèse, nous proposons trois contributions appliquées dans le cadre de la théorie des fonctions de croyance.Tout d'abord, nous nous sommes intéressés à montrer l'avantage de l'utilisation des attributs évidentiels dans les réseaux sociaux. En effet, nous avons comparé les résultats de la classification des nœuds ayant des attributs incertains (numériques, probabilistes, évidentiels) générés en fonction de la structure du réseau. Pour ce faire, nous avons considéré deux scénarios : attributs générés aléatoirement et d'autres triés. Nous avons également effectué les tests dans le cas des données qui ont été bruitées. Afin de mesurer la qualité des résultats dela classification, nous avons utilisé l'information mutuelle normalisée.La deuxième contribution consiste en la correction des informations bruitées dans les réseaux sociaux. Pour ce faire, nous avons proposé un modèle qui se fonde sur la comparaison des distances calculées entre les triplets du réseau et les triplets cohérents définis initialement. On appelle un triplet deux nœuds reliés entre eux par un lien. Afin de tester l'approche proposée, nous avons testé dans un premier temps trois cas : les nœuds uniquement sont bruités, les liens uniquement sont bruités et enfin les nœuds et les liens sont bruités simultanément. Ensuite, nous avons testé la méthode en faisant varier plusieurs paramètres du réseau. Dans le but de mesurer la qualité des résultats obtenus, nous avons calculé l'exactitude.La troisième contribution consiste à détecter quels sont les liens spammés dans un réseau social. Un lien est considéré comme spammé si sa classe initiale se modifie en fonction des types de messages transitant dessus. Pour ce faire, nous avons utilisé la théorie des fonctions de croyance pour combiner les informations des liens et des messages. Dans le but de tester notre approche, nous avons considéré deux cas : les messages sont bruités uniquement et les messages ainsi que les liens sont bruités simultanément. La qualité des résultats de la classification a été mesurée en utilisant les mesures de l'exactitude, la précision et le rappel.

The development of online social media has created many opportunities to communicate, access, and share information from anywhere and at anytime. This kind of application such as Instagram, WhatsApp, Imo, Line, as well as Facebook affords plenty of possibilities for getting in touch with friends, colleagues, and relatives at every moment with real-time messages, photos, videos, etc.Data collected from those applications integrate two parameters such as the time and the geographical position from which they were sent and/or received. Therefore, it is worthwhile to build a social graph based on these data where individuals are the vertices and their interactions the edges.Alongside the growth of online social media, there is a rapid expansion of social network analysis (SNA), which is a process of exploring the graph in order to discover knowledge leading to informative decision-making. At the heart of the SNA topics that attract many scientists, we have the community detection. The mean reason is related to the fact that individuals tend to form a community in manyreal-life situations.Early works in community detection focused mainly on partitioning networks into several global communities before they target communities evolution over time. The main drawback of such approaches is the difficulty to obtain the entire network on which we may process a set of algorithms to track evolution. As a result, many researchers focused on detecting and tracking local dynamic communities. An extension of local communities is called “ego-communities”. Unlike local communities, ego-centered ones can be built based on a large neighborhood of the ego. They allow, among others, to better identify and track the network elements activities from some particular nodes. Moreover, the existing works on ego-communities are built based on the direct neighborhood of the ego ignoring the fact that indirect neighbors may have special impact on the structure. In addition, existing works did not take into account dynamic ego-communities. To overcome these weaknesses, we have proposed adynamic ego-community solution that works in three steps, namely :1. create several snapshots of the dynamic network. Each snapshot represents the state of the dynamic network during a given period ;2. propose and apply a static ego-community detection algorithm on each snapshot to discover ego-communities ;3. get the structure of the detected ego-communities on two successive snapshots and check whether there are major changes. Depending on the nature of the change, the algorithm performs an interpretation corresponding to a characterization of the community evolution.In order to validate our solution, we conducted a validation on three datasets. The results of experimentation showed the effectiveness of our solution and its benefits., Le développement des réseaux sociaux en ligne a donné naissance à plusieurs opportunités permettant de communiquer, d'accéder et de partager de l'information de n'importe où et à n'importe quel moment. Par exemple, les applications sociales telles que Facebook, Viber, WhatsApp, Imo, Line, entre autres, permettent de faire connaissance avec des amis et de discuter avec eux via des photos, des vidéos ou encore par messagerie instantanée.Les données collectées à partir de ces applications intègrent le temps et la position géographique à partir desquels les messages ont été envoyés et/ou reçus. De ce fait, il serait intéressant de construire à partir de ces données un graphe social dont les nœuds représentent les individus et les liens leur relations.L'expansion des réseaux sociaux en ligne s'est accompagnée d'un développement remarquable de l'Analyse des Réseaux Sociaux (ARS), qui est un processus d'exploration de réseaux visant à identifier des caractéristiques et d'en exploiter les informations. La détection de communautés est l'une des thématiques principales de l'ARS qui attirent de plus en plus l'attention de nombreux chercheurs. Les premiers travaux relatifs à la détection de communautés se limitaient aux communautés statiques. Avec le temps, la dimension temporelle qui désigne l'évolution de communautés a été ajoutée pour pouvoir gérer l'aspect dynamique des réseaux sociaux actuels.En effet, la majorité des travaux existants cherchent à partitionner un réseau en plusieurs communautés « globales » et suivre leur évolution au fil du temps. L'inconvénient principale de cette approche est qu'elle nécessite l'état global du réseau. Or, il est souvent difficile d'obtenir un réseau dynamique dans sa globalité. Une autre approche consiste à détecter les communautés « locales » qui sont construites à partir de certains nœuds spécifiques, appelés « nœuds d'intérêt ». Une extension de communautés locales est appelée « communautés ego-centrées » et constitue le contexte d'étude de cette thèse. En effet, contrairement aux communautés locales, celles ego-centrées sont construites sur la base d'un voisinage direct ou indirect du nœud d'intérêt. Ainsi, elles permettent, entre autres, de mieux comprendre les relations établies entre le nœud d'intérêt et ses voisins directs et indirects.Même si la longueur du voisinage constitue un atout de communautés ego-centrées, les travaux existants se limitent encore au voisinage direct lors de la détection de communautés. De plus, les solutions existantes ne prennent pas en compte les communautés ego-centrées dynamiques. L'objectif de cette thèse est de pallier à ces manquements dans l'étude des communautés égo-centrées. Pour ce faire, nous avons proposé une solution de détection de communautés dynamiques qui fonctionne en trois étapes, à savoir :1.Faire plusieurs captures du réseau dynamique à des instants précis. Chaque capture représente l'état du réseau dynamique au cours d'une période donnée ;2.Proposer et appliquer un algorithme de détection de communautés statiques sur chaque capture en vue de découvrir des communautés égo-centrées ;3.Prendre la structure d'une communauté égo-centrée sur deux instantanés successifs et vérifier s'il y a eu des changements majeurs. Pour interpréter la nature des changements possibles, nous avons défini des règles de correspondance. Ainsi, au fil du temps nous établissons la manière d'évolution des différentes communautés.Nous avons implémenté notre solution avec une pile d'outils dédiés à l'ARS et nous avons utilisé trois jeux de données. Les résultats d'expérimentation ont montré la faisabilité de notre solution, ses gains et son efficacité.

In a global effort to achieve sustainable land management, regional and urban planning call for new adaptive datasets and methods to better grasp interactions between people and places. Understanding the moves of people, freight and information, and the relationships with the geographies of places are necessary knowledge for land use policies.Big-data currently offer a huge amount of information at very fine scales and in real-time. Analysing these data requires new techniques to obtain quick robust results. When dealing with origin and destination matrices resulting from big-data, community detection methods are useful to find how places are connected. The Louvain Method was applied on census or sensors datasets to define ‘interaction fields’. Analyses are performed on Belgium and Brussels.After a theoretical background, the second Part performs sensitivity analyses of the Louvain Method. The third part analyses moves of people. Results show that communities of commuting moves are much larger than those obtained by residential changes, and that administrative borders are serious constraints, confirmed by the study of train schedules requests. The fourth part uses GPS traces left by trucks as proxy of freight transportation. Diverting a dataset from its original fiscal objective requires pre-processing and conceptualisation that are time consuming. However, outcomes show that this dataset is a real opportunity to model goods transportation. Finally, the fifth part deals with mobile phone as proxy of moves of information. The very fine scale of the data and their variation in time lead to urban pulses but also to partitions varying in time and space. Big-data are a real opportunity to measure and understand space, but they need to be clearly understood and theoretically conceptualised.; Dans l’effort global d’atteindre une gestion durable du territoire, l’aménagement du territoire urbain et régional requièrent de nouvelles données et méthodes afin de mieux évaluer les interactions entre les personnes et les lieux. Comprendre les déplacements des personnes, du fret et de l’information, ainsi que leurs relations avec la géographie des lieux sont des connaissances nécessaires aux politiques d’aménagement du territoire.Les big-data offrent actuellement un déluge d’information en temps-réel à une échelle très fine, et l’analyse de celles-ci nécessite de nouvelles techniques pour obtenir rapidement des résultats robustes. Lorsque l’on manipule des matrices d’origines et de destinations résultant des big-data, les méthodes de détections de communautés sont efficaces pour mettre en évidence comment les lieux sont connectés. La Méthode de Louvain a été appliquée de nombreuses fois sur des données du census mais également sur des données provenant de senseurs afin de définir des ‘champs d’interactions’. Les analyses ont été appliquées à l’échelle de la Belgique et de Bruxelles.Après le développement du cadre théorique, la deuxième partie de cette thèse se concentre sur les analyses de sensibilité de la Méthode de Louvain. La troisième partie analyse quant à elle les mouvements des personnes. Les résultats montrent que les communautés de navettes ont une empreinte spatiale plus large que celles détectées dans les mouvements de changements de résidence, et que les frontières administratives sont de sérieuses contraintes, comme confirmé par l’étude des données portant sur les recherches des horaires de trains effectuées depuis internet. La quatrième partie utilise les traces GPS émises par la circulation des camions comme un proxy du transport de fret. Détourner un tel jeu de données de son objectif fiscal initial demande des traitements et des conceptualisations qui sont consommatrice de temps. Cependant, les résultats font de ces données une réelle opportunité de modélisation du transport de marchandise. Finalement, la cinquième partie se concentre sur les appels téléphoniques mobiles comme proxy des mouvements d’informations dans l’espace. L’échelle très fine des données, ainsi que leurs variations dans le temps mènent aux pulsations des villes mais également à des partitions spatiales qui varient dans le temps et l’espace. Les big-data sont donc une réelle opportunité de mesurer et de comprendre l’espace mais elles ont besoin d’être clairement comprises et théoriquement conceptualisées.

The detection of block structures in matrices is an important challenge. First in data analysis where matrices are a key tool for data representation, as data tables or adjacency matrices. Indeed, for the first one, finding a co-clustering is equivalent to finding a row and column block structure of the matrix. For the second one, finding a structure of diagonal dominant blocks leads to a clustering of the data. Moreover, block structure detection is also usefull for the resolution of linear systems. For instance, it helps to create efficient Block Jacobi precoditioners or to find groups of rows that are strongly decorrelated in order to apply a solver such as Block Cimmino. In this dissertation, we focus our analysis on the detection of dominant diagonal block structures by symmetrically permuting the rows and columns of matrices. Lots of algorithms have been designed that aim to highlight such structures. Among them, spectral algorithms play a key role. They can be divided into two kinds. The first one consists of algorithms that first project the matrix rows onto a low-dimensional space generated by the matrix leading eigenvectors, and then apply a procedure such as a k-means on the reduced data. Their main drawbacks is that the knowledge of number of clusters to uncover is required. The second kind consists of iterative procedures that look for the k-th best partition into two subblocks of the matrix at step k. However, if the matrix structure shows more than two blocks, the best partition into two blocks may be a poor fit to the matrix groundtruth structure. Hence, we propose a spectral algorithm that deals with both issues described above. To that end, we preprocess the matrix with a doubly-stochastic scaling, which leverages the blocks. First we show the benefits of using such a scaling by using it as a preprocessing for the Louvain's algorithm, in order to uncover community structures in networks. We also investigate several global modularity measures designed for quantifying the consistency of a block structure. We generalise them to make them able to handle doubly-stochastic matrices, and thus we remark that our scaling tends to unify these measures. Then, we describe our algorithm that is based on spectral elements of the scaled matrix. Our method is built on the principle that leading singular vectors of a doubly-stochastic matrix should have a staircase pattern when their coordinates are sorted in the increasing order, under the condition that the matrix shows a hidden block structure. Tools from signal processing-that have been initially designed to detect jumps in signals-are applied to the sorted vectors in order to detect steps in these vectors, and thus to find the separations between the blocks. However, these tools are not specifically designed to this purpose. Hence procedures that we have implemented to answer the encountered issues are also described. We then propose three applications for the matrices block structure detection. First, community detection in networks, and the design of efficient Block Jacobi type preconditioners for solving linear systems. For these applications, we compare the results of our algorithm with those of algorithms that have been designed on purpose. Finally, we deal with the dialogue act detection in a discorsre, using the STAC database that consists in a chat of online players of " The Settlers of Catan ". To that end we connect classical clustering algorithms with a BiLSTM neural network taht preprocesses the dialogue unities. Finally, we conclude by giving some preliminary remarks about the extension of our method to rectangular matrices., La détection de structures par blocs dans les matrices est un enjeu important. D'abord en analyse de données, où les matrices sont classiquement utilisées pour représenter des données, par exemple via les tables de données ou les matrices d'adjacence. Dans le premier cas, la détection d'une structure par blocs de lignes et de colonnes permet de trouver un co-clustering. Dans le second cas, la détection d'une structure par blocs diagonaux dominants fournit un clustering. En outre, la détection d'une structure par blocs est aussi utile pour la résolution de systèmes linéaires car elle permet, notamment, de rendre efficace des préconditionneurs type Block Jacobi, ou de trouver des groupes de lignes fortement décorrélés en vue de l'application d'un solveur type Block Cimmino. Dans cette thèse, nous centrons notre analyse sur la détection de blocs diagonaux dominants par permutations symétriques des lignes et des colonnes. De nombreux algorithmes pour trouver ces structures ont été créés. Parmi eux, les algorithmes spectraux jouent un rôle crucial, et se divisent en deux catégories. La première est composée d'algorithmes qui projettent les lignes de la matrice dans un espace de faible dimension composé des vecteurs propres dominants avant d'appliquer une procédure de type k-means sur les données réduites. Ces algorithmes ont le désavantage de nécessiter la connaissance du nombre de classes à découvrir. La deuxième famille est composée de procédures itératives qui, à chaque itération, cherchent la k-ième meilleure partition en deux blocs. Mais pour les matrices ayant plus de deux blocs, la partition optimale en deux blocs ne coïncide en général pas avec la véritable structure. Nous proposons donc un algorithme spectral répondant aux deux problèmes évoqués ci-dessus. Pour ce faire, nous prétraitons notre matrice via un équilibrage bi-stochastique permettant de stratifier les blocs. D'abord, nous montrons les bénéfices de cet équilibrage sur la détection de structures par blocs en l'utilisant comme prétraitement de l'algorithme de Louvain pour détecter des communautés dans des réseaux. Nous explorons aussi plusieurs mesures globales utilisées pour évaluer la cohérence d'une structure par blocs. En adaptant ces mesures à nos matrices bi-stochastiques, nous remarquons que notre équilibrage tend à unifier ces mesures. Ensuite, nous détaillons notre algorithme basé sur les éléments propres de la matrice équilibrée. Il est construit sur le principe que les vecteurs singuliers dominants d'une matrice bi-stochastique doivent présenter une structure en escalier lorsque l'on réordonne leurs coordonnées dans l'ordre croissant, à condition que la matrice ait une structure par blocs. Des outils de traitement du signal, initialement conçus pour détecter les sauts dans des signaux, sont appliqués aux vecteurs pour en détecter les paliers, et donc les séparations entre les blocs. Cependant, ces outils ne sont pas naturellement adaptés pour cette utilisation. Des procédures, mises en place pour répondre à des problèmes rencontrés, sont donc aussi détaillées. Nous proposons ensuite trois applications de la détection de structures par blocs dans les matrices. D'abord la détection de communautés dans des réseaux, et le préconditionnement de type Block Jacobi de systèmes linéaire. Pour ces applications, nous comparons les résultats de notre algorithme avec ceux d'algorithmes spécifiquement conçus à cet effet. Enfin, la détection des actes de dialogues dans un discours en utilisant la base de données STAC qui consiste en un chat de joueurs des "Colons de Catane" en ligne. Pour ce faire nous couplons des algorithmes de clustering non supervisés avec un réseau de neurones BiLSTM permettant de prétraiter les unités de dialogue. Enfin, nous concluons en entamant une réflexion sur la généralisation de notre méthode au cas des matrices rectangulaires.

Graphs are ubiquitous in many fields of research ranging from sociology to biology. A graph is a very simple mathematical structure that consists of a set of elements, called nodes, connected to each other by edges. It is yet able to represent complex systems such as protein-protein interaction or scientific collaborations. Graph clustering is a central problem in the analysis of graphs whose objective is to identify dense groups of nodes that are sparsely connected to the rest of the graph. These groups of nodes, called clusters, are fundamental to an in-depth understanding of graph structures. There is no universal definition of what a good cluster is, and different approaches might be best suited for different applications. Whereas most of classic methods focus on finding node partitions, i.e. on coloring graph nodes so that each node has one and only one color, more elaborate approaches are often necessary to model the complex structure of real-life graphs and to address sophisticated applications. In particular, in many cases, we must consider that a given node can belong to more than one cluster. Besides, many real-world systems exhibit multi-scale structures and one much seek for hierarchies of clusters rather than flat clusterings. Furthermore, graphs often evolve over time and are too massive to be handled in one batch so that one must be able to process stream of edges. Finally, in many applications, processing entire graphs is irrelevant or expensive, and it can be more appropriate to recover local clusters in the neighborhood of nodes of interest rather than color all graph nodes. In this work, we study alternative approaches and design novel algorithms to tackle these different problems. The novel methods that we propose to address these different problems are mostly inspired by variants of modularity, a classic measure that accesses the quality of a node partition, and by random walks, stochastic processes whose properties are closely related to the graph structure. We provide analyses that give theoretical guarantees for the different proposed techniques, and endeavour to evaluate these algorithms on real-world datasets and use cases., Les graphes sont omniprésents dans de nombreux domaines de recherche, allant de la biologie à la sociologie. Un graphe est une structure mathématique très simple constituée d’un ensemble d’éléments, appelés nœuds, reliés entre eux par des liens, appelés arêtes. Malgré cette simplicité, les graphes sont capables de représenter des systèmes extrêmement complexes, comme les interactions entre protéines ou les collaborations scientifiques. Le partitionnement ou clustering de graphe est un problème central en analyse de graphe dont l’objectif est d’identifier des groupes de nœuds densément interconnectés et peu connectés avec le reste du graphe. Ces groupes de nœuds, appelés clusters, sont fondamentaux pour une compréhension fine de la structure des graphes. Il n’existe pas de définition universelle de ce qu’est un bon cluster, et différentes approches peuvent s’avérer mieux adaptées dans différentes situations. Alors que les méthodes classiques s’attachent à trouver des partitions des nœuds de graphe, c’est-à-dire à colorer ces nœuds de manière à ce qu’un nœud donné n’ait qu’une et une seule couleur, des approches plus élaborées se révèlent nécessaires pour modéliser la structure complexe des graphes que l’on rencontre en situation réelle. En particulier, dans de nombreux cas, il est nécessaire de considérer qu’un nœud donné peut appartenir à plus d’un cluster. Par ailleurs, de nombreux systèmes que l’on rencontre en pratique présentent une structure multi-échelle pour laquelle il est nécessaire de partir à la recherche de hiérarchies de clusters plutôt que d’effectuer un partitionnement à plat. De plus, les graphes que l’on rencontre en pratique évoluent souvent avec le temps et sont trop massifs pour être traités en un seul lot. Pour ces raisons, il est souvent nécessaire d’adopter des approches dites de streaming qui traitent les arêtes au fil de l’eau. Enfin, dans de nombreuses applications, traiter des graphes entiers n’est pas nécessaire ou est trop coûteux, et il est plus approprié de retrouver des clusters locaux dans un voisinage de nœuds d’intérêt plutôt que de colorer tous les nœuds. Dans ce travail, nous étudions des approches alternatives de partitionnement de graphe et mettons au point de nouveaux algorithmes afin de résoudre les différents problèmes évoqués ci-dessus.

In the real world, numerous networks appear naturally, they are everywhere, in many disciplines, for example in computer science with router networks, satellite networks, webpage networks, in biology with neural networks, in ecology with biological interaction networks, in linguistic with synonym networks, in law with legal decision networks, in economy with interbank networks, in social sciences and humanities with social networks. Generally, a network reflects the interactions between many entities of a system. These interactions have different sources, a social link or a friendship link in a social network, a cable in a router network, a chemical reaction in a protein-protein interaction network, a hyperlink in a webpage network. Furthermore, the rapid democratization of digital technology in our societies, with internet in particular, leads to create new systems which can be seen as networks. Finally, all these networks depict very specific features : they come from pratical contexts, most of the time they are big (they may be comprised of several billion of nodes and links, containing a large amount of information), they share statistical properties. In this regard, they are called real-world networks or complex networks. Nowaday, network science is a research area in its own right focusing on describing and modeling these networks in order to reveal their main features and improve our understanding of their mecanisms. Most of the works in this area use graphs formalism which provides a set of mathematical tools well suited for analyzing the topology of these networks. It exists many applications, for instance applications in spread of epidemy or computer viruses, weakness of networks in case of a breakdown, attack resilience, study for link prediction, recommandation, etc. One of the major issue is the identification of community structure. The large majority of real-world networks depicts several levels of organization in their structure. Because of there is a weak global density coupled with a strong local density, we observe that nodes are usually organized into groups, called communities, which are more internally connected than they are to the rest of the network. Moreover, these structures have a meaning in the network itself, for example communities of a social network may correspond to social groups (friends, families, etc.), communities of a protein-protein network may translate fonctions of a cell, communities may be also related to similar subjects in a webpage network [...]; Il existe dans le monde réel un nombre important de réseaux qui apparaissent naturellement, on les retrouve un peu partout, dans de nombreuses disciplines, par exemple en informatique avec les réseaux de routeurs, les réseaux de satellites, les réseaux de pages Web, en biologie avec les réseaux des neurones, en écologie avec les réseaux d’interactions biologiques, en linguistiques avec les réseaux de synonymes, en droit avec les réseaux de décisions juridiques, en économie avec les réseaux interbancaires, en sciences humaines avec les réseaux sociaux. De manière générale, un réseau reflète les interactions entre les nombreuses entités d’un système. Ces interactions peuvent être de différentes natures, un lien social ou un lien d’amitié dans un réseau social constitué de personnes, un câble dans un réseau de routeurs, une réaction chimique dans un réseau biologique de protéines, un hyperlien dans un réseau de pages Web, etc. Plus encore, la rapide démocratisation du numérique dans nos sociétés, avec Internet notamment, a pour conséquence de produire de nouveaux systèmes qui peuvent être représentés sous forme de réseaux. Finalement, tous ces réseaux présentent des particularités bien spécifiques : ils sont issus de contextes pratiques, ils sont le plus souvent de grande taille (on retrouve quelques fois des réseaux constitués de plusieurs milliards de nœuds et de liens, contenant donc une grande quantité d’information), ils présentent des propriétés statistiques communes. À cet égard, ils sont regroupés sous l’appellation de réseaux réels, graphes de terrain ou encore réseaux complexes. Aujourd'hui, la science des réseaux est un domaine de recherche à part entière dont l’enjeu principal est de parvenir à décrire et modéliser ces réseaux avec précision afin de révéler leurs caractéristiques générales et de mieux comprendre leurs mécanismes. La plupart des travaux dans ce domaine utilisent le formalisme des graphes qui fournit un ensemble d’outils mathématiques particulièrement adaptés à l’analyse topologique et structurelle des réseaux. Il existe de nombreuses applications dans ce domaine, par exemple des applications concernant la propagation d’épidémie ou de virus informatique, la fragilité du réseau en cas de panne, sa résilience en cas d’attaque, l’étude de la dynamique pour prédire l’apparition de nouveaux liens, la recommandation, etc. L’un des problèmes complexes actuels, qui a beaucoup d’applications, est l’identification de la structure communautaire. La grande majorité des réseaux réels sont caractérisés par des niveaux d’organisation dans leur structure mésoscopique. Du fait de la faible densité globale des réseaux réels couplée à la forte densité locale, on observe la présence de groupes de nœuds fortement liés entre eux et plus faiblement liés avec le reste du réseau, que l’on appelle communautés. Ces structures ont également du sens dans le réseau lui-même, par exemple les communautés d’un réseau social peuvent correspondre à des groupes sociaux (amis, familles, etc.), les communautés d’un réseau de protéines peuvent traduire des réponses fonctionnelles, elles peuvent correspondre à des sujets similaires dans un réseau de pages Web, pour donner quelques exemples [...]

Spurred by recent advances on the theoretical analysis of the performances of the data-driven machine learning algorithms, this thesis tackles the performance analysis and improvement of high dimensional data and graph clustering. Specifically, in the first bigger part of the thesis, using advanced tools from random matrix theory, the performance analysis of spectral methods on dense realistic graph models and on high dimensional kernel random matrices is performed through the study of the eigenvalues and eigenvectors of the similarity matrices characterizing those data. New improved methods are proposed and are shown to outperform state-of-the-art approaches. In a second part, a new algorithm is proposed for the detection of heterogeneous communities from multi-layer graphs using variational Bayes approaches to approximate the posterior distribution of the sought variables. The proposed methods are successfully applied to synthetic benchmarks as well as real-world datasets and are shown to outperform standard approaches to clustering in those specific contexts.; Motivée par les récentes avancées dans l'analyse théorique des performances des algorithmes d'apprentissage automatisé, cette thèse s'intéresse à l'analyse de performances et à l'amélioration de la classification nonsupervisée de données et graphes en grande dimension. Spécifiquement, dans la première grande partie de cette thèse, en s'appuyant sur des outils avancés de la théorie des grandes matrices aléatoires, nous analysons les performances de méthodes spectrales sur des modèles de graphes réalistes et denses ainsi que sur des données en grandes dimensions en étudiant notamment les valeurs propres et vecteurs propres des matrices d'affinités de ces données. De nouvelles méthodes améliorées sont proposées sur la base de cette analyse théorique et démontrent à travers de nombreuses simulations que leurs performances sont meilleures comparées aux méthodes de l'état de l'art. Dans la seconde partie de la thèse, nous proposons un nouvel algorithme pour la détection de communautés hétérogènes entre plusieurs couches d'un graphe à plusieurs types d'interaction. Une approche bayésienne variationnelle est utilisée pour approximer la distribution apostériori des variables latentes du modèle. Toutes les méthodes proposées dans cette thèse sont utilisées sur des bases de données synthétiques et sur des données réelles et présentent de meilleures performances en comparaison aux approches standard de classification dans les contextes susmentionnés.

Spurred by recent advances on the theoretical analysis of the performances of the data-driven machine learning algorithms, this thesis tackles the performance analysis and improvement of high dimensional data and graph clustering. Specifically, in the first bigger part of the thesis, using advanced tools from random matrix theory, the performance analysis of spectral methods on dense realistic graph models and on high dimensional kernel random matrices is performed through the study of the eigenvalues and eigenvectors of the similarity matrices characterizing those data. New improved methods are proposed and are shown to outperform state-of-the-art approaches. In a second part, a new algorithm is proposed for the detection of heterogeneous communities from multi-layer graphs using variational Bayes approaches to approximate the posterior distribution of the sought variables. The proposed methods are successfully applied to synthetic benchmarks as well as real-world datasets and are shown to outperform standard approaches to clustering in those specific contexts.; Motivée par les récentes avancées dans l'analyse théorique des performances des algorithmes d'apprentissage automatisé, cette thèse s'intéresse à l'analyse de performances et à l'amélioration de la classification nonsupervisée de données et graphes en grande dimension. Spécifiquement, dans la première grande partie de cette thèse, en s'appuyant sur des outils avancés de la théorie des grandes matrices aléatoires, nous analysons les performances de méthodes spectrales sur des modèles de graphes réalistes et denses ainsi que sur des données en grandes dimensions en étudiant notamment les valeurs propres et vecteurs propres des matrices d'affinités de ces données. De nouvelles méthodes améliorées sont proposées sur la base de cette analyse théorique et démontrent à travers de nombreuses simulations que leurs performances sont meilleures comparées aux méthodes de l'état de l'art. Dans la seconde partie de la thèse, nous proposons un nouvel algorithme pour la détection de communautés hétérogènes entre plusieurs couches d'un graphe à plusieurs types d'interaction. Une approche bayésienne variationnelle est utilisée pour approximer la distribution apostériori des variables latentes du modèle. Toutes les méthodes proposées dans cette thèse sont utilisées sur des bases de données synthétiques et sur des données réelles et présentent de meilleures performances en comparaison aux approches standard de classification dans les contextes susmentionnés.

In complex networks analysis field, much effort has been focused on identifying graphs communities of related nodes with dense internal connections and few external connections. In addition to node connectivity information that are mostly composed by different types of links, most real-world networks contains also node and/or edge associated attributes which can be very relevant during the learning process to find out the groups of nodes i.e. communities. In this case, two types of information are available : graph data to represent the relationship between objects and attributes information to characterize the objects i.e nodes. Classic community detection and data clustering techniques handle either one of the two types but not both. Consequently, the resultant clustering may not only miss important information but also lead to inaccurate findings. Therefore, various methods have been developed to uncover communities in networks by combining structural and attribute information such that nodes in a community are not only densely connected, but also share similar attribute values. Such graph-shape data is often referred to as attributed graph.This thesis focuses on developing algorithms and models for attributed graphs. Specifically, I focus in the first part on the different types of edges which represent different types of relations between vertices. I proposed a new clustering algorithms and I also present a redefinition of principal metrics that deals with this type of networks.Then, I tackle the problem of clustering using the node attribute information by describing a new original community detection algorithm that uncover communities in node attributed networks which use structural and attribute information simultaneously. At last, I proposed a collaborative filtering model in which I applied the proposed clustering algorithms.; Au cours de la dernière décennie, les réseaux (les graphes) se sont révélés être un outil efficace pour modéliser des systèmes complexes. La problématique de détection de communautés est une tâche centrale dans l’analyse des réseaux complexes. La majeur partie des travaux dans ce domaine s’intéresse à la structure topologique des réseaux. Cependant, dans plusieurs cas réels, les réseaux complexes ont un ensemble d’attributs associés aux nœuds et/ou aux liens. Ces réseaux sont dites : réseaux attribués. Mes activités de recherche sont basées principalement sur la détection des communautés dans les réseaux attribués. Pour aborder ce problème, on s’est intéressé dans un premier temps aux attributs relatifs aux liens, qui sont un cas particulier des réseaux multiplexes. Un multiplex est un modèle de graphe multi-relationnel. Il est souvent représenté par un graphe multi-couches. Chaque couche contient le même ensemble de nœuds mais encode une relation différente. Dans mes travaux de recherche, nous proposons une étude comparative des différentes approches de détection de communautés dans les réseaux multiplexes. Cette étude est faite sur des réseaux réels. Nous proposons une nouvelle approche centrée "graine" pour la détection de communautés dans les graphes multiplexes qui a nécessité la redéfinition des métriques de bases des réseaux complexes au cas multiplex. Puis, nous proposons une approche de clustering dans les réseaux attribués qui prend en considération à la fois les attributs sur les nœuds et sur les liens. La validation de mes approches a été faite avec des indices internes et externes, mais aussi par une validation guidée par un système de recommandation que nous avons proposé et dont la détection de communautés est sa tâche principale. Les résultats obtenus sur ces approches permettent d’améliorer la qualité des communautés détectées en prenant en compte les informations sur les attributs du réseaux. De plus, nous offrons des outils d’analyse des réseaux attribués sous le langage de programmation R.

In complex networks analysis field, much effort has been focused on identifying graphs communities of related nodes with dense internal connections and few external connections. In addition to node connectivity information that are mostly composed by different types of links, most real-world networks contains also node and/or edge associated attributes which can be very relevant during the learning process to find out the groups of nodes i.e. communities. In this case, two types of information are available : graph data to represent the relationship between objects and attributes information to characterize the objects i.e nodes. Classic community detection and data clustering techniques handle either one of the two types but not both. Consequently, the resultant clustering may not only miss important information but also lead to inaccurate findings. Therefore, various methods have been developed to uncover communities in networks by combining structural and attribute information such that nodes in a community are not only densely connected, but also share similar attribute values. Such graph-shape data is often referred to as attributed graph.This thesis focuses on developing algorithms and models for attributed graphs. Specifically, I focus in the first part on the different types of edges which represent different types of relations between vertices. I proposed a new clustering algorithms and I also present a redefinition of principal metrics that deals with this type of networks.Then, I tackle the problem of clustering using the node attribute information by describing a new original community detection algorithm that uncover communities in node attributed networks which use structural and attribute information simultaneously. At last, I proposed a collaborative filtering model in which I applied the proposed clustering algorithms., Au cours de la dernière décennie, les réseaux (les graphes) se sont révélés être un outil efficace pour modéliser des systèmes complexes. La problématique de détection de communautés est une tâche centrale dans l’analyse des réseaux complexes. La majeur partie des travaux dans ce domaine s’intéresse à la structure topologique des réseaux. Cependant, dans plusieurs cas réels, les réseaux complexes ont un ensemble d’attributs associés aux nœuds et/ou aux liens. Ces réseaux sont dites : réseaux attribués. Mes activités de recherche sont basées principalement sur la détection des communautés dans les réseaux attribués. Pour aborder ce problème, on s’est intéressé dans un premier temps aux attributs relatifs aux liens, qui sont un cas particulier des réseaux multiplexes. Un multiplex est un modèle de graphe multi-relationnel. Il est souvent représenté par un graphe multi-couches. Chaque couche contient le même ensemble de nœuds mais encode une relation différente. Dans mes travaux de recherche, nous proposons une étude comparative des différentes approches de détection de communautés dans les réseaux multiplexes. Cette étude est faite sur des réseaux réels. Nous proposons une nouvelle approche centrée "graine" pour la détection de communautés dans les graphes multiplexes qui a nécessité la redéfinition des métriques de bases des réseaux complexes au cas multiplex. Puis, nous proposons une approche de clustering dans les réseaux attribués qui prend en considération à la fois les attributs sur les nœuds et sur les liens. La validation de mes approches a été faite avec des indices internes et externes, mais aussi par une validation guidée par un système de recommandation que nous avons proposé et dont la détection de communautés est sa tâche principale. Les résultats obtenus sur ces approches permettent d’améliorer la qualité des communautés détectées en prenant en compte les informations sur les attributs du réseaux. De plus, nous offrons des outils d’analyse des réseaux attribués sous le langage de programmation R.

In the real world, numerous networks appear naturally, they are everywhere, in many disciplines, for example in computer science with router networks, satellite networks, webpage networks, in biology with neural networks, in ecology with biological interaction networks, in linguistic with synonym networks, in law with legal decision networks, in economy with interbank networks, in social sciences and humanities with social networks. Generally, a network reflects the interactions between many entities of a system. These interactions have different sources, a social link or a friendship link in a social network, a cable in a router network, a chemical reaction in a protein-protein interaction network, a hyperlink in a webpage network. Furthermore, the rapid democratization of digital technology in our societies, with internet in particular, leads to create new systems which can be seen as networks. Finally, all these networks depict very specific features : they come from pratical contexts, most of the time they are big (they may be comprised of several billion of nodes and links, containing a large amount of information), they share statistical properties. In this regard, they are called real-world networks or complex networks. Nowaday, network science is a research area in its own right focusing on describing and modeling these networks in order to reveal their main features and improve our understanding of their mecanisms. Most of the works in this area use graphs formalism which provides a set of mathematical tools well suited for analyzing the topology of these networks. It exists many applications, for instance applications in spread of epidemy or computer viruses, weakness of networks in case of a breakdown, attack resilience, study for link prediction, recommandation, etc. One of the major issue is the identification of community structure. The large majority of real-world networks depicts several levels of organization in their structure. Because of there is a weak global density coupled with a strong local density, we observe that nodes are usually organized into groups, called communities, which are more internally connected than they are to the rest of the network. Moreover, these structures have a meaning in the network itself, for example communities of a social network may correspond to social groups (friends, families, etc.), communities of a protein-protein network may translate fonctions of a cell, communities may be also related to similar subjects in a webpage network [...], Il existe dans le monde réel un nombre important de réseaux qui apparaissent naturellement, on les retrouve un peu partout, dans de nombreuses disciplines, par exemple en informatique avec les réseaux de routeurs, les réseaux de satellites, les réseaux de pages Web, en biologie avec les réseaux des neurones, en écologie avec les réseaux d’interactions biologiques, en linguistiques avec les réseaux de synonymes, en droit avec les réseaux de décisions juridiques, en économie avec les réseaux interbancaires, en sciences humaines avec les réseaux sociaux. De manière générale, un réseau reflète les interactions entre les nombreuses entités d’un système. Ces interactions peuvent être de différentes natures, un lien social ou un lien d’amitié dans un réseau social constitué de personnes, un câble dans un réseau de routeurs, une réaction chimique dans un réseau biologique de protéines, un hyperlien dans un réseau de pages Web, etc. Plus encore, la rapide démocratisation du numérique dans nos sociétés, avec Internet notamment, a pour conséquence de produire de nouveaux systèmes qui peuvent être représentés sous forme de réseaux. Finalement, tous ces réseaux présentent des particularités bien spécifiques : ils sont issus de contextes pratiques, ils sont le plus souvent de grande taille (on retrouve quelques fois des réseaux constitués de plusieurs milliards de nœuds et de liens, contenant donc une grande quantité d’information), ils présentent des propriétés statistiques communes. À cet égard, ils sont regroupés sous l’appellation de réseaux réels, graphes de terrain ou encore réseaux complexes. Aujourd'hui, la science des réseaux est un domaine de recherche à part entière dont l’enjeu principal est de parvenir à décrire et modéliser ces réseaux avec précision afin de révéler leurs caractéristiques générales et de mieux comprendre leurs mécanismes. La plupart des travaux dans ce domaine utilisent le formalisme des graphes qui fournit un ensemble d’outils mathématiques particulièrement adaptés à l’analyse topologique et structurelle des réseaux. Il existe de nombreuses applications dans ce domaine, par exemple des applications concernant la propagation d’épidémie ou de virus informatique, la fragilité du réseau en cas de panne, sa résilience en cas d’attaque, l’étude de la dynamique pour prédire l’apparition de nouveaux liens, la recommandation, etc. L’un des problèmes complexes actuels, qui a beaucoup d’applications, est l’identification de la structure communautaire. La grande majorité des réseaux réels sont caractérisés par des niveaux d’organisation dans leur structure mésoscopique. Du fait de la faible densité globale des réseaux réels couplée à la forte densité locale, on observe la présence de groupes de nœuds fortement liés entre eux et plus faiblement liés avec le reste du réseau, que l’on appelle communautés. Ces structures ont également du sens dans le réseau lui-même, par exemple les communautés d’un réseau social peuvent correspondre à des groupes sociaux (amis, familles, etc.), les communautés d’un réseau de protéines peuvent traduire des réponses fonctionnelles, elles peuvent correspondre à des sujets similaires dans un réseau de pages Web, pour donner quelques exemples [...]

Our research is in the field of complex network analysis and mining, specifically addressing the communit detection task, ie. algorithms aiming to uncover particularly dense subgraphs. We focus on the implementation of such an algorithm in a decentralised and distributed context : opportunistic MANET constituted of small wireless devices using peer-to-peer communication. To tackle the implementation constraints in such networks, we propose several methods designed according to the novel and trending vertex-centred paradigm, by combining Think-Like-a-Vertex graph processing with vertex-centred community detection methods based on leaders or seeds : they show specific properties allowing dsitributed implementations suiting the opportunistic MANET case. In this context, we first a global working principle and implement it in three different algorithms dedicated to three different configurations of community detection : the VOLCAN algorithm manages the classical disjoint community detection task in a static graph. We extend it with the LOCNeSs algorithm, that is dealing with overlapping communities which means that one vertex can belong to several communities. It adds more flexibility to the method and more significance to produced results. We also tackle the dynamic graphe case (graph evolving over time), addressed by the DynLOCNeSs algorithm.Each algorithm comes with a decentralised implementation and theoretical as well as experimental studies conducted both on real and synthetic benchmark data, allowing to evaluate the quality of the results and compare to existing state-of-the-art methods. Finally, we consider a special case of opportunistic decentralised MANET developped as a part of a research project about smart and communicating clothing. We formalise a task of path finding between smart t-shirts holders and propose a recommandation strategy using community structure, that we model and evaluate through an algorithm named SWAGG.; Les travaux présentés dans la thèse s'inscrivent dans le cadre de l'analyse des graphes de terrain (complex networks) et plus précisément de la tâche de détection de communautés, c'est-à-dire la reconnaissance algorithmique de sous-graphes particulièrement denses. Nous nous intéressons spécifiquement à l'implémentation d'une telle méthode dans un contexte fortement décentralisé et distribué : des réseaux MANET opportunistes formés par de petits objets connectés communiquant en pair-à-pair. Afin de tenir compte des contraintes d'exécution d'algorithme dans de tels réseaux, les travaux présentés dans la thèse proposent des méthodes conçues selon le paradigme récent et actif nommé orienté sommet, en alliant le traitement de graphes Think-Like-a-Vertex aux méthodes de détection de communautés basées sur des leaders ou des graines : celles-ci présentent en effet des propriétés de décentralisation qui autorisent des implémentations parallèles et distribuées appropriées au cadre applicatif considéré. Dans ce contexte, nous proposons d'une part un principe global de fonctionnement original que nous mettons en oeuvre et déclinons dans trois algorithmes dédiés à trois configurations différentes de la tâche de détection de communautés : l'algorithme VOLCAN considère le cas de référence des communautés disjointes dans un graphe statique. Nous l'étendons ensuite avec l'algorithme LOCNeSs au cas des communautés recouvrantes, qui autorisent un sommet à appartenir à plusieurs communautés simultanément : cette généralisation donne plus de flexibilité à la détection et la rend plus appropriée au cadre applicatif considéré. Nous examinons également le cas des graphes dynamiques, c'est-à-dire dont les sommets et les arêtes évoluent au cours du temps, auquel est consacré l'algorithme DynLOCNeSs. Chacun des algorithmes est associé à une implémentation décentralisée et fait l'objet d'une étude théorique ainsi qu'expérimentale sur des données artificielles et réelles permettant d'évaluer la qualité des résultats fournis et de les comparer aux méthodes de l'état de l'art. Nous considérons également, dans un cas particulier de réseau mobile ad-hoc spontané et décentralisé issu d'une application réelle de vêtements intelligents et communicants, une tâche de cheminement permettant d'identifier des interlocuteurs. Nous proposons une stratégie de recommandation utilisant la structure communautaire, modélisée et évaluée à travers un algorithme nommé SWAGG.

International audience; Les méthodes de détection de communautés sont des outils potentiellement puissants pour analyser des réseaux spatiaux puisqu'elles permettent d'identifier des lieux qui interagissent de manière préférentielle. Néanmoins, ces méthodes souffrent d'un biais important : elles ne tiennent pas compte des distances qui séparent les lieux. Une fois cartographiées, les communautés détectées apparaissent généralement très contraintes spatialement et contribuent à mettre simplement en évidence l'importance de la distance dans l'intensité des relations étudiées. Cette contrainte étant déjà bien connue, les résultats obtenus peuvent alors apparaitre triviaux. Pour faire face à ce biais et faire apparaitre des phénomènes plus intéressants, il est proposé d'adapter les algorithmes de détection de communautés à des données spatialisées en y incorporant des modèles de type gravitaire à l'instar de travaux déjà existants. Ce nouvel algorithme se distingue néanmoins des précédents en ayant recours de manière explicite à des modèles gravitaires couramment utilisés en géographie, ce qui doit permettre de simplifier l'interprétation des résultats et d'éviter de possibles erreurs. L'algorithme sera présenté dans une première partie, puis appliqué dans une deuxième partie à un cas d'étude : l'analyse des flux domicile-travail en Ile-de-France. Ce papier confirme que l'ajout de modèles gravitaires permet de dépasser les résultats triviaux obtenus avec des méthodes de détection de communautés plus classiques. Les résultats restent cependant toujours difficiles à interpréter.

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.; 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.

The objective is to refresh the geography of Belgium using interactions between places by means of a community detection algorithm (Louvain Method) inspired by Complex theory and Data Sciences. Places that are tightly related are optimally clustered into communities, leading to a new and optimal partition of Belgium. Migrations and commuting movements (Census11) are here analysed. We obtain a mosaic of “interaction fields” that are here interpreted in terms of methodological choices, human and urban geography as well as Belgian political dilemmas. They give the opportunity to remind that researchers have to control the impact of their methodological choices and that each type of data leads to a different geographical partitioning, with one major unexpected common spatial feature in Belgium: the pre-eminence of the provincial borders. This perfectly fits with current political questioning. L’objectif est d’apporter un regard neuf sur la géographie de la Belgique à l’aide de données relationnelles et d’un algorithme de détection de communautés (Méthode de Louvain) inspiré de l’ingénierie mathématique et des sciences de données. Les lieux qui sont fortement liés en termes d’échanges sont ici classés de façon optimale en « communautés », conduisant à une partition innovante de la Belgique. Nous nous limitons ici aux mouvements de navettes et aux déménagements (migrations) issus du dernier recensement (Census11).Les différentes partitions de la Belgique sont discutées et interprétées d’un point de vue géographique et méthodologique. Ces résultats nous donnent l’occasion de rappeler qu’il importe de maîtriser les choix méthodologiques et que chaque type de données conduit à une partition différente qu’il convient d’interpréter en fonction de la théorie. De manière surprenante, une tendance spatiale inattendue apparaît à travers les résultats obtenus : la prééminence des frontières provinciales. Ce résultat interpelle au vu des questionnements politiques actuels en Belgique.

N this thesis, I first present a new way of characterising communities from a network of timestamped messages. I show that its structure is linked with communities : communication structures are over-represented inside communities while diffusion structures appear mainly on the boundaries.Then, I propose to evaluate communities with a new quality function, compacity, that measures the propagation speed of communications in communities. I also present the Lex-Clustering, a new community detection algorithm based on the LexDFS graph traversal that features some characteristics of information diffusion.Finally, I present a methodology that I used to link quality functions and ground-truths. I introduce the concept of contexts, sets of ground-truths that are similar in some way. I implemented this methodology in a software called CoDACom (Community Detection Algorithm Comparator, codacom.greyc.fr) that also provides many community detection tools., Dans cette thèse, je commence par présenter une nouvelle caractérisation des communautés à partir d'un réseau de messages inscrits dans le temps. Je montre que la structure de ce réseau a un lien avec les communautés : on trouve majoritairement des échanges d'information à l'intérieur des communautés tandis que les frontières servent à la diffusion.Je propose ensuite d'évaluer les communautés par la vitesse de propagation des communications qui s'y déroulent avec une nouvelle fonction de qualité : la compacité. J'y présente aussi un algorithme de détection de communautés, le Lex-Clustering, basé sur un algorithme de parcours de graphe qui reproduit des caractéristiques des modèles de diffusion d'information. Enfin, je présente une méthodologie permettant de faire le lien entre les fonctions de qualité et les vérités de terrain. J'introduis le concept de contexte, des ensembles de vérités de terrain qui présentente des ressemblances. Je mets à disposition un logiciel nommé CoDACom (Community Detection Algorithm Comparator, codacom.greyc.fr) permettant d'appliquer cette méthodologie ainsi que d'utiliser un grand nombre d'outils de détection de communautés.

Privacy is a serious concern of users in daily usage of social networks. Social networks are a valuable data source for large-scale studies on social organization and evolution and are usually published in anonymized forms. This thesis addresses three privacy problems of social networks: graph anonymization, private community detection and private link exchange. First, we tackle the problem of graph anonymization via uncertainty semantics and differential privacy. As for uncertainty semantics, we propose a general obfuscation model called Uncertain Adjacency Matrix (UAM) that keep expected node degrees equal to those in the unanonymized graph. We analyze two recently proposed schemes and show their fitting into the model. We also present our scheme Maximum Variance (MaxVar) to fill the gap between them. Using differential privacy, the problem is very challenging because of the huge output space of noisy graphs. A large body of existing schemes on differentially private release of graphs are not consistent with increasing privacy budgets as well as do not clarify the upper bounds of privacy budgets. In this thesis, such a bound is provided. We introduce the new linear scheme Top-m-Filter (TmF) and improve the existing technique EdgeFlip. Thorough comparative evaluation on a wide range of graphs provides a panorama of the state-of-the-art's performance as well as validates our proposed schemes. Second, we present the problem of community detection under differential privacy. We analyze the major challenges behind the problem and propose several schemes to tackle them from two perspectives: input perturbation (LouvainDP) and algorithm perturbation (ModDivisive); La vie privée est une préoccupation des utilisateurs des réseaux sociaux. Les réseaux sociaux sont une source de données précieuses pour des analyses scientifiques ou commerciales. Cette thèse aborde trois problèmes de confidentialité des réseaux sociaux: l'anonymisation de graphes sociaux, la détection de communautés privées et l'échange de liens privés. Nous abordons le problème d'anonymisation de graphes via la sémantique de l'incertitude et l'intimité différentielle. Pour la première, nous proposons un modèle général appelé Uncertain Adjacency Matrix (UAM) qui préserve dans le graphe anonymisé les degrés des nœuds du graphe non-anonymisé. Nous analysons deux schémas proposés récemment et montrons leur adaptation dans notre modèle. Nous aussi présentons notre approche dite MaxVar. Pour la technique d'intimité différentielle, le problème devient difficile en raison de l'énorme espace des graphes anonymisés possibles. Un grand nombre de systèmes existants ne permettent pas de relâcher le budget contrôlant la vie privée, ni de déterminer sa borne supérieure. Dans notre approche nous pouvons calculer cette borne. Nous introduisons le nouveau schéma Top-m-Filter de complexité linéaire et améliorons la technique récente EdgeFlip. L'évaluation de ces algorithmes sur une large gamme de graphes donne un panorama de l'état de l'art. Nous présentons le problème original de la détection de la communauté dans le cadre de l'intimité différentielle. Nous analysons les défis majeurs du problème et nous proposons quelques approches pour les aborder sous deux angles: par perturbation d'entrée (schéma LouvainDP) et par perturbation d'algorithme (schéma ModDivisive)

National audience; Les sommets multi-appartenants constituent une caractéristique importante à prendre en compte lors de la conception d'une méthode de détection de communautés. Nous proposons dans cet article LOCNeSs, un algorithme de détection utilisant une approche orientée som-met. LOCNeSs permet une implémentation complètement décentralisée et limite la propagation, deux caractéristiques utiles pour une utilisation dans un environnement décentralisée ou très distribué. L'algorithme modélise des préférences entre sommets, basées sur l'attachement pré-férentiel, afin d'aggréger ces sommets pour former des communautés. Une étude expérimentale permet de montrer que LOCNeSs identifie les sommets multi-appartenants de façon exhaustive et pertinente. ABSTRACT. Overlapping vertices are an important characteristic to consider when designing a community detection method. In this article, we propose LOCNeSs, a detection algorithm using a vertex-oriented approach. It allows a decentralised implementation limiting information propagation in the graph, which is suitable to be used in a heavily decentralised or distributed environment. The algorithm models preference between vertices using a measure based on preferential attachment, and then aggregates these vertices to from communities. An experimental study shows that LOCNeSs accurately identifies relevant overlapping vertices.

Interactions are everywhere: in the contexts of face-to-face contacts, emails, phone calls, IP traffic, etc. In all of them, an interaction is characterized by two entities and a time interval: for instance, two individuals meet from 1pm to 3pm. We model them as link stream which is a set of quadruplets (b,e,u,v) where each quadruplet means that a link exists between u and v from time b to time e. In graphs, a community is a subset which is more densely connected than a reference. Within the link stream formalism, the notion of density and reference have to be redefined. Therefore, we study how to extend the notion of density for link streams. To this end, we use a real data set where a community structure is known. Then, we develop a method that finds automatically substream which are considered relevant. These substream, defined as subsets of links, are discovered by a classical community detection algorithm applied on the link stream the transformed into a static graph. A substream is considered relevant, if it is denser than the substreams which are close temporally and structurally. Thus, we deepen the notion of neighbourhood and reference in link streams. We apply our method on several real world interaction networks and we find relevant substream which would not have been found by existing methods. Finally, we discuss the generation of link streams having a given community structure and also a proper way to evaluate such community structure., Les interactions sont partout : il peut s'agir de contacts entre individus, d'emails, d'appels téléphoniques, etc. Toutes ces interactions sont définies par deux entités interagissant sur un intervalle de temps: par exemple, deux individus se rencontrant entre 12h et 14h. Nous modélisons ces interactions par des flots de liens qui sont des ensembles de quadruplets (b, e, u, v), où chaque quadruplet représente un lien entre les noeuds u et v existant durant l'intervalle [b,e]. Dans un graphe, une communauté est un sous-ensemble plus densément connecté qu’une référence. Dans le formalisme de flot de liens, les notions même de densité et de référence sont à définir. Nous étudions donc comment étendre la notion de communauté aux flots de liens. Pour ce faire, nous nous appuyons sur des données réel où une structure communautaire est connue. Puis, nous développons une méthode permettant de trouver automatiquement des sous-flots qui sont jugés pertinents. Ces sous-flots, c’est-à-dire des sous-ensembles de liens, sont trouvés grâce à une méthode de détection de communautés appliquée sur une projection du flot sur un graphe statique. Un sous-flot est jugé pertinent s’il est plus dense que les sous-flots qui lui sont proches temporellement et topologiquement. Ainsi nous approfondissons les notions de voisinage et référence dans les flots de liens. Nous appliquons cette méthode sur plusieurs jeux de données d’interactions réelles et obtenons des groupes pertinents qui n’auraient pas pu être détectés par les méthodes existantes. Enfin, nous abordons la génération de flots de liens avec une structure communautaire donnée et à la manière d'évaluer une telle partition.

Communities are groups of nodes (vertices) which probably share common properties and/or play similar roles within the graph. They can extract specific structures from complex networks, and consequently community detection has attracted considerable attention crossing many areas where systems are often represented as graphs. We consider in this work to represent graphs as relational data, and propose models for the corresponding relational data clustering. Four approaches are brought forward to handle the community detection problem under different scenarios. We start with a basic situation where nodes in the graph are clustered based on the dissimilarities and propose a new c-partition clustering approach named Median Evidential C-Means (MECM) algorithm. This approach extends the median clustering methods in the framework of belief function theory. Moreover, a community detection scheme based on MECM is presented. The proposed approach could provide credal partitions for data sets with only known dissimilarities. The dissimilarity measure could be neither symmetric nor fulfilling any metric requirements. It is only required to be of intuitive meaning. Thus it expands application scope of credal partitions. In order to capture various aspects of the community structures, we may need more members rather than one to be referred as the prototypes of an individual group. Motivated by this idea, a Similarity-based Multiple Prototype (SMP) community detection approach is proposed. The centrality values are used as the criterion to select multiple prototypes to characterize each community. The prototype weights are derived to describe the degree of representativeness of objects for their own communities. Then the similarity between each node and community is defined, and the nodes are partitioned into divided communities according to these similarities. Crisp and fuzzy partitions could be obtained by the application of SMP. Following, we extend SMP in the framework of belief functions to get credal partitions so that we can gain a better understanding of the data structure. The prototype weights are incorporate into the objective function of evidential clustering. The mass membership and the prototype weights could be updated alternatively during the optimization process. In this case, each cluster could be described using multiple weighted prototypes. As we will show, the prototype weights could also provide us some useful information for structure analysis of the data sets. Lastly, the original update rule and propagation criterion of LPA are extended in the framework of belief functions. A new community detection approach, called Semi-supervised Evidential Label Propagation (SELP), is proposed as an enhanced version of the conventional LPA. One of the advantages of SELP is that it could take use of the available prior knowledge about the community labels of some individuals. This is very common in real practice. In SELP, the nodes are divided into two parts. One contains the labeled nodes, and the other includes the unlabeled ones. The community labels are propagated from the labeled nodes to the unlabeled ones step by step according to the proposed evidential label propagation rule. The performance of the proposed approaches is evaluated using benchmark graph data sets and generated graphs. Our experimental results illustrate the effectiveness of the proposed clustering algorithms and community detection approaches.; Les communautés sont des groupes de nœuds (sommets) qui partagent probablement des propriétés communes et/ou jouent des rôles similaires dans le graphe. Ils peuvent extraire des structures spécifiques des réseaux complexes, et par conséquent la détection de ces communautés a été étudiée dans de nombreux domaines où les systèmes sont souvent représentés sous forme de graphes. La détection de communautés est en fait un problème de classification (ou clustering) sur les graphes, et l'information disponible dans ce problème est souvent sous la forme de similitudes ou de différences (entre les nœuds). Nous commençons par une situation de base où les nœuds dans le graphe sont regroupés selon leurs similarités et proposons une nouvelle approche de clustering enc-partition nommée algorithme Median Evidential C-Means (MECM). Cette approche étend la méthode de classification par médiane dans le cadre de la théorie des fonctions de croyance. En outre, une détection de communautés fondée sur l'approche MECM est également présentée. L'approche proposée permet de fournir des partitions crédales selon des similarités avec seulement des données connues. La mesure de dissimilarité pourrait être ni symétrique et même ne comporter aucune exigences de métriques.Elle est simplement intuitive. Ainsi, elle élargit la portée d'applications des partitions crédales. Afin de saisir les divers aspects des structures de communautés, nous pouvons avoir besoin de plusieurs nœuds plutôt qu'un seul pour représenter un prototype représentant un groupe d'individus. Motivée par cette idée, une approche de détection de communautés fondée sur le Similarity-based Multiple Prototype (SMP) est proposée.Les valeurs de centralité sont utilisées comme critère pour sélectionner plusieurs nœuds(prototypes) pour caractériser chaque communauté, et les poids des prototypes sont considérés pour décrire le degré de représentativité des objets liés à leur propre communauté. Ensuite, la similarité entre chaque nœud et les communautés est définie. Les nœuds sont divisés pour former des communautés selon leurs similarités. Les partitions nettes et floues peuvent être obtenues par l'approche SMP. Ensuite, nous étendons l'approche SMP au cadre des fonctions de croyance pour obtenir des partitions crédales de sorte que l'on puisse obtenir une meilleure compréhension de la structure des données. Les poids du prototype sont incorporés dans la fonction d’objectif de la communauté. La composition de masse et les poids des prototypes ont pu être mis à jour alternativement pendant le processus d'optimisation. Dans ce cas,chaque groupe peut être décrit en utilisant de multiples prototypes pondérés. Comme nous allons le montrer, les poids des prototypes peuvent également nous fournir des informations utiles pour l'analyse des données. la règle de mise à jour et le critère de propagation du LPA sont étendus aux fonctions de croyance. Une nouvelle approche de détection de communautés, appelée Semisupervised Evidential Label Propagation (SELP) est proposée comme une version améliorée de la méthode LPA conventionnelle. L'un des avantages de l'approche SELP est quelle permet de tenir compte de la connaissance préalable disponible sur les étiquettes des communautés de certains individus. Ceci est tr` es courant dans la pratique réelle. Dans la méthode SELP, les nœuds sont divisés en deux partis. Certains contiennent des nœuds labellisés et les autres des nœuds non labellisés. Les labels sont propagés depuis les nœuds labellisés à ceux non labellisés, étape par étape en utilisant la règle crédibiliste de propagation de labels proposée. Les performances des approches proposées sont évaluées en utilisant les graphes de référence des ensembles de données et des graphes générés. Nos résultats expérimentaux illustrent l'efficacité des algorithmes de classification proposés et des méthodes de détection de communautés.

In an era of unprecedented deluge of (mostly unstructured) data, graphs are proving more and more useful, across the sciences, as a flexible abstraction to capture complex relationships between complex objects. One of the main challenges arising in the study of such networks is the inference of macroscopic, large-scale properties affecting a large number of objects, based solely on he microscopic interactions between their elementary constituents. Statistical physics, precisely created to recover the macroscopic laws of thermodynamics from an idealized model of interacting particles, provides significant insight to tackle such complex networks.In this dissertation, we use methods derived from the statistical physics of disordered systems to design and study new algorithms for inference on graphs. Our focus is on spectral methods, based on certain eigenvectors of carefully chosen matrices, and sparse graphs, containing only a small amount of information. We develop an original theory of spectral inference based on a relaxation of various meanfield free energy optimizations. Our approach is therefore fully probabilistic, and contrasts with more traditional motivations based on the optimization of a cost function. We illustrate the efficiency of our approach on various problems, including community detection, randomized similarity-based clustering, and matrix completion., Face au déluge actuel de données principalement non structurées, les graphes ont démontré, dans une variété de domaines scientifiques, leur importance croissante comme language abstrait pour décrire des interactions complexes entre des objets complexes. L’un des principaux défis posés par l’étude de ces réseaux est l’inférence de propriétés macroscopiques à grande échelle, affectant un grand nombre d’objets ou d’agents, sur la seule base des interactions microscopiquesqu’entretiennent leurs constituants élémentaires. La physique statistique, créée précisément dans le but d’obtenir les lois macroscopiques de la thermodynamique à partir d’un modèle idéal de particules en interaction, fournit une intuition décisive dans l’étude des réseaux complexes.Dans cette thèse, nous utilisons des méthodes issues de la physique statistique des systèmes désordonnés pour mettre au point et analyser de nouveaux algorithmes d’inférence sur les graphes. Nous nous concentrons sur les méthodes spectrales, utilisant certains vecteurs propres de matrices bien choisies, et sur les graphes parcimonieux, qui contiennent une faible quantité d’information. Nous développons une théorie originale de l’inférence spectrale, fondée sur une relaxation de l’optimisation de certaines énergies libres en champ moyen. Notre approche est donc entièrement probabiliste, et diffère considérablement des motivations plus classiques fondées sur l’optimisation d’une fonction de coût. Nous illustrons l’efficacité de notre approchesur différents problèmes, dont la détection de communautés, la classification non supervisée à partir de similarités mesurées aléatoirement, et la complétion de matrices.

Relational data in our society are on a constant increasing, rising arduous challenges. In this thesis, we consider two aspects of relational data. First, we are interested in relational data with weighted relationship. As a concrete example, relationships among Twitter's users could be weighted with regard to their shared number of followers. The second aspect is related to the dynamism which is inherent to data nature. As an instance, in the previous example the number of common followers between two Twitter's users can change over time. In order to handle these complex and dynamic relational data, we use the modelling strength of graphs. Another facet considered in this thesis deals with community identification on weighted and dynamic graphs. For an analyst, the community detection might be helpful to grasp the semantic behind the graph structure. Our assumption relies on the idea to use a set of disjoint pairwise triangles as a basis to detect the community structure. To select these triangles, several algorithms are proposed (i.e., branch-and-bound, greedy search, heuristics and genetic algorithm). Thereafter, we propose a community detection algorithm, called Tribase. In the latter, the weights of communities are compared allowing dominant communities to gain in size. Tribase is compared with the well-known LFR benchmark. The results show that Tribase identifies efficiently the communities while a community structure exists. Additionally, to asset Tribase on real-world data, we consider social networks data, especially Twitter's data, of the ANR-Info-RSN project. In order to support the analyst in its knowledge acquisition, we elaborate a visual interactive approach. To this end, an interactive application, called NLCOMS is introduced. NLCOMS uses multiple synchronous views for visualizing community structure and the related information. Furthermore, we propose an algorithm for the identification of communities over time, called Dyci. The latter takes advantage from the previously detected communities. Several changes' scenarios are considered like, node/edge addition, node/edge removing and edge weight update. The main idea of the proposed algorithm is to track whether a part of the weighted graph becomes weak over time, in order to merge it with the "dominant" neighbour community. In order to assess the quality of the returned community structure, we conduct a comparison with a genetic algorithm on real-world data of the ARN-Info-RSN project. The conducted comparison shows that Dyci algorithm provides a good trade-off between efficiency and consumed time. Finally, the dynamic changes which occur to the underlying graph structure can be visualized with NLCOMS which combines physical an axial time to fulfil this need, De nos jours, nous générons une quantité immensément grande de données juste en accomplissant nos simples tâches quotidiennes. L'analyse de ces données soulève des challenges ardus. Dans cette thèse, nous nous intéressons à deux aspects des données relationnelles. En premier lieu, nous considérons les données relationnelles dans lesquelles les relations sont pondérées. Un exemple concret serait le nombre commun de suiveurs entre deux utilisateurs de Twitter. Dans un deuxième temps, nous abordons le cas dynamique de ces données qui est inhérent à leur nature. Par exemple, le nombre de suiveurs communs pourrait changer au fil du temps. Dans cette thèse nous utilisons les graphes pour modéliser ces données qui sont à la fois complexes et évolutives. Les travaux de cette thèse s'articulent aussi autour de la détection de communautés pour les graphes pondérés et dynamiques. Pour un utilisateur expert, l'identification de ces communautés pourrait l'aider à comprendre la sémantique sous-jacente à la structure du graphe. Notre hypothèse repose sur l'utilisation des triangles comme ossature pour la détection de communautés. Cela nous a amenés à proposer plusieurs algorithmes : Séparation et évaluation, recherche gloutonne, heuristiques et algorithme génétique sont proposés. En se basant sur cet ensemble de triangles, nous proposons un algorithme de détection de communautés, appelé Tribase. L'idée conductrice de cet algorithme est de comparer les poids des communautés, permettant aux communautés dominantes d'acquérir plus de membres. Les résultats de l'étude comparative sur le benchmark LFR montrent que l'algorithme que nous proposons parvient à détecter les communautés dans les graphes dans lesquels une structure de communautés existe. De plus, l'applicabilité de notre algorithme a été testée sur des données réelles du projet ANR Info-RSN. Dans l'optique d'accompagner l'utilisateur expert dans son processus d'acquisition de l'information, une application visuelle et interactive a été implémentée. NLCOMS (Nœud-Lien et COMmunautéS) propose une panoplie de vues synchronisées pour la représentation de l'information. Par ailleurs, nous proposons dans cette thèse un algorithme de détection de communautés pour les graphes pondérés et dynamiques, appelé Dyci. Dyci permet de gérer les différents scénarios de mise à jour possibles de la structure du graphe. L'idée principale de Dyci est de guetter au cours du temps l'affaiblissement d'une communauté (en termes de poids) dans le but de reconsidérer localement sa place dans la structure, évitant ainsi une réindentification globale des communautés. Une étude comparative a été menée montrant que l'algorithme que nous proposons offre un bon compromis entre la solution obtenue et le temps de calcul. Finalement, l'intégration dans NLCOMS des visualisations adéquates pour la variante dynamique a été effectuée

Communities are groups of nodes (vertices) which probably share common properties and/or play similar roles within the graph. They can extract specific structures from complex networks, and consequently community detection has attracted considerable attention crossing many areas where systems are often represented as graphs. We consider in this work to represent graphs as relational data, and propose models for the corresponding relational data clustering. Four approaches are brought forward to handle the community detection problem under different scenarios. We start with a basic situation where nodes in the graph are clustered based on the dissimilarities and propose a new c-partition clustering approach named Median Evidential C-Means (MECM) algorithm. This approach extends the median clustering methods in the framework of belief function theory. Moreover, a community detection scheme based on MECM is presented. The proposed approach could provide credal partitions for data sets with only known dissimilarities. The dissimilarity measure could be neither symmetric nor fulfilling any metric requirements. It is only required to be of intuitive meaning. Thus it expands application scope of credal partitions. In order to capture various aspects of the community structures, we may need more members rather than one to be referred as the prototypes of an individual group. Motivated by this idea, a Similarity-based Multiple Prototype (SMP) community detection approach is proposed. The centrality values are used as the criterion to select multiple prototypes to characterize each community. The prototype weights are derived to describe the degree of representativeness of objects for their own communities. Then the similarity between each node and community is defined, and the nodes are partitioned into divided communities according to these similarities. Crisp and fuzzy partitions could be obtained by the application of SMP. Following, we extend SMP in the framework of belief functions to get credal partitions so that we can gain a better understanding of the data structure. The prototype weights are incorporate into the objective function of evidential clustering. The mass membership and the prototype weights could be updated alternatively during the optimization process. In this case, each cluster could be described using multiple weighted prototypes. As we will show, the prototype weights could also provide us some useful information for structure analysis of the data sets. Lastly, the original update rule and propagation criterion of LPA are extended in the framework of belief functions. A new community detection approach, called Semi-supervised Evidential Label Propagation (SELP), is proposed as an enhanced version of the conventional LPA. One of the advantages of SELP is that it could take use of the available prior knowledge about the community labels of some individuals. This is very common in real practice. In SELP, the nodes are divided into two parts. One contains the labeled nodes, and the other includes the unlabeled ones. The community labels are propagated from the labeled nodes to the unlabeled ones step by step according to the proposed evidential label propagation rule. The performance of the proposed approaches is evaluated using benchmark graph data sets and generated graphs. Our experimental results illustrate the effectiveness of the proposed clustering algorithms and community detection approaches., Les communautés sont des groupes de nœuds (sommets) qui partagent probablement des propriétés communes et/ou jouent des rôles similaires dans le graphe. Ils peuvent extraire des structures spécifiques des réseaux complexes, et par conséquent la détection de ces communautés a été étudiée dans de nombreux domaines où les systèmes sont souvent représentés sous forme de graphes. La détection de communautés est en fait un problème de classification (ou clustering) sur les graphes, et l'information disponible dans ce problème est souvent sous la forme de similitudes ou de différences (entre les nœuds). Nous commençons par une situation de base où les nœuds dans le graphe sont regroupés selon leurs similarités et proposons une nouvelle approche de clustering enc-partition nommée algorithme Median Evidential C-Means (MECM). Cette approche étend la méthode de classification par médiane dans le cadre de la théorie des fonctions de croyance. En outre, une détection de communautés fondée sur l'approche MECM est également présentée. L'approche proposée permet de fournir des partitions crédales selon des similarités avec seulement des données connues. La mesure de dissimilarité pourrait être ni symétrique et même ne comporter aucune exigences de métriques.Elle est simplement intuitive. Ainsi, elle élargit la portée d'applications des partitions crédales. Afin de saisir les divers aspects des structures de communautés, nous pouvons avoir besoin de plusieurs nœuds plutôt qu'un seul pour représenter un prototype représentant un groupe d'individus. Motivée par cette idée, une approche de détection de communautés fondée sur le Similarity-based Multiple Prototype (SMP) est proposée.Les valeurs de centralité sont utilisées comme critère pour sélectionner plusieurs nœuds(prototypes) pour caractériser chaque communauté, et les poids des prototypes sont considérés pour décrire le degré de représentativité des objets liés à leur propre communauté. Ensuite, la similarité entre chaque nœud et les communautés est définie. Les nœuds sont divisés pour former des communautés selon leurs similarités. Les partitions nettes et floues peuvent être obtenues par l'approche SMP. Ensuite, nous étendons l'approche SMP au cadre des fonctions de croyance pour obtenir des partitions crédales de sorte que l'on puisse obtenir une meilleure compréhension de la structure des données. Les poids du prototype sont incorporés dans la fonction d’objectif de la communauté. La composition de masse et les poids des prototypes ont pu être mis à jour alternativement pendant le processus d'optimisation. Dans ce cas,chaque groupe peut être décrit en utilisant de multiples prototypes pondérés. Comme nous allons le montrer, les poids des prototypes peuvent également nous fournir des informations utiles pour l'analyse des données. la règle de mise à jour et le critère de propagation du LPA sont étendus aux fonctions de croyance. Une nouvelle approche de détection de communautés, appelée Semisupervised Evidential Label Propagation (SELP) est proposée comme une version améliorée de la méthode LPA conventionnelle. L'un des avantages de l'approche SELP est quelle permet de tenir compte de la connaissance préalable disponible sur les étiquettes des communautés de certains individus. Ceci est tr` es courant dans la pratique réelle. Dans la méthode SELP, les nœuds sont divisés en deux partis. Certains contiennent des nœuds labellisés et les autres des nœuds non labellisés. Les labels sont propagés depuis les nœuds labellisés à ceux non labellisés, étape par étape en utilisant la règle crédibiliste de propagation de labels proposée. Les performances des approches proposées sont évaluées en utilisant les graphes de référence des ensembles de données et des graphes générés. Nos résultats expérimentaux illustrent l'efficacité des algorithmes de classification proposés et des méthodes de détection de communautés.

International audience; RÉSUMÉ. L'objectif de la détection de communautés est de créer une partition des sommets, de telle sorte que les communautés soient composées de sommets fortement connectés. Les ap-proches existantes de détection de communautés se concentrent principalement sur la structure topologique du réseau, mais elles ignorent largement les informations disponibles à propos des attributs des noeuds. Dans cet article, une nouvelle appproche de détection de communautés qui utilise à la fois les informations structurelles et d'attributs pour extraire une structure de graphe imprécise, est proposée dans le cadre de la théorie des fonctions de croyance. L'objectif de notre méthode consiste à partitionner les sommets dans différents groupes afin que chaque cluster contienne un sous-graphe connecté densément avec les valeurs de l'attribut homogène. Les résultats expérimentaux montrent l'efficacité de la méthode proposée et montrent qu'elle pourrait améliorer les performances de la détection de communautés où les informations sur les propriétés du graphe sont disponibles en complément avec la structure topologique. ABSTRACT. The goal of community detection is to partition nodes into different small subgroups in such a way that vertices in the same community have strong connections. Existing community detection approaches mainly focus on the topological structure of the network, but ignore the information about node attributes. In this paper, a new Evidential Community detection approach which could utilize both Structural and Attribute information, named ECSA, is proposed using belief functions to extract imprecise graph structure. The goal of our method is to partition vertices into different groups so that each cluster contains a densely connected subgraph with homogeneous attribute values. Experimental results illustrate the effectiveness of the proposed method and show that it could indeed improve the performance of community detection when the information about vertex properties is available together with topological structure.

This thesis describes new tools specifically designed for the analysis of networks such as social, transportation, neuronal, protein, communication networks... These networks, along with the rapid expansion of electronic, IT and mobile technologies are increasingly monitored and measured. Adapted tools of analysis are therefore very much in demand, which need to be universal, powerful, and precise enough to be able to extract useful information from very different possibly large networks. To this end, a large community of researchers from various disciplines have concentrated their efforts on the analysis of graphs, well define mathematical tools modeling the interconnected structure of networks. Among all the considered directions of research, graph signal processing brings a new and promising vision : a signal is no longer defined on a regular n-dimensional topology, but on a particular topology defined by the graph. To apply these new ideas on the practical problems of network analysis paves the way to an analysis firmly rooted in signal processing theory. It is precisely this frontier between signal processing and network science that we explore throughout this thesis, as shown by two of its major contributions. Firstly, a multiscale version of community detection in networks is proposed, based on the recent definition of graph wavelets. Then, a network-adapted bootstrap method is introduced, that enables statistical estimation based on carefully designed graph resampling schemes.; Cette thèse propose de nouveaux outils adaptés à l'analyse des réseaux : sociaux, de transport, de neurones, de protéines, de télécommunications... Ces réseaux, avec l'essor de certaines technologies électroniques, informatiques et mobiles, sont de plus en plus mesurables et mesurés ; la demande d'outils d'analyse assez génériques pour s'appliquer à ces réseaux de natures différentes, assez puissants pour gérer leur grande taille et assez pertinents pour en extraire l'information utile, augmente en conséquence. Pour répondre à cette demande, une grande communauté de chercheurs de différents horizons scientifiques concentre ses efforts sur l'analyse des graphes, des outils mathématiques modélisant la structure relationnelle des objets d'un réseau. Parmi les directions de recherche envisagées, le traitement du signal sur graphe apporte un éclairage prometteur sur la question : le signal n'est plus défini comme en traitement du signal classique sur une topologie régulière à n dimensions, mais sur une topologie particulière définie par le graphe. Appliquer ces idées nouvelles aux problématiques concrètes d'analyse d'un réseau, c'est ouvrir la voie à une analyse solidement fondée sur la théorie du signal. C'est précisément autour de cette frontière entre traitement du signal et science des réseaux que s'articule cette thèse, comme l'illustrent ses deux principales contributions. D'abord, une version multiéchelle de détection de communautés dans un réseau est introduite, basée sur la définition récente des ondelettes sur graphe. Puis, inspirée du concept classique de bootstrap, une méthode de rééchantillonnage de graphes est proposée à des fins d'estimation statistique.

International audience; Étant donné un ensemble de nœuds d'un graphe, nous proposons une méthode par apprentissage d'une mesure de proximité afin de compléter, si possible, cet ensemble de nœuds en une communauté. Si cette complétion est possible, la décroissance des proximités a alors une forme plateau/décroissance permettant une détection précise et rapide de la communauté, dite {\em multi-ego-centrée}. Nos résultats sont validés sur un grand ensemble de pages Wikipédia et sur des benchmarks. L'apprentissage et la détection de plateau/décroissance sont les deux contributions majeures de l'article.

International audience; Les réseaux complexes, appelés aussi "graphes de terrain", apparaissent dans divers contextes tels que l'informatique (e.g. réseaux de pages Web), la sociologie (e.g. réseaux collaboratifs) ou la biologie (e.g. réseaux de régulation de gènes). Une propriété importante et commune à tous ces graphes est qu'ils sont généralement constitués de sous-graphes fortement interconnectés appelés "communautés". La détection de communautés (qui peut être vue comme un problème de partitionnement de graphes) est une problématique très largement étudiée ces dernières années et, dans ce sens, beaucoup d'algorithmes ont été proposés. Bon nombre d'entre eux cherchent à maximiser la fonction de qualité de Newman-Girvan, appelée aussi "modularité" (il s'agit d'un problème NP-difficile). C'est le cas notamment de l'algorithme de Louvain, qui est actuellement le meilleur algorithme en terme de complexité pour calculer des communautés sur de très grands graphes (il est capable de traiter en moins de 3h des graphes ayant plus d'un milliard de sommets et d'arêtes). La modularité présente toutefois plusieurs inconvénients. En la maximisant, on peut trouver des partitions de bonne qualité dans des graphes qui n'ont pas de communautés (des graphes réguliers, des graphes aléatoires, des arbres...). Elle privilégie également des communautés de grande taille. Nous avons ainsi adapté la méthode de Louvain à d'autres critères de qualité (comme le critère de Zahn-Condorcet par exemple). nous obtenons globalement les mêmes performances en terme de temps de calcul que l'algorithme de Louvain classique.De plus, nous avons exhibé une condition suffisante pour savoir si un critère pouvait être intégré à la méthode de Louvain.

Many complex systems are modeled through complex networks whose analysis reveals typical topological properties. Amongst those, the community structure is one of the most studied. Many methods are proposed to detect communities, not only in plain, but also in attributed, directed or even dynamic networks. A community structure takes the form of a partition of the node set, which must then be characterized relatively to the properties of the studied system. We propose a method to support such a characterization task. We define a sequence-based representation of networks, combining temporal information, topological measures, and nodal attributes. We then characterize communities using the most representative emerging sequential patterns of its nodes. This also allows detecting unusual behavior in a community. We describe an empirical study of a network of scientific collaborations.---De nombreux syst\`emes complexes sont \'etudi\'es via l'analyse de r\'eseaux dits complexes ayant des propri\'et\'es topologiques typiques. Parmi cellesci, les structures de communaut\'es sont particuli\`erement \'etudi\'ees. De nombreuses m\'ethodes permettent de les d\'etecter, y compris dans des r\'eseaux contenant des attributs nodaux, des liens orient\'es ou \'evoluant dans le temps. La d\'etection prend la forme d'une partition de l'ensemble des noeuds, qu'il faut ensuite caract\'eriser relativement au syst\`eme mod\'elis\'e. Nous travaillons sur l'assistance \`a cette t\^ache de caract\'erisation. Nous proposons une repr\'esentation des r\'eseaux sous la forme de s\'equences de descripteurs de noeuds, qui combinent les informations temporelles, les mesures topologiques, et les valeurs des attributs nodaux. Les communaut\'es sont caract\'eris\'ees au moyen des motifs s\'equentiels \'emergents les plus repr\'esentatifs issus de leurs noeuds. Ceci permet notamment la d\'etection de comportements inhabituels au sein d'une communaut\'e. Nous d\'ecrivons une \'etude empirique sur un r\'eseau de collaboration scientifique., Comment: in French

The notion of community structure is particularly useful when analyzing complex networks, because it provides an intermediate level, compared to the more classic global (whole network) and local (node neighborhood) approaches. The concept of community role of a node was derived from this base, in order to describe the position of a node in a network depending on its connectivity at the community level. However, the existing approaches are restricted to undirected networks, use topological measures which do not consider all aspects of community-related connectivity, and their role identification methods are not generalizable to all networks. We tackle these limitations by generalizing and extending the measures, and using an unsupervised approach to determine the roles. We then illustrate the applicability of our method by analyzing a Twitter network.We show how our modifications allow discovering the fact some particular users called social capitalists occupy very specific roles in this system. --- La notion de structure de communaut\'es est particuli\`erement utile pour \'etudier les r\'eseaux complexes, car elle am\`ene un niveau d'analyse interm\'ediaire, par opposition aux plus classiques niveaux local (voisinage des noeuds) et global (r\'eseau entier). Le concept de r\^ole communautaire permet de d\'ecrire le positionnement d'un noeud en fonction de sa connectivit\'e communautaire. Cependant, les approches existantes sont restreintes aux r\'eseaux non-orient\'es, utilisent des mesures topologiques ne consid\'erant pas tous les aspects de la connectivit\'e communautaire, et des m\'ethodes d'identification des r\^oles non-g\'en\'eralisables \`a tous les r\'eseaux. Nous proposons de r\'esoudre ces probl\`emes en g\'en\'eralisant les mesures existantes, et en utilisant une m\'ethode non-supervis\'ee pour d\'eterminer les r\^oles. Nous illustrons l'int\'er\^et de notre m\'ethode en l'appliquant au r\'eseau de Twitter. Nous montrons que nos modifications mettent en \'evidence les r\^oles sp\'ecifiques d'utilisateurs particuliers du r\'eseau, nomm\'es capitalistes sociaux., Comment: arXiv admin note: substantial text overlap with arXiv:1309.2132

Complex networks arises in many contexts and applications : biology, transports, online social networks (ONS). Many recent applications deal with large amount of personal data. The links between peoples may reflect freindship, messaging, or some common interests. Entities in complex network, and espacially persons, tend to form communities. Here, a community can be defined as a set of entities interacting more between each other than with the rest of the network. The topic of community detection in large networks as been extensively studied during the last decades, following the seminal work by newman, who popularized the modularity criteria. However, most community detection algorithms assume that the network is entirely known and that is does not evolve with time. This is usually not true in real world applications. In this thesis, we start by proposing novel methods for local community identification (considering only the vicinity of a given node, without accessing the whole graph). Our algorithms experimentally outperform the state-of-art methods. We show how to use the local communities to enhance the prediction of a user's behaviour. Secondly, we propose some approaches to predict the evolution of the detected communities based on machine learning methods. Finally we propose a framework for storing and processing distributed social networks in a Big Data environment. The proposed methods are validated using (among others) real world data, provided by a industrial partner operating a major social network platform in France (40 millions of users)., Les réseaux sont présents dans plusieurs contextes et applications : biologie, transports, réseaux sociaux en ligne, etc. De nombreuses applications récentes traitent d'immenses volumes de données personnelles. Les liens entre les personnes dans ces données peuvent traduire des liens d'amitiés, des échanges de messages, ou des intérêts communs. Les entités impliquées dans les réseaux, et spécialement les personnes, ont tendance à former des communautés. Dans ce contexte, une communauté peut être définie comme un ensemble d'entités qui interagissent beaucoup plus entre elles qu'avec le reste du réseau. La détection de communautés dans les grands réseaux a largement été étudiée pendant ces dernières années, suite aux travaux précurseurs de Newman qui a introduit le critère de modularité. Toutefois, la majorité des algorithmes de détection de communautés supposent que le réseau est complètement connu et qu'il n'évolue pas avec le temps. Dans cette thèse, nous commençons par proposer de nouvelles méthodes pour la détection de communautés locales (en considérant uniquement le voisinage d'un nœud donné et sans accéder à la totalité du réseau). Nos algorithmes sont plus efficaces que ceux de l'état de l'art. Nous montrons ensuite comment utiliser les communautés détectées pour améliorer la prévision de comportements utilisateurs. Dans un deuxième temps, nous proposons des approches pour prévoir l'évolution des communautés détectées. Ces méthodes sont basées sur des techniques d'apprentissage automatique. Enfin, nous proposons un framework général pour stocker et analyser les réseaux distribués dans un environnement "Big Data" . Les méthodes proposées sont validées en utilisant (entre autre) des données réelles issues d'un partenaire industriel fournissant un des réseaux en ligne les plus utilisés en France (40 millions d'utilisateurs).

Session 3 : Web social; National audience; La détection de communautés dans les réseaux sociaux est devenue un enjeu majeur pour extraire de la connaissance, observer l'émergence d'opinions ou de savoirs et les réinjecter de manière ciblée sur des groupes sociaux particuliers. Les nombreux algorithmes de détection déjà proposés fournissent des solutions approchées sur laquelle l'analyste ou même les entités regroupées ne peuvent guère intervenir. Dans cet article nous proposons un renversement de perspective. Nous considérons les entités comme des agents qui cherchent à se regrouper et qui peuvent agir sur leur stratégie de regroupement afin d'en tirer le meilleur bénéfice avec différentes règles partagées. Les communautés sont optimisées via la recherche d'un Équilibre de Nash. Cet article explore plus avant ce paradigme en considérant les différentes possibilités offertes par la recherche de l'Équilibre de Nash en matière de réorganisation pilotée par la sémantique, l'intention pragmatique, ou l'évolution spontanée du réseau.

Dans cet article, nous proposons une nouvelle approche basée sur l'Analyse Formelle des Concepts (AFC) pour la détection de communautés dans un réseau social. Nous proposons une fonction basée sur une modularité adaptée, appelée GroupNode modularity, qui améliore une méthode de détection partielle proposée par Falzon en considérant tous les acteurs du réseau social. Nous appelons notre approche GNOM-FCA (GroupNOde Modularity combined with Formal Concept Analysis approach). En outre, nous avons adapté une fonction issue du domaine de la recherche d'information, à savoir la F-mesure, dans le cas de classes multiples pour évaluer et comparer la qualité des communautés détectées. Enfin, nous avons validé notre approche par des expérimentations sur des réseaux sociaux issus du monde réel connus dans le domaine.

This thesis describes new tools specifically designed for the analysis of networks such as social, transportation, neuronal, protein, communication networks... These networks, along with the rapid expansion of electronic, IT and mobile technologies are increasingly monitored and measured. Adapted tools of analysis are therefore very much in demand, which need to be universal, powerful, and precise enough to be able to extract useful information from very different possibly large networks. To this end, a large community of researchers from various disciplines have concentrated their efforts on the analysis of graphs, well define mathematical tools modeling the interconnected structure of networks. Among all the considered directions of research, graph signal processing brings a new and promising vision : a signal is no longer defined on a regular n-dimensional topology, but on a particular topology defined by the graph. To apply these new ideas on the practical problems of network analysis paves the way to an analysis firmly rooted in signal processing theory. It is precisely this frontier between signal processing and network science that we explore throughout this thesis, as shown by two of its major contributions. Firstly, a multiscale version of community detection in networks is proposed, based on the recent definition of graph wavelets. Then, a network-adapted bootstrap method is introduced, that enables statistical estimation based on carefully designed graph resampling schemes., Cette thèse propose de nouveaux outils adaptés à l'analyse des réseaux : sociaux, de transport, de neurones, de protéines, de télécommunications... Ces réseaux, avec l'essor de certaines technologies électroniques, informatiques et mobiles, sont de plus en plus mesurables et mesurés ; la demande d'outils d'analyse assez génériques pour s'appliquer à ces réseaux de natures différentes, assez puissants pour gérer leur grande taille et assez pertinents pour en extraire l'information utile, augmente en conséquence. Pour répondre à cette demande, une grande communauté de chercheurs de différents horizons scientifiques concentre ses efforts sur l'analyse des graphes, des outils mathématiques modélisant la structure relationnelle des objets d'un réseau. Parmi les directions de recherche envisagées, le traitement du signal sur graphe apporte un éclairage prometteur sur la question : le signal n'est plus défini comme en traitement du signal classique sur une topologie régulière à n dimensions, mais sur une topologie particulière définie par le graphe. Appliquer ces idées nouvelles aux problématiques concrètes d'analyse d'un réseau, c'est ouvrir la voie à une analyse solidement fondée sur la théorie du signal. C'est précisément autour de cette frontière entre traitement du signal et science des réseaux que s'articule cette thèse, comme l'illustrent ses deux principales contributions. D'abord, une version multiéchelle de détection de communautés dans un réseau est introduite, basée sur la définition récente des ondelettes sur graphe. Puis, inspirée du concept classique de bootstrap, une méthode de rééchantillonnage de graphes est proposée à des fins d'estimation statistique.

From various applications, in sociology or biology for instance,complex networks exhib the remarquable property of communitystructure. Groups, sometimes called communities, has a stronginternal cohesion and poor links between them. Whithout priorknowledge of the number of communities, the difficulty lies in thecharacterization of a good clustering. Modularity is an overallmeasure of clustering quality widely used to capture the doubleconstraint, internal and external, of well formed communities. Theproblem became a NP-hard optimization problem. The main weakof modularity is the resolution limit, which tends to makeundetectable very small communities especially as the network islarge. The algorithm of Louvain, one of the most efficient one tooptimize modularity, proceeds by merging communities. This thesisattempts to modify the algorithm so that it mainly produces relevantmerges that do not make worse the effects of resolution limit, usinga merge condition. In addition, by combining it with a memeticalgorithm, proposed clusterings are very close to the expected onesfor graphs generated by a model that reproduces the characteristicsof complex networks. Finally, the memetic algorithm greatly reducesthe inconsistency of solution, another weakness of modularity suchthat, for the same graph, two partitions found from an exploration ofnodes in a random order can be structurally very different, makingthem difficult to interpret.; Les réseaux complexes, issus de relevés de terrain d’origines trèsvariées, en biologie, science de l’information ou sociologie,présentent une caractéristique remarquable dénommée structurecommunautaire. Des groupes, ou communautés, à l’intérieur duréseau, ont une cohésion interne forte et des liens entre eux plusfaibles. Sans connaissance a priori du nombre de communautés, ladifficulté réside dans la caractérisation d’un bon partitionnement encommunautés. La modularité est une mesure globale de qualité departitionnement très utilisée qui capture les contraintes de cohésioninterne forte et de liens externes faibles. Elle transforme le problèmede détection de communautés en problème d’optimisationNP-difficile. Elle souffre d’un défaut, la limite de résolution, qui tendà rendre indétectables les très petites communautés d’autant plusque le réseau est grand. L’algorithme le plus efficace pour optimiserla modularité, dit de Louvain, procède par fusion de communautés.Cette thèse s’attache à modifier cet algorithme pour qu’il réalisemajoritairement des fusions pertinentes, qui n’aggravent pas lalimite de résolution, en utilisant une condition de fusion. De plus, enl’associant à un algorithme mémétique, les partitions proposéessont très proches des partitions attendues pour des graphesgénérés par un modèle qui reproduit les caractéristiques desréseaux complexes. Enfin, cet algorithme mémétique réduitfortement l’inconsistance de solution, défaut de la modularité selonlequel deux partitions trouvées à partir d’un examen des noeudsdans un ordre aléatoire, pour le même graphe, peuvent êtrestructurellement très différentes, rendant leur interprétation délicate.

Network analysis is an important step in the understanding of complex systems studied in various areas such as biology, geography or sociology. This thesis focuses on the problems related to the decomposition of those networks when they are modeled by graphs. Graph decomposition methods are useful for data compression, community detection or network visualisation. One possible decomposition is a hierarchical partition of the set of vertices. We propose a method to evaluate the quality of such structures using quality measures and algorithms to maximise those measures. We also discuss the design of effective visual metaphors to represent various graph decompositions.; 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.

From various applications, in sociology or biology for instance,complex networks exhib the remarquable property of communitystructure. Groups, sometimes called communities, has a stronginternal cohesion and poor links between them. Whithout priorknowledge of the number of communities, the difficulty lies in thecharacterization of a good clustering. Modularity is an overallmeasure of clustering quality widely used to capture the doubleconstraint, internal and external, of well formed communities. Theproblem became a NP-hard optimization problem. The main weakof modularity is the resolution limit, which tends to makeundetectable very small communities especially as the network islarge. The algorithm of Louvain, one of the most efficient one tooptimize modularity, proceeds by merging communities. This thesisattempts to modify the algorithm so that it mainly produces relevantmerges that do not make worse the effects of resolution limit, usinga merge condition. In addition, by combining it with a memeticalgorithm, proposed clusterings are very close to the expected onesfor graphs generated by a model that reproduces the characteristicsof complex networks. Finally, the memetic algorithm greatly reducesthe inconsistency of solution, another weakness of modularity suchthat, for the same graph, two partitions found from an exploration ofnodes in a random order can be structurally very different, makingthem difficult to interpret., Les réseaux complexes, issus de relevés de terrain d’origines trèsvariées, en biologie, science de l’information ou sociologie,présentent une caractéristique remarquable dénommée structurecommunautaire. Des groupes, ou communautés, à l’intérieur duréseau, ont une cohésion interne forte et des liens entre eux plusfaibles. Sans connaissance a priori du nombre de communautés, ladifficulté réside dans la caractérisation d’un bon partitionnement encommunautés. La modularité est une mesure globale de qualité departitionnement très utilisée qui capture les contraintes de cohésioninterne forte et de liens externes faibles. Elle transforme le problèmede détection de communautés en problème d’optimisationNP-difficile. Elle souffre d’un défaut, la limite de résolution, qui tendà rendre indétectables les très petites communautés d’autant plusque le réseau est grand. L’algorithme le plus efficace pour optimiserla modularité, dit de Louvain, procède par fusion de communautés.Cette thèse s’attache à modifier cet algorithme pour qu’il réalisemajoritairement des fusions pertinentes, qui n’aggravent pas lalimite de résolution, en utilisant une condition de fusion. De plus, enl’associant à un algorithme mémétique, les partitions proposéessont très proches des partitions attendues pour des graphesgénérés par un modèle qui reproduit les caractéristiques desréseaux complexes. Enfin, cet algorithme mémétique réduitfortement l’inconsistance de solution, défaut de la modularité selonlequel deux partitions trouvées à partir d’un examen des noeudsdans un ordre aléatoire, pour le même graphe, peuvent êtrestructurellement très différentes, rendant leur interprétation délicate.

In this paper, we present a quick survey of current approaches for community detection in multiplex networks. Most of existing approaches are based on transforming, in one way or another, the problem into a problem of community detection in simple graphs. This can basically be made either by applying a slice aggregation strategy, either by applying community detection on each slice aside then merging obtained partitions using ensemble clustering like approaches. We argue that more interesting approaches would be based on exploring all slices at once. Recently proposed multiplex metrics allow to extend the application of promising community detection approaches, mainly grain-based approaches.

La détection de communautés dans les réseaux est aujourd'hui un domaine ayant donné lieu à une abondante littérature. Depuis les travaux de Girvan et Newman en 2002, des centaines de travaux ont été menés sur le sujet, notamment la proposition d'un nombre important d'algorithmes de plus en plus élaborés. Cependant, la majorité de ces travaux portent sur des communautés statiques dans des réseaux statiques. Or, beaucoup de réseaux de terrains sont en fait dynamiques, ils évoluent au cours du temps. L'apport principal de cette thèse est donc la conception d'un algorithme de détection de communautés dynamiques sur des réseaux temporels. Le manuscrit est découpé en quatre sections : La première est un état de l'art, où sont passés en revu les méthodes existantes pour la détection de communauté, statiques, dynamiques, avec et sans recouvrement. La seconde est la présentation de la solution que nous proposons : iLCD, un framework pour la détection de communautés dynamiques dans les réseaux temporels, ainsi que deux implémentations de ce framework. La troisième partie présente les travaux effectués pour valider iLCD sur le plan statique, c'est à dire valider que les communautés trouvées sont pertinentes comparées à d'autres algorithmes existant sur des réseaux statiques. Pour ce faire, nous proposons des idées originales, afin de pouvoir comparer des méthodes sur des graphes réels. Enfin, la dernière partie est consacrée à la validation de l'aspect dynamique d'iLCD. En effet, la dynamique introduit des données supplémentaires : l'apparition et la disparition de communautés, leur évolution en continue, ainsi que des opérations complexes, telles que la fusion ou la division de communautés au cours du temps. Ce sont ces aspects qui sont validés ici, en étudiant en détail les résultats obtenus sur des réseaux réels.

Within the community detection problem it is possible to use either the structural dimension or the composition dimension of the social network; on the first case the communities contain groups of well-connected and dissimilar nodes whereas on the second case, the communities contain groups of similar but loosely connected nodes. Therefore the amount of information extracted is reduced as one of the dimensions is discarded. The objective of this Thesis is to propose a novel approach for detecting communities in which the structural and composition dimensions are integrated in such a way the communities contain groups of well-connected and similar nodes. This approach requires first, a new definition of community that includes both dimensions of the network, then a new community detection model suited for this new definition that allows us to find groups of well-connected and similar nodes. The model starts introducing the notion of point of view that allows the division of the composition dimension for analyzing the network from different perspectives. Then the model influences the community detection process by integrating the composition information into the graph structure. The last step is the social network visualization that places the nodes according to their structural and compositional similarities and that allows us to find important nodes regarding the interaction between communities., Dans le problème de détection de communautés il est possible d'utiliser soit la dimension structurelle, soit la dimension compositionelle du réseau : dans le premier cas les communautés seraient composées par des groupes de noeuds fortement connectés mais peu similaires, et pour le deuxième cas, les groupes auraient des noeuds similaires mais faiblement connectés. Donc en ne choisissant qu'une des dimensions la quantité possible d'information à extraire est réduite. Cette thèse a pour objectif de proposer une nouvelle approche pour utiliser en même temps les dimensions structurelle et compositionelle lors de la détection de communautés de façon telle que les groupes aient des noeuds similaires et bien connectés. Pour la mise en oeuvre de cette approche il faut d'abord une nouvelle définition de communauté qui prend en compte les deux dimensions présentées auparavant et ensuite un modèle nouveau de détection qui utilise cette définition, en trouvant des groupes de noeuds similaires et bien connectés. Le modèle commence par l'introduction de la notion de point de vue qui permet de diviser la dimension compositionelle pour analyser le réseau depuis différentes perspectives. Ensuite le modèle, en utilisant l'information compositionelle, influence le processus de détection de communautés qui intègre les deux dimensions du réseau. La dernière étape est la visualisation du graphe de communautés qui positionne les noeuds selon leur similarité structurelle et compositionelle, ce qui permet d'identifier des noeuds importants pour les interactions entre communautés.