Alors que les réseaux sociaux s'attachent à représenter des entités et les relations existant entre elles, les réseaux d'information intègrent également des attributs décrivant ces entités ; ce qui conduit à revisiter les méthodes d'analyse et de fouille de ces réseaux. Dans ces travaux, nous proposons des méthodes de classification des entités du réseau d'information qui exploitent d'une part les relations entre celles-ci et d'autre part les attributs les caractérisant. Nous nous penchons sur le cas des réseaux à vecteurs d'attributs, où les entités du réseau sont décrites par des vecteurs numériques. Ainsi nous proposons des approches basées sur des techniques reconnues pour chaque type d'information, faisant appel notamment à l'inertie pour la classification automatique et à la modularité de Newman et Girvan pour la détection de communautés. Nous évaluons nos propositions sur des réseaux issus de données bibliographiques, faisant usage en particulier d'information textuelle. Nous évaluons également nos approches face à diverses évolutions du réseau, notamment au regard d'une détérioration des informations des liens et des attributs, et nous caractérisons la robustesse de nos méthodes à celle-ci

Au vu de l'utilisation croissante des technologies de l'information et de la communication dans les réseaux électriques, il est indispensable d'étudier l'étroite liaison entre ces infrastructures et d'avoir une vision intégrée du système couplé. Cette thèse porte ainsi sur la modélisation des systèmes multi-infrastructures. Cela inclut les interdépendances et les trajectoires de défaillances de type modes communs, aggravations et cascades. Il est en effet nécessaire d'identifier les points de faiblesse qui peuvent déclencher une ou de multiples défaillance(s), se succéder en cascade au travers de ces infrastructures liées et ainsi entrainer des défaillances inattendues et de plus en plus graves dans des autres infrastructures. Dans cette optique, différents modèles basés sur la théorie des Réseaux Complexes sont développés afin d'identifier les composants les plus importantes, et pourtant critiques, dans le système interconnecté. Un des principaux verrous scientifiques levé dans cette thèse est relatif au dé-veloppement d'un modèle mathématique " unifié " afin de représenter les comportements des multiples infrastructures non-homogènes qui ont des interdépendances asymétriques.

Au vu de l’utilisation croissante des technologies de l’information et de la communication dans les réseaux électriques, il est indispensable d’étudier l’étroite liaison entre ces infrastructures et d’avoir une vision intégrée du système couplé. Cette thèse porte ainsi sur la modélisation des systèmes multi-infrastructures. Cela inclut les interdépendances et les trajectoires de défaillances de type modes communs, aggravations et cascades. Il est en effet nécessaire d’identifier les points de faiblesse qui peuvent déclencher une ou de multiples défaillance(s), se succéder en cascade au travers de ces infrastructures liées et ainsi entrainer des défaillances inattendues et de plus en plus graves dans des autres infrastructures. Dans cette optique, différents modèles basés sur la théorie des Réseaux Complexes sont développés afin d’identifier les composants les plus importantes, et pourtant critiques, dans le système interconnecté. Un des principaux verrous scientifiques levé dans cette thèse est relatif au développement d'un modèle mathématique « unifié » afin de représenter les comportements des multiples infrastructures non-homogènes qui ont des interdépendances asymétriques. / In view of the increasing use of Information and Communication Technol-ogies in power systems, it is essential to study the interdependencies between these coupled heterogeneous systems. This thesis focuses on the modeling of multi- infrastructure systems. This includes interdependencies and the three major failures families: common mode, escalat-ing and cascading. It is indeed necessary to identify the weaknesses that can trigger one or multiple failure(s) and cascade through these interdependent infrastructures, causing unex-pected and increasingly more serious failures to other infrastructures. In this context, different approaches, based on the theory of Complex Networks, are developed to identify the most critical components in the coupled heterogeneous system. One of the major scientific barriers addressed in this thesis is the development of a unified mathematical model to represent the behavior.

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. / In complex networks, the notion of community structure refers to the presence of groups of nodes in a network. These groups are more densely connected internally than with the rest of the network. The presence of communities inside a network gives an insight on network structural properties. For example, in social networks, communities are based on common interests, location, hobbies.... Generally, a community structure is described by a partition of the network nodes, where each node belongs to a unique community. A more reasonable description seems to be overlapping community structure, where nodes are allowed to be shared by several communities. Moreover, when considering dynamic networks whose interactions between nodes evolve in time, it appears crucial to consider also the evolution of the intrinsic community structure. This thesis focus on mining dynamic community evolution and overlapping community detection. We have proposed two distinct methods for overlapping community detection. The first one named clique optimization and the second one called fuzzy detection. Our clique optimization aims to identify granular overlaps and it is a fine grain scale approach. Our fuzzy detection is at a coarser grain scale with the strategy of identifying modular overlaps. Their applications in synthetic and real networks indicate that both methods can be used for characterizing overlapping nodes but in distinct and complementary views. We also propose the definition of predecessor and successor in mining community evolution. Such definition describes the relationship between communities at different time steps. We use it to detect community evolution in dynamic networks and show how modular overlaps evolve over time. A visualization tool called lineage diagrams is used to show community evolution by connecting communities in relationship of predecessor and successor. Several cases are studied.

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

Cette thèse présente des algorithmes de résolution de quatre problèmes de clique : clique de poids maximum (MVWCP), s-plex maximum (MsPlex), clique maximum équilibrée dans un graphe biparti (MBBP) et clique partition (CPP). Les trois premiers problèmes sont des généralisations ou relaxations du problème de la clique maximum, tandis que le dernier est un problème de couverture. Ces problèmes, ayant de nombreuses applications pratiques, sont NP-difficiles, rendant leur résolution ardue dans le cas général. Nous présentons ici des algorithmes de recherche locale, principalement basés sur la recherche tabou, permettant de traiter efficacement ces problèmes ; chacun de ces algorithmes emploie des composants originaux et spécifiquement adaptés aux problèmes traités, comme de nouveaux opérateurs ou mécanismes perturbatifs. Nous y intégrons également des stratégies telles que la réduction de graphe ou la propagation afin de traiter des réseaux de plus grande taille. Des expérimentations basées sur des jeux d’instances nombreux et variés permettent de montrer la compétitivité de nos algorithmes en comparaison avec les autres stratégies existantes. / This thesis considers four clique problems: the maximum vertex weight clique problem (MVWCP), the maximum s-plex problem (MsPlex), the maximum balanced biclique problem (MBBP) and the clique partitioning problem (CPP). The first three are generalization and relaxation of the classic maximum clique problem (MCP), while the last problem belongs to a clique grouping problem. These combinatorial problems have numerous practical applications. Given that they all belong to the NP-Hard family, it is computationally difficult to solve them in the general case. For this reason, this thesis is devoted to develop effective algorithms to tackle these challenging problems. Specifically, we propose two restart tabu search algorithms based on a generalized PUSH operator for MVWCP, a frequency driven local search algorithms for MsPlex, a graph reduction based tabu search as well as effective exact branch and bound algorithms for MBBP and lastly, a three phase local search algorithm for CPP. In addition to the design of efficient move operators for local search algorithms, we also integrate components like graph reduction or upper bound propagation in order to deal deal with very large real-life networks. The experimental tests on a wide range of instances show that our algorithms compete favorably with the main state-of-the-art algorithms.

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

Les systèmes de vélos en libre-service sont devenus des éléments indispensables dans les offres de transport urbain des grandes villes mondiales. À partir des données que ces systèmes génèrent, il est possible d'avoir une caractérisation fine de l'utilisation du vélo en milieu urbain, tant sur des problématiques traitant du domaine des transports que des aspects socio-économiques. Comme pour de nombreux domaines profitant de la récente abondance en données permises par les technologies actuelles de communication et de stockage de l'information, les enjeux actuels résident dans le développement de méthodes d'analyse de données efficaces et adaptées aux systèmes étudiés. Cette thèse se propose de répondre à cette problématique, à la fois par des développements méthodologiques et par une application à des données réelles issues du système de vélos en libre-service Vélo'v à Lyon.Le système Vélo'v peut se représenter sous la forme d'un réseau, décrivant un ensemble de relations entre les différentes stations. Cette représentation, valable également pour de nombreux systèmes, permet l'utilisation d'outils pour décrire la structure du réseau basés sur la théorie des graphes. Néanmoins, la prise en compte d'une dynamique temporelle dans l'évolution des systèmes nécessite d'étendre l'analyse à des réseaux temporels, dont la structure évolue au cours du temps. Le parallèle avec le domaine du traitement du signal, dont le but est l'analyse de signaux temporels, amène à considérer des connexions entre la description de l'évolution d'un réseau temporel et celle d'un signal. Ces travaux proposent de considérer une dualité entre les réseaux temporels et les signaux, de sorte que l'analyse dans le domaine des signaux, à l'aide des outils du traitement du signal, permet de caractériser le réseau temporel correspondant.Cette méthodologie, à la frontière entre le traitement du signal et l'analyse des réseaux, est tout d'abord justifiée par l'étude du système Vélo'v, en comparant différentes approches d'analyse de données et les apports de la représentation sous la forme de réseau temporel. Une méthode d'étiquetage des noeuds d'un graphe est ensuite discutée, permettant d'ouvrir la voie vers une dualité entre réseaux et signaux. Cette dualité est étendue aux réseaux temporels, pour lesquels une méthode d'extraction automatique des structures pertinentes au cours du temps est proposée, à travers la décomposition des signaux correspondants. / Bike-sharing systems have become essential elements in urban transportation systems of many world's big cities. Thanks to the data generated by these systems, it is possible to obtain a precise characterization of urban cycling, both in terms of transportation and socio-economic aspects. Taking advantage of the recent abundance of data allowed by the current technology, the challenges lie in the development of efficient data analysis method, adapted to these systems. This PhD thesis proposes some answers to this issue, first by methodological developments and second by studying real-world data obtained from the bike-sharing system in Lyon, called Vélo'v.The Vélo'v system can be represented as a network, describing a set of relations between the stations spread over the city. This representation, used for many systems, enables the use of tools from network theory to measure the network structure and understand the underlying mechanisms. Nevertheless, taking into account the dynamic evolution of the structure requires an extension of the classical tools to the temporal case. Parallels between this problem and the field of signal processing can be done, and opens the way to the consideration of connections between the description of the dynamics of temporal networks and those of signals. This work introduces a duality between temporal networks and signals, such that the analysis of the signals using the classical tools of signal processing helps to the characterization of the structure of the corresponding network.This methodology, at the juncture between signal processing and network analysis, is first justified by the study of the Vélo'v network, by comparing different data analysis method and the representation of the system as a temporal network. Then, a method to relabel the vertices of the graph according to the topology of the network is discussed, opening up a duality between networks and signals. This duality is then extended to temporal networks: The analysis of the spectral properties of the signals are studied through a fully automated extraction method, enabling the decomposition of relevant network structure over time.

L'objectif de cette thèse de doctorat est (i) d'étudier et de développer des méthodes d’analyse et de commande de systèmes de contrôle en réseau linéaires et non linéaires et (ii) de montrer le potentiel de ces approches dans des applications complexes pertinentes. À cet égard, la théorie des systèmes à plusieurs agents, la théorie des graphes algébriques et le consensus sont des outils méthodologiques les plus intéressants. Une attention particulière est accordée à la caractérisation des relations entre, d'une part, la topologie du graphe de communication qui sous-tend l'évolution du système à plusieurs agents considéré et, d'autre part, les propriétés spectrales de la matrice Laplacienne associée au graphe lui-même. Le contrôle d'un groupe d'agents autonomes est étudié sous différents angles. Le principal objectif de contrôle est de s’assurer que les agents travaillent ensemble de manière coopérative, où la coopération représente la relation étroite entre tous les agents de l'équipe, le partage de l'information jouant un rôle important. En particulier, beaucoup de problèmes de consensus/accord/ synchronisation /rendez-vous sont étudiés afin de guider un groupe d’agents vers un état commun. Le consensus est étudié dans un contexte à temps discret parce que la dynamique du système est en général continue alors que les mesures et les entrées de contrôle sont des données échantillonnées. En outre, la théorie des jeux est utilisée pour faire face aux problèmes de coordination distribués à plusieurs agents, avec une application aux réseaux connus sous le nom de Software Defined Networks. À cet égard, on peut montrer que, sous des protocoles correctement conçus, les joueurs convergent vers un équilibre unique de Wardrop. On concentre l’attention sur le contrôle distribué, car cette approche présente des avantages évidents par rapport à la centralisation, comme l'évolutivité et la robustesse. Pourtant, le contrôle distribué a également ses propres inconvénients : avant tout, un inconvénient est que chaque agent ne peut pas prédire efficacement le comportement global du groupe en se basant uniquement sur des informations locales. Une certaine attention est également accordée à la nécessité de sécuriser les réseaux électriques contre le danger des attaques cyber-physiques grâce au développement de technologies d'intelligence distribuée. À cet égard, sur la base de topologies de réseaux d'énergie réalistes, nous présentons brièvement la conception d'un schéma de protection contre les attaques dynamiques à un point et à points multiples en boucle fermée. Nous formulons et résolvons un problème d'optimisation non convexe soumis à une contrainte de stabilité de Lyapunov pour la représentation à plusieurs agents autonome d'un réseau électrique obtenue après la linéarisation et l'application des lois d’attaque et de contrôle de fréquence. Finalement, nous présentons des résultats obtenus sur : le pilotage exact de la dynamique non linéaire finie à données échantillonnées avec des retards sur les entrées, au sujet de la stabilisation à données échantillonnées et de la poursuite de l'orbite quasi-halo autour du point de libration translunaire L₂, et au sujet des algorithmes heuristiques basés sur des méthodes d'apprentissage par renforcement à plusieurs agents capables d'effectuer un contrôle adaptatif optimal de qualité de service / qualité de l’expérience dans des scénarios sans modèle. / The objective of this PhD thesis is (i) to investigate and develop methods for the analysis and design of linear and nonlinear networked control systems and (ii) to show the potential of such approaches in relevant complex applications. In this respect, multi-agent systems theory, algebraic graph theory and consensus are the most interesting methodological tools, and specific attention is paid to the characterization of the relationships between, on the one hand, the topology of the communication graph that underlies the evolution of the considered multiagent system and, on the other hand, the spectral properties of the Laplacian matrix associated with the graph itself. The control of a group of autonomous agents is investigated from different perspectives. The main control objective is to make sure that the agents work together in a cooperative fashion, where cooperation accounts for the close relationship among all agents in the team, with information sharing playing an important role. In particular, various problems regarding consensus/agreement/synchronization/rendezvous are investigated with the specific aim of driving a group of agents to some common state. Consensus is investigated in a discrete-time setting due to the fact that the system dynamics is normally continuous while the measurements and control inputs might only be made in a sampled-data setting. Moreover, game theory is relied upon in order to cope with distributed multi-agent coordination problems, with application to Software Defined Networks. In this respect, it can be shown that, under properly designed protocols, the players converge to a unique Wardrop equilibrium. We focus on distributed control, since this approach shows obvious benefits over centralization, such as scalability and robustness. Yet, it also has its own drawbacks: among all, one drawback is that each agent cannot effectively predict the overall group behaviour based on only local information. Some attention is also devoted to the need for securing power grids against the danger of cyber-physical attacks through the development of distributed intelligence technologies accompanied by appropriate security enforcements. In this respect, based on realistic power network topologies, we briefly present the design of a protection scheme against closed-loop single-point and multi-point dynamic load altering attacks. This is done by formulating and solving a non-convex optimization problem subject to a Lyapunov stability constraint for the autonomous multiagent representation of a power system obtained after linearization and application of the attack and frequency control laws. Eventually, we show some other results achieved in terms of the exact steeering of finite sampled nonlinear dynamics with input delays, of sampled-data stabilization and quasi-halo orbit following around the L₂ translunar libration point, and of heuristic algorithms based on multi-agent reinforcement learning methods capable of performing optimal adaptive Quality of Service/Quality of Experience control in model-free scenarios.

Dans cette étude, nous produisons une analyse des réseaux de transport publics (acronyme PTN en anglais) en combinant des outils de la théorie des réseaux complexes, des simulations numériques et des approches analytiques. Nous avons commencé par une analyse empirique des PTN de 14 villes importantes dans le monde et en avons déterminé les principales caractéristiques en termes de réseaux complexes. Cette apporche empirique montre que les PTN apparaissent comme des réseaux ("small world") fortement corrélés avec des "coefficients d'agrégation" élevés et des "distances les plus courtes moyennes" comparativement faibles. Nous avons ensuite introduit divers modèles de PTN à 1 et 2 dimensions. Le modèle de marches aléatoires auto-évitantes (SAW) en interactions mutuelles capture certaines des propriété statistiques des PTN dans les divers modes de représentation. Nous avons poursuivi cette étude en examinant la résistance des PTN à divers scénarios d'attaques, ce qui permet de définir des critères de robustesse des réseaux considérés.