Search

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.

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

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.

International audience; La détection de communautés dans les réseaux sociaux est devenue un champ de recherche majeur. La plupart des méthodes, à l'exemple de l'algorithme de Louvain, s'intéressent aux graphes de personnes (graphes monopartis) pour extraire des communautés disjointes. Elles s'appuient de manière globale sur l'optimisation d'un critère appelé modularité. En s'inspirant des treillis de Galois nous présentons une méthode originale de détection de communautés chevauchantes pour les graphes bipartis. Contrairement aux quelques méthodes qui exploitent aussi des treillis de Galois notre approche est de complexité polynomiale et prend en compte en final tous les individus. Dans le même esprit que la modularité nous proposons un critère de regroupement, l'autonomie, qui combine la cohésion interne d'une communauté et son indépendance des autres communautés. Plusieurs exemples illustrent notre approche et en montrent la validité sémantique et pragmatique.

The outburst of social functionalities in web-based applications has fostered the deployment of a social media landscape where people freely contribute, gather and interact with each other. The integration of various means for publishing and socializing allows us to quickly share, recommend and propagate information to our social network, trigger reactions, and finally enrich it. These shared spaces fostered the creation and development of interest communities that publish, filter and organize directories of references in their domains at an impressive scale with very agile responses to changes. In order to reproduce the information sharing success story of the web, more and more social platforms are deployed into corporate intranets. However, the benefit of these platforms is often hindered when the social network becomes so large that relevant information is frequently lost in an overwhelming flow of activity notifications. Organizing this huge amount of information is one of the major challenges of Web 2.0 to achieve the full potential of Enterprise 2.0, i.e., the efficient use of Web 2.0 technologies like blogs and wikis within the Intranet. This thesis proposes to help analyzing the characteristics of the heterogeneous social networks that emerge from the use of web-based social applications, with an original contribution that leverages Social Network Analysis with Semantic Web frameworks. Social Network Analysis (SNA) proposes graph algorithms to characterize the structure of a social network and its strategic positions. Semantic Web frameworks allow representing and exchanging knowledge across web applications with a rich typed graph model (RDF), a query language (SPARQL) and schema definition frameworks (RDFS and OWL). In this thesis, we merge both models in order to go beyond the mining of the flat link structure of social graphs by integrating a semantic processing of the network typing and the emerging knowledge of online activities. In particular we investigate how (1) to bring online social data to ontology-based representations, (2) to conduct a social network analysis that takes advantage of the rich semantics of such representations, and (3) to semantically detect and label communities of online social networks and social tagging activities.; L'explosion des fonctionnalités sociales au sein des applications du Web a favorisé le déploiement d'un panorama de médias sociaux permettant aux utilisateurs de librement contribuer, de se regrouper et d'interagir entre eux. La combinaison de divers moyens de publication et de socialisation permet de rapidement partager, recommander et propager l'information dans son réseau social, ainsi que de solliciter des réactions et de nouvelles contributions. Ces espaces partagés ont favorisé la création et le développement de communautés d'intérêts qui publient, filtrent et organisent de vastes répertoires de références dans leurs domaines, avec une impressionnante réactivité aux changements. Afin de reproduire les succès du Web dans la gestion d'information, de plus en plus de plates-formes sociales sont déployées dans des intranets d'entreprise. Cependant, l'avantage de ces plates-formes est fortement atténué lorsque le réseau social devient si grand que les informations pertinentes sont noyées dans des flux continus de notifications. Organiser cette énorme quantité d'informations est l'un des défis majeurs du Web 2.0 afin de tirer pleinement partie des bénéfices de l'Entreprise 2.0, à savoir, l'utilisation des technologies du Web 2.0, tel que les blogs et les wikis, dans un intranet. Cette thèse propose d'améliorer l'analyse des réseaux sociaux multiples et variés émergeant des usages sociaux du Web, au travers d'une contribution originale qui enrichit l'analyse des réseaux sociaux avec les technologies du Web Sémantique. L'analyse des réseaux sociaux propose des algorithmes de graphes pour caractériser la structure d'un réseau social et ses positions stratégiques. Les technologies du Web Sémantique permettent de représenter et d'échanger les connaissances entre des applications distribuées sur le Web avec un modèle de graphes richement typés (RDF), un langage de requête (SPARQL) et des langages de description de modèles (RDFS et OWL). Dans cette thèse, nous fusionnons ces deux modèles afin d'aller au-delà de l'analyse structurelle des graphes sociaux en intégrant un traitement sémantique de leur typage et des connaissances qu'ils contiennent. En particulier nous examinons comment (1) modéliser des données sociales en ligne à base d'ontologies, (2) réaliser une analyse du réseau social qui tire partie de la sémantique de ces représentations, et (3) détecter et étiqueter explicitement des communautés à partir de réseaux sociaux et de folksonomies.

The outburst of social functionalities in web-based applications has fostered the deployment of a social media landscape where people freely contribute, gather and interact with each other. The integration of various means for publishing and socializing allows us to quickly share, recommend and propagate information to our social network, trigger reactions, and finally enrich it. These shared spaces fostered the creation and development of interest communities that publish, filter and organize directories of references in their domains at an impressive scale with very agile responses to changes. In order to reproduce the information sharing success story of the web, more and more social platforms are deployed into corporate intranets. However, the benefit of these platforms is often hindered when the social network becomes so large that relevant information is frequently lost in an overwhelming flow of activity notifications. Organizing this huge amount of information is one of the major challenges of Web 2.0 to achieve the full potential of Enterprise 2.0, i.e., the efficient use of Web 2.0 technologies like blogs and wikis within the Intranet. This thesis proposes to help analyzing the characteristics of the heterogeneous social networks that emerge from the use of web-based social applications, with an original contribution that leverages Social Network Analysis with Semantic Web frameworks. Social Network Analysis (SNA) proposes graph algorithms to characterize the structure of a social network and its strategic positions. Semantic Web frameworks allow representing and exchanging knowledge across web applications with a rich typed graph model (RDF), a query language (SPARQL) and schema definition frameworks (RDFS and OWL). In this thesis, we merge both models in order to go beyond the mining of the flat link structure of social graphs by integrating a semantic processing of the network typing and the emerging knowledge of online activities. In particular we investigate how (1) to bring online social data to ontology-based representations, (2) to conduct a social network analysis that takes advantage of the rich semantics of such representations, and (3) to semantically detect and label communities of online social networks and social tagging activities.; L'explosion des fonctionnalités sociales au sein des applications du Web a favorisé le déploiement d'un panorama de médias sociaux permettant aux utilisateurs de librement contribuer, de se regrouper et d'interagir entre eux. La combinaison de divers moyens de publication et de socialisation permet de rapidement partager, recommander et propager l'information dans son réseau social, ainsi que de solliciter des réactions et de nouvelles contributions. Ces espaces partagés ont favorisé la création et le développement de communautés d'intérêts qui publient, filtrent et organisent de vastes répertoires de références dans leurs domaines, avec une impressionnante réactivité aux changements. Afin de reproduire les succès du Web dans la gestion d'information, de plus en plus de plates-formes sociales sont déployées dans des intranets d'entreprise. Cependant, l'avantage de ces plates-formes est fortement atténué lorsque le réseau social devient si grand que les informations pertinentes sont noyées dans des flux continus de notifications. Organiser cette énorme quantité d'informations est l'un des défis majeurs du Web 2.0 afin de tirer pleinement partie des bénéfices de l'Entreprise 2.0, à savoir, l'utilisation des technologies du Web 2.0, tel que les blogs et les wikis, dans un intranet. Cette thèse propose d'améliorer l'analyse des réseaux sociaux multiples et variés émergeant des usages sociaux du Web, au travers d'une contribution originale qui enrichit l'analyse des réseaux sociaux avec les technologies du Web Sémantique. L'analyse des réseaux sociaux propose des algorithmes de graphes pour caractériser la structure d'un réseau social et ses positions stratégiques. Les technologies du Web Sémantique permettent de représenter et d'échanger les connaissances entre des applications distribuées sur le Web avec un modèle de graphes richement typés (RDF), un langage de requête (SPARQL) et des langages de description de modèles (RDFS et OWL). Dans cette thèse, nous fusionnons ces deux modèles afin d'aller au-delà de l'analyse structurelle des graphes sociaux en intégrant un traitement sémantique de leur typage et des connaissances qu'ils contiennent. En particulier nous examinons comment (1) modéliser des données sociales en ligne à base d'ontologies, (2) réaliser une analyse du réseau social qui tire partie de la sémantique de ces représentations, et (3) détecter et étiqueter explicitement des communautés à partir de réseaux sociaux et de folksonomies.