Dans le contexte des réseaux complexes, la structure communautaire du réseau devient un sujet important pour plusieurs domaines de recherche. Les communautés sont en général vues comme des groupes intérieurement denses. La détection de tels groupes offre un éclairage intéressant sur la structure du réseau. Par exemple, une communauté de pages web regroupe des pages traitant du même sujet. La définition de communautés est en général limitée à une partition de l'ensemble des nœds. Cela exclut par définition qu'un nœd puisse appartenir à plusieurs communautés, ce qui pourtant est naturel dans de nombreux (cas des réseaux sociaux par exemple). Une autre question importante et sans réponse est l'étude des réseaux et de leur structure communautaire en tenant compte de leur dynamique. Cette thèse porte sur l'étude de réseaux dynamiques et la détection de communautés recouvrantes. Nous proposons deux méthodes différentes pour la détection de communautés recouvrantes. La première méthode est appelée optimisation de clique. L'optimisation de clique vise à détecter les nœds recouvrants granulaires. La méthode de l'optimisation de clique est une approche à grain fin. La seconde méthode est nommée détection floue (fuzzy detection). Cette méthode est à grain plus grossier et vise à identifier les groupes recouvrants. Nous appliquons ces deux méthodes à des réseaux synthétiques et réels. Les résultats obtenus indiquent que les deux méthodes peuvent être utilisées pour caractériser les nœds recouvrants. Les deux approches apportent des points de vue distincts et complémentaires. Dans le cas des graphes dynamiques, nous donnons une définition sur la relation entre les communautés à deux pas de temps consécutif. Cette technique permet de représenter le changement de la structure en fonction du temps. Pour mettre en évidence cette relation, nous proposons des diagrammes de lignage pour la visualisation de la dynamique des communautés. Ces diagrammes qui connectent des communautés à des pas de temps successifs montrent l'évolution de la structure et l'évolution des groupes recouvrantes., Nous avons également appliquer ces outils à des cas concrets.

Les réseaux sont présents dans pratiquement tous les aspects de la vie. Le monde quinous entoure comporte énormément de réseaux. Par exemple, les réseaux de communicationconstitués de téléphones, les réseaux électriques, les réseaux d'ordinateurs, le réseaudes lignes aériennes, ... etc, sont autant de réseaux importants dans la vie de chaque jour.Le cadre mathématique des réseaux est bien approprié pour décrire plusieurs systèmescomposés d'un grand nombre d'entités qui interagissent entre elles. Chaque entité est représentéepar un noeud du réseau et chaque interaction par un lien entre deux noeuds. Ilest donc possible de modéliser ces réseaux par des graphes. Pour la plupart de ces réseaux,la difficulté provient principalement du grand nombre d'entités, ainsi que de la façon dontelles sont interconnectées. Une approche naturelle pour simplifier de tels systèmes consistedonc à réduire leur taille. Cette simplification n'est pas faite aléatoirement, mais de tellefaçon à ce que les noeuds de la même composante aient plus de liens entre eux qu'avec lesautres composantes. Ces groupes de noeuds ou composantes sont appelés communautésd'intérêt. Notre thèse se positionne dans le domaine de l'étude des graphes sociaux. Elle s'intéresseprincipalement à l'étude de la robustesse des structures sociales émergentes dansles réseaux d'interactions. L'aspect de la robustesse des réseaux constitue un challengetrès important pour comprendre leur fonctionnement, le comportement des entités lesconstituant et surtout pour comprendre les interactions qui peuvent se produire entreelles, permettant l'émergence de certains comportements qui n'étaient pas du tout prévisiblesau préalable. Actuellement, les études de la robustesse des réseaux qui existentdans la littérature traitent cet aspect du point de vue purement structurel, i.e. toutes lesperturbations sont appliquées soit sur les noeuds, soit sur les arêtes du graphe. Pour cequi est de notre étude, nous nous sommes intéressés à définir une nouvelle stratégie qui sebase sur des perturbations appliquées sur les paramètres qui permettent l'émergence desgraphes sociaux dans les réseaux d'interaction. Cette façon d'aborder l'aspect robustessedes graphes constitue une nouvelle manière d'évaluer et de quantifier les changements quipeuvent intervenir dans les structures de ces graphes.

Les réseaux sont présents dans pratiquement tous les aspects de la vie. Le monde quinous entoure comporte énormément de réseaux. Par exemple, les réseaux de communicationconstitués de téléphones, les réseaux électriques, les réseaux d’ordinateurs, le réseaudes lignes aériennes, ... etc, sont autant de réseaux importants dans la vie de chaque jour.Le cadre mathématique des réseaux est bien approprié pour décrire plusieurs systèmescomposés d’un grand nombre d’entités qui interagissent entre elles. Chaque entité est représentéepar un noeud du réseau et chaque interaction par un lien entre deux noeuds. Ilest donc possible de modéliser ces réseaux par des graphes. Pour la plupart de ces réseaux,la difficulté provient principalement du grand nombre d’entités, ainsi que de la façon dontelles sont interconnectées. Une approche naturelle pour simplifier de tels systèmes consistedonc à réduire leur taille. Cette simplification n’est pas faite aléatoirement, mais de tellefaçon à ce que les noeuds de la même composante aient plus de liens entre eux qu’avec lesautres composantes. Ces groupes de noeuds ou composantes sont appelés communautésd’intérêt. Notre thèse se positionne dans le domaine de l’étude des graphes sociaux. Elle s’intéresseprincipalement à l’étude de la robustesse des structures sociales émergentes dansles réseaux d’interactions. L’aspect de la robustesse des réseaux constitue un challengetrès important pour comprendre leur fonctionnement, le comportement des entités lesconstituant et surtout pour comprendre les interactions qui peuvent se produire entreelles, permettant l’émergence de certains comportements qui n’étaient pas du tout prévisiblesau préalable. Actuellement, les études de la robustesse des réseaux qui existentdans la littérature traitent cet aspect du point de vue purement structurel, i.e. toutes lesperturbations sont appliquées soit sur les noeuds, soit sur les arêtes du graphe. Pour cequi est de notre étude, nous nous sommes intéressés à définir une nouvelle stratégie qui sebase sur des perturbations appliquées sur les paramètres qui permettent l’émergence desgraphes sociaux dans les réseaux d’interaction. Cette façon d’aborder l’aspect robustessedes graphes constitue une nouvelle manière d’évaluer et de quantifier les changements quipeuvent intervenir dans les structures de ces graphes. / Networks are present in virtually all aspects of life. The world surrounding usincludes to many networks. For example, communication networks constituted of phones,electrical networks, computers networks, aerial lines network, ? etc, are such importantnetworks in our daily life. The mathematical framework of networks is well appropriatedto describe different systems composed of many entities interacting with each other. Eachentity is represented by a network node and each interaction by a link between twonodes. Therefore, it is possible to model these networks by graphs. For most of thesenetworks, the difficulty comes mainly from the large number of entities and the way theyare interconnected. A natural approach to simplify such systems is therefore to reducetheir size. This simplification is not made randomly, but in such a way that the nodes ofthe same component would have more connections between themselves than with othercomponents. These groups of nodes or components are called communities of interest.Our thesis is positioned in the field of social graphs study. It is mainly interested instudying the robustness of social structures emerging in interaction networks. The aspectof networks robustness is a very important challenge to understand their functioning,the behavior of the constituting entities and especially to understand the interactionsthat may occur between them, allowing the emergence of certain behaviors that were notpredictable at all in advance. Currently, studies of networks robustness that exist in theliterature treat this aspect from a purely structural point of view, ie, all perturbations areapplied either on nodes or on the edges of the graph. In terms of our study, we focused ondefining a new strategy based on perturbations applied on the parameters that allow theemergence of social graphs in interaction networks. This way to approach the robustnessappearance of the graphs is a new way to assess and quantify the changes that may occurin the structures of these graphs.

Les interactions sont partout : il peut s'agir de contacts entre individus, d'emails, d'appels téléphoniques, de trafic IP, d'achats en ligne, d'exécution de code, etc. Les interactions peuvent être dirigées, pondérées, enrichies d'informations supplémentaires, cependant, dans tous les cas, une interaction signifie que deux entités u et v ont interagi du temps b au temps e : par exemple, deux individus u et v se rencontrent du temps b au temps e, deux machines sur un réseau démarrent une session IP du temps b au temps e, deux personnes u et v se téléphonent du temps b au temps e, etc.Dans cette thèse, nous explorons une nouvelle approche visant à modéliser les interactions directement comme des flots de liens, c'est-à-dire des séquences de quadruplets (b,e,u,v) signifiant que u et v ont interagi du temps b au temps e. Nous posons les fondations du formalisme correspondant. Afin de valider notre travail théorique, nous nous concentrons sur l'analyse de trafic IP. Il est en effet crucial pour nous d'effectuer des aller-retours constants entre théorie et pratique : les cas pratiques doivent nourrir notre réflexion théorique, et, en retour, les outils formels doivent être conçus de façon à être appliqués de la manière la plus générale.Nous appliquons notre formalisme à l'analyse de trafic IP, dans le but de valider la pertinence de notre formalisme for l'analyse de trafic IP, ainsi que comme méthodologie de détection d'événements. Nous élaborons une méthode permettant d'identifier des événements recouvrant plusieurs échelles de temps, et l'appliquons à une trace de trafic issue du jeu de données MAWI. / Interactions are everywhere: in the contexts of face-to-face contacts, emails, phone calls, IP traffic, online purchases, running code, and many others. Interactions may be directed, weighted, enriched with supplementary information, yet the baseline remains: in all cases, an interaction means that two entities u and v interact together from time b to time e: for instance, two individuals u and v meet from time b to time e, two machines on a network start an IP session from time b to time e, two persons u and v phone each other from time b to time e, and so on.In this thesis, we explore a new approach consisting in modelling interactions directly as link streams, i.e. series of quadruplets ( b, e, u, v ) meaning that u and v interacted from time b to time e, and we develop the basis of the corresponding formalism. In order to guide and assess this fundamental work, we focus on the analysis of IP traffic. It is particularly important to us that we make both fundamental and applied progress: application cases should feed our theoretical thoughts, and formal tools are designed to have meaning on application cases in the most general way.We apply our framework to the analysis of IP traffic, with the aim of assessing the relevance of link streams for describing IP traffic as well as finding events inside the traffic. We devise a method to identify events at different scales, and apply it to a trace of traffic from the MAWI dataset.

Les données relationnelles sont omniprésentes dans la nature et leur accessibilité ne cesse d'augmenter depuis ces dernières années. Ces données, vues comme un tout, forment un réseau qui peut être représenté par une structure de données appelée graphe où chaque nœud du graphe est une entité et chaque arête représente une relation ou connexion entre ces entités. Les réseaux complexes en général, tels que le Web, les réseaux de communications ou les réseaux sociaux sont connus pour exhiber des propriétés structurelles communes qui émergent aux travers de leurs graphes. Dans cette thèse, nous mettons l'accent sur deux importantes propriétés appelées *homophilie* et *attachement préférentiel* qui se produisent dans un grand nombre de réseaux réels. Dans une première phase, nous étudions une classe de modèles de graphes aléatoires dans un contexte Bayésien non-paramétrique, appelé *modèle de composition mixée*, et nous nous concentrons à montrer si ces modèles satisfont ou non les propriétés mentionnées, après avoir proposé des définitions formelles pour ces dernières. Nous conduisons ensuite une évaluation empirique pour mettre à l'épreuve nos résultats sur des jeux de données de réseaux synthétiques et réels. Dans une seconde phase, nous proposons un nouveau modèle, qui généralise un précédent modèle à composition mixée stochastique, adapté pour les réseaux pondérés et nous développons un algorithme d'inférence efficace capable de s'adapter à des réseaux de grande échelle. / Relational data are ubiquitous in the nature and their accessibility has not ceased to increase in recent years. Those data, see as a whole, form a network, which can be represented by a data structure called a graph, where each vertex of the graph is an entity and each edge a connection between pair of vertices. Complex networks in general, such as the Web, communication networks or social network, are known to exhibit common structural properties that emerge through their graphs. In this work we emphasize two important properties called *homophilly* and *preferential attachment* that arise on most of the real-world networks. We firstly study a class of powerful *random graph models* in a Bayesian nonparametric setting, called *mixed-membership model* and we focus on showing whether the models in this class comply with the mentioned properties, after giving formal definitions in a probabilistic context of the latter. Furthermore, we empirically evaluate our findings on synthetic and real-world network datasets. Secondly, we propose a new model, which extends the former Stochastic Mixed-Membership Model, for weighted networks and we develop an efficient inference algorithm able to scale to large-scale networks.

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.

Nous nous intéressons dans cette thèse à la problématique de recommandation de tags dans les systèmes de partage et de classification sociale des ressources, dits folksonomies. Les utilisateurs annotent les ressources à partager par des tags librement choisis. Or, la liberté de choix de tags les rends ambigus. Nous proposons une nouvelle approche topologique nommé TLTR (Two Level Tag Recommendation)pour la recommandation de tags. TLTR est basée sur une approche originale de compression des graphes. Le graphe d'une folksonomie est compressé en appliquant une méthode de clustering sur chacune des trois composantes d'une folksonomie, à savoir: l'ensemble des utilisateurs, des ressources et des tags. Nous proposons également une méthode de clustering topologique basée sur une approche centrée graine pour la détection des communautés dans les graphes multiplexes. Une approche topologique classique, en occurrence la méthode Folkrank, est appliquée sur le graphe réduit afin de sélectionner les clusters de tags les plus appropriés. Ces clusters sont ensuite utilisés pour construire un autre graphe contextuel extrait du graphe original représentant la folksonomie. La méthode Folkrank est à nouveau appliquée afin de calculer la liste de tags à recommander. Des expérimentations sur des grandes folksonomies, notamment, des jeux de données extraits du système de partage des références bibliographiques Bibsonomy montrent la pertinence de notre approche. / We focus in this thesis on the problem of tag recommendation in social sharing to classification systems called folksonomies. Users of a folksonomy annotate their resources with freely tags chosen. We propose here a new topological approach for tags recommendation called TLTR (Two Level Tag Recommendation). TLTR (Two Level Tag Recommendation) is based on an original approach of graph compression. The graph of a folksonomy is compressed by a clustering each of the three components, namely the set of users, resources and tags. A topological clustering method based on a seed-centered approach for community detection in multiplex graphs is proposed. A classical topological approach, namely Folkrank, is applied to the reduced graph to select the most appropriate clusters of tags. These clusters are then used to build another contextual graph extracted from the original graph representing the folksonomy. Folkrank method is applied again to compute the list of tags to recommend. Experiments on large folksonomy, including, data extracted from references system Bibsonomy show the relevance of our approach.

Nous nous intéressons dans ce travail au problème de prévision de nouveaux liens dans des grands graphes de terrain. Nous explorons en particulier les approches topologiques dyadiques pour la prévision de liens. Différentes mesures de proximité topologique ont été étudiées dans la littérature pour prédire l’apparition de nouveaux liens. Des techniques d’apprentissage supervisé ont été aussi utilisées afin de combiner ces différentes mesures pour construire des modèles prédictifs. Le problème d’apprentissage supervisé est ici un problème difficile à cause notamment du fort déséquilibre de classes. Dans cette thèse, nous explorons différentes approches alternatives pour améliorer les performances des approches dyadiques pour la prévision de liens. Nous proposons d’abord, une approche originale de combinaison des prévisions fondée sur des techniques d’agrégation supervisée de listes triées (ou agrégation de préférences). Nous explorons aussi différentes approches pour améliorer les performances des approches supervisées pour la prévision de liens. Une première approche consiste à étendre l’ensemble des attributs décrivant un exemple (paires de noeuds) par des attributs calculés dans un réseau multiplexe qui englobe le réseau cible. Un deuxième axe consiste à évaluer l’apport destechniques de détection de communautés pour l’échantillonnage des exemples. Des expérimentations menées sur des réseaux réels extraits de la base bibliographique DBLP montrent l’intérêt des approaches proposées. / In this work, we are interested to tackle the problem of link prediction in complex networks. In particular, we explore topological dyadic approaches for link prediction. Different topological proximity measures have been studied in the scientific literature for finding the probability of appearance of new links in a complex network. Supervided learning methods have also been used to combine the predictions made or information provided by different topological measures. The create predictive models using various topological measures. The problem of supervised learning for link prediction is a difficult problem especially due to the presence of heavy class imbalance. In this thesis, we search different alternative approaches to improve the performance of different dyadic approaches for link prediction. We propose here, a new approach of link prediction based on supervised rank agregation that uses concepts from computational social choice theory. Our approach is founded on supervised techniques of aggregating sorted lists (or preference aggregation). We also explore different ways of improving supervised link prediction approaches. One approach is to extend the set of attributes describing an example (pair of nodes) by attributes calculated in a multiplex network that includes the target network. Multiplex networks have a layered structure, each layer having different kinds of links between same sets of nodes. The second way is to use community information for sampling of examples to deal with the problem of classe imabalance. Experiments conducted on real networks extracted from well known DBLP bibliographic database.

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