To see the other types of publications on this topic, follow the link: Dynamiques de graphes.
Dissertations / Theses on the topic 'Dynamiques de graphes'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 50 dissertations / theses for your research on the topic 'Dynamiques de graphes.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Browse dissertations / theses on a wide variety of disciplines and organise your bibliography correctly.
1
Crespelle, Christophe. "Représentations dynamiques de graphes." Phd thesis, Université Montpellier II - Sciences et Techniques du Languedoc, 2007. http://tel.archives-ouvertes.fr/tel-00402838.
Full textAbstract:
Ce travail de thèse traite du maintien dynamique de représentations géométriques de graphes. Le manuscrit met en avant des connexions fortes entre trois types de représentation de graphes : les décompositions de graphes, les modèles géométriques et les représentations arborescentes à degrés de liberté (PQ-arbres, PC-arbres et autres structures du même type). De nouvelles relations entre ces objets sont mises en évidence et d'autres déjà connues sont approfondies. Notamment, il est établi une équivalence mathématique et algorithmique entre la décomposition modulaire des graphes d'intervalles et le PQ-arbre de leurs cliques maximales.<br /><br />Les connexions entre les trois types de représentation précités sont exploitées pour la conception d'algorithmes de reconnaissance entièrement dynamiques pour les cographes orientés, les graphes de permutation et les graphes d'intervalles. Pour les cographes orientés, l'algorithme présenté est de complexité optimale, il traite les modifications de sommet en temps O(d), où d est le degré du sommet en question, et les modifications d'arête en temps constant. Les algorithmes pour les graphes de permutation et les graphes d'intervalles ont la même complexité : les modifications d'arête et de sommet sont traitées en temps O(n), où n est le nombre de sommets du graphe. Une des contributions du mémoire est de mettre en lumière des similarités très fortes entre les opérations d'ajout d'un sommet dans un graphe de permutation et dans un graphe d'intervalles. <br />L'approche mise en oeuvre dans ce mémoire est assez générale pour laisser entrevoir les mêmes possibilités algorithmiques pour d'autres classes de graphes définies géométriquement.
2
Duvignau, Romaric. "Maintenance et simulation de graphes aléatoires dynamiques." Thesis, Bordeaux, 2015. http://www.theses.fr/2015BORD0177/document.
Full textAbstract:
Nous étudions le problème de maintenir une distribution donnée de graphes aléatoires après une séquence arbitraire d’insertions et de suppressions de sommets. Dans l’objectif de modéliser l’évolution de réseaux logiques dynamiques,nous travaillons dans un modèle local où l’accès à la liste des sommets est restreint. À la place, nous faisons l’hypothèse d’un accès à une primitive globale qui retourne un sommet aléatoire, choisi uniformément dans l’ensemble total des sommets. Le problème de maintenance a été exploré sur plusieurs modèles simples de graphes aléatoires (graphes d’Erdos–Rényi, graphes basés sur le modèle par paires, graphes k-sortants uniformes). Pour chacun des modèles, un ou plusieurs algorithmes pour la tâche de maintenance ont été décris et analysés ; les plus élaborés de ces algorithmes sont asymptotiquement optimaux. Le problème de maintenance soulève plusieurs problèmes de simulation liés à notre contexte distribué. Nous nous sommes intéressé en particulier à la maintenabilité de distributions de graphes et à la simulabilité de familles de distributions de probabilité sur les entiers, dans le modèle d’aléa présenté.Une attention particulière a été portée sur la simulation efficace de lois spécifiques nous intéressant (certaines lois binomiales). Cette dernière a pu être obtenue en exploitant les propriétés d’un nouvel arbre de génération pour les permutations, que nous avons introduit<br>We study the problem of maintaining a given distribution of randomgraphs under an arbitrary sequence of vertex insertions and deletions. Keeping inmind our objective to model the evolution of dynamic logical networks, we work ina local model where we do not have direct access to the list of all vertices. Instead,we assume access to a global primitive that returns a random vertex, chosen uniformlyfrom the whole vertex set. The maintenance problem has been explored onseveral simple random graph models (Erdos–Rényi random graphs, pairing modelbased random graphs, uniform k-out graphs). For each model, one or several updatealgorithms for the maintenance task have been described and analyzed ; the mostelaborate of them are asymptically optimal. The maintenance task rise several simulationissues linked to our distributed context. In particular, we have focused onmaintenability of random graph distributions and simulability of families of probabilitydistributions over integers in our local random model. Special attention hasbeen paid to efficient simulation of particular distributions we were interested in(certain binomial distributions). The latter has been obtained through the use ofproperties of a new generation tree for permutations, which has been introducedalong the way
3
Vernet, Mathilde. "Modèles et algorithmes pour les graphes dynamiques." Thesis, Normandie, 2020. http://www.theses.fr/2020NORMLH12.
Full textAbstract:
Les problèmes de graphes ont été largement étudiés dans le cas des graphes statiques. Cependant, ces graphes ne permettent pas de prendre en compte la dimension temporelle, qui est souvent une donnée importante pour les situations à modéliser. Les graphes dynamiques viennent combler ces lacunes en permettant de modéliser des évolutions dans le temps. On peut alors s'interroger sur ces mêmes problèmes de graphes dans un contexte dynamique. Cela passe d'abord par la définition du modèle de graphes dynamiques le plus approprié et la modélisation précise du problème sur ces graphes. Lorsque le problème ne peut pas être résolu efficacement en appliquant directement des méthodes connues sur les graphes statiques, il faut alors concevoir un algorithme de résolution spécifique aux graphes dynamiques et l'analyser théoriquement et expérimentalement.En suivant cette démarche, l'objectif de cette thèse est de s'interroger sur l'extension aux graphes dynamiques des problèmes bien connus sur les graphes statiques. Ce travail s'intéresse à plusieurs problèmes de graphes en contexte dynamique en se focalisant sur les aspects algorithmiques et en s'abstrayant des domaines d'applications<br>Graph problems have been widely studied in the case of static graphs. However, these graphs do not allow a time dimension to be considered, even though time is an important variable for the situations to model. Dynamic graphs make it possible to model evolution over time. This is a reason to wonder about graph problems in a dynamic context. First, it is necessary to define the most appropriate dynamic graphs model and the precise problem on those graphs. When the problem cannot be efficiently solved directly using known static graph methods, an algorithm specific to dynamic graphs must be designed and analyzed theoretically and practically.With that approach, this thesis' objective is to study graph problems' extensions to dynamic graphs. This works deals with several graph problems in a dynamic context by focusing on algorithmic aspects and without considering application domains
4
Wade, Ahmed mouhamadou. "Complexité de l'exploration par agent mobile des graphes dynamiques." Thesis, Bordeaux, 2014. http://www.theses.fr/2014BORD0484/document.
Full textAbstract:
Cette thèse porte sur l’étude de la complexité de l’exploration de graphes dynamiquespar agent mobile. Une entité mobile (appelée agent) se déplaçant dans un graphe dynamiquedoit traverser/visiter au moins une fois chacun de ses sommets. (Le tempsde traversée d’une arête est unitaire.) Ce problème fondamental en algorithmique paragents mobiles a été très étudié dans les graphes statiques depuis l’article originel deClaude Shannon. Concernant les graphes dynamiques, seul le cas des graphes dynamiquespériodiques a été étudié. Nous étudions ce problème dans deux familles degraphes dynamiques, les graphes dynamiques périodiquement variables (PV-graphes)et les graphes dynamiques T-intervalle-connexes. Les résultats obtenus dans cette thèseaméliorent des résultats existants et donnent des bornes optimales sur le problèmeétudié<br>In this thesis, we study the complexity of the problem of exploration by a mobileagent in dynamic graphs. A mobile entity (called agent) moving in a dynamic graph hasto traverse/visit each of its vertices at least once. This fundamental problem in computatingby mobile agents has been well-studied in static graphs since the original paper ofClaude Shannon. However, for highly dynamic graphs, only the case of periodic dynamicgraphs has been studied. We study this problem in two families of dynamic graphs,periodically-varying graphs (PV-graphs) and T-interval-connected dynamic graphs. Theobtained results improve the existing results and give optimal bounds on the studiedproblems
5
Durbec, Amélia. "Dynamiques causales de graphes réversibles et quantiques." Electronic Thesis or Diss., Aix-Marseille, 2022. http://www.theses.fr/2022AIXM0459.
Full textAbstract:
Les dynamiques causales de graphes sont une double extension des automates cellulaires : la grille sous-jacente est étendue à un graphe arbitraire de degré borné et le graphe lui-même peut évoluer dans le temps.Dans le régime réversible, nous prouvons qu’une dynamique causale de graphes peut être réversible tout en créant/détruisant des sommets, à travers trois différents modèles, que nous prouvons équivalents.En s'appuyant sur ces résultats, nous exhibons des dynamiques causales à la fois réversibles et croissantes en espace, ce qui apporte un nouveau regard sur la compatibilité entre la flèche du temps et la réversibilité. Nous définissons une notion de \subshift de graphes, qui peut être utilisée pour étudier les dynamiques causales de graphes en unifiant les dimensions temporelles et spatiales, de la même manière que les automates cellulaires 1D peuvent être étudiés par des \subshifts de type fini 2D.Dans le régime quantique, notre première contribution est de fournir une définition rigoureuse de l'espace d'état. Une question notable était de savoir si les noms des sommets sont nécessaires; nous prouvons que c'est le cas afin d'empêcher une propagation de l'information plus rapide que la lumière. Nous soulignons également que les renommages sur les graphes sont l'analogue nativement discret des changements de coordonnées<br>Causal graph dynamics are a twofold extension of cellular automata: the underlying grid is extended to an arbitrary graph of bounded degree and the graph itself can evolve in time.In the reversible regime, we prove that causal graph dynamics can be reversible while creating/destroying vertices, through three different models that we prove to be equivalent.Based on these results, we exhibit causal dynamics that are both reversible and increasing in space, which brings new insights into the compatibility between the time arrow and reversibility. We define a notion of graph subshifts, which can be used to study causal dynamics of graphs by unifying temporal and spatial dimensions, in the same way that 1D cellular automata can be studied with 2D subshifts of finite type.In the quantum regime, our first contribution is to provide a rigorous definition of state space. A notable question was whether vertex names are necessary; we prove they are indeed necessary in order to prevent faster-than-light signaling. We also point out that renaming on graphs is the natively discrete analog of coordinate changes
6
Maag, Maria Coralia Laura. "Apprentissage automatique de fonctions d'anonymisation pour les graphes et les graphes dynamiques." Thesis, Paris 6, 2015. http://www.theses.fr/2015PA066050/document.
Full textAbstract:
La confidentialité des données est un problème majeur qui doit être considéré avant de rendre publiques les données ou avant de les transmettre à des partenaires tiers avec comme but d'analyser ou de calculer des statistiques sur ces données. Leur confidentialité est principalement préservée en utilisant des techniques d'anonymisation. Dans ce contexte, un nombre important de techniques d'anonymisation a été proposé dans la littérature. Cependant, des méthodes génériques capables de s'adapter à des situations variées sont souhaitables. Nous adressons le problème de la confidentialité des données représentées sous forme de graphe, données qui nécessitent, pour différentes raisons, d'être rendues publiques. Nous considérons que l'anonymiseur n'a pas accès aux méthodes utilisées pour analyser les données. Une méthodologie générique est proposée basée sur des techniques d'apprentissage artificiel afin d'obtenir directement une fonction d'anonymisation et d'optimiser la balance entre le risque pour la confidentialité et la perte dans l'utilité des données. La méthodologie permet d'obtenir une bonne procédure d'anonymisation pour une large catégorie d'attaques et des caractéristiques à préserver dans un ensemble de données. La méthodologie est instanciée pour des graphes simples et des graphes dynamiques avec une composante temporelle. La méthodologie a été expérimentée avec succès sur des ensembles de données provenant de Twitter, Enron ou Amazon. Les résultats sont comparés avec des méthodes de référence et il est montré que la méthodologie proposée est générique et peut s'adapter automatiquement à différents contextes d'anonymisation<br>Data privacy is a major problem that has to be considered before releasing datasets to the public or even to a partner company that would compute statistics or make a deep analysis of these data. Privacy is insured by performing data anonymization as required by legislation. In this context, many different anonymization techniques have been proposed in the literature. These techniques are difficult to use in a general context where attacks can be of different types, and where measures are not known to the anonymizer. Generic methods able to adapt to different situations become desirable. We are addressing the problem of privacy related to graph data which needs, for different reasons, to be publicly made available. This corresponds to the anonymized graph data publishing problem. We are placing from the perspective of an anonymizer not having access to the methods used to analyze the data. A generic methodology is proposed based on machine learning to obtain directly an anonymization function from a set of training data so as to optimize a tradeoff between privacy risk and utility loss. The method thus allows one to get a good anonymization procedure for any kind of attacks, and any characteristic in a given set. The methodology is instantiated for simple graphs and complex timestamped graphs. A tool has been developed implementing the method and has been experimented with success on real anonymized datasets coming from Twitter, Enron or Amazon. Results are compared with baseline and it is showed that the proposed method is generic and can automatically adapt itself to different anonymization contexts
7
Maag, Maria Coralia Laura. "Apprentissage automatique de fonctions d'anonymisation pour les graphes et les graphes dynamiques." Electronic Thesis or Diss., Paris 6, 2015. http://www.theses.fr/2015PA066050.
Full textAbstract:
La confidentialité des données est un problème majeur qui doit être considéré avant de rendre publiques les données ou avant de les transmettre à des partenaires tiers avec comme but d'analyser ou de calculer des statistiques sur ces données. Leur confidentialité est principalement préservée en utilisant des techniques d'anonymisation. Dans ce contexte, un nombre important de techniques d'anonymisation a été proposé dans la littérature. Cependant, des méthodes génériques capables de s'adapter à des situations variées sont souhaitables. Nous adressons le problème de la confidentialité des données représentées sous forme de graphe, données qui nécessitent, pour différentes raisons, d'être rendues publiques. Nous considérons que l'anonymiseur n'a pas accès aux méthodes utilisées pour analyser les données. Une méthodologie générique est proposée basée sur des techniques d'apprentissage artificiel afin d'obtenir directement une fonction d'anonymisation et d'optimiser la balance entre le risque pour la confidentialité et la perte dans l'utilité des données. La méthodologie permet d'obtenir une bonne procédure d'anonymisation pour une large catégorie d'attaques et des caractéristiques à préserver dans un ensemble de données. La méthodologie est instanciée pour des graphes simples et des graphes dynamiques avec une composante temporelle. La méthodologie a été expérimentée avec succès sur des ensembles de données provenant de Twitter, Enron ou Amazon. Les résultats sont comparés avec des méthodes de référence et il est montré que la méthodologie proposée est générique et peut s'adapter automatiquement à différents contextes d'anonymisation<br>Data privacy is a major problem that has to be considered before releasing datasets to the public or even to a partner company that would compute statistics or make a deep analysis of these data. Privacy is insured by performing data anonymization as required by legislation. In this context, many different anonymization techniques have been proposed in the literature. These techniques are difficult to use in a general context where attacks can be of different types, and where measures are not known to the anonymizer. Generic methods able to adapt to different situations become desirable. We are addressing the problem of privacy related to graph data which needs, for different reasons, to be publicly made available. This corresponds to the anonymized graph data publishing problem. We are placing from the perspective of an anonymizer not having access to the methods used to analyze the data. A generic methodology is proposed based on machine learning to obtain directly an anonymization function from a set of training data so as to optimize a tradeoff between privacy risk and utility loss. The method thus allows one to get a good anonymization procedure for any kind of attacks, and any characteristic in a given set. The methodology is instantiated for simple graphs and complex timestamped graphs. A tool has been developed implementing the method and has been experimented with success on real anonymized datasets coming from Twitter, Enron or Amazon. Results are compared with baseline and it is showed that the proposed method is generic and can automatically adapt itself to different anonymization contexts
8
Martiel, Simon. "Approches informatique et mathématique des dynamiques causales de graphes." Thesis, Nice, 2015. http://www.theses.fr/2015NICE4043/document.
Full textAbstract:
Le modèle des automates cellulaires constitue un des modèles le mieux établi de physique discrète sur espace euclidien. Ils implantent trois symétries fondamentales de la physique: la causalité, l'homogénéité et la densité finie de l'information. Bien que l'origine des automates cellulaires provienne de la physique, leur utilisation est très répandue comme modèles de calcul distribué dans l'espace (machines auto-réplicantes, problèmes de synchronisation,...), ou bien comme modèles de systèmes multi-agents (congestion du trafic routier, études démographiques,...). Bien qu'ils soient parmi les modèles de calcul distribué les plus étudiés, la rigidité de leur structure interdit toute extension triviale vers un modèle de topologie variant dans le temps, qui se trouve être un prérequis fondamental à la modélisation de certains phénomènes biologiques, sociaux ou physiques, comme par exemple la discrétisation de la relativité générale. Les dynamiques causales de graphes généralisent les automates cellulaires aux graphes arbitraires de degré borné et pouvant varier dans le temps. Dans cette thèse, nous nous attacherons à généraliser certains des résultats fondamentaux de la théorie des automates cellulaires. En munissant nos graphes d'une métrique compacte, nous présenterons deux approches différentes du modèle. Une première approche axiomatique basée sur les notions de continuité et d'invariance par translation, et une deuxième approche constructive, où une règle locale est appliquée en parallèle et de manière synchrone sur l'ensemble des sommets du graphe<br>Cellular Automata constitute one of the most established model of discrete physical transformations that accounts for euclidean space. They implement three fundamental symmetries of physics: causality, homogeneity and finite density of information. Even though their origins lies in physics, they are widely used to model spatially distributed computation (self-replicating machines, synchronization problems,...), as well as a great variety of multi-agents phenomena (traffic jams, demographics,...). While being one of the most studied model of distributed computation, their rigidity forbids any trivial extension toward time-varying topology, which is a fundamental requirement when it comes to modelling phenomena in biology, sociology or physics: for instance when looking for a discrete formulation of general relativity. Causal graph dynamics generalize cellular automata to arbitrary, bounded degree, time-varying graphs. In this work, we generalize the fundamental structure results of cellular automata for this type of transformations. We endow our graphs with a compact metric space structure, and follow two approaches. An axiomatic approach based on the notions of continuity and shift-invariance, and a constructive approach, where a local rule is applied synchronously on every vertex of the graph. Compactness allows us to show the equivalence of these two definitions, extending the famous result of Curtis-Hedlund-Lyndon’s theorem. Another physics-inspired symmetry is then added to the model, namely reversibility
9
Boria, Nicolas. "Optimisation combinatoire et environnements dynamiques." Paris 9, 2011. http://basepub.dauphine.fr/xmlui/handle/123456789/7232.
Full text
10
Neggaz, Mohammed Yessin. "Automatic classification of dynamic graphs." Thesis, Bordeaux, 2016. http://www.theses.fr/2016BORD0169/document.
Full textAbstract:
Les réseaux dynamiques sont constitués d’entités établissant des contacts les unes avec les autres dans le temps. Un défi majeur dans les réseaux dynamiques est de prédire les modèles de mobilité et de décider si l’évolution de la topologie satisfait aux exigences du succès d’un algorithme donné. Les types de dynamique résultant de ces réseaux sont variés en échelle et en nature. Par exemple,certains de ces réseaux restent connexes tout le temps; d’autres sont toujours déconnectés mais offrent toujours une sorte de connexité dans le temps et dans l’espace(connexité temporelle); d’autres sont connexes de manière récurrente, périodique,etc. Tous ces contextes peuvent être représentés sous forme de classes de graphes dynamiques correspondant à des conditions nécessaires et/ou suffisantes pour des problèmes ou algorithmes distribués donnés. Étant donné un graphe dynamique,une question naturelle est de savoir à quelles classes appartient ce graphe. Dans ce travail, nous apportons une contribution à l’automatisation de la classification de graphes dynamiques. Nous proposons des stratégies pour tester l’appartenance d’un graphe dynamique à une classe donnée et nous définissons un cadre générique pour le test de propriétés dans les graphes dynamiques. Nous explorons également le cas où aucune propriété sur le graphe n’est garantie, à travers l’étude du problème de maintien d’une forêt d’arbres couvrants dans un graphe dynamique<br>Dynamic networks consist of entities making contact over time with one another. A major challenge in dynamic networks is to predict mobility patterns and decide whether the evolution of the topology satisfies requirements for the successof a given algorithm. The types of dynamics resulting from these networks are varied in scale and nature. For instance, some of these networks remain connected at all times; others are always disconnected but still offer some kind of connectivity over time and space (temporal connectivity); others are recurrently connected,periodic, etc. All of these contexts can be represented as dynamic graph classes corresponding to necessary or sufficient conditions for given distributed problems or algorithms. Given a dynamic graph, a natural question to ask is to which of the classes this graph belongs. In this work we provide a contribution to the automation of dynamic graphs classification. We provide strategies for testing membership of a dynamic graph to a given class and a generic framework to test properties in dynamic graphs. We also attempt to understand what can still be done in a context where no property on the graph is guaranteed through the distributed problem of maintaining a spanning forest in highly dynamic graphs
11
Gautero, François. "CW-complexes dynamiques." Nice, 1998. http://www.theses.fr/1998NICE5137.
Full textAbstract:
On définit à partir de quelques conditions algébriques simples une classe de CW-complexes, appelés CW-complexes dynamiques. On montre que ces CW-complexes dynamiques ont la propriété de porter un semi-flot non singulier. On donne alors un critère nécessaire et suffisant pour que tout semi-flot dans une classe bien définie admette une section globale. Ce critère est facilement vérifiable en pratique. S'il existe une section globale, le complexe admet un feuilletage en graphes compacts tous homotopiquement équivalents et toute application de retour de tout semi-flot sur une section induit un automorphisme sur le groupe fondamental de la section. Réciproquement si o est un automorphisme quelconque du groupe libre Fn, on établit que le groupe suspension de o est le groupe fondamental d'un CW-complexe dynamique admettant un feuilletage en graphes compacts homotopiquement équivalents, de groupe fondamental isomorphe a Fn et tel que l'automorphisme induit soit conjugue a o dans out(Fn). La construction d'un tel CW-complexe dynamique est combinatoire. On étudie ensuite quelques propriétés topologiques et dynamiques liées a la combinatoire d'un CW-complexe dynamique et on fait notamment le lien avec les surfaces branchées dynamiques de Christy-Williams. Dans le dernier chapitre, on présente un algorithme fini pour la construction d'un template a la birman-williams associe au flot suspension d'un homéomorphisme pseudo-Anosov du disque troué.
12
Eichler, Cédric. "Modélisation formelle de systèmes dynamiques autonomes : graphe, réécriture et grammaire." Thesis, Toulouse 3, 2015. http://www.theses.fr/2015TOU30057/document.
Full textAbstract:
Les systèmes distribués modernes à large-échelle évoluent dans des contextes variables soumis à de nombreux aléas auxquels ils doivent s'adapter dynamiquement. Dans ce cadre, l'informatique autonome se propose de réduire les interventions humaines lentes et coûteuses, en leur préférant l'auto-gestion. Elle repose avant tout sur une description adéquate de ses composants, de leurs interactions et des différents aspects ou topologies qu'il peut adopter. Diverses approches de modélisation ont étés proposées dans la littérature, se concentrant en général sur certains du système dynamique et ne permettent ainsi pas de répondre à chacune des problématiques inhérentes à l'auto-gestion. Cette thèse traite de la modélisation basée graphes des systèmes dynamiques et de son adéquation pour la mise en œuvre des quatre propriétés fondamentales de l'informatique. Elle propose quatre principales contributions théoriques et appliquées. La première est une méthodologie pour la construction et la caractérisation générative de transformations correctes par construction dont l'application préserve nécessairement la correction du système. La seconde contribution consiste en une extension des systèmes de réécriture de graphe permettant de représenter, mettre à jour, évaluer et paramétrer les caractéristiques d'un système aisément et efficacement. Une étude expérimentale extensive révèle un net gain d'efficacité vis à vis de méthodes classiques. Les deux dernières contributions s'articulent autour de l'élaboration de deux modules de gestions visant : (1) des requêtes de traitement d'événements complexes et (2) tout système Machine-à-Machine se conformant au standard ETSI M2M<br>Modern, large-scale systems are deployed in changing environments. They must dynamically adapt to context changes. In this scope, autonomic computing aims at reducing slow and costly human interventions, by building self-managed systems. Self-adaptability of a system is primarily based on a suitable description of its components, their interactions and the various states it can adopt. Various modeling approaches have been elaborated. They usually focus on some aspects or properties of dynamic systems and do not tackle each of self-management's requirements. This manuscript deals with graph-based representations of dynamic systems and their suitability for the implementation of autonomic computing's four fundamental properties : self-optimization, self-protection, self-healing and self-configuring. This thesis offers four principal theoretical and applied contributions. The first one is a methodology for the construction and generative characterization of transformations correct by construction whose application necessarily preserves a system's correctness. The second one consists in an extension of graph rewriting systems allowing to easily and efficiently represent, update, evaluate and configure a system's characteristics. An experimental study reveals a significant efficiency gain with regard to classical methods. The two lasts contribution are articulated around the design of two autonomic managers driving: (1) complex events processing requests and (2) any Machine-to-Machine system complying to the ETSI M2M2 standard
13
Albano, Alice. "Dynamique des graphes de terrain : analyse en temps intrinsèque." Thesis, Paris 6, 2014. http://www.theses.fr/2014PA066260/document.
Full textAbstract:
Nous sommes entourés par une multitude de réseaux d'interactions, issus de contextes très différents. Ces réseaux peuvent être modélisés par des graphes, appelés graphes de terrain. Ils possèdent une structure en communautés, c'est-à-dire en groupes de nœuds très liés entre eux, et peu liés avec les autres. Un phénomène que l'on étudie sur les graphes dans de nombreux contextes est la diffusion. La propagation d'une maladie en est un exemple. Ces phénomènes dépendent d'un paramètre important, mais souvent peu étudié : l'échelle de temps selon laquelle on les observe. Selon l'échelle choisie, la dynamique du graphe peut varier de manière très importante.Dans cette thèse, nous proposons d'étudier des processus dynamiques en utilisant une échelle de temps adaptée. Nous considérons une notion de temps relatif, que nous appelons le temps intrinsèque, par opposition au temps "classique", que nous appelons temps extrinsèque. Nous étudions en premier lieu des phénomènes de diffusion selon une échelle de temps intrinsèque, et nous comparons les résultats obtenus avec une échelle extrinsèque. Ceci nous permet de mettre en évidence le fait qu'un même phénomène observé dans deux échelles de temps différentes puisse présenter un comportement très différent. Nous analysons ensuite la pertinence de l'utilisation du temps intrinsèque pour la détection de communautés dynamiques. Les communautés obtenues selon les échelles de temps extrinsèques et intrinsèques nous montrent qu'une échelle intrinsèque permet la détection de communautés beaucoup plus significatives et détaillées que l'échelle extrinsèque<br>We are surrounded by a multitude of interaction networks from different contexts. These networks can be modeled as graphs, called complex networks. They have a community structure, i.e. groups of nodes closely related to each other and less connected with the rest of the graph. An other phenomenon studied in complex networks in many contexts is diffusion. The spread of a disease is an example of diffusion. These phenomena are dynamic and depend on an important parameter, which is often little studied: the time scale in which they are observed. According to the chosen scale, the graph dynamics can vary significantly. In this thesis, we propose to study dynamic processes using a suitable time scale. We consider a notion of relative time which we call intrinsic time, opposed to "traditional" time, which we call extrinsic time. We first study diffusion phenomena using intrinsic time, and we compare our results with an extrinsic time scale. This allows us to highlight the fact that the same phenomenon observed at two different time scales can have a very different behavior. We then analyze the relevance of the use of intrinsic time scale for detecting dynamic communities. Comparing communities obtained according extrinsic and intrinsic scales shows that the intrinsic time scale allows a more significant detection than extrinsic time scale
14
Albano, Alice. "Dynamique des graphes de terrain : analyse en temps intrinsèque." Electronic Thesis or Diss., Paris 6, 2014. http://www.theses.fr/2014PA066260.
Full textAbstract:
Nous sommes entourés par une multitude de réseaux d'interactions, issus de contextes très différents. Ces réseaux peuvent être modélisés par des graphes, appelés graphes de terrain. Ils possèdent une structure en communautés, c'est-à-dire en groupes de nœuds très liés entre eux, et peu liés avec les autres. Un phénomène que l'on étudie sur les graphes dans de nombreux contextes est la diffusion. La propagation d'une maladie en est un exemple. Ces phénomènes dépendent d'un paramètre important, mais souvent peu étudié : l'échelle de temps selon laquelle on les observe. Selon l'échelle choisie, la dynamique du graphe peut varier de manière très importante.Dans cette thèse, nous proposons d'étudier des processus dynamiques en utilisant une échelle de temps adaptée. Nous considérons une notion de temps relatif, que nous appelons le temps intrinsèque, par opposition au temps "classique", que nous appelons temps extrinsèque. Nous étudions en premier lieu des phénomènes de diffusion selon une échelle de temps intrinsèque, et nous comparons les résultats obtenus avec une échelle extrinsèque. Ceci nous permet de mettre en évidence le fait qu'un même phénomène observé dans deux échelles de temps différentes puisse présenter un comportement très différent. Nous analysons ensuite la pertinence de l'utilisation du temps intrinsèque pour la détection de communautés dynamiques. Les communautés obtenues selon les échelles de temps extrinsèques et intrinsèques nous montrent qu'une échelle intrinsèque permet la détection de communautés beaucoup plus significatives et détaillées que l'échelle extrinsèque<br>We are surrounded by a multitude of interaction networks from different contexts. These networks can be modeled as graphs, called complex networks. They have a community structure, i.e. groups of nodes closely related to each other and less connected with the rest of the graph. An other phenomenon studied in complex networks in many contexts is diffusion. The spread of a disease is an example of diffusion. These phenomena are dynamic and depend on an important parameter, which is often little studied: the time scale in which they are observed. According to the chosen scale, the graph dynamics can vary significantly. In this thesis, we propose to study dynamic processes using a suitable time scale. We consider a notion of relative time which we call intrinsic time, opposed to "traditional" time, which we call extrinsic time. We first study diffusion phenomena using intrinsic time, and we compare our results with an extrinsic time scale. This allows us to highlight the fact that the same phenomenon observed at two different time scales can have a very different behavior. We then analyze the relevance of the use of intrinsic time scale for detecting dynamic communities. Comparing communities obtained according extrinsic and intrinsic scales shows that the intrinsic time scale allows a more significant detection than extrinsic time scale
15
Ouassir, Abdelmajid. "Contribution au diagnostic de systèmes dynamiques par l'utilisation de graphes orientés signés." Compiègne, 1997. http://www.theses.fr/1997COMP1073.
Full textAbstract:
Dans ce mémoire de thèse, nous proposons une étude approfondie d'utilisation de l'approche à base de modèles qualitatifs fondés sur les graphes orientés signés pour le diagnostic de procédés continus. Pour cela nous nous sommes appuyés sur l'analyse de deux approches génériques de conception proposées respectivement, par M. Kramer et ses élèves à la fin des années 80, et par O'Shima et ses collègues à la fin des années 70. Pour chacune, après en avoir exposé les principes et montré certaines de leurs limites, nous avons présenté une nouvelle méthode. Pour ce qui concerne la première approche de conception (Kramer-Palowitch), nous avons rejeté la contrainte d'un seul changement d'état qualitatif des variables, et proposé d'exploiter les relations de causalité de manière locale uniquement. Ces hypothèses ont conduit à une méthode algorithmique qui ne nécessite aucun traitement spécial pour les cycles contenus dans le graphe, contrairement à l'approche proposée par Kramer-Palowitch. La deuxième approche consiste à fournir, en ligne, la ou les causes possibles de la dérive constatée (c'est-à-dire par une succession de symptômes). Ici encore, après avoir présenté les principes de la méthode originale de tri et al. , et montré ses limites, nous avons proposé une nouvelle méthode algorithmique. Celle-ci consiste à transformer le graphe orienté signé de départ en un nouveau graphe orienté signé qui ne contient que des chemins simples de longueur unité entre toutes les causes possibles de dérive prises en compte et toutes les variables mesurées de l'installation. Pour une dérive constatée, cette méthode, qui à chaque symptôme associe un ensemble de causes possibles, permet de suivre dans le temps la persistance, ou la non persistance des causes proposées comme explication<br>In this thesis, an important class of qualitative causal models based on the Signed Directed Graph (SDG) was carried out. The SDG model consists of nodes symbolizing process variables, and signed directed arcs that represent the local cause and effet relationships between variables. Previous work on SDG models has not adequately addressed the role of feedback and complex dynamics. Disturbance propagation is restricted to feedforward path in the SDG and heuristics are applied to account for complex dynamic process behavior arising due to interactions in negative feedback loops. The heuristics are imcomplite as they do not account for all instances of dynamic behavior. In diagnostic applications, these limitations result in unnecessary losses of diagnostic resolution and the production of inaccurate diagnosis. The above limitations are crucial and have in the past reduced the potential applications of diagnostic systems based on SDG models. A rigorous analysis was performed and indicated that disturbance propagation assumptions (simple transition) and heuristics are inadequate, leading to the exclusion of inverse and compensatory response arising from interactions in non-control negative feedback loops in the SDG. On of the recurring concepts developed in this thesis has been the systematic use of "multiple transition" assumption. An algorithmic technique for deriving the knowledge base for online diagnostic reasoning program for continous process was developed. A nouvel feature of the technique is that certain behaviors not apparent from SDG models but result from global process interactions are automatically represented in the diagnostic knowledge base
16
VENET, ARNAUD. "Analyse statique des systemes dynamiques de graphes dans les langages non types." Palaiseau, Ecole polytechnique, 1998. http://www.theses.fr/1998EPXX0073.
Full textAbstract:
Dans cette these nous decrivons des techniques d'interpretation abstraite de programmes manipulant des structures dynamiques de graphes. Nous concentrons notre etude autour de deux problemes importants en analyse statique : la determination automatique des alias de pointeurs dans les langages non types et l'analyse de la topologie des communications dans les systemes de processus mobiles decrits dans le pi-calcul. Ces deux analyses sont originales et permettent d'identifier les elements de structures definies de maniere recursive.
17
Cuenca, Pauta Erick. "Visualisation de données dynamiques et complexes : des séries temporelles hiérarchiques aux graphes multicouches." Thesis, Montpellier, 2018. http://www.theses.fr/2018MONTS054/document.
Full textAbstract:
L'analyse de données de plus en plus complexes, volumineuses et issues de différentes sources (e.g. internet, médias sociaux, etc.) est une tâche difficile. Elle reste cependant cruciale dans de très nombreux domaines d'application. Elle implique, pour pouvoir en extraire des connaissances, de mieux comprendre la nature des données, leur évolution ou les nombreuses relations complexes qu'elles peuvent contenir. La visualisation d'informations s'intéresse aux méthodes de représentations visuelles et interactives permettant d'aider un utilisateur à extraire des connaissances. C'est dans ce contexte que se situe le travail présenté dans ce mémoire. Dans un premier temps, nous nous intéressons à la visualisation de longues séries temporelles hiérarchiques. Après avoir analysé les différentes approches existantes, nous présentons le système MultiStream permettant de visualiser, explorer et comparer l'évolution de séries organisées dans une structure hiérarchique. Nous illustrons son utilisation par deux exemples d'utilisation : émotions exprimées dans des médias sociaux et évolution des genres musicaux. Dans un second temps nous abordons la problématique de données complexes modélisées sous la forme de graphes multicouches (différentes types d'arêtes peuvent relier les n÷uds). Plus particulièrement nous nous intéressons au requêtage visuel de graphes volumineux en présentant VERTIGo un système qui permet de construire des requêtes, d'interroger un moteur spécifique, de visualiser/explorer les résultats à différentes niveaux de détail et de suggérer de nouvelles extensions de requêtes. Nous illustrons son utilisation à l'aide d'un graphe d'auteurs provenant de différentes communautés<br>The analysis of data that is increasingly complex, large and from different sources (e.g. internet, social medias, etc.) is a dificult task. However, it remains crucial for many fields of application. It implies, in order to extract knowledge, to better understand the nature of the data, its evolution or the many complex relationships it may contain. Information visualization is about visual and interactive representation methods to help a user to extract knowledge. The work presented in this document takes place in this context. At first, we are interested in the visualization of large hierarchical time series. After analyzing the different existing approaches, we present the MultiStream system for visualizing, exploring and comparing the evolution of the series organized into a hierarchical structure. We illustrate its use by two examples: emotions expressed in social media and the evolution of musical genres. In a second time, we tackle the problem of complex data modeled in the form of multilayer graphs (different types of edges can connect the nodes). More specifically, we are interested in the visual querying of large graphs and we present VERTIGo, a system which makes it possible to build queries, to launch them on a specific engine, to visualize/explore the results at different levels of details and to suggest new query extensions. We illustrate its use with a graph of co-authors from different communities
18
Ghanem, Abdelmotaal Marwan Tarek. "Les centralités temporelles : étude de l'importance des noeuds dans les réseaux dynamiques." Electronic Thesis or Diss., Sorbonne université, 2018. http://www.theses.fr/2018SORUS086.
Full textAbstract:
De nos jours, les interactions ont une part prépondérante dans notre vie. Ces interactions peuvent représenter la diffusion de rumeurs, de maladies, etc. Comprendre comment ces interactions affectent notre vie est important. Une façon naturelle de faire est d'utiliser la théorie des graphes. Néanmoins, comme le montrent certaines études, l'aspect temporel ne doit pas être négligé. Dans ce travail, nous nous sommes concentrés sur la détection d'individus importants dans ces graphes en utilisant des métriques de centralité qui prennent en compte l'aspect temporel. Nous avons proposé un protocole de comparaison qui compare les différentes mesures de centralité existantes. Nous l'avons appliqué sur plusieurs graphes, ce qui nous a donné un aperçu de la façon dont les différentes métriques agissent. Ensuite, nous avons observé le besoin de calcul élevé de ces métriques de centralité. Dès lors, nous avons introduit une méthode qui réduit ce besoin. Finalement, nous avons introduit une nouvelle mesure de centralité, appelée ego-betweenness centrality<br>Nowadays, interactions are a huge part of our daily life. These interactions can represent the diffusion of rumors, diseases, etc. Understanding how these interactions affect our life is quite important. A natural way to do so is using graph theory. However, this is not straightforward as studies show the temporal aspect, in other words, the order of interactions, should be taken into account. In this work, we concentrated on detecting the important individuals in these graphs using centrality metrics that take into account the temporal aspect. We proposed a comparison protocol that compares the different centrality metrics that exist. We applied it on several networks, which gave us insight on how the different metrics react. Secondly, we observed the high computational need of these centrality metrics. Therefore, we introduced a method to reduce this need. And finally, we introduced a novel centrality metric that we call ego-betweenness centrality
19
Rannou, Léo. "Temporal Connectivity and Path Computation for Stream Graph." Electronic Thesis or Diss., Sorbonne université, 2020. http://www.theses.fr/2020SORUS418.
Full textAbstract:
Les données structurelles et les données temporelles ont, pendant longtemps, été analysées séparément. De nombreux réseaux complexes contiennent une dimension temporelle, comme les contacts entre individus ou les transactions financières. La théorie des graphes fournit un large ensemble d'outils pour modéliser et analyser les connexions entre entités. Malheureusement, cette approche ne prend pas compte la nature temporelle des interactions. La théorie des stream graphs est un formalisme permettant de modéliser les réseaux dynamiques dans lesquels les nœuds et/ou les liens arrivent et/ou partent au fil du temps. Plusieurs concepts théoriques tels que les composantes connexes dans les stream graphs ont été définis récemment, mais aucun algorithme n'a été proposé pour les calculer. De plus, la complexité algorithmique de ces problèmes est inconnue, ainsi que les connaissances qu'ils peuvent apporter sur les stream graphs de terrain. Dans cette thèse, nous proposons plusieurs solutions pour le calcul de notions de connectivité et de chemins dans les stream graphs. Nous présentons également des représentations alternatives - des structures de données conçues pour faciliter certains calculs - stream graphs. Nous fournissons également des implémentations et comparons expérimentalement nos méthodes sur une grande variété de cas pratiques. Nous montrons que ces concepts apportent beaucoup d'informations sur les caractéristiques de ces ensembles de données. Straph, une bibliothèque python, a été développée afin de disposer d'une ressource fiable afin de manipuler, analyser et visualiser les stream graphs<br>For a long time, structured data and temporal data have been analysed separately. Many real world complex networks have a temporal dimension, such as contacts between individuals or financial transactions. Graph theory provides a wide set of tools to model and analyze static connections between entities. Unfortunately, this approach does not take into account the temporal nature of interactions. Stream graph theory is a formalism to model highly dynamic networks in which nodes and/or links arrive and/or leave over time. The number of applications of stream graph theory has risen rapidly, along with the number of theoretical concepts and algorithms to compute them. Several theoretical concepts such as connected components and temporal paths in stream graphs were defined recently, but no algorithm was provided to compute them. Moreover, the algorithmic complexities of these problems are unknown, as well as the insight they may shed on real-world stream graphs of interest. In this thesis, we present several solutions to compute notions of connectivity and path concepts in stream graphs. We also present alternative representations - data structures designed to facilitate specific computations - of stream graphs. We provide implementations and experimentally compare our methods in a wide range of practical cases. We show that these concepts indeed give much insight on features of large-scale datasets. Straph, a python library, was developed in order to have a reliable library for manipulating, analysing and visualising stream graphs, to design algorithms and models, and to rapidly evaluate them
20
Mostefaoui, Mustapha. "Analyse des propriétés temporelles des graphes d'événements valués continus." Nantes, 2001. http://www.theses.fr/2001NANT2100.
Full textAbstract:
Les réseaux de Petri (RdP) sont un formalisme puissant de modélisation et d'évaluation des systèmes dynamiques complexes. Une classe particulière des RdP, que sont les graphes d'événements valués (GdEV) fortement connexes, permet plus particulièrement d'analyser les systèmes cycliques sans conflit structurel. Lorsque la notion de flux apparaît (système fluide, structure à haut débit, etc. ) il est possible d'utiliser un modèle GdEV continu (GdEVC). Le plus souvent, les méthodes d'analyse des propriétés temporelles des RdP continus se basent sur le développement du graphe d'évolution qui représente la dynamique du système. . .
21
Casteigts, Arnaud. "Contribution à l'algorithmique distribuée dans les réseaux mobiles ad hocCalculs locaux et réétiquetages de graphes dynamiques." Bordeaux 1, 2007. http://www.theses.fr/2007BOR13430.
Full textAbstract:
Les réseaux mibiles ad hoc sont par nature instables et imprévisibles. De ces caractéristiques découle la difficulté à concevoir et analyser des algorithmes distribués garantissant certaines propriétés. C'est sur ce point que porte la contribution majeure de cette thèse. Pour amorcer cette étude, nous avons étudié quelques problèmes fondamentaux de l'algorithmique distribuée dans ce type d'environnement. Du fait de la nature de ces réseaux, nous avons considéré des modèles de calculs, où chaque étape ne fait collaborer que des noeuds directement voisins. Nous avons notamment proposé un nouveau cadre d'analyse, combinant réétiquetages de graphes dynamiques et graphes évolutifs (modèle combinatoire pour els réseaux dynamiques). Notre approche permet de caractériser les conditions d'un succès ou d'échec d'un algorithme en fonction de la dynamique du réseau, autrement dit, en fonction de conditions nécessaires et/ou suffisantes sur les graphes évolutifs correspondants. Nous avons également étudié la synchronisation sou-jacente aux calculs, ainsi que la manière dont une application réelle peut reposer sur un algorithme de réétiquetage. Un certain nombre de logiciels ont également été réalisés autour de ces travaux, notamment un simulateur de réétiquetage de graphes dynamiques et un vérificateur de propriétés sur les graphes évolutifs.
22
Ghanem, Abdelmotaal Marwan Tarek. "Les centralités temporelles : étude de l'importance des noeuds dans les réseaux dynamiques." Thesis, Sorbonne université, 2018. http://www.theses.fr/2018SORUS086/document.
Full textAbstract:
De nos jours, les interactions ont une part prépondérante dans notre vie. Ces interactions peuvent représenter la diffusion de rumeurs, de maladies, etc. Comprendre comment ces interactions affectent notre vie est important. Une façon naturelle de faire est d'utiliser la théorie des graphes. Néanmoins, comme le montrent certaines études, l'aspect temporel ne doit pas être négligé. Dans ce travail, nous nous sommes concentrés sur la détection d'individus importants dans ces graphes en utilisant des métriques de centralité qui prennent en compte l'aspect temporel. Nous avons proposé un protocole de comparaison qui compare les différentes mesures de centralité existantes. Nous l'avons appliqué sur plusieurs graphes, ce qui nous a donné un aperçu de la façon dont les différentes métriques agissent. Ensuite, nous avons observé le besoin de calcul élevé de ces métriques de centralité. Dès lors, nous avons introduit une méthode qui réduit ce besoin. Finalement, nous avons introduit une nouvelle mesure de centralité, appelée ego-betweenness centrality<br>Nowadays, interactions are a huge part of our daily life. These interactions can represent the diffusion of rumors, diseases, etc. Understanding how these interactions affect our life is quite important. A natural way to do so is using graph theory. However, this is not straightforward as studies show the temporal aspect, in other words, the order of interactions, should be taken into account. In this work, we concentrated on detecting the important individuals in these graphs using centrality metrics that take into account the temporal aspect. We proposed a comparison protocol that compares the different centrality metrics that exist. We applied it on several networks, which gave us insight on how the different metrics react. Secondly, we observed the high computational need of these centrality metrics. Therefore, we introduced a method to reduce this need. And finally, we introduced a novel centrality metric that we call ego-betweenness centrality
23
Aynaud, Thomas. "Détection de communautés dans les réseaux dynamiques." Paris 6, 2011. http://www.theses.fr/2011PA066438.
Full textAbstract:
La plupart des graphes de terrain ont une structure particulière dans laquelle les noeuds sont organisés suivant des groupes, appelés communautés, avec beaucoup de connexions internes mais peu entre eux. L'identification des communautés apporte un éclairage nouveau sur la structure du graphe et est importante dans de nombreux contextes. Nous allons étudier cette structure dans le cas des réseaux dynamiques afin de comprendre comment évoluent les groupes. Pour cela, nous allons suivre deux approches. La première consiste à suivre des communautés au cours du temps en les détectant à chaque instant et en suivant leur évolution. Bien que très naturelle, cette approche pose de nombreuses questions de stabilité : les algorithmes ont tendance à modifier beaucoup leur résultat même si le réseau change peu. Nous proposerons donc une analyse de l'instabilité de trois algorithmes et une solution à cette instabilité. La deuxième approche consiste à détecter la structure communautaire non pas juste pour un instant mais pour une période donnée. La durée de celle-ci est alors un problème crucial et nous proposons une méthode de décomposition hiérarchique en fenêtres de temps permettant de détecter des structures se répétant. Enfin, nous conclurons par des applications à la détection d'événements sur Internet et la segmentation de vidéos. Nous montrerons que l'on peut détecter des événements en trouvant les moments où la structure change brutalement. Pour la segmentation de vidéos, nous avons aussi eu des problème de stabilité et nous avons développé une méthode plus stable de suivi<br>Most complex networks have a particular structure in which nodes are arranged in groups, called communities, with many internal links but only a few between them. The identification of communities gives insights on the structure of the graph and is important in many contexts. We will study this structure in the case of dynamic networks using two different approaches. The first approach consists in tracking communities over time by detecting them at every timestep and following their evolution. We will see that although very natural, this approach raises many questions of stability: the algorithms tend to change their results a lot even if the network changes only a little. This implies that the observed changes in the communities are in fact related to the algorithm and not to real transformations in network structure. We therefore propose an analysis of the instability of three algorithms and a solution to the instability. The second approach consists in detecting the community structure not just for a moment but for a period of time called the time window. The length of the time window is then a crucial problem and we propose a hierachical time segmentation method in time windows. Moreover, the time windows do not have to be contiguous allowing for example to detect a repeating structure. Finally, we conclude with applications to event detection on the Internet and segmentation of videos. We will show that we can detect events by finding the times when the structure changes abruptly. For the segmentation of videos, we also had stability issues and thus we have developed a more stable tracking and detection algorithm
24
Castets, Mathieu. "Pavages réguliers et modélisation des dynamiques spatiales à base de graphes d'interaction : conception, implémentation, application." Thesis, Montpellier, 2015. http://www.theses.fr/2015MONTS241/document.
Full textAbstract:
La modélisation et la simulation de dynamiques spatiales, en particulier pour l'étude de l'évolution de paysages ou de problématiques environnementales pose la question de l'intégration des différentes formes de représentation de l'espace au sein d'un même modèle. Ocelet est une approche de modélisation de dynamiques spatiales basée sur le concept original de graphe d'interaction. Le graphe porte à la fois la structure d'une relation entre entités d’un modèle et la sémantique décrivant son évolution. Les relations entre entités spatiales sont ici traduites en graphes d'interactions et ce sont ces graphes que l'on fait évoluer lors d'une simulation. Les concepts à la base d'Ocelet peuvent potentiellement manipuler les deux formes de représentation spatiale connues, celle aux contours définis (format vecteur) ou la discrétisation en grille régulière (format raster). Le format vecteur est déjà intégré dans la première version d'Ocelet. L'intégration du format raster et la combinaison des deux restaient à étudier et à réaliser. L'objectif de la thèse est d'abord étudier les problématiques liées à l'intégration des champs continus et leur représentation discrétisée en pavage régulier, à la fois dans le langage Ocelet et dans les concepts sur lesquels il repose. Il a fallu notamment prendre en compte les aspects dynamiques de cette intégration, et d'étudier les transitions entre données géographiques de différentes formes et graphe d'interactions à l'aide de concepts formalisés. Il s'est agi ensuite de réaliser l'implémentation de ces concepts dans la plateforme de modélisation Ocelet, en adaptant à la fois son compilateur et son moteur d'exécution. Enfin, ces nouveaux concepts et outils ont été mis à l'épreuve dans trois cas d'application très différents : deux modèles sur l’île de la Réunion, le premier simulant le ruissellement dans le bassin versant de la Ravine Saint Gilles s'écoulant vers la Côte Ouest de l'île, l’autre simulant la diffusion de plantes invasives dans les plaines des hauts à l'intérieur du Parc National de La Réunion. Le dernier cas décrit la spatialisation d'un modèle de culture et est appliqué ici pour simuler les rendements de cultures céréalières sur l’ensemble de l’Afrique de l’Ouest, dans le contexte d'un système d'alerte précoce de suivi des cultures à l'échelle régionale<br>The modelling and simulation of spatial dynamics, particularly for studying landscape changes or environmental issues, raises the question of integrating different forms of spatial representation within the same model. Ocelet is an approach for modelling spatial dynamics based on the original concept of interaction graph. Such a graph holds both the structure of a relation between entities of a model and the semantics describing its evolution. The relationships between spatial entities are here translated into interaction graphs and these graphs are made to evolve during a simulation. The concepts on which Ocelet is based can potentially handle two known forms of spatial representation: shapes with contours (vector format) or regular grid cells (raster). The vector format is already integrated in the first version of Ocelet. The integration of raster and the combination of the two remained to be studied and carried out. The aim of the thesis is to first study the issues related to the integration of continuous fields and their representation by regular tiling, both in the Ocelet language and the concepts on which it is based. The dynamic aspects of this integration had to be taken into account and transitions between different forms of geographic data and interaction graphs had to be studied in the light of the concepts formalized. The concepts were then implemented in the Ocelet modelling platform, with the adaptation of both its compiler and runtime. Finally, these new concepts and tools were tested in three very different cases: two models on Reunion Island, the first simulating runoff in Ravine Saint Gilles watershed in the West Coast of the island, the other simulating the spread of invasive plants in the high plains inside the Reunion National Park. The last case describes the spatialisation of a crop model and is applied here to simulate the cereal crop yields in West Africa, in the context of an early warning system for regional crop monitoring
25
Hamaci, Samir. "Etude des graphes d'événements temporisés avec multiplieurs dans l'algèbre (min, +)." Angers, 2005. http://www.theses.fr/2005ANGE0021.
Full textAbstract:
Les graphes d'événements temporisés avec multiplieurs forment une sous classe des réseaux de Petri dont le comportement ne peut pas être décrit par des équations linéaires dans l'algèbre (min,+) de par la présence des poids sur les arcs. Ce mémoire est consacré à l'étude des systèmes dynamiques, modélisés par des graphes d'événements temporisés discrets, voire hybrides avec multiplieurs. Nous abordons le problème de la représentation entrée-sortie de ces graphes dans l'algèbre (min,+). Pour pallier le problème de non-linéarité, une approche de modélisation à base d'opérateurs est proposée. La commande en juste-à-temps est calculée pour les graphes d'événements temporisés discrets avec multiplieurs dans un dioïde d'opérateurs. Une extension de cette commande aux graphes d'événements temporisés hybrides avec multiplieurs est présentée. Est abordé ensuite, l'analyse des performances des graphes d'événements temporisés discret avec multiplieurs. Nous proposons deux méthodes de linéarisation de ces graphes, dans le but d'obtenir des représentations linéaires dans l'algèbre (min,+), ceci afin d'appliquer certains résultats de base de la théorie spectrale, habituellement utilisée pour évaluer les performances des graphes d'événements temporisés ordinaires<br>Timed event graphs with multipliers form a subclass of Petri nets whose behavior can not be described by linear equations in (min, +) algebra. This nonlinearity is due to the presence of weights on arcs. This report is devoted to the study of dynamic systems modelled by discrete timed event graphs with multipliers and hybrid timed event graphs with multipliers. We tackle the problem of input-output representation of these graphs, in (min,+) algebra. To mitigate the problem of nonlinearity, an approach of modelling, based on operators, is proposed. A just in time control is calculated for discrete timed event graphs with multipliers. An extension of this control to the hybrid Timed event graphs with multipliers is presented. Then, the performance analysis of timed event graphs with multipliers, is tackled. We propose two linearization methods of these graphs, in the purpose to obtain a linear representation in (min, +) algebra, and to apply some basic results of the spectral theory, usually used to evaluate the performances of ordinary timed event graphs
26
Vimont, Guillaume. "Approximation dynamique de clusters dans un graphe social : méthodes et applications." Thesis, Paris 2, 2019. http://www.theses.fr/2019PA020007.
Full textAbstract:
Nous étudions comment détecter des clusters dans un graphe défini par un flux d’arêtes, sans stocker l'ensemble du graphe. Nous montrons comment détecter de gros clusters de l'ordre de √n dans des graphes qui ont m = O(n log(n)) arêtes, tout en stockant √n.log(n) arêtes. Les graphes sociaux suivent le régime où m satisfait cette condition. Nous étendons notre approche aux graphes dynamiques définis par les arêtes les plus récentes du flux et à plusieurs flux. Nous proposons des méthodes simples et robustes afin de détecter ces clusters de manière approchée.Nous définissons la corrélation de contenu de deux flux ρ(t) par la similarité de Jaccard de leurs clusters, dans les fenêtres au temps t. Nous proposons une méthode simple et efficace pour approcher cette corrélation en ligne et montrons que pour les graphes aléatoires dynamiques qui suivent une loi de puissance, nous pouvons garantir une bonne approximation.Une des applications est l’analyse des flux Twitter. Nous calculons les corrélations de contenu de ces flux en ligne. Nous proposons ensuite une recherche par corrélation où les réponses aux ensembles de mots-clés sont entièrement basées sur les petites corrélations des flux. Les réponses sont ordonnées par les corrélations, et les explications peuvent être tracées avec les clusters stockés<br>We study how to detect clusters in a graph defined by a stream of edges, without storing the entire graph. We show how to detect large clusters in the order of √n in graphs that have m = O(n log(n)) edges, while storing √n.log(n) edges. Social graphs satisfy this condition m. We extend our approach to dynamic graphs defined by the most recent stream of edges and multiple streams. We propose simple and robust methods based on the approximation to detect these clusters.We define the content correlation of two streams ρ(t) is the Jaccard similarity of their clusters in the windows before time t. We propose a simple and efficient method to approach this online correlation and show that for dynamic random graphs that follow a power law, we can guarantee a good approximation.As an applications we follow Twitter streams and compute their content correlations online. We then propose a search by correlation where answers to sets of keywords are entirely based on the small correlations of the streams. Answers are ordered by the correlations, and explanations can be traced with the stored clusters
27
Guennoun, Mohammed Karim. "Architectures dynamiques dans le contexte des applications à base de composants et orientées services." Toulouse 3, 2006. http://www.theses.fr/2006TOU30236.
Full textAbstract:
L'adaptabilité des applications logicielles peut être séparée en deux catégories. La première concerne l'adaptation comportementale appelée aussi adaptation algorithmique. Cette adaptation traite la redéfinition du comportement de l'application et de ses composants et implique, par exemple, l'introduction d'une nouvelle méthode dans l'interface d'un composant ou le changement du protocole d'orchestration qui coordonne un ensemble de services. Nos travaux, que nous classons dans une deuxième catégorie, traitent l'adaptation structurelle et considèrent une reconfiguration au niveau architectural. Ce type de reconfiguration traite l'organisation de l'architecture et consiste, par exemple, à remplacer un composant défaillant par un autre composant qui possède les mêmes fonctionnalités ou rediriger un client d'un service qui ne respecte pas le contrat de QdS vers un service susceptible d'offrir de meilleures garanties. Dans ce mémoire, nous définissons un méta-modèle relatif à la description et la gestion automatique des architectures dynamiques. Les instances des architectures sont décrites par des graphes étendus où les composants (ou les services) sont représentés par des n\oe uds, et les interdépendances (e. G. Les connexions, les relations de contrôle. . . Etc) sont décrites par des arcs. Les styles architecturaux sont spécifiés par des grammaires de graphes étendues. Le méta-modèle admet des descriptions en considérant différents niveaux d'abstraction et offre des mécanismes pour raffiner ou abstraire les descriptions selon des points de vues spécifiques. Il permet, aussi, de décrire le protocole de gestion de l'architecture et de caractériser les propriétés architecturales à préserver pour chaque niveau architectural considéré. Nous avons développé un algorithme de recherche d'homomorphismes de graphes et un algorithme de transformation de graphes pour les grammaires de graphes étendus définis pour notre méta-modèle. L'analyse de complexité des algorithmes ainsi que les résultats expérimentaux obtenus ont permis de conclure à leur efficacité. Une deuxième version des deux algorithmes a été définie profitant de la spécificité du contexte de la transformation de graphes. L'analyse de complexité de ces nouvelles versions donne des résultats encore plus performants pour le passage à l'échelle. .<br>Adaptability for software applications can be separated into two categories. First relates to the behavioral adaptation also called algorithmic adaptation. This adaptation addresses the redefinition of the behavior of the application and its components and implies, for example, adding a new method into the interface of a component or updating the orchestration protocol that coordinates a set of services. Second category, in which we can classify our work, relates to the structural adaptation and implies a reconfiguration at the architectural level. This kind of reconfiguration deals with the organization of the architecture and involve, for instance, the substitution of a failing component by another with same functionalities or the redirection for a customer of a service which does not respect the QoS contract towards a service likely to offer better guarantees. In this thesis, we specify a meta-model relating to the description and the automatic management of dynamic architectures. Architecture instances are described by extended graphs where components (or services) are represented by vertices, and interdependencies (e. G. Connections, relations of control. . . Etc) are described by edges. The architectural styles are specified by extended graph grammars. The meta-model considers descriptions by admitting various abstraction levels and offers mechanisms to either abstract or refine descriptions according to specific points of view. It, also, makes it possible to describe architecture management protocols and to characterize the architectural properties to be preserved for each considered architectural level. We developed an algorithm for graph homomorphisms building and an algorithm for graph transformation in the context of extended graph grammars defined for our meta-model. .
28
Fotsu, Ngwompo Roger. "Contribution au dimensionnement des systèmes sur des critères dynamiques et énergétiques : approche par bond graph." Lyon, INSA, 1997. http://www.theses.fr/1997ISAL0023.
Full textAbstract:
L'objet de ce mémoire est la présentation d'une méthodologie de dimensionnement des systèmes sur' des critères dynamiques et énergétiques. Un cahier des charges étant imposé et une structure choisie pour la chaîne d'actionnement, il s'agit de vérifier que les composants du système sont susceptibles de suivre les dynamiques imposées tout en respectant les contraintes de puissance. L'outil de modélisation adopté est le bond graph pour ses propriétés de représentation des transferts de puissance et des interconnexions entre les éléments d'un système. Les liens entre le dimensionnement et l'inversion des systèmes nous ont conduit à étudier les problèmes d'inversion d'abord par les méthodes classiques. Ensuite, nous proposons des critères d'étude de l'inversibilité et des procédures de construction des modèles inverses par une approche bond graph en utilisant le concept de bicausalité. Quelques analyses structurelles sur le modèle bond graph inverse sont menées en exploitant les propriétés des liens bicausaux. A partir de ces outils théoriques pour la représentation graphique des m9dèles inverses, nous présentons une méthode de vérification de l'adéquation d'un ensemble d'actionnement à des spécifications imposées par un cahier des charges en remontant des sorties de la chaîne aux entrées par étages successifs. L'illustration de la méthode est faite sur la validation des actionneurs d'un manipulateur deux axes et il est ainsi possible d'analyser les causes d'éventuelles saturations ou de détecter les composantes qui imposent les limitations aux performances du système<br>The purpose of this work is to present a methodology to validate the size of a system components for its proper operation based on dynamic and energetic criteria. If some specifications of a desired performance are given and a structure of actuator system is chosen, then the problem considered here is to check that components of the actuator system are able to follow the desired dynamic while satisfying the power constraints. The modelling tool adopted is bond graph for its property of representing power transfer and interconnections between elements of a system. The links between sizing problem and inverse system have led us to study the problem of system inversion firstly using classical theory. We then propose a bond graph based method for invertibility study and a procedure for construction of inverse bond graph using the concept of bicausality. Some structural anal y sis on the inverse bond graph are carried out by exploiting the properties of bicausal bonds. These theoretical tools and the graphic representation of inverse model then allow us to develop a method for verification of the appropriateness of an actuator system to some performance specifications by checking the proper operation of the system at each lev el from the output to the input. For illustration, the proposed method is applied to the validation of a two-link manipulator actuators and it is thus possible to analyse the causes of saturations and to detect components which impose limitations to the performance of the system
29
Frusque, Gaëtan. "Inférence et décomposition modale de réseaux dynamiques en neurosciences." Thesis, Lyon, 2020. http://www.theses.fr/2020LYSEN080.
Full textAbstract:
Les graphes dynamiques permettent de comprendre l'évolution de systèmes complexes qui évoluent dans le temps. Ce type de graphe a récemment fait l'objet d'une attention considérable. Cependant, il n'existe pas de consensus sur les manières d'inférer et d'étudier ces graphes. Dans cette thèse, on propose des méthodes d'analyse de graphes dynamiques spécifiques. Ceux-ci peuvent être vues comme une succession de graphes complets partageant les mêmes nœuds, mais dont les poids associés à chaque lien évoluent dans le temps. Les méthodes proposées peuvent avoir des applications en neurosciences ou dans l'étude des réseaux sociaux comme Twitter et Facebook par exemple. L'enjeu applicatif de cette thèse est l'épilepsie, l'une des maladies neurologiques les plus rependues dans le monde affectant environ 1% de la population.La première partie concerne l'inférence de graphe dynamique à partir de signaux neurophysiologiques. Cette inférence est généralement réalisée à l'aide de mesures de connectivité fonctionnelle permettant d'évaluer la similarité entre deux signaux. La comparaison de ces mesures est donc d'un grand intérêt pour comprendre les caractéristiques des graphes obtenus. On compare alors des mesures de connectivité fonctionnelle impliquant la phase et l'amplitude instantanée des signaux. On s'intéresse en particulier à une mesure nommée Phase-Locking-Value (PLV) qui quantifie la synchronie des phases entre deux signaux. On propose ensuite, afin d'inférer des graphes dynamiques robustes et interprétables, deux nouvelles mesures de PLV conditionnées et régulariséesLa seconde partie présente des méthodes de décomposition de graphes dynamiques. L'objectif est de proposer une méthode semi-automatique afin de caractériser les informations les plus importantes du réseau pathologique de plusieurs crises d'un même patient. Dans un premier temps on considère des crises qui ont des durées et des évolutions temporelles similaires. Une décomposition tensorielle spécifique est alors appliquée. Dans un second temps, on considère des crises qui ont des durées hétérogènes. Plusieurs stratégies sont proposées et comparées. Ce sont des méthodes qui en plus d'extraire les sous-graphes caractéristiques communs à toutes les crises, permettent d'observer leurs profils d'activation temporelle spécifiques à chaque crise. Finalement, on utilise la méthode retenue pour une application clinique. Les décompositions obtenues sont comparées à l'interprétation visuelle du clinicien. Dans l'ensemble, on constate que les sous-graphes extraits correspondent aux régions du cerveau impliquées dans la crise d'épilepsie. De plus l'évolution de l'activation de ces sous-graphes est cohérente avec l'interprétation visuelle<br>Dynamic graphs make it possible to understand the evolution of complex systems evolving over time. This type of graph has recently received considerable attention. However, there is no consensus on how to infer and study these graphs. In this thesis, we propose specific methods for dynamical graph analysis. A dynamical graph can be seen as a succession of complete graphs sharing the same nodes, but with the weights associated with each link changing over time. The proposed methods can have applications in neuroscience or in the study of social networks such as Twitter and Facebook for example. The issue of this thesis is epilepsy, one of the most common neurological diseases in the world affecting around 1% of the population.The first part concerns the inference of dynamical graph from neurophysiological signals. To assess the similarity between each pairs of signals, in order to make the graph, we use measures of functional connectivity. The comparison of these measurements is therefore of great interest to understand the characteristics of the resulting graphs. We then compare functional connectivity measurements involving the instantaneous phase and amplitude of the signals. We are particularly interested in a measure called Phase-Locking-Value (PLV) which quantifies the phase synchrony between two signals. We then propose, in order to infer robust and interpretable dynamic graphs, two new indexes that are conditioned and regularized PLV. The second part concerns tools for dynamical graphs decompositions. The objective is to propose a semi-automatic method in order to characterize the most important patterns in the pathological network from several seizures of the same patient. First, we consider seizures that have similar durations and temporal evolutions. In this case the data can be conveniently represented as a tensor. A specific tensor decomposition is then applied. Secondly, we consider seizures that have heterogeneous durations. Several strategies are proposed and compared. These are methods which, in addition to extracting the characteristic subgraphs common to all the seizures, make it possible to observe their temporal activation profiles specific to each seizures. Finally, the selected method is used for a clinical application. The obtained decompositions are compared to the visual interpretation of the clinician. As a whole, we found that activated subgraphs corresponded to brain regions involved during the course of the seizures and their time course were highly consistent with classical visual interpretation
30
Mezyani, Touria El. "Méthodologie de surveillance des systèmes dynamiques hybrides." Lille 1, 2005. https://pepite-depot.univ-lille.fr/RESTREINT/Th_Num/2005/50376-2005-122.pdf.
Full textAbstract:
De nombreux procédés industriels sont hybrides par nature, ce qui signifie que leur comportement résulte de l'évolution et de l'interaction de variables continues et de variables discrètes. Le comportement dynamique d'un système hybride peut être représenté par une succession de modes. Chaque mode est caractérisé par une modalité de l'état discret, un ensemble de contraintes de type égalité (équations d'état par exemple) et un domaine d'admissibilité ou invariant décrit par un ensemble d'inégalités. Une transition d'un mode vers un autre mode a lieu lorsque certaines conditions logiques sont vérifiées. Les transitions peuvent être provoquées par un événement externe contrôlé ou un événement interne directement lié à l'évolution continue. Le principe général de la surveillance : détection et localisation de défaillances, d'un système dynamique, consiste à comparer l'évolution en ligne du système avec les évolutions prédites à partir d'un modèle établi sous des hypothèses de fonctionnement normal et défaillant. Dans le cadre de ce travail, nous avons choisi le modèle automate hybride comme modèle de référence du SDH. Une classification des défaillances est proposée suivant que celles-ci se manifestent sur la dynamique continue et/ou sur la dynamique discrète. Sur cette base et à partir de l'automate hybride représentant toutes les évolutions physiquement possibles du système, des graphes de prédictions de fonctionnement normal GPFN et des graphes de prédictions de fonctionnement défaillant GPFD sont construits. Ces graphes, directement extraits de l'automate, permettent de représenter les trajectoires hybrides du système en fonctionnement normal et en présence de défaillances. Une méthodologie générale de surveillance est décrite sur la base de la classification des défaillances proposée et des graphes de prédiction. Des tests de cohérence sont effectués de telle sorte que les observations continues et discrètes prélevées en-ligne sur le système soient confrontées avec les évolutions décrites par les GPFN et les GPFD. Les résidus stmcturés, issus des Relations de Redondance Analytiques, sont classiquement utilisés pour la surveillance des systèmes continus. Leur utilisation est étendue pour identifier le mode de fonctionnement courant. Ceci nécessite d'introduire les notions de discernabilité et de similarité entre modes. La méthodologie de surveillance est appliquée sur l'exemple d'un système hydraulique constitué de deux réservoirs connectés.
31
Démare, Thibaut. "Une approche systémique à base d'agents et de graphes dynamiques pour modéliser l'interface logistique port-métropole." Thesis, Le Havre, 2016. http://www.theses.fr/2016LEHA0021/document.
Full textAbstract:
Un système logistique est une composante essentielle d'un système spatial dans lequel les acteurs s'organisent autour d'infrastructures pour faire circuler des flux (de marchandises, d'information et financier) sur un territoire. L'organisation logistique globale résulte d'un processus auto-organisé et distribué de la part des acteurs. Ce travail vise à comprendre, à de multiples échelles, comment des acteurs autonomes et très hétérogènes (dans leurs modes de fonctionnements et dans leurs objectifs), s'organisent collectivement autour des infrastructures à leurs dispositions pour gérer des flux soumis à un ensemble de contraintes (temporelles, spatiales,...). On propose ici un modèle orienté agent permettant de simuler les processus de création et d'organisation des flux liés à la logistique sur un territoire. Le modèle prévoit de décrire l'interface entre les flux internationaux et les flux urbains afin de comprendre comment les dynamiques portuaires et urbaines cohabitent au sein du système. Le modèle intègre une dynamique structurelle et organisationnelle grâce aux graphes dynamiques afin de représenter l'évolution du système. Le modèle permet ainsi aux agents de s'adapter, comme dans la réalité, à des perturbations du système<br>A logistic system is an essential component of a spatial system. Actors are organised around infrastructures in order to move different kinds of flow (of goods, of information, or financial) over a territory. The logistic organisation comes from an auto-organised and distributed process from the actors. This works aims to understand, at different scales, how autonomous and heterogeneous actors (according to their goals and methods to take decisions) are collectively organised around infrastructures to manage different kinds of flow, and despite numerous constraints (temporal, spatial,...). We propose an agent-based model which allows to simulate the processes to create and organise logistic flow over a territory. The model describes an interface between international and urban flow in order to understand how the port and urban dynamics work together. The model integrates a structural and organisational dynamics thanks to dynamic graphs in order to represent the evolution of this kind of system. Thus, the agents can adapt themselves to system's perturbations as in the reality
32
Magos, Rivera Miguel. "Sur la modélisation des systèmes dynamiques à topologie variable : une formulation Hamiltonienne à ports paramétrée." Lyon 1, 2005. http://www.theses.fr/2005LYO10016.
Full textAbstract:
Dans cette thèse, nous nous intéressons à la modélisation pour la commande des systèmes physiques à topologie variable. La modélisation du système physique non commandé, est effectuée par une formulation qui conserve explicitement la représentation de l’interconnexion et l’énergie, ce qui permettra l’étude des systèmes non-réguliers par une approche modulaire basée sur le concept de l’énergie. Le principal objectif est alors de représenter de manière structurée toutes les configurations du système, en terme de comportement physiquement possible. Les résultats présentés dans ce mémoire ont pour support un formalisme réseau dynamique pour lequel la théorie des graphes fournit plusieurs représentations mathématiques. Celles-ci permettent la formulation des structures d’interconnexion du système sous forme d’une famille paramétrée de Dirac. Une formulation Hamiltonienne à ports est donc établie à partir de cette expression pour les systèmes physiques à topologie variable incluant des sources d’énergie, des éléments en excès ou des éléments dissipatifs. Cette méthode de modélisation permet d’obtenir un modèle des dynamiques du système mais aussi de ces interconnexions. La représentation sous forme de graphes dynamiques facilite l’analyse des configurations admissibles et des configurations contraintes du système
33
Casteigts, Arnaud. "Contribution à l'algorithmique distribuée dans les réseaux mobiles ad hoc - Calculs locaux et réétiquetages de graphes dynamiques." Phd thesis, Université Sciences et Technologies - Bordeaux I, 2007. http://tel.archives-ouvertes.fr/tel-00193181.
Full textAbstract:
Les réseaux mobiles ad hoc sont par nature instables et imprévisibles. De ces caractéristiques découle la difficulté à concevoir et analyser des algorithmes distribués garantissant certaines propriétés. C'est sur ce point que porte la contribution majeure de cette thèse. Pour amorcer cette étude, nous avons étudié quelques problèmes fondamentaux de l'algorithmique distribuée dans ce type d'environnement. Du fait de la nature de ces réseaux, nous avons considéré des modèles de calculs locaux, où chaque étape ne fait collaborer que des n\oe uds directement voisins. Nous avons notamment proposé un nouveau cadre d'analyse, combinant réétiquetages de graphes dynamiques et graphes évolutifs (modèle combinatoire pour les réseaux dynamiques). Notre approche permet de caractériser les conditions de succès ou d'échec d'un algorithme en fonction de la dynamique du réseau, autrement dit, en fonction de conditions nécessaires et/ou suffisantes sur les graphes évolutifs correspondants. Nous avons également étudié la synchronisation sous-jacente aux calculs, ainsi que la manière dont une application réelle peut reposer sur un algorithme de réétiquetage. Un certain nombre de logiciels ont également été réalisés autour de ces travaux, notamment un simulateur de réétiquetage de graphes dynamiques et un vérificateur de propriétés sur les graphes évolutifs.
34
Varloot, Rémi. "Dynamic network formation." Thesis, Paris Sciences et Lettres (ComUE), 2018. http://www.theses.fr/2018PSLEE048/document.
Full textAbstract:
Cette thèse porte sur la rapidité du temps de mélange de chaînes de Markov sur des graphes. La contribution principale concerne les graphes avec des dynamiques locales sur les arêtes, la topologie du graphe évoluant au fur et à mesure que les arêtes glissent les unes le long des autres. Nous proposons une classification des différents modèles existants de graphes dynamiques, tout en illustrant l’importance des transitions le long d’une structure mouvante pour améliorer la vitesse de convergence. Cette étude est complétée par la preuve, pour l’une de ces dynamiques, d’un temps de mélange rapide. Nous définissons notamment l’expansion partielle d’un graphe. Celle-ci permet de suivre l’avancement de la dynamique, partant d’un état de faible expansion, jusqu’à obtention d’une bonne expansion à l’équilibre. La fin de cette thèse porte sur une amélioration de l’algorithme de simulation parfaite de Propp et Wilson. Nous introduisant un oracle pour les transitions, inspiré de l’échantillonnage préférentiel, qui permet de réduire la complexité de l’algorithme. Nous fournissons une preuve de correction, ainsi qu’une étude de l’impact de cette méthode sur la vitesse d’échantillonnage d’ensembles indépendants pour certains graphes<br>This thesis focuses on the rapid mixing of graph-related Markov chains. The main contribution concerns graphs with local edge dynamics, in which the topology of a graph evolves as edges slide along one another. We propose a classification of existing models of dynamic graphs, and illustrate how evolving along a changing structure improves the convergence rate. This is complemented by a proof of the rapid mixing time for one such dynamic. As part of this proof, we introduce the partial expansion of a graph. This notion allows us to track the progression of the dynamic, from a state with poor expansion to good expansion at equilibrium. The end of the thesis proposes an improvement of the Propp and Wilson perfect sampling technique. We introduce oracle sampling, a method inspired by importance sampling that reduces the overall complexity of the Propp and Wilson algorithm. We provide a proof of correctness, and study the performance of this method when sampling independent sets from certain graphs
35
Benamara, Lamia. "Dynamique des graphes de terrain : caractérisation et étude du biais lié à la mesure." Paris 6, 2011. http://www.theses.fr/2011PA066447.
Full textAbstract:
Les graphes dynamiques apparaissent dans de nombreux contextes, réseaux informatiques dans lesquels des machines ou des liens peuvent subir des pannes, réseaux sociaux dans lesquels des connexions entre individus apparaissent et disparaissent au cours du temps, graphes du web dans lesquels des pages sont créées ou supprimées, etc. Jusqu'à récemment ces objets étaient principalement étudiés sous un angle statique. Or, la plupart de ces graphes sont en réalité des graphes dynamiques. Cette dynamique peut apparaître d'une façon différente selon les contextes : réseaux sociaux dans lesquels des connexions entre individus apparaissent et disparaissent au cours du temps, graphes du web dans lesquels des pages sont créées ou supprimées, etc. Un grand nombre de résultats de ces 10 dernières années ont introduit un ensemble d'outils pour l'analyse et la description des graphes statiques, mais peu a été fait pour l'étude de leur dynamique. Nous avons abordé dans cette thèse la problématique de la caractérisation de la dynamique des graphes de terrain tout en prenant en compte le biais lié à la mesure, en nous appuyant sur des cas concrets de graphes dynamiques. Nos contributions se sont orientées dans deux directions. Nous nous somme tout d'abord intéressés à l'étude du biais dans l'observation de la dynamique induit par le fait que la période d'observation est finie. Nous avons proposé une nouvelle méthodologie qui permet de déterminer si la longueur de la période d'observation est suffisante pour une caractérisation rigoureuse d'une propriété donnée. Cette méthodologie est générique et peut être appliquée à n'importe quelle propriété caractérisant un graphe de terrain dynamique. Pour démontrer la pertinence de notre méthodologie, nous l'avons appliquée à l'étude de différentes propriétés dans un système P2P. Notre deuxième contribution consiste en une approche pour étudier des graphes dynamiques. Nous avons cherché à la fois à caractériser la dynamique globale de ces systèmes, et à identifier les éventuels nœuds ayant un comportement particulier. Nous avons étudié plusieurs jeux de données issus de réseaux de contacts entre personnes et nous avons montré que chaque jeu de données a ses particularités. Nous avons également constaté que certaines caractéristiques sont partagées par tous les jeux de données. En particulier, la dynamique globale du réseau change en fonction de la période d'observation et le comportement de certains nœuds diffère du comportement global du système<br>Complex networks appear in many contexts: computer networks, social networks, web graphs, etc. Until recently, these objects were mainly studied from a static point of view. However, most of these graphs are dynamic. This dynamics may appear differently depending on the context: social networks in which connections between people appear and disappear over time, web graphs in which web pages are created or deleted, etc. Many results of the last 10 years have introduced a set of tools for the analysis and the description of static graphs, but little has been done to study their dynamics. In this this thesis, we addressed the problem of characterizing the dynamics of complex networks, taking into account the measurement bias, by considering concrete cases of dynamic graphs. We made two main contributions. First, we studied the bias in the dynamics measurement induced by the fact that the observation period is finite. We introduced a new methodology for deciding if the length of the observation period is sufficient to rigorously characterize a given property. This methodology is generic and can be applied to any property in any dynamic system. To illustrate its relevance, we have applied it to several properties in a large P2P system. Our second contribution consists in an approach to characterize the dynamics of contact networks. We attempted to characterize the global dynamics of these systems, and to identify nodes with particular behaviors. We studied several datasets of contact networks between individuals and we have shown that each dataset has its particularities. We also found that some characteristics are shared by all datasets. In particular, the global dynamics of the network changes depending on the observation period and the behavior of some nodes differs from the global behavior of the system
36
Canu, Maël. "Détection de communautés orientée sommet pour des réseaux mobiles opportunistes sociaux." Electronic Thesis or Diss., Paris 6, 2017. http://www.theses.fr/2017PA066378.
Full textAbstract:
Les travaux présentés dans la thèse s'inscrivent dans le cadre de l'analyse des graphes de terrain (complex networks) et plus précisément de la tâche de détection de communautés, c'est-à-dire la reconnaissance algorithmique de sous-graphes particulièrement denses. Nous nous intéressons spécifiquement à l'implémentation d'une telle méthode dans un contexte fortement décentralisé et distribué : des réseaux MANET opportunistes formés par de petits objets connectés communiquant en pair-à-pair. Afin de tenir compte des contraintes d'exécution d'algorithme dans de tels réseaux, les travaux présentés dans la thèse proposent des méthodes conçues selon le paradigme récent et actif nommé orienté sommet, en alliant le traitement de graphes Think-Like-a-Vertex aux méthodes de détection de communautés basées sur des leaders ou des graines : celles-ci présentent en effet des propriétés de décentralisation qui autorisent des implémentations parallèles et distribuées appropriées au cadre applicatif considéré. Dans ce contexte, nous proposons d'une part un principe global de fonctionnement original que nous mettons en oeuvre et déclinons dans trois algorithmes dédiés à trois configurations différentes de la tâche de détection de communautés : l'algorithme VOLCAN considère le cas de référence des communautés disjointes dans un graphe statique. Nous l'étendons ensuite avec l'algorithme LOCNeSs au cas des communautés recouvrantes, qui autorisent un sommet à appartenir à plusieurs communautés simultanément : cette généralisation donne plus de flexibilité à la détection et la rend plus appropriée au cadre applicatif considéré. Nous examinons également le cas des graphes dynamiques, c'est-à-dire dont les sommets et les arêtes évoluent au cours du temps, auquel est consacré l'algorithme DynLOCNeSs. Chacun des algorithmes est associé à une implémentation décentralisée et fait l'objet d'une étude théorique ainsi qu'expérimentale sur des données artificielles et réelles permettant d'évaluer la qualité des résultats fournis et de les comparer aux méthodes de l'état de l'art. Nous considérons également, dans un cas particulier de réseau mobile ad-hoc spontané et décentralisé issu d'une application réelle de vêtements intelligents et communicants, une tâche de cheminement permettant d'identifier des interlocuteurs. Nous proposons une stratégie de recommandation utilisant la structure communautaire, modélisée et évaluée à travers un algorithme nommé SWAGG<br>Our research is in the field of complex network analysis and mining, specifically addressing the communit detection task, ie. algorithms aiming to uncover particularly dense subgraphs. We focus on the implementation of such an algorithm in a decentralised and distributed context : opportunistic MANET constituted of small wireless devices using peer-to-peer communication. To tackle the implementation constraints in such networks, we propose several methods designed according to the novel and trending vertex-centred paradigm, by combining Think-Like-a-Vertex graph processing with vertex-centred community detection methods based on leaders or seeds : they show specific properties allowing dsitributed implementations suiting the opportunistic MANET case. In this context, we first a global working principle and implement it in three different algorithms dedicated to three different configurations of community detection : the VOLCAN algorithm manages the classical disjoint community detection task in a static graph. We extend it with the LOCNeSs algorithm, that is dealing with overlapping communities which means that one vertex can belong to several communities. It adds more flexibility to the method and more significance to produced results. We also tackle the dynamic graphe case (graph evolving over time), addressed by the DynLOCNeSs algorithm.Each algorithm comes with a decentralised implementation and theoretical as well as experimental studies conducted both on real and synthetic benchmark data, allowing to evaluate the quality of the results and compare to existing state-of-the-art methods. Finally, we consider a special case of opportunistic decentralised MANET developped as a part of a research project about smart and communicating clothing. We formalise a task of path finding between smart t-shirts holders and propose a recommandation strategy using community structure, that we model and evaluate through an algorithm named SWAGG
37
Martinet, Lucie. "Réseaux dynamiques de terrain : caractérisation et propriétés de diffusion en milieu hospitalier." Thesis, Lyon, École normale supérieure, 2015. http://www.theses.fr/2015ENSL1010/document.
Full textAbstract:
Durant cette thèse, nous nous sommes intéressés aux outils permettant d'extraire les propriétés structurelles et temporelles de réseaux dynamiques ainsi que les caractéristiques de certains scénarios de diffusion pouvant s'opérer sur ces réseaux. Nous avons travaillé sur un jeu de données spécifiques, issu du projet MOSAR, qui comporte entre autre le réseau de proximité des personnes au cours du temps durant 6 mois à l'hôpital de Berk-sur-mer. Ce réseau est particulier dans le sens où il est constitué de trois dimensions: temporelle, structurelle par la répartition des personnes en services et fonctionnelle car chaque personne appartient à une catégorie socio-professionnelle. Pour chacune des dimensions, nous avons utilisé des outils existants en physique statistique ainsi qu'en théorie des graphes pour extraire des informations permettant de décrire certaines propriétés du réseau. Cela nous a permis de souligner le caractère très structuré de la répartition des contacts qui suit la répartition en services et mis en évidence les accointances entre certaines catégories professionnelles. Concernant la partie temporelle, nous avons mis en avant l'évolution périodique circadienne et hebdomadaire ainsi que les différences fondamentales entre l'évolution des interactions des patients et celle des personnels. Nous avons aussi présenté des outils permettant de comparer l'activité entre deux périodes données et de quantifier la similarité de ces périodes. Nous avons ensuite utilisé la technique de simulation pour extraire des propriétés de diffusion de ce réseau afin de donner quelques indices pour établir une politique de prévention<br>In this thesis, we focus on tools whose aim is to extract structural and temporal properties of dynamic networks as well as diffusion characteristics which can occur on these networks. We work on specific data, from the European MOSAR project, including the network of individuals proximity from time to time during 6 months at the Brek-sur-Mer Hospital. The studied network is notable because of its three dimensions constitution : the structural one induced by the distribution of individuals into distinct services, the functional dimension due to the partition of individual into groups of socio-professional categories and the temporal dimension.For each dimension, we used tools well known from the areas of statistical physics as well as graphs theory in order to extract information which enable to describe the network properties. These methods underline the specific structure of the contacts distribution which follows the individuals distribution into services. We also highlight strong links within specific socio-professional categories. Regarding the temporal part, we extract circadian and weekly patterns and quantify the similarities of these activities. We also notice distinct behaviour within patients and staff evolution. In addition, we present tools to compare the network activity within two given periods. To finish, we use simulations techniques to extract diffusion properties of the network to find some clues in order to establish a prevention policy
38
Pigné, Yoann. "Modélisation et traitement décentralisé des graphes dynamiquesApplication aux réseaux mobiles ad hoc." Phd thesis, Université du Havre, 2008. http://tel.archives-ouvertes.fr/tel-00371962.
Full textAbstract:
Les graphes dynamiques sont un outil de plus en plus utilisé dans des contextes variés où il s'avère nécessaire de modéliser des environnements changeants ou incertains. Les modèles aujourd'hui proposés sont dédiés à ces applications précises. Il n'existe pas de modèle général reprenant, hors de tout contexte applicatif, ces caractéristiques. D'autre part la résolution de problèmes liés à ces environnements dynamiques et incertains est problématique. Nous proposons, ici, la formalisation d'un modèle général de graphe dynamique. <br /><br />Nous étudions la résolution de problèmes dans ces graphes à l'aide de méthodes inspirées de mécanismes d'intelligence collective. <br /><br />Les modèles proposés sont validés dans le contexte applicatif des réseaux mobiles ad hoc. Une approche originale de construction et de maintien de chemins de communication sous plusieurs contraintes est proposée. Le problème de la construction et du maintien d'une forêt couvrante dans un réseau mobile ad hoc est également étudié.
39
Bratcu, Antoneta. "Détermination systématique des graphes de précédence et équilibrage des lignes d'assemblage." Phd thesis, Université de Franche-Comté, 2001. http://tel.archives-ouvertes.fr/tel-00258992.
Full textAbstract:
Cette thèse est une contribution à une démarche globale de conception rationnelle des systèmes d'assemblage. Elle concerne plus précisément le problème de génération des graphes de précédence, en vue de leur utilisation par les méthodes d'équilibrage des systèmes d'assemblage. Le premier chapitre de ce travail est consacré à la description de la problématique des systèmes d'assemblage. Le deuxième chapitre présente un état de l'art des approches de génération des graphes de précédence pour l'assemblage. Les propriétés de ceux-ci sont listées et comparées à celles des autres modèles des processus d'assemblage. L'objectif du troisième chapitre est l'élaboration d'une méthode systématique d'obtention des graphes de précédence à partir d'un ensemble de gammes d'assemblage. Dans ce but, deux algorithmes sont proposés. Ils sont basés sur la vérification d'une propriété structurelle – la propriété ? – qui est nécessaire et suffisante pour assurer l'équivalence d'un ensemble de gammes à un seul graphe de précédence. Un état de l'art des méthodes de conception des systèmes d'assemblage issues de l'équilibrage des lignes d'assemblage est présenté dans le quatrième chapitre. Le problème d'équilibrage consiste à trouver l'affectation des tâches aux postes, telle qu'elle assure la minimisation du temps de cycle total. Une approche systémique est proposée par la formulation de ce problème comme problème d'optimisation discrète, en vue de la résolution par la programmation dynamique. Le dernier chapitre est dédié à l'analyse des systèmes d'assemblage avec auto-équilibrage, dont la conception évite la résolution d'un problème d'équilibrage classique. Il est suffisant qu'un tel système satisfasse une contrainte technologique simple de placement des opérateurs (humains) sur la ligne – du plus lent au plus rapide – pour qu'il atteigne spontanément un comportement optimal du point de vue de l'équilibrage. Une analyse par simulation de tels systèmes est présentée. Ils peuvent être traités comme systèmes dynamiques hybrides à commutations et sauts autonomes. La condition suffisante de l'autoéquilibrage – le "bon ordre" – est démontrée en utilisant les critères de stabilité des systèmes dynamiques discrets.
40
Cazabet, Rémy. "Détection de communautés dynamiques dans des réseaux temporels." Phd thesis, Université Paul Sabatier - Toulouse III, 2013. http://tel.archives-ouvertes.fr/tel-00874017.
Full textAbstract:
La détection de communautés dans les réseaux est aujourd'hui un domaine ayant donné lieu à une abondante littérature. Depuis les travaux de Girvan et Newman en 2002, des centaines de travaux ont été menés sur le sujet, notamment la proposition d'un nombre important d'algorithmes de plus en plus élaborés. Cependant, la majorité de ces travaux portent sur des communautés statiques dans des réseaux statiques. Or, beaucoup de réseaux de terrains sont en fait dynamiques, ils évoluent au cours du temps. L'apport principal de cette thèse est donc la conception d'un algorithme de détection de communautés dynamiques sur des réseaux temporels. Le manuscrit est découpé en quatre sections : La première est un état de l'art, où sont passés en revu les méthodes existantes pour la détection de communauté, statiques, dynamiques, avec et sans recouvrement. La seconde est la présentation de la solution que nous proposons : iLCD, un framework pour la détection de communautés dynamiques dans les réseaux temporels, ainsi que deux implémentations de ce framework. La troisième partie présente les travaux effectués pour valider iLCD sur le plan statique, c'est à dire valider que les communautés trouvées sont pertinentes comparées à d'autres algorithmes existant sur des réseaux statiques. Pour ce faire, nous proposons des idées originales, afin de pouvoir comparer des méthodes sur des graphes réels. Enfin, la dernière partie est consacrée à la validation de l'aspect dynamique d'iLCD. En effet, la dynamique introduit des données supplémentaires : l'apparition et la disparition de communautés, leur évolution en continue, ainsi que des opérations complexes, telles que la fusion ou la division de communautés au cours du temps. Ce sont ces aspects qui sont validés ici, en étudiant en détail les résultats obtenus sur des réseaux réels.
41
Edibe, Bénédicte. "Modélisation et simulation de systèmes dynamiques par les bond graphs : application aux systèmes mécaniques polyarticulés." Rennes 1, 1995. http://www.theses.fr/1995REN1A007.
Full text
42
Zaïdi, Abdelaziz. "Intégration des réseaux bayésiens et bond graphs pour la supervision des systèmes dynamiques." Thesis, Lille 1, 2012. http://www.theses.fr/2012LIL10035/document.
Full textAbstract:
La supervision des processus industriels critiques est une tâche complexe qui nécessite des algorithmes robustes. La littérature montre un intérêt croissant des approches graphiques à cause de la simplicité de l’implémentation des algorithmes dérivés. Le diagnostic à base de modèle est une méthode qui devient de plus en plus utilisée à cause de la richesse des méthodes graphiques et structurelles permettant la modélisation des processus complexes et ne nécessitent pas une phase d’apprentissage en ligne. L’outil bond graph (BG) par ses propriétés graphique et multidisciplinaire est un outil puissant de modélisation reconnu. Dans ce contexte, les propriétés structurelles et causales de cet outil (utilisées pour la détection de défauts) sont exploitées ici pour intégrer les réseaux bayésiens graphiques permettant d’incorporer des statistiques de pannes des composants pour améliorer l’étape de décision. Cette méthodologie permet de pallier aux problèmes relatifs aux signatures de défauts inconnues ou identiques pour plusieurs composants et le suivie de la dégradation du système. Sur la base de la littérature consultée, il n’apparait pas de travaux qui évoquent une démarche pour la supervision associant un modèle bayésien de la fiabilité avec une approche de détection et isolation de défaut (FDI) basée sur le modèle BG. Notre contribution concerne l’intégration de deux outils graphiques (BG et réseaux Bayésiens (RB)) pour la conception d’un système de supervision robuste. Les résidus générés par le modèle BG sont couplés avec le modèle de fiabilité des composants à surveiller pour en déduire finalement un modèle de diagnostic de type RB hybride. Ce modèle est utilisé dans l’étape de décision face aux incertitudes du modèle bond graph en tenant compte des probabilités de fausses alarmes et de non détection estimées par une approche hiérarchique bayésienne. Une application à une partie d’une centrale thermique a validé la théorie développée<br>The supervision of complex and critical industrial processes is a very heavy task which requires effective algorithms. The literature shows a growing interest of graphical approaches because of the simplicity of establishment of the derived algorithms. The model based diagnosis is a method which becomes widespread because of the richness of graphical and structural methods allowing modeling of most complex processes. The bond graph (BG) tool, with its multidisciplinary representation, is one of the most recognized approaches in this framework. In this context, we try in present work to couple this graphical approach with another graphical one allowing incorporating statistics of components failures. All this aims to mitigate the problems: unknown failure signatures or identical signatures for several components and monitoring the system degradation. Indeed, on the basis of consulted literature, it does not appear work which evokes a supervision strategy associating a Bayesian reliability model with a BG model based fault detection and isolation (FDI) approach. Consequently, the suggested work illustrates a method to outline this objective. We propose a new methodology for the supervision of the dynamic and hybrid dynamic systems. Our contribution appears in the proposal for a strategy of risk based supervision by combining two graphical approaches: BG and Bayesian networks (BN). The resulting model for diagnosis is a hybrid BN. It is able to make a decision under uncertainties of BG model and takes account of the probabilities of false alarm and non-detection. Furthermore, integration of two graphical approaches (BG and Bayesian networks (BN) to design robust supervision system is another innovative interest. Generated residuals from BG model are coupled with the component reliability model of components leading to a hybrid BN diagnostic model. This model is then used to make a decision under uncertainties of BG model and takes into account the probabilities of false alarm and non-detection. The developed theory is applied to a thermal power station
43
Six, Béranger. "Génération automatique de modèles pour la supervision des systèmes dynamiques hybrides : application aux systèmes ferroviaires." Thesis, Lille, 2018. http://www.theses.fr/2018LIL1I048.
Full textAbstract:
Ce travail de thèse présente différentes contributions pour la génération automatique de modèles représentant les Systèmes Dynamiques Hybrides (SDH) caractérisés par plusieurs modes de fonctionnement. Les composants du système (notamment les capteurs) peuvent être manuellement sélectionnée ou automatiquement exportés à partir des données de Conception Assistée par Ordinateur (CAO) ; ces éléments sont ensuite interconnectés pour reproduire le modèle complet du système industriel. Une fois le modèle créé, des schémas-blocs de simulation et de diagnostic, ainsi que la Matrice de Signature de Fautes (FSM) seront produits. Le logiciel est basé sur les Bonds Graph Hybrides ; la présence de commutations engendre des dynamiques variables (notamment des changements de causalité). Pour lever ces verrous, différents algorithmes sont proposés. En comparaison des logiciels existants, les algorithmes proposés sont valides pour les systèmes continus, discrets ou hybrides. Les théories et algorithmes développés sont appliqués sur un système ferroviaire de freinage électropneumatique<br>This thesis work contributes to perform a automed model builder for Hybrid Dynamic Systems (HDS) with numerous modes. Technological components including sensors with an iconic format can be automatically export from a computer-aided design (CAD) scheme or manually drag from database and interconnected, so as to produce the overall HDS model, following industrial technological schemes. Once the model has been created, block diagram for simulation and diagnosis and a Fault Signature Matrix (FSM) could be generated.The theory and algorithm behind the software are based on Hybrid Bond Graphs (HBG). The switching behaviour engenders variables dynamics (particularly causal changes). To solve this problematic, news algorithm are performed. Compared with developed programs for automated modelling, the presented algorithm are valid for continuous, discrete and hybrid systems. The theory is illustrated by an industrial application which consists of the pneumo-electrical control of rolling stock
44
Coutereel, Luc. "Étude et réalisation d'un processeur d'aide à la modélisation des systèmes dynamiques par l'approche Bond-Graph." Lille 1, 1991. http://www.theses.fr/1991LIL10003.
Full textAbstract:
Les travaux présentés dans cette thèse, contribuent au développement des systèmes experts liés a la modélisation de systèmes physiques dynamiques. Ce processeur ARCHER utilise conjointement les techniques de l'intelligence artificielle et l'outil Bond-Graph. ARCHER permet, à partir d'une description en langage utilisateur proche du langage naturel du système physique, la construction du modèle Bond-Graph et la détermination de l'équation d'état associée sous forme d'expressions formelles. Ecrit en Turbo-Prolog et développé sur Pc, ARCHER possède par sa construction même, certaines qualités d'un système expert spécialisé. Les domaines physiques concernés par le processeur sont les systèmes mécaniques en dimension 1 et les systèmes électriques linéaires
45
Guennoun, Mohammed Karim. "Architectures dynamiques dans le contexte des applications à base de composants et orientées service." Phd thesis, Université Paul Sabatier - Toulouse III, 2006. http://tel.archives-ouvertes.fr/tel-00136075.
Full textAbstract:
L'adaptabilité des applications logicielles peut être séparée en deux catégories. La première concerne l'adaptation comportementale appelée aussi adaptation algorithmique. Cette adaptation traite la redéfinition du comportement de l'application et de ses composants et implique, par exemple, l'introduction d'une nouvelle méthode dans l'interface d'un composant ou le changement du protocole d'orchestration qui coordonne un ensemble de services. Nos travaux, que nous classons dans une deuxième catégorie, traitent l'adaptation structurelle et considèrent une reconfiguration au niveau architectural. Ce type de reconfiguration traite l'organisation de l'architecture et consiste, par exemple, à remplacer un composant défaillant par un autre composant qui possède les mêmes fonctionnalités ou rediriger un client d'un service qui ne respecte pas le contrat de QdS vers un service susceptible d'offrir de meilleures garanties. Dans ce mémoire, nous définissons un méta-modèle relatif à la description et la gestion automatique des architectures dynamiques. Les instances des architectures sont décrites par des graphes étendus où les composants (ou les services) sont représentés par des n\oe uds, et les interdépendances (e.g. les connexions, les relations de contrôle ...etc) sont décrites par des arcs. Les styles architecturaux sont spécifiés par des grammaires de graphes étendues. Le méta-modèle admet des descriptions en considérant différents niveaux d'abstraction et offre des mécanismes pour raffiner ou abstraire les descriptions selon des points de vues spécifiques. Il permet, aussi, de décrire le protocole de gestion de l'architecture et de caractériser les propriétés architecturales à préserver pour chaque niveau architectural considéré. Nous avons développé un algorithme de recherche d'homomorphismes de graphes et un algorithme de transformation de graphes pour les grammaires de graphes étendus définis pour notre méta-modèle. L'analyse de complexité des algorithmes ains i que les résultats expérimentaux obtenus ont permis de conclure à leur efficacité. Une deuxième version des deux algorithmes a été définie profitant de la spécificité du contexte de la transformation de graphes. L'analyse de complexité de ces nouvelles versions donne des résultats encore plus performants pour le passage à l'échelle. Notre approche a été éprouvée en l'appliquant à un cas d'étude dans le contexte des activités d'opération d'intervention d'urgence. L'application implique des groupes structurés de robots ou de personnel militaire qui disposent de ressources inégales en capacités de communication, en CPU et en énergie. Les besoins d'adaptabilité découlent des changements du contexte d'exécution, de l'occurrence de pannes et du provisionnement de la QdS.
46
Bournat, Marjorie. "Graceful Degradation and Speculation for Robots in Highly Dynamic Environments." Electronic Thesis or Diss., Sorbonne université, 2019. http://www.theses.fr/2019SORUS035.
Full textAbstract:
Les systèmes distribués sont des systèmes composés de plusieurs processus communiquants et coopérants ensemble pour résoudre des tâches communes. C’est un modèle générique pour de nombreux systèmes réels comme les réseaux sans fil ou mobiles, les systèmes multiprocesseurs à mémoire partagée, etc. D’un point de vue algorithmique, il est reconnu que de fortes hypothèses (comme l’asynchronisme ou la mobilité) sur de tels systèmes mènent souvent à des résultats d’impossibilité ou à de fortes bornes inférieures sur les complexités. Dans cette thèse, nous étudions des algorithmes qui s’auto-adaptent à leur environnement (i.e., l’union de toutes les hypothèses sur le système) en se concentrant sur les deux approches suivantes. La dégradation progressive contourne les résultats d’impossibilité en dégradant les propriétés offertes par l’algorithme lorsque l’environnement devient fort. La spéculation contourne les bornes inférieures élevées sur les complexités en optimisant l’algorithme seulement sur les environnements les plus probables. Les réseaux de robots représentent un cas particulier des systèmes distribués où les processus, dotés de capteurs, sont capables de bouger d’une localisation à une autre. Nous considérons des environnements dynamiques dans lesquels cette capacité peut évoluer avec le temps. Cette thèse répond positivement à la question ouverte de savoir s’il est possible et bénéfique d’appliquer les approches progressivement dégradante et spéculative aux réseaux de robots dans des environnements dynamiques. Cette réponse est obtenue en étudiant le rassemblement (où tous les robots doivent se retrouver à la même localisation en temps fini) progressivement dégradant et l’exploration perpétuelle (où les robots doivent visiter infiniment souvent chaque localisation) spéculative<br>Distributed systems are systems composed of multiple communicant processes cooperating to solve a common task. This is a generic model for numerous real systems as wired or mobile networks, shared-memory multiprocessor systems, and so on. From an algorithmic point of view, it is well-known that strong assumptions (as asynchronism or mobility) on such systems lead often to impossibility results or high lower bounds on complexity. In this thesis, we study algorithms that adapt themselves to their environment (i.e., the union of all assumptions on the system) by focusing on the two following approaches. Graceful degradation circumvents impossibility results by degrading the properties offered by the algorithm as the environment become stronger. Speculation allows to bypass high lower bounds on complexity by optimizing the algorithm only on more probable environments. Robot networks are a particular case of distributed systems where processes are endowed with sensors and able to move from a location to another. We consider dynamic environments in which this ability may evolve with time. This thesis answers positively to the open question whether it is possible and attractive to apply gracefully degrading and speculative approaches to robot networks in dynamic environments. This answer is obtained through contributions on gracefully degrading gathering (where all robots have to meet on the same location in finite time) and on speculative perpetual exploration (where robots must visit infinitely often each location)
47
Gilbert, Frédéric. "Méthodes et modèles pour la visualisation de grandes masses de données multidimensionnelles nominatives dynamiques." Thesis, Bordeaux 1, 2012. http://www.theses.fr/2012BOR14498/document.
Full textAbstract:
La visualisation d'informations est un domaine qui connaît un réel intérêt depuis une dizaine d'années. Dernièrement, avec l'explosion des moyens de communication, l'analyse de réseaux sociaux fait l'objet de nombreux travaux de recherches. Nous présentons dans cette thèse des travaux sur l'analyse de réseaux sociaux dynamiques, c'est à dire que nous prenons en compte l'aspect temporel des données. [...]<br>Since ten years, informations visualization domain knows a real interest.Recently, with the growing of communications, the research on social networks analysis becomes strongly active. In this thesis, we present results on dynamic social networks analysis. That means that we take into account the temporal aspect of data. We were particularly interested in communities extraction within networks and their evolutions through time. [...]
48
Carvin, Denis. "Mécanismes de supervision distribuée pour les réseaux de communication dynamiques." Thesis, Toulouse, INSA, 2015. http://www.theses.fr/2015ISAT0025/document.
Full textAbstract:
Avec l’arrivée massive des technologies sans fil, le nombre de terminaux mobiles n’a cessé de croître, pour des usages et des ressources de communication diversifiés. En intégrant les objets du quotidien, nos réseaux de communications sont devenus dynamiques aussi bien en termes de ressources que de topologie physique, offrant accès à des informations de plus en plus riches. La tâche de gestion s’est ainsi complexifiée et requiert des temps de réponse de plus en plus courts difficilement réalisables par un administrateur humain. Il devient indispensable de mettre en œuvre des capacités de gestion autonomes pour les nouveaux réseaux. Dans tous les cas, la gestion d’un système implique une étape essentielle : sa mesure et sa supervision. Peu importe sa nature, c’est cette étape de prise d’information qui permet sa caractérisation, son analyse et son contrôle. Le domaine des réseaux n’échappe pas à cette règle et les objets qui le composent auront besoin d’acquérir des informations sur leur environnement pour mieux s’y adapter. Dans cette thèse, nous nous intéressons au partage efficace de ces informations de mesures à des fins d’auto-analyse et d’évaluation distribuée de la performance. Après avoir formalisé le problème de la mesure distribuée, nous nous consacrons dans un premier temps à l’organisation des échanges de mesures dans les graphes dynamiques. Nous proposons une nouvelle heuristique pour le consensus de la moyenne qui converge plus rapidement que celles de l’état de l’art. Dans un second temps, nous considérons des topologies plus stables pouvant utiliser des flux TCP comme moyen d’échange. Nous proposons un mécanisme d’ordonnancement de ces flux qui conserve le même comportement face à la congestion, tout en réduisant leur latence moyenne. Enfin, nous nous intéressons à l’information de mesure échangée. Nous montrons comment les nœuds peuvent superviser diverses métriques telles que la performance d’un système en se basant sur l’utilité de ses agents, et proposons une méthode pour qu’ils puissent analyser l’évolution de cette performance<br>With the massive rise of wireless technologies, the number of mobile stations is constantly growing. Both their uses and their communication resources are diversified. By integrating our daily life objects, our communication networks become dynamic in terms of physical topology but also in term of resources. Furthermore, they give access to a richer information. As a result, the management task has become complex and requires shorter response time that a human administrator can not respect. It becomes necessary to develop an autonomic management behavior in next generation networks. In any manner, managing a system requires essential steps which are : its measurement and its supervision. Whatever the nature of a system, this stage of information gathering, allows its characterization and its control. The field of networks is not the exception to the rule and objects that compose them will need to acquire information on their environment for a better adaptation. In this thesis, we focus on the efficient sharing of this information, for self-analysis and distributed performance evaluation purposes. After having formalized the problem of the distributed measurement, we address in a first part the fusion and the diffusion of measures in dynamic graphs. We develop a new heuristic for the average consensus problem offering a better contraction rate than the ones of the state of the art. In a second part, we consider more stable topologies where TCP is used to convey measures. We offer a scheduling mechanism for TCP flows that guaranty the same impact on the network congestion, while reducing the average latency. Finally, we show how nodes can supervise various metrics such as the system performance based on their utilities and suggest a method to allow them to analyze the evolution of this performance
49
Abdelsadek, Youcef. "Triangle packing for community detection : algorithms, visualizations and application to Twitter's network." Thesis, Université de Lorraine, 2016. http://www.theses.fr/2016LORR0310.
Full textAbstract:
De nos jours, nous générons une quantité immensément grande de données juste en accomplissant nos simples tâches quotidiennes. L'analyse de ces données soulève des challenges ardus. Dans cette thèse, nous nous intéressons à deux aspects des données relationnelles. En premier lieu, nous considérons les données relationnelles dans lesquelles les relations sont pondérées. Un exemple concret serait le nombre commun de suiveurs entre deux utilisateurs de Twitter. Dans un deuxième temps, nous abordons le cas dynamique de ces données qui est inhérent à leur nature. Par exemple, le nombre de suiveurs communs pourrait changer au fil du temps. Dans cette thèse nous utilisons les graphes pour modéliser ces données qui sont à la fois complexes et évolutives. Les travaux de cette thèse s'articulent aussi autour de la détection de communautés pour les graphes pondérés et dynamiques. Pour un utilisateur expert, l'identification de ces communautés pourrait l'aider à comprendre la sémantique sous-jacente à la structure du graphe. Notre hypothèse repose sur l'utilisation des triangles comme ossature pour la détection de communautés. Cela nous a amenés à proposer plusieurs algorithmes : Séparation et évaluation, recherche gloutonne, heuristiques et algorithme génétique sont proposés. En se basant sur cet ensemble de triangles, nous proposons un algorithme de détection de communautés, appelé Tribase. L'idée conductrice de cet algorithme est de comparer les poids des communautés, permettant aux communautés dominantes d'acquérir plus de membres. Les résultats de l'étude comparative sur le benchmark LFR montrent que l'algorithme que nous proposons parvient à détecter les communautés dans les graphes dans lesquels une structure de communautés existe. De plus, l'applicabilité de notre algorithme a été testée sur des données réelles du projet ANR Info-RSN. Dans l'optique d'accompagner l'utilisateur expert dans son processus d'acquisition de l'information, une application visuelle et interactive a été implémentée. NLCOMS (Nœud-Lien et COMmunautéS) propose une panoplie de vues synchronisées pour la représentation de l'information. Par ailleurs, nous proposons dans cette thèse un algorithme de détection de communautés pour les graphes pondérés et dynamiques, appelé Dyci. Dyci permet de gérer les différents scénarios de mise à jour possibles de la structure du graphe. L'idée principale de Dyci est de guetter au cours du temps l'affaiblissement d'une communauté (en termes de poids) dans le but de reconsidérer localement sa place dans la structure, évitant ainsi une réindentification globale des communautés. Une étude comparative a été menée montrant que l'algorithme que nous proposons offre un bon compromis entre la solution obtenue et le temps de calcul. Finalement, l'intégration dans NLCOMS des visualisations adéquates pour la variante dynamique a été effectuée<br>Relational data in our society are on a constant increasing, rising arduous challenges. In this thesis, we consider two aspects of relational data. First, we are interested in relational data with weighted relationship. As a concrete example, relationships among Twitter's users could be weighted with regard to their shared number of followers. The second aspect is related to the dynamism which is inherent to data nature. As an instance, in the previous example the number of common followers between two Twitter's users can change over time. In order to handle these complex and dynamic relational data, we use the modelling strength of graphs. Another facet considered in this thesis deals with community identification on weighted and dynamic graphs. For an analyst, the community detection might be helpful to grasp the semantic behind the graph structure. Our assumption relies on the idea to use a set of disjoint pairwise triangles as a basis to detect the community structure. To select these triangles, several algorithms are proposed (i.e., branch-and-bound, greedy search, heuristics and genetic algorithm). Thereafter, we propose a community detection algorithm, called Tribase. In the latter, the weights of communities are compared allowing dominant communities to gain in size. Tribase is compared with the well-known LFR benchmark. The results show that Tribase identifies efficiently the communities while a community structure exists. Additionally, to asset Tribase on real-world data, we consider social networks data, especially Twitter's data, of the ANR-Info-RSN project. In order to support the analyst in its knowledge acquisition, we elaborate a visual interactive approach. To this end, an interactive application, called NLCOMS is introduced. NLCOMS uses multiple synchronous views for visualizing community structure and the related information. Furthermore, we propose an algorithm for the identification of communities over time, called Dyci. The latter takes advantage from the previously detected communities. Several changes' scenarios are considered like, node/edge addition, node/edge removing and edge weight update. The main idea of the proposed algorithm is to track whether a part of the weighted graph becomes weak over time, in order to merge it with the "dominant" neighbour community. In order to assess the quality of the returned community structure, we conduct a comparison with a genetic algorithm on real-world data of the ARN-Info-RSN project. The conducted comparison shows that Dyci algorithm provides a good trade-off between efficiency and consumed time. Finally, the dynamic changes which occur to the underlying graph structure can be visualized with NLCOMS which combines physical an axial time to fulfil this need
50
Halfeld, Ferrari Alves Mirian. "Aspects dynamiques de XML et spécification des interfaces de services web avec PEWS." Habilitation à diriger des recherches, Université François Rabelais - Tours, 2007. http://tel.archives-ouvertes.fr/tel-00271099.
Full textAbstract:
Nous nous intéressons par le problème de la sémantique des mises à jour et de la cohérence des bases de données dans différents contextes comme les documents XML et les services web. En effet, des difficultés particulières sont à prévoir lors de la mise à jour d'une base ayant des contraintes à respecter, car, des données originalement cohérentes par rapport aux contraintes peuvent devenir incohérentes suite aux mises à jour. Dans une première partie de notre travail, nous considérons la mise à jour et le maintien de la cohérence d'une base de données XML par rapport au type (ou schéma) ainsi que par rapport aux contraintes d'intégrité. Nous abordons ce problème de différentes manières. Tout d'abord, nous proposons une procédure de validation incrémentale par rapport aux contraintes, évitant de revalider les parties du document qui n'ont pas été touchées par les mises à jour. Cette approche traite aussi bien le cas des contraintes de schéma que le cas des contraintes d'intégrité. Dans ce cadre, les listes de mises à jour qui violent la validité sont rejetées. Quand la validation incrémentale échoue, c'est-à-dire, quand une mise à jour viole le type, deux propositions de traitement sont faites\,: (A) Une routine de correction est activée pour adapter le document XML au type tout en prenant en compte la mise à jour. La mise à jour a donc une priorité par rapport aux données déjà stockées. (B) Une routine propose une adaptation du type du document, de façon à accepter le document mis à jour en préservant la validité des autres documents originalement valides et non soumis à la mise à jour. Dans ce cas, la mise à jour est prioritaire et les contraintes peuvent être modifiées. Une deuxième partie du travail considère la construction d'une plate-forme d'aide à la spécification, à l'implémentation et à la manipulation de services. L'idée de pouvoir spécifier et modifier des compositions de services nous a amené à la définition du langage PEWS (\textit{Path Expressions for Web Services}), ayant une sémantique formelle bien définie et permettant la spécification du comportement des interfaces des services web simples ou composés. Pour pouvoir tester statiquement des propriétés liées à la composition des services, nous proposons l'utilisation de la théorie des traces et les graphes de dépendances.