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). / 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).

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

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.

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.

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.

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

Dans le contexte des réseaux complexes, cette thèse s’inscrit dans deux axes : (1) Méthodologiede la détection de communautés et (2) Evaluation de la qualité des algorithmes de détection de communautés. Dans le premier axe, nous nous intéressons en particulier aux approches fondées sur les Leaders (sommets autour desquels s’agrègent les communautés). Premièrement, nous proposons un enrichissement de la méthodologie LICOD qui permet d’évaluer les différentes stratégies des algorithmes fondés sur les leaders, en intégrant différentes mesures dans toutes les étapes de l’algorithme. Deuxièmement, nous proposons une extension de LICOD, appelée it-LICOD. Cette extension introduit une étape d’auto-validation de l’ensemble des leaders. Les résultats expérimentaux de it-LICOD sur les réseaux réels et artificiels sont bons par rapport à LICOD et compétitifs par rapport aux autres méthodes. Troisièmement, nous proposons une mesure de centralité semi-locale, appelée TopoCent, pour remédier au problème de la non-pertinence des mesures locales et de la complexité de calcul élevée des mesures globales. Nous montrons expérimentalement que LICOD est souvent plus performant avec TopoCent qu’avec les autres mesures de centralité. Dans le deuxième axe, nous proposons deux méthodes orientées-tâche, CLE et PLE, afin d’évaluer les algorithmes de détection de communautés. Nous supposons que la qualité de la solution des algorithmes peut être estimée en les confrontant à d’autres tâches que la détection de communautés en elle-même. Dans la méthode CLE nous utilisons comme tâche la classification non-supervisée et les algorithmes sont évalués sur des graphes générés à partir des jeux de données numériques. On bénéficie dans ce cas de la disponibilité de la vérité de terrain (les regroupements) de plusieurs jeux de données numériques. En ce qui concerne la méthode PLE, la qualité des algorithmes est mesurée par rapport à leurs contributions dans une tâche de prévision de liens. L’expérimentation des méthodes CLE et PLE donne de nouveaux éclairages sur les performances des algorithmes de détection de communautés / In this thesis we focus, on one hand, on community detection in complex networks, and on the other hand, on the evaluation of community detection algorithms. In the first axis, we are particularly interested in Leaders driven community detection algorithms. First, we propose an enrichment of LICOD : a framework for building different leaders-driven algorithms. We instantiate different implementations of the provided hotspots. Second, we propose an extension of LICOD, we call it-LICOD. This extension introduces a self-validation step of all identified leaders. Experimental results of it-LICOD on real and artificial networks show that it outperform the initial LICOD approach. Obtained results are also competitive with those of other state-of-the art methods. Thirdly, we propose a semi-local centrality measure, called TopoCent, that address the problem of the irrelevance of local measures and high computational complexity of globalmeasures. We experimentally show that LICOD is often more efficient with TopoCent than with the other classical centrality measures. In the second axis, we propose two task-based community evaluation methods : CLE and PLE. We examine he hypothesis that the quality of community detection algorithms can be estimated by comparing obtained results in the context of other relevent tasks. The CLE approach, we use a data clustering task as a reference. The PLE method apply a link prediction task. We show that the experimentation of CLE and PLE methods gives new insights into the performance of community detection algorithms.

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

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

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.