To see the other types of publications on this topic, follow the link: Analyse des graphes dynamiques.
Dissertations / Theses on the topic 'Analyse des graphes dynamiques'
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 'Analyse des graphes dynamiques.'
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
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èqueWe 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
2
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èqueWe 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
3
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. . .
4
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.
5
Bridonneau, Vincent. "Generation and Analysis of Dynamic Graphs." Electronic Thesis or Diss., Normandie, 2024. http://www.theses.fr/2024NORMLH23.
Full textAbstract:
La nature et les sociétés humaines offrent de nombreux exemples de systèmes composés d'entités qui interagissent, communiquent ou sont simplement connectées les unes aux autres. La théorie des graphes offre un excellent formalisme pour modéliser ces systèmes complexes, allant des réseaux sociaux aux systèmes biologiques. La plupart des phénomènes observés dans ces réseaux peuvent s'exprimer sous forme de propriétés sur les graphes. On peut notamment citer le phénomène du « petit monde » ou les réseaux dits « sans échelle ». Comprendre les mécanismes sous-jacents à leur évolution est essentiel pour saisir les dynamiques de ces réseaux. Différents mécanismes existent pour reproduire les propriétés observées. Parmi eux, on peut citer l'attachement préférentiel, utilisé notamment par le modèle de Barabasi-Albert (BA), qui permet de produire des séquences de graphes croissants sans échelle. Dans une direction parallèle, on peut également étendre le concept de graphe en y ajoutant une dimension temporelle. Dans ce cas, les propriétés statiques des graphes sont retravaillées pour tenir compte de l'évolution des graphes dans le temps. Par exemple, on peut citer la notion de trajet qui, semblable à celle de chemin, traduit la possibilité de se déplacer d'un sommet à un autre en respectant des contraintes temporelles. De même que dans le cas des réseaux complexes, la capacité à générer des graphes temporels est étudiée afin de produire des graphes aux propriétés spécifiques.On peut par exemple évoquer le modèle Edge-Markovian Graph, un processus stochastique permettant de produire des graphes et d’étudier des problèmes de communication. L'observation de ces mécanismes de génération donne naissance à la problématique de cette thèse, qui réside dans l'étude de processus itératifs de génération de graphes temporels. Lorsqu'un graphe est obtenu par itérations successives d'un tel mécanisme, on parle d'un graphe dynamique. Cette dénomination met en avant l'aspect itératif du processus pour produire une séquence ordonnée de graphes. Une question nous a particulièrement intéressés dans le cadre de ce travail : que se passe-t-il lorsqu’un générateur n'est soumis à aucune contrainte, notamment en ce qui concerne l'évolution du nombre de sommets au fil du temps ? Cette situation soulève deux problématiques : la possibilité qu'un processus conduise à des graphes périodiques au-delà d'un certain moment et la quantification des changements entre deux étapes consécutives du processus. Pour répondre à ces interrogations, nous avons introduit deux métriques.La première, que nous avons appelé sustainability, et que l'on peut traduire par pérennité, est une mesure qualitative : un générateur est dit sustainable s'il produit des graphes qui ne deviennent ni vides ni périodiques. La seconde métrique, le DynamicScore, quantifie les changements entre deux instants successifs, à la fois au niveau des sommets (V-DynamicScore) et des arêtes (E-DynamicScore). Pour démontrer la pertinence de la notion de pérennité, nous avons défini et étudié un générateur de graphes mettant en évidence les nombreux défis rencontrés lors de l'exploration de cette notion. En ce qui concerne le DynamicScore, nous l'avons testé sur divers générateurs ainsi que sur des données réelles, démontrant sa capacité à capturer la dynamique d’un réseau, qu’il soit artificiel ou réel. L’étude de ces deux concepts a ouvert la voie à de nombreuses nouvelles questions et renforcé les liens entre l’analyse des réseaux complexes et la théorie des graphes temporelsIn this thesis, we investigate iterative processes producing a flow of graphs. These processes findapplications both in complex networks and time-varying graphs. Starting from an initial configurationcalled a seed, these processes produce a continuous flow of graphs. A key question arises when theseprocesses impose no constraints on the size of the generated graphs: under what conditions can we ensurethat the graphs do not become empty? And how can we account for the changes between successive stepsof the process? To address the first question, we introduced the concept of sustainability, which verifieswhether an iterative process is likely to produce graphs with periodic behaviors. We defined and studied agraph generator that highlights the many challenges encountered when exploring this notion. Regardingthe second question, we designed a metric to quantify the changes occurring between two consecutive stepsof the process. This metric was tested on various generators as well as on real-world data, demonstratingits ability to capture the dynamics of a network, whether artificial or real. The study of these two conceptshas opened the door to many new questions and strengthened the connections between complex networkanalysis and temporal graph theory
6
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é.
7
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.
8
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. [...]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. [...]
9
Delanoue, Nicolas. "Algorithmes numériques pour l'analyse topologique : Analyse par intervalles et théorie des graphes." Phd thesis, Université d'Angers, 2006. http://tel.archives-ouvertes.fr/tel-00340999.
Full textAbstract:
Le travail présenté dans cette thèse concerne d'une part, l'étude qualitative d'ensembles et d'autre part, celui de l'étude de la stabilité d'un système dynamique. Les méthodes numériques proposées combinent le calcul par intervalles et la théorie des graphes.De nombreux problèmes, comme l'étude de l'espace des configurations d'un robot, se ramènent à une étude qualitative d'ensembles. Ici, la ``taille'' de l'ensemble importe peu, ce qui compte, c'est sa ``topologie''. Les méthodes proposées calculent des invariants topologiques d'ensembles. Les ensembles considérés sont décrits à l'aide d'inégalités $\mathcal{C}^{\infty}$. L'idée maîtresse est de décomposer un ensemble donné en parties contractiles et d'utiliser l'homologie de \v Cech.
La seconde partie de la thèse concerne l'étude de point
asymptotiquement stables des systèmes dynamiques (linéaires ou non). Plus largement, on propose une méthode pour approcher le bassin d'attraction d'un point asymptotiquement stable. Dans un premier temps, on utilise la théorie de Lyapunov et le calcul par intervalle
pour trouver effectivement un voisinage inclus dans le bassin d'attraction d'un point prouvé asymptotiquement stable. Puis, on combine, une fois de plus, la théorie des graphes et les méthodes d'intégration d'équations différentielles ordinaires pour améliorer ce voisinage et ainsi construire un ensemble inclus dans le bassin
d'attraction de ce point.
10
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éventionIn 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
11
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ésWe 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
12
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èmeA 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
13
Jahel, Camille. "Analyse des dynamiques des agroécosystèmes par modélisation spatialisée et utilisation d’images satellitaires, Cas d’étude de l’ouest du Burkina Faso." Electronic Thesis or Diss., Paris, AgroParisTech, 2016. http://www.theses.fr/2016AGPT0059.
Full textAbstract:
L’organisation des territoires ruraux d’Afrique de l’Ouest a été bouleversée ces vingt dernières années par des changements rapides, dus à un accroissement démographique sans précédent, à des politiques favorisant les cultures d’exportation et à l’introduction de nouvelles techniques culturales. On assiste aujourd’hui à une mutation des structures d’exploitation, une pression sur les ressources forestières, un épuisement des sols et une saturation de l’espace cultivé. Les tensions pour l’accès aux ressources se multiplient, faisant souvent ressurgir d’anciens conflits ethniques, et la question de la sécurité alimentaire se pose. Dans ce contexte, des systèmes d’alerte précoce ont été mis en place dans le but d’anticiper et d’endiguer l’insécurité alimentaire par l’analyse des risques de catastrophe.La thèse s’inscrit dans le cadre de ces systèmes d’alerte précoce et traite de l’étude des changements agraires et de leurs mécanismes. Elle se propose d’explorer de nouvelles pistes méthodologiques, basées à la fois sur la modélisation et la télédétection, pour réaliser une analyse rétrospective et prospective des dynamiques agraires de la province du Tuy, située à l’ouest du Burkina Faso.Nous abordons tout d’abord la question du croisement d’échelles dans les modèles de dynamiques des agroécosystèmes en développant un modèle multiscalaire des évolutions passées. Le modèle utilise les graphes d’interaction pour simuler des processus allant de l’échelle de la parcelle à l’échelle régionale (évolution des rendements, évolution des assolements, déforestation). Nous montrons ainsi qu’il est possible d’effectuer un croisement d’échelles dans un modèle sans avoir recours aux méthodes d’agrégation ou de désagrégation habituellement employées pour ce type d’étude.Le modèle est ensuite utilisé pour analyser deux aspects des dynamiques agraires de la province du Tuy. Le premier aborde les dynamiques de défriche, d’abord analysées à la lumière du débat Malthus-Boserup qui porte sur l’impact de la croissance démographique sur les ressources naturelles. Des scénarios prospectifs sont simulés et leurs conséquences sur les surfaces en végétation naturelle sont évaluées : ces scénarios simulent l’émigration d’une partie de la population vers d’autres régions, la création de zones protégées, la mise en place de politiques démographiques et la conversion progressive des systèmes de production à l’agro-écologie.Le second aspect concerne les processus décisionnels des agriculteurs pour constituer leurs assolements. L’étude consiste plus précisément à comprendre les importantes variations des surfaces allouées aux différentes cultures, observées au cours de la période étudiée, via l’analyse de l’évolution simulée du poids des différents facteurs intervenant dans la prise de décision.Dans une dernière partie, nous montrons qu’il est possible de détecter explicitement des empreintes de processus anthropiques dans les images de télédétection en utilisant les simulations multiscalaires du modèle développé. Nous réalisons ensuite une assimilation de l’information satellitaire dans le modèle, pour le ré-étalonner et ainsi renforcer ses capacités à reproduire les dynamiques ayant eu lieu. Cette dernière partie ouvre d’importantes perspectives concernant l’utilisation conjointe de l’information satellitaire et des modèles de dynamiques des agroécosystèmesRural areas of West Africa have seen notable transformations these last two decades, mainly due to high population growth, development policies in favor of export crops and introduction of new cropping practices. The results of these developments are a pressure on forestry resources, an evolution of farming systems, a depletion of soils and a saturation of cultivated areas. The number of conflicts for resources access increases, reviving buried ethnical tensions, and the question of food security is raised. In that context, early warning systems have been developed in order to foresee and curb food insecurity by the mean of hazard analyses.The present work deals with agrarian changes and their mechanisms, in the context of early warning systems development. New methodological approaches are explored, based on modeling and remote sensing in order to create a retrospective and prospective analysis of agrarian dynamics of the Tuy province, located in West Burkina Faso.We first focus on the issue of cross-scaling in agro-ecosystems dynamics models, by building a multi-scalar model of past developments. The model uses interaction graphs to simulate processes occurring from the plot scale to the regional scale (crop production, crop rotation and crop area expansion). We show that modelling across scales is achievable without resorting to methods of aggregation or disaggregation, usually applied for this type of study.The model is then used to analyze two aspects of agrarian dynamics of Tuy province. The first one deals with clearances dynamics in the context of Malthus vs Boserup debate, concerning the impacts of demographic growth on natural resources. Prospective scenarios are simulated and their consequences on natural vegetation surfaces are assessed: these scenarios simulate emigrations of a part of the population towards other areas, the implementation of protected areas, a demographic regulation and an ecological intensification of farming systems.The second aspect concerns decisional processes of farmers in order to constitute their crops rotations. The study consists in understanding the important variations of cultivated species, observed during the studied period, by analyzing the simulated weight evolution of different determining factors involved in the decisional processes.Finally, we show that anthropic processes footprints are explicitly detectable in remote sensing images, by using multi-scalar simulations of the model developed. Then, we create an assimilation of satellite data in the model in order to re-calibrate it and reinforce its abilities to reproduce past dynamics. This last part opens important perspectives concerning the joint use of remote sensing data and agro-ecosystems dynamics
14
Seifi, Massoud. "Coeurs stables de communautés dans les graphes de terrain." Paris 6, 2012. http://www.theses.fr/2012PA066058.
Full textAbstract:
Dans de nombreux contextes, des ensembles d'entités en relation peuvent être modélisés par des graphes, dans lesquels les entités individuelles sont représentées par des sommets et les relations entre ces entités par des liens. Ces graphes, que nous appellerons "graphes de terrain", peuvent être rencontrés dans le monde réel dans différents domaines tels que les sciences sociales, l'informatique, la biologie, le transport, la linguistique, etc. La plupart des graphes de terrain sont composés de sous-graphes denses faiblement inter-connectés appelés "communautés" et de nombreux algorithmes ont été proposés afin d'identifier cette structure communautaire automatiquement. Nous nous sommes intéressés dans cette thèse aux problèmes des algorithmes de détéction de communautés, notamment leur non-déterminisme et l'instabilité qui en découle. Nous avons présenté une méthodologie qui tire parti de ce non- déterminisme afin d'améliorer les résultats obtenus avec les techniques actuelles de détection de communautés. Nous avons proposé une approche basée sur le concept de communautés fortes ou "coeurs de communautés" et nous avons montré l'amélioration apportée par notre approche en l'appliquant à des graphes réels et artificiels. Nous avons aussi étudié la structure des coeurs des graphes aléatoires et nous avons montré qu'à la différence des algorithmes classiques de détection de communautés qui peuvent trouver des partitions en communautés dans des graphes n'ayant pourtant aucune structure communautaire intrinsèque, notre approche indique clairement l'absence de structure communautaire dans les graphes aléatoires et permet en ce sens de distinguer les graphes aléatoires des graphes réels. Nous avons étudié également l'évolution des coeurs dans des réseaux dynamiques via une dynamique simulée simple et contrôlable ainsi qu'une dynamique réelle. Nous avons montré que les coeurs sont beaucoup plus stables que les communautés obtenues par les techniques actuelles de détection de communautés et que notre approche peut donc pallier les défauts des méthodes stabilisées qui ont été proposées récemmentIn many contexts, sets of related entities can be modeled by graphs, in which entities are represented by nodes and relationships between these entities by edges. These graphs, which we call "complex networks", may be encountered in the real world in various fields such as social science, computer science, biology, transportation, linguistics, etc. Most complex networks are composed of dense subgraphs weakly interconnected called "communities" and many algorithms have been proposed to identify the community structure of complex networks automatically. During this thesis, we focused on the problems of community detection algorithms, especially their non-determinism and the instability that results. We presented a methodology that takes advantage of this non-determinism to improve the results obtained with current community detection techniques. We proposed an approach based on the concept of strong communities, or "community cores", and we showed the improvement made by our approach by applying it to real and artificial graphs. We also studied the structure of cores in random graphs and we showed that unlike classical community detection algorithms which can find communities in graphs with no intrinsic community structure, our approach clearly indicates the absence of community structure in random graphs and, in this way, allows to distinguish between random and real graphs. We also studied the evolution of cores in dynamical networks using a simple and controllable simulated dynamic and a real dynamic. We showed that cores are much more stable than communities obtained by current community detection techniques and our approach can overcome the disadvantages of stabilized methods that have been recently proposed
15
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.
16
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é SWAGGOur 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
17
Botterman, Hông-Lan. "Corrélations dans les graphes d'information hétérogène : prédiction et modélisation de liens à partir de méta-chemins." Electronic Thesis or Diss., Sorbonne université, 2020. http://www.theses.fr/2020SORUS083.
Full textAbstract:
De nombreuses entités possiblement de natures différentes sont reliées par des liens pouvant également être de natures différentes. De telles données peuvent être représentées par un graphe d’information hétérogène (heterogeneous information network, HIN). De plus, il existe souvent des corrélations entre entités ou événements de la vie réelle. Une fois ces derniers représentés par des abstractions appropriées telles que les HIN, les corrélations peuvent dès lors se retrouver dans ces graphes particuliers. Motivé par ces considérations, cette thèse s’intéresse aux effets des possibles corrélations entre les liens d’un HIN sur sa structure. Ce présent travail tente de répondre à des questions telles que : y a-t-il des corrélations entre les liens de différents types ? Si oui, est-il possible de les quantifier ? Que signifient-elles ? Est-ce que ces corrélations peuvent servir à prédire l’apparition de liens ? À modéliser des dynamiques de co-évolution ? Les exemples étudiés peuvent être divisés en deux catégories. Premièrement, l’utilisation des corrélations pour la prédiction du poids des liens est étudiée. Il est montré que les corrélations entre les liens, et plus particulièrement entre les chemins, peuvent être utilisées pour récupérer et prédire le poids d’autres liens, d’un type spécifié. Deuxièmement, une dynamique de poids de liens est considérée. Il est montré que la co-évolution de liens peut servir, par exemple, à définir un modèle d’attention entre individus et sujets. Les résultats préliminaires sont en accord avec d’autres présents dans la littérature, principalement relatifs aux modèles de dynamiques d’opinions. Globalement, ce travail illustre l’importance des corrélations entre les liens d’un HIN. En outre, il soutient le fait général que différents types de nœuds et liens abondent dans la nature et qu’il peut être important et instructif de prendre en compte cette diversité afin de comprendre l’organisation et le fonctionnement d’un systèmeMany entities, possibly of different natures, are linked by physical or virtual links, that may also be of different natures. Such data can be represented by a heterogeneous information network (HIN). In addition, there are often correlations between real-life entities or events. Once represented by suitable abstractions (such as HIN), these correlations can therefore be found in the HIN. Motivated by these considerations, this thesis investigates the effects of possible correlations between the links of an HIN on its structure. This present work aims at answering questions such as: are there indeed correlations between different types of links? If so, is it possible to quantify them? What do they mean? How can they be interpreted? Can these correlations be used to predict the occurrence of links? To model co-evolution dynamics? The examples studied can be divided into two categories. First, the use of correlations for the prediction of the links’ weight is studied. It is shown that correlations between links, and more specifically between paths, can be used to recover and, to some extent, predict the weight of other links of a specified type. Second, a link weight dynamics is considered. It is shown that link co-evolution can be used, for example, to define a model of attention between individuals and subjects. The preliminary results are in agreement with others in the literature, mainly related to models of opinion dynamics. Overall, this work illustrates the importance of correlations between the links of an HIN. In addition, it supports the general fact that different types of nodes and links abound in nature and that it could be important and instructive to take this diversity into account in order to understand the organization and functioning of a system
18
Mortelier, Alexis. "Οbservatοire de la tactique en (e-)spοrt cοllectif." Electronic Thesis or Diss., Normandie, 2024. http://www.theses.fr/2024NORMC245.
Full textAbstract:
Cette thèse explore les dynamiques de jeu et les performances collectives en alternant entre les analyses de sports traditionnels, comme le handball, et des e-sports, tels que DotA2 et OverWatch. L'objectif est de segmenter le processus de traitement des données en plusieurs étapes, chacune apportant une compréhension spécifique. En adoptant une approche comparative entre sport et e-sport, ce travail non seulement distingue les différentes étapes de traitement des données, mais propose également une vue d'ensemble de l'analyse du (e-)sport. La première contribution réside dans le développement de techniques de représentation des matchs de handball à l’aide de graphes dynamiques, ainsi que dans la simplification des trajectoires dans DotA2 grâce à des indices géométriques. Ces méthodes permettent une meilleure visualisation et compréhension des mouvements collectifs.La deuxième contribution se concentre sur la définition et le calcul de métriques de performance, essentielles pour l'apprentissage automatique. Des modèles d’expected goal (xG) pour le handball et des facteurs d’engagement dans OverWatch ont été élaborés pour servir de cibles aux algorithmes. La troisième contribution est la création d’un observatoire tactique dédié au handball, et l'étude des configurations géométriques dans DotA2 qui mènent à des événements clés. Ces analyses approfondissent la compréhension des tactiques qui influencent le déroulement des matchsThis thesis explores game dynamics and collective performance by alternating between analyses of traditional sports, such as handball, and e-sports, such as DotA2 and OverWatch. The aim is to segment the data processing process into several stages, each providing a specific understanding. By adopting a comparative approach between sport and e-sport, this work not only distinguishes the different stages of data processing, but also offers an overview of (e-)sport analysis. The first contribution is the development of techniques for representing handball matches using dynamic graphs, and the simplification of trajectories in DotA2 using geometric indices. The second contribution focuses on the definition and calculation of performance metrics, essential for machine learning. Expected goal (xG) models for handball and commitment factors in OverWatch have been developed as targets for algorithms. The third contribution is the creation of a tactical observatory dedicated to handball, and the study of geometric configurations in DotA2 that lead to key events. These analyses deepen our understanding of the tactics that influence the course of matches
19
Olivier, Pierre. "Modélisation et analyse du comportement dynamique d'un système d'électrolyse PEM soumis à des sollicitations intermittentes : Approche Bond Graph." Thesis, Lille 1, 2016. http://www.theses.fr/2016LIL10212/document.
Full textAbstract:
L’électrolyse est une technologie qui permet de répondre à deux problématiques cruciales. D’une part, répondre au besoin en stockage d’énergie liée à l’intégration de sources intermittentes sur les réseaux électriques. D’autre part, répondre à la croissance de la demande en hydrogène, liée aux marchés naissants de l’hydrogène énergie. La nature des besoins liés au développement de la technologie d’électrolyse implique des sollicitations intermittentes dont les impacts quant au fonctionnement du système sont encore méconnus. En ce sens, et face aux manques de la littérature quant à la modélisation à l’échelle système de la technologie d’électrolyse PEM, un nouveau modèle est développé. Pour cela, le formalisme de modélisation graphique Bond Graph est utilisé, notamment pour sa capacité à représenter tout type d’échange énergétique de manière unifiée. Le modèle développé permet de représenter l’intégralité d’un système d’électrolyse PEM, ses différents composants et lois de contrôle associées. Il est validé sur la base du comportement dynamique d’une installation semi-industrielle disponible au CEA. Ce modèle est ensuite utilisé pour identifier et comprendre les enjeux liées à une sollicitation intermittente d’un système d’électrolyse PEM d’un point de vue de l’efficacité du système, de sa flexibilité et de sa capacité de suivi de charge, de sa fiabilité, de sa sûreté ou encore de sa durabilité. Différentes modifications de conception sont simulées et évaluées à la lumière de ces différents enjeux. Finalement, le modèle Bond Graph est exploité d’un point de vue de ses propriétés structurelles afin d’analyser les conditions de surveillabilité d’un système d’électrolyse PEMPEM Electrolysis is a technology which to enable to face two major challenges : (i) Fulfill the need of energy storage caused by the integration of intermittent energy sources on electricity networks; (ii) Cope with the growing need of carbon free hydrogen caused by the future market applications of hydrogen energy. These particular needs, regarding electrolysis technology development, involve an intermittent operating mode which impacts on the dynamic behavior of the system remain unknown. Modelling is a critical tool to understand these issues and provide a thorough analysis. State of the art of existing modelling works highlighted that only a few models take into account the dynamic of the whole system including Balance of Plant. Therefore a new dynamic and multiphysic model was developed under Bond Graph formalism. This graphical modelling formalism was selected especially thanks to its ability to represent any kind of power exchange in a unified way. The model enables to represent the whole system including balance of plant and associated control laws. It is validated on the dynamic behavior of an experimental device available in CEA. The model is then used in order to identify and understand the issues related to intermittent operation of a PEM electrolysis system. These issues are related to system efficiency, flexibility, reliability, safety and durability. Regarding these issues, some design changes are simulated and assessed. Finally, the Bond Graph model and its structural properties enable to perform diagnosis and monitorability analyses of a PEM electrolysis system
20
Gautier, Jacques. "GrAPHiSTUne approche d’analyse exploratoire pour l’identification des dynamiques des phénomènes spatio-temporels." Thesis, Université Grenoble Alpes (ComUE), 2018. http://www.theses.fr/2018GREAS025/document.
Full textAbstract:
Les données permettant de décrire des phénomènes spatio-temporels sont de plus en plus nombreuses. Ces nouvelles données peuvent alors être éloignées de celles habituellement observées pour l'étude de certains phénomènes. Leur analyse, selon une approche hypothético-déductive telle qu'elle est majoritairement effectuée en statistique et dans les SIG, peut ainsi passer sous silence certaines informations insoupçonnées, mais pertinentes, sur les dynamiques de ces phénomènes spatio-temporels.Il peut alors être intéressant de simplement donner à voir les données, pour observer ce qu'elles ont à montrer, avant de les analyser. Ce principe est celui de l'analyse exploratoire: le procédé est de permettre à un utilisateur d'effectuer une exploration libre des données, au moyen de représentations visuelles, afin de mettre en lumière des structures ou des relations insoupçonnées. Aujourd'hui, l'analyse exploratoire est notamment possible au moyen d'environnements de visualisation, intégrant différentes représentations graphiques et cartographiques interactives.Les environnements de visualisation sont majoritairement développés de manière ad hoc, dans le cadre d'une thématique particulière. Or l'émergence constante de nouvelles données incite à promouvoir des méthodes d'analyse applicables à des phénomènes de différentes natures. En fonction de la problématique dans laquelle s'insèrent ces derniers, les dynamiques sur lesquelles va se focaliser l'analyse diffèrent. Analyser un phénomène météorologique dans un but de prévision implique de s’intéresser aux récurrences cycliques du phénomène. Analyser l'évolution d'une population pour la mise en place de politiques publiques implique d’analyser ce phénomène sur le temps long et selon différentes zones de l’espace.Notre objectif est de proposer une méthode d'analyse exploratoire des phénomènes spatio-temporels et de leurs dynamiques, indépendante du thème traité. Pour cela, nous proposons un environnement de géovisualisation, GrAPHiST (Géovisualisation pour l'Analyse des PHenomenes Spatio-Temporels), permettant l'analyse de différentes dynamiques, selon différentes échelles spatiales et temporelles (linéaires ou cycliques). Développer cet environnement implique de s’interroger sur la modélisation du changement dans l’espace, la nature des dynamiques spatio-temporelles à étudier, et les outils visuels et interactifs permettant de les identifier.Ainsi, les contributions de notre recherche se situent à plusieurs niveaux :- une modélisation générique des phénomènes spatio-temporels, sous la forme de séries événementielles;- de nouvelles méthodes de représentations graphiques et interactives, autorisant la recherche et l'identification des dynamiques spatio-temporelles, notamment: l'introduction de diagrammes temporels interactifs permettant la recherche visuelle de récurrences cycliques dans les données spatio-temporelles; l'utilisation de règles de symbologie permettant la visualisation des relations entre les composantes temporelle et spatiale des phénomènes; de nouvelles méthodes de représentations des agrégats d'événements proches, permettant d'identifier des structures dans leur distribution spatio-temporelle;- la formalisation d’une approche d'analyse exploratoire des dynamiques spatio-temporelles, déclinée en plusieurs scénarios selon l’objectif poursuivi.Nous validons notre approche en l'appliquant à l'analyse de différents jeux de données. L'objectif est de vérifier la possibilité d'identifier des dynamiques, relatives au temps linéaire ou cyclique, au moyen de GrAPHiST, et d'illustrer le caractère générique de l'approche, ainsi que les opportunités d'analyse offertes par l'environnementDatasets allowing the description of spatio-temporal phenomena are becoming ever more numerous. These new data can be very different from those usually observed for studying spatio-temporal phenomena. An analysis through a hypothetico-deductive approach, like is mainly done in statistic and GIS domains, can ignore some unsuspected, but relevant, information about the dynamics of these spatio-temporal phenomena.It can be interesting then, to just present the data, to observe what they have to show, before analysing them. This is the principle of the exploratory data analysis: the process is to allow a user to freely explore data, through visual representations, in order to highlight unsuspected structures or relationships. Today, exploratory analysis is possible through visualization environments, which integrate different graphic or cartographic interactive representations.Visualization environments are mainly developed in an ad hoc manner, in the context of a particular thematic field. However, the constant appearance of new data encourages promoting analysis methods, which could be applied to several types of phenomena. According to the domain related to these phenomena, the analysis will be focused on different dynamics. Analysing a meteorological phenomenon, in a forecasting purpose, implies a focus on the cyclic recurrences of the phenomenon. Analysing the increase of a population, for the purpose of deciding public policies, implies an analysis of the phenomenon on a long-term, through different spatial areas.Our objective is to propose a method for the exploratory analysis of spatio-temporal phenomena and their dynamics, which would be independent of the topic. In order to achieve this, we propose a geovisualization environment, GrAPHiST (Géovisualisation pour l'Analyse des PHenomenes Spatio-Temporels; Geovisualization for spatio-temporal phenomena analysis), allowing the analysis of several dynamics, through different spatial and temporal (linear or cyclic) scales. Developing this environment implies to focus on how spatial changes are modelled, on the nature of the spatio-temporal dynamics we have to study, and on the visual and interactive tools, which allow the identification of these dynamics.So, the contributions of our research can be found at several levels:a generic modelling approach of spatio-temporal phenomena, in the form of event series;new graphical and interactive representation methods, which allow the searching and the identification of spatio-temporal dynamics, including: the introduction of interactive temporal diagrams, which allow the visual searching of cyclic recurrences in spatio-temporal data; the use of symbology rules, which allow the visualization of relationships between the spatial and temporal components of phenomena; new methods to represent aggregated closed events, which allow to identify structures in their spatio-temporal distribution;the formalization of an exploratory approach for the spatio-temporal dynamics analysis, divided into several scenarios, according to the purpose of the analysis.We validate our proposition by applying it to the analysis of several datasets. The objective is to verify the possibility to identify dynamics, related to linear or cyclic time, through the use of GrAPHiST, and to illustrate the generic aspect of the approach, as well as the analysis opportunities given by the environment
21
Jardin, Audrey. "Contribution à une méthodologie de dimensionnement des systèmes mécatroniques : analyse structurelle et couplage à l'optimisation dynamique." Phd thesis, INSA de Lyon, 2010. http://tel.archives-ouvertes.fr/tel-00597430.
Full textAbstract:
Cette thèse s'inscrit dans le cadre de la conception de systèmes mécatroniques et traite plus spécifiquement du problème de leur dimensionnement. Dans ce sens, elle s'intéresse aux méthodes permettant de sélectionner les composants constituant leurs chaînes d'actionnement afin de satisfaire au mieux un cahier des charges donné. Puisque les lois concurrentielles actuelles demandent un renouvellement fréquent des produits malgré une complexité toujours croissante, les démarches adoptées pour traiter ce type de problème se doivent d'être les moins coûteuses en termes financiers mais aussi en termes de temps d'étude. Pour diminuer le nombre d'itérations du processus de conception, une solution possible est de reformuler le problème sous la forme d'un problème inverse où les inconnues du problème de dimensionnement sont directement calculées à partir des spécifications du cahier des charges sur les sorties du système. Dans cette optique, le laboratoire Ampère propose une méthodologie de dimensionnement par modèles bond graph inverses. L'objectif de cette thèse est de contribuer au développement de cette méthodologie d'une part dans sa phase d'analyse structurelle (phase permettant de vérifier avant toute simulation si le problème inverse est correctement posé) puis, d'autre part, dans sa phase de dimensionnement (phase durant laquelle l'inversion du modèle est effectivement mise en œuvre puis exploitée). Concernant la phase d'analyse structurelle, le mémoire s'attache à détailler les mécanismes d'une telle analyse dans le langage bond graph mais vise aussi à préciser son domaine de validité. Pour cela, une comparaison de l'approche bond graph aux approches Modelica, système structuré et modèle d'état permet de mettre en évidence l'existence de plusieurs niveaux d'information et de description sur le système. Selon l'exploitation ou non de ces différents niveaux d'information et de description, plusieurs niveaux d'analyse sont ensuite proposés : le niveau structuré, le niveau BG-structurel et le niveau comportemental. Il est également montré comment ces différents niveaux d'analyse peuvent être mis à profit dans une démarche de conception et comment ceux-ci permettent de reformuler certaines propriétés bond graph selon la phase de conception dans laquelle nous nous trouvons les propriétés au niveau d'analyse BG-structurel permettent d'infirmer ou de valider l'architecture du système). Concernant la phase de dimensionnement, le mémoire aborde le cas où le problème de dimensionnement ne peut se formuler complètement sous la forme d'un problème inverse et où la méthodologie ne peut s'appliquer directement. Pour cela, le problème de la représentation bond graph d'un problème d'optimisation dynamique est étudié afin de traiter des spécifications qui ne peuvent s'exprimer sous forme de fonctions dépendant explicitement du temps. Une procédure bond graph d'optimisation est à cette fin reprise puis étendue notamment à une classe de systèmes non linéaires. Enfin, un exemple de couplage entre méthodologie de dimensionnement et optimisation dynamique est effectivement mis en œuvre jusqu'à l'obtention de résultats numériques afin d'illustrer la faisabilité de la méthodologie tout au long du processus de conception.
22
Ren, Haolin. "Visualizing media with interactive multiplex networks." Thesis, Bordeaux, 2019. http://www.theses.fr/2019BORD0036/document.
Full textAbstract:
Les flux d’information suivent aujourd’hui des chemins complexes: la propagation des informations, impliquant éditeurs on-line, chaînes d’information en continu et réseaux sociaux, emprunte alors des chemins croisés, susceptibles d’agir sur le contenu et sa perception. Ce projet de thèse étudie l’adaptation des mesures de graphes classiques aux graphes multiplexes en relation avec le domaine étudié, propose de construire des visualisations à partir de plusieurs représentations graphiques des réseaux, et de les combiner (visualisations multi-vues synchronisées, représentations hybrides, etc.). L’accent est mis sur les modes d’interaction permettant de prendre en compte l’aspect multiplexe (multicouche) des réseaux. Ces représentations et manipulations interactives s’appuient aussi sur le calcul d’indicateurs propres aux réseaux multiplexes. Ce travail est basé sur deux jeux de données principaux: l’un est une archive de 12 ans de l’émission japonaise publique quotidienne NHK News 7, de 2001 à 2013. L’autre recense les participants aux émissions de télévision/radio françaises entre 2010 et 2015. Deux systèmes de visualisation s’appuyant sur une interface Web ont été développés pour analyser des réseaux multiplexes, que nous appelons «Visual Cloud» et «Laputa». Dans le Visual Cloud, nous définissons formellement une notion de similitude entre les concepts et les groupes de concepts que nous nommons possibilité de co-occurrence (CP). Conformément à cette définition, nous proposons un algorithme de classification hiérarchique. Nous regroupons les couches dans le réseau multiplexe de documents, et intégrons cette hiérarchie dans un nuage de mots interactif. Nous améliorons les algorithmes traditionnels de disposition de mise en forme de nuages de mots de sorte à préserver les contraintes sur la hiérarchie de concepts. Le système Laputa est destiné à l’analyse complexe de réseaux temporels denses et multidimensionnels. Pour ce faire, il associe un graphe à une segmentation. La segmentation par communauté, par attribut, ou encore par tranche temporelle, forme des vues de ce graphe. Afin d’associer ces vues avec le tout global, nous utilisons des diagrammes de Sankey pour révéler l’évolution des communautés (diagrammes que nous avons augmentés avec un zoom sémantique). Cette thèse nous permet ainsi de parcourir trois aspects (3V) des plus intéressants de la donnée et du BigData appliqués aux archives multimédia: Le Volume de nos données dans l’immensité des archives, nous atteignons des ordres de grandeurs qui ne sont pas praticables pour la visualisation et l’exploitation des liens. La Vélocité à cause de la nature temporelle de nos données (par définition). La Variété qui est un corollaire de la richesse des données multimédia et de tout ce que l’on peut souhaiter vouloir y investiguer. Ce que l’on peut retenir de cette thèse c’est que la traduction de ces trois défis a pris dans tous les cas une réponse sous la forme d’une analyse de réseaux multiplexes. Nous retrouvons toujours ces structures au coeur de notre travail, que ce soit de manière plus discrète dans les critères pour filtrer les arêtes par l’algorithme Simmelian backbone, que ce soit par la superposition de tranches temporelles, ou bien que ce soit beaucoup plus directement dans la combinaison d’indices sémantiques visuels et textuels pour laquelle nous extrayons les hiérarchies permettant notre visualisationNowadays, information follows complex paths: information propagation involving on-line editors, 24-hour news providers and social medias following entangled paths acting on information content and perception. This thesis studies the adaptation of classical graph measurements to multiplex graphs, to build visualizations from several graphical representations of the networks, and to combine them (synchronized multi-view visualizations, hybrid representations, etc.). Emphasis is placed on the modes of interaction allowing to take in hand the multiplex nature (multilayer) of the networks. These representations and interactive manipulations are also based on the calculation of indicators specific to multiplex networks. The work is based on two main datasets: one is a 12-year archive of the Japanese public daily broadcast NHK News 7, from 2001 to 2013. Another lists the participants in the French TV/radio shows between 2010 and 2015. Two visualization systems based on a Web interface have been developed for multiplex network analysis, which we call "Visual Cloud" and "Laputa". In the Visual Cloud, we formally define a notion of similarity between concepts and groups of concepts that we call co-occurrence possibility (CP). According to this definition, we propose a hierarchical classification algorithm. We aggregate the layers in a multiplex network of documents, and integrate that hierarchy into an interactive word cloud. Here we improve the traditional word cloud layout algorithms so as to preserve the constraints on the concept hierarchy. The Laputa system is intended for the complex analysis of dense and multidimensional temporal networks. To do this, it associates a graph with a segmentation. The segmentation by communities, by attributes, or by time slices, forms views of this graph. In order to associate these views with the global whole, we use Sankey diagrams to reveal the evolution of the communities (diagrams that we have increased with a semantic zoom). This thesis allows us to browse three aspects of the most interesting aspects of the data miming and BigData applied to multimedia archives: The Volume since our archives are immense and reach orders of magnitude that are usually not practicable for the visualization; Velocity, because of the temporal nature of our data (by definition). The Variety that is a corollary of the richness of multimedia data and of all that one may wish to want to investigate. What we can retain from this thesis is that we met each of these three challenges by taking an answer in the form of a multiplex network analysis. These structures are always at the heart of our work, whether in the criteria for filtering edges using the Simmelian backbone algorithm, or in the superposition of time slices in the complex networks, or much more directly in the combinations of visual and textual semantic indices for which we extract hierarchies allowing our visualization
23
Guezzi, Abdelhak. "Modélisation, analyse de performance et commande des systèmes à événements discrets." Phd thesis, Université d'Angers, 2010. http://tel.archives-ouvertes.fr/tel-00730500.
Full textAbstract:
Ce mémoire porte sur la modélisation et l'analyse de réseaux de Petri de type Graphes d' Événements (GE) temporises et temporels, au moyen d'outils algébriques utilisée dans l'algèbre conventionnelle. La modélisation mathématique de ces systèmes dynamiques a événements discrets (SDED) conduit a une écriture polyédrale de la forme A:x b, o u x est un vecteur de dates. Nous donnons une technique algébrique permettant d'exprimer les trajectoires au plus tôt et réalisons une synthèse de la commande sous le critère classique de juste- a-temps d'un GE temporise. On utilise les concepts d'ordre composante par composante, de demi-treillis et d'inégalités monotones. Nous analysons la performance d'un graphe d'événements p-temporels, cette analyse se réduit a un problème de la programmation linéaire dont l'objectif est de calculer la valeur maximale et minimale du temps de cycle d'un graphe d'événements P-temporels. Dans une autre partie, nous constituons un modèle entrées/sorties dont le fonctionnement est proche de celui de l'équation d'état de l'automatique classique. Ensuite, en appliquant une formulation de la programmation linéaire, on calcule la trajectoire au plus tôt et au plus tard en utilisant une fonction objectif. Enfin, nous considérons le problème de la poursuite de trajectoire sur un horizon glissant.
24
Yazman, Atilla. "Modélisation des robots flexibles par les Bond-Graphs : application à l'analyse de leurs performances dynamiques." Paris 11, 1988. http://www.theses.fr/1988PA112106.
Full textAbstract:
Ce mémoire constitue une contribution à la modélisation des robots flexibles. Dans le but d'aborder ces systèmes pluridisciplinaires avec une perception unitaire, la technique des Bond-Graphs a été utilisée. Les différents domaines énergétiques abordés dans ce travail sont ainsi décrits d'une façon unifiée. Toutefois, pour modéliser le comportement dynamique des segments flexibles, une extension de l'application des Multibond-Graphs à ces systèmes a été développée en utilisant différentes méthodes d'analyse des structures. Après avoir présenté dans le premier chapitre une analyse des travaux les plus pertinents sur la modélisation des robots flexibles, il est proposé dans le second chapitre une méthode reposant sur la technique des Bond-Graphs et la technique d'analyse modale. Basés sur les deux formes duales des équations de Hamilton d'une poutre de Bernoulli, deux modèles en petits déplacements de segment flexible non contraint sont présentés. L'extension de cette approche à l'analyse des couplages énergétiques entre les petits déplacements et les grands déplacements d'une part, et entre les petits déplacements dans les deux plans perpendiculaires de segment flexible d'autre part, est ensuite proposée dans le troisième chapitre. Dans le cas où sa rigidité structurale est prédominante, les modèles en grands déplacements de segment flexible non contraint sont proposés en utilisant les méthodes des modes statiques, d'analyse modale et les éléments finis. La méthode d'analyse modale étant très sensible aux contraintes géométriques et dynamiques pouvant être imposées au système, les procédures de déduction des modèles approchés de segment flexible contraint à partir du modèle générique correspondant à son état non contraint sont étudiées dans le quatrième chapitre. En vue d'améliorer la précision des modèles approchés ainsi obtenus, la méthode de synthèse modale couramment utilisée pour les modèles en éléments finis est étendue aux modèles en analyse modale. Le chapitre cinq est consacré à l'analyse comparative des procédures de construction récursive des modèles dynamiques de segment flexible à section variable et correspondant à la méthode des éléments finis et à la méthode d'analyse modale. L'incorporation de ces modèles dans les procédures de modélisation par les Multibond-Graphs des robots rigides est discutée. Les modèles développés ont été utilisés dans le sixième chapitre en vue d'analyser les performances dynamiques d'un robot hydraulique en phase de conception. L'extension de la méthode de double décomposition modale aux modèles en Bond-Graph comportant des non linéarités, dues exclusivement au repère tournant est proposée en vue de réduire la complexité du modèle global. En annexe de robot incluant de ce chapitre un exemple d'une procédure de conception à la fois l'architecture mécanique et la structure de commande est présenté.
25
Canu, Maël. "Détection de communautés orientée sommet pour des réseaux mobiles opportunistes sociaux." Thesis, Paris 6, 2017. http://www.theses.fr/2017PA066378/document.
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é SWAGGOur 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
26
Chatti, Nizar. "Contribution à la supervision des systèmes dynamiques à base des bond graph signés." Thesis, Lille 1, 2013. http://www.theses.fr/2013LIL10124/document.
Full textAbstract:
Les travaux présentés dans ce mémoire concernent l'étude du diagnostic de défauts simples et multiples pour des systèmes dynamiques continus et consistent à développer une stratégie de diagnostic globale pour la gestion des modes de fonctionnement en situations normale et anormale. Nous avons d'abord développé un nouveau formalisme graphique de modélisation des systèmes dynamiques émanant des BG et que nous avons appelé le BGS. Ce formalisme est très aisément interprétable grâce à un certain nombre de propriétés et de définitions que nous avons établies. L'élaboration d'un tel formalisme permet de faire appel aux propriétés structurelles et causales du BG et d'élargir leur champ d'étude pour inclure le raisonnement qualitatif. Nous avons ensuite proposé un modèle générique permettant d'intégrer les modèles Génériques de Composants (MGC) fonctionnels et les modèles BGS pour la gestion, par un automate fini, des modes de fonctionnement et des conditions de reconfiguration d'un système autonome. Enfin, nous avons proposé une méthode de diagnostic des défauts simples et multiples en utilisant une approche par abduction basée sur l'étude de la propagation de défauts sur le BGS à partir des observations. La méthodologie proposée est validée par deux systèmes de complexité différente et en l'occurrence une pile à combustible à membrane échangeuse de protons et un système électromécanique d'un véhicule électriqueThe work presented in this paper deals with the diagnosis of single and multiple faults for continuous dynamic systems. It consists on developing a global diagnosis strategy for the operating modes management in both normal and abnormal situations. We first developed a new graphical formalism for dynamic system modelling. This formalism is emanating from the BG methodology and it is called Signed Bond Graph (SBG). This latter is easily understandable by a number of properties and definitions that we have established. The development of such formalism allows to use structural and causal properties of the BG and to expand its scope to include qualitative reasoning. Furthermore, we proposed a generic model for integrating functional Generic Component Models(GCM) and SBG models for the management of operating modes and reconfiguration conditions of an autonomous system using a finite automaton. Finally, we proposed a method for diagnosing both single and multiple faults using an abduction approach based on the faults propagation within the SBG by starting from a set of observations. The proposed methodology is validated by two different systems namely a proton exchange membrane fuel cell and an electromechanical system of an electric vehicle
27
Wilmet, Audrey. "Détection d'anomalies dans les flots de liens : combiner les caractéristiques structurelles et temporelles." Electronic Thesis or Diss., Sorbonne université, 2019. http://www.theses.fr/2019SORUS402.
Full textAbstract:
Un flot de liens est un ensemble de liens {(t,u,v)} dans lequel un triplet (t,u,v) modélise l'interaction entre deux entités u et v à l'instant t. Dans de nombreuses situations, les données résultent de la mesure des interactions entre plusieurs millions d'entités au cours du temps et peuvent ainsi être étudiées grâce au formalisme des flots de liens. C'est le cas des appels téléphoniques, des échanges d'e-mails, des transferts d'argent, des contacts entre individus, du trafic IP, des achats en ligne, et bien d'autres encore. L'objectif de cette thèse est la détection d'ensembles de liens anormaux dans un flot de liens. Dans une première partie, nous concevons une méthode qui construit différents contextes, un contexte étant un ensemble de caractéristiques décrivant les circonstances d'une anomalie. Ces contextes nous permettent de trouver des comportements inattendus pertinents, selon plusieurs dimensions et perspectives. Dans une seconde partie, nous concevons une méthode permettant de détecter des anomalies dans des distributions hétérogènes dont le comportement est constant au cours du temps, en comparant une séquence de distributions hétérogènes similaires. Nous appliquons nos outils méthodologiques à des interactions temporelles provenant de retweets sur Twitter et de trafic IP du groupe MAWIA link stream is a set of links {(t, u, v)} in which a triplet (t, u, v) models the interaction between two entities u and v at time t. In many situations, data result from the measurement of interactions between several million of entities over time and can thus be studied through the link stream's formalism. This is the case, for instance, of phone calls, email exchanges, money transfers, contacts between individuals, IP traffic, online shopping, and many more. The goal of this thesis is the detection of sets of abnormal links in a link stream. In a first part, we design a method that constructs different contexts, a context being a set of characteristics describing the circumstances of an anomaly. These contexts allow us to find unexpected behaviors that are relevant, according to several dimensions and perspectives. In a second part, we design a method to detect anomalies in heterogeneous distributions whose behavior is constant over time, by comparing a sequence of similar heterogeneous distributions. We apply our methodological tools to temporal interactions coming from retweets of Twitter and IP traffic of MAWI group
28
Lebert, Didier. "Essais sur la structure et la dynamique du capitalisme contemporain et de la division internationale du travail." Paris 1, 2010. http://www.theses.fr/2010PA010067.
Full textAbstract:
Cette thèse sur travaux articule six publications en deux parties. La première partie traite de l'hypothèse du capitalisme cognitif. En privilégiant une lecture néo-marxiste de la dynamique du système économique capitaliste, nous avons retracé à grands traits la trajectoire historique conduisant de la crise du capitalisme industriel à l'émergence d'un nouveau " système historique d'accumulation " caractérisé par le développement d'une économie fondée sur la connaissance, développement contraint par les stratégies d'appropriation et de valorisation mises en oeuvre par le capital. Nous avons repéré les facteurs à l'origine de la crise du capitalisme industriel, la logique d'organisation du capitalisme cognitif et certaines des tensions économiques et sociales qui la traversent. La deuxième partie de la thèse traite quant à elle plus précisément des transformations contemporaines de la division internationale du travail. Nous avons proposé de nouveaux outils structuraux issus de la théorie des graphes d'influence pour analyser la topologie évolutive du commerce international sur longue période, appliqués dans ce travail aux seules marchandises industrielles. Ces nouveaux indicateurs, qui permettent de cartographier des réseaux « complexes» (c'est-à-dire à la fois orientés, pondérés et multiplexes ), partitionnent la structure des échanges en fonction de interdépendances commerciales, mesurent la centralité d'un pays ou d'un secteur dans ce commerce en adoptant différents points de vue, et mesurent également les contributions des pays et des secteurs à ces scores de centralité. Nous en déduisons les caractéristiques d'un « espace international des produits » permettant de situer les spécialisations industrielles des nations et leurs évolutions.
29
Zreik, Rawya. "Analyse statistique des réseaux et applications aux sciences humaines." Thesis, Paris 1, 2016. http://www.theses.fr/2016PA01E061/document.
Full textAbstract:
Depuis les travaux précurseurs de Moreno (1934), l’analyse des réseaux est devenue une discipline forte, qui ne se limite plus à la sociologie et qui est à présent appliquée à des domaines très variés tels que la biologie, la géographie ou l’histoire. L’intérêt croissant pour l’analyse des réseaux s’explique d’une part par la forte présence de ce type de données dans le monde numérique d’aujourd’hui et, d’autre part, par les progrès récents dans la modélisation et le traitement de ces données. En effet, informaticiens et statisticiens ont porté leurs efforts depuis plus d’une dizaine d’années sur ces données de type réseau en proposant des nombreuses techniques permettant leur analyse. Parmi ces techniques on note les méthodes de clustering qui permettent en particulier de découvrir une structure en groupes cachés dans le réseau. De nombreux facteurs peuvent exercer une influence sur la structure d’un réseau ou rendre les analyses plus faciles à comprendre. Parmi ceux-ci, on trouve deux facteurs importants: le facteur du temps, et le contexte du réseau. Le premier implique l’évolution des connexions entre les nœuds au cours du temps. Le contexte du réseau peut alors être caractérisé par différents types d’informations, par exemple des messages texte (courrier électronique, tweets, Facebook, messages, etc.) échangés entre des nœuds, des informations catégoriques sur les nœuds (âge, sexe, passe-temps, Les fréquences d’interaction (par exemple, le nombre de courriels envoyés ou les commentaires affichés), et ainsi de suite. La prise en considération de ces facteurs nous permet de capturer de plus en plus d’informations complexes et cachées à partir des données. L’objectif de ma thèse été de définir des nouveaux modèles de graphes aléatoires qui prennent en compte les deux facteurs mentionnés ci-dessus, afin de développer l’analyse de la structure du réseau et permettre l’extraction de l’information cachée à partir des données. Ces modèles visent à regrouper les sommets d’un réseau en fonction de leurs profils de connexion et structures de réseau, qui sont statiques ou évoluant dynamiquement au cours du temps. Le point de départ de ces travaux est le modèle de bloc stochastique (SBM). Il s’agit d’un modèle de mélange pour les graphiques qui ont été initialement développés en sciences sociales. Il suppose que les sommets d’un réseau sont répartis sur différentes classes, de sorte que la probabilité d’une arête entre deux sommets ne dépend que des classes auxquelles ils appartiennentOver the last two decades, network structure analysis has experienced rapid growth with its construction and its intervention in many fields, such as: communication networks, financial transaction networks, gene regulatory networks, disease transmission networks, mobile telephone networks. Social networks are now commonly used to represent the interactions between groups of people; for instance, ourselves, our professional colleagues, our friends and family, are often part of online networks, such as Facebook, Twitter, email. In a network, many factors can exert influence or make analyses easier to understand. Among these, we find two important ones: the time factor, and the network context. The former involves the evolution of connections between nodes over time. The network context can then be characterized by different types of information such as text messages (email, tweets, Facebook, posts, etc.) exchanged between nodes, categorical information on the nodes (age, gender, hobbies, status, etc.), interaction frequencies (e.g., number of emails sent or comments posted), and so on. Taking into consideration these factors can lead to the capture of increasingly complex and hidden information from the data. The aim of this thesis is to define new models for graphs which take into consideration the two factors mentioned above, in order to develop the analysis of network structure and allow extraction of the hidden information from the data. These models aim at clustering the vertices of a network depending on their connection profiles and network structures, which are either static or dynamically evolving. The starting point of this work is the stochastic block model, or SBM. This is a mixture model for graphs which was originally developed in social sciences. It assumes that the vertices of a network are spread over different classes, so that the probability of an edge between two vertices only depends on the classes they belong to
30
Manouvrier, Jean-François. "Méthode de décomposition pour résoudre des problèmes combinatoires sur les graphes." Compiègne, 1998. http://www.theses.fr/1998COMP1152.
Full textAbstract:
Les travaux de cette thèse utilisent une méthode de décomposition pour résoudre des problèmes combinatoires NP-difficiles énoncés sous la forme de problèmes de graphes. Parmi les méthodes exactes existantes, les méthodes utilisant une décomposition-arbre du graphe permettent de résoudre certains problèmes NP-difficiles en temps polynomial pour un graphe de largeur-arbre inferieur à K. K est une constante fixée en fonction du problème et des capacités de la machine utilisée. Nous nommons ces méthodes de programmation dynamique : méthodes de décomposition. Dans cette thèse, nous utilisons une décomposition-chemin du graphe, basée sur une numérotation linéaire des sommets du graphe, pour résoudre certains problèmes NP-difficiles. Les problèmes que nous avons ainsi traites sont les problèmes de la fiabilité des réseaux (fiabilité tous-terminaux et fiabilité 2-arête-connexe tous-terminaux), le problème du voyageur de commerce et le problème de l'arbre de Steiner minimal. Pour chacun de ces problèmes, nous étudions les autres méthodes existantes, nous démontrons que la méthode de décomposition peut être appliquée, en modélisant des classes d'équivalences regroupant des solutions partielles, et nous analysons l'implémentation de ces méthodes. Une des difficultés essentielles de l'implémentation des programmes de décomposition consiste à gérer efficacement en mémoire les classes. Pour la fiabilité 2-arête-connexe tous-terminaux, la structure des classes nous a contraints à introduire un concept de forêts fictives et à développer un algorithme énumérant ces forêts. Nous obtenons ainsi des algorithmes de décomposition résolvant ces problèmes, dont les complexités en temps sont linéaires en fonction de la taille du graphe pour des graphes de largeur-chemin bornée.
31
El, Feki Mariem. "Analyse et synthèse de tolérance pour la conception et le dimensionnement des systèmes mécatroniques." Phd thesis, Ecole Centrale de Lyon, 2011. http://tel.archives-ouvertes.fr/tel-00688247.
Full textAbstract:
Cette thèse s'inscrit dans le cadre de la conception des systèmes mécatroniques et porte, plus particulièrement, sur le dimensionnement de chaînes d'actionnement et les méthodes à mettre en œuvre pour satisfaire le cahier des charges et réduire au mieux le temps de développement. Afin de suivre l'évolution du marché et faire face à la concurrence croissante, les concepteurs ont eu recours au cycle de conception en Vet au prototypage virtuel. Pour réduire davantage la durée du processus de conception, la formulation du problème de conception sous la forme d'un problème inverse est une solution intéressante. Dans ce contexte, le laboratoire Ampère propose une méthodologie de dimensionnement par modèles bond graph inverses. Ainsi, l'objectif de cette thèse est de contribuer au développement de cette méthodologie d'une part dans sa phase de vérification de l'adéquation des spécifications du cahier des charges à la structure retenue pour le modèle de conception et, d'autre part, par la prise en compte des tolérances dans le problème de conception. Pour la phase de vérification de l'adéquation spécifications/structure, le mémoire présente tout d'abord, l'analyse structurelle du cahier des charges qui permet de vérifier, avant toute simulation et à partir du modèle bond graph, si le problème de conception par modèle inverse est bien posé. Différents niveaux d'analyse sont supposés pour renforcer la démarche chronologique du travail de conception ou de reconception proposée par la méthodologie de dimensionnement. Ensuite, ces niveaux d'analyse sont mis à profit pour définir une procédure de vérification de l'adéquation des spécifications, définies sous forme de comportements type, au modèle de conception. En cas d'inadéquation, des recommandations pour la remise en question des spécifications ou de la structure du modèle de conception sont proposées et ce, selon le niveau d'analyse considéré. Au niveau de l'analyse numérique (le niveau d'analyse le plus bas), cette procédure peut être utilisée pour la synthèse paramétrique ou encore pour la synthèse de tolérance en cas de prise en compte des incertitudes dans le problème de conception. Concernant cet aspect, le mémoire présente également une contribution à la représentation des incertitudes paramétriques dans le formalisme bond graph, formalisme de base de la méthodologie de dimensionnement. Enfin, l'approche probabiliste est utilisée pour la modélisation des incertitudes dans la démarche de dimensionnement des systèmes dynamiques par inversion des modèles bond graph : les deux cas d'inversion, entrées/sorties d'une part (pour la remontée de spécifications), et paramètres/sorties d'autre part (pour la synthèse de tolérances paramétriques), sont abordés. Les règles d'exploitation d'un modèle bond graph probabiliste permettant la propagation des fonctions de densité de probabilité et des grandeurs caractéristiques(espérance et variance) tout le long de la structure énergétique du système sont proposées et illustrées par un exemple.
32
Corneli, Marco. "Dynamic stochastic block models, clustering and segmentation in dynamic graphs." Thesis, Paris 1, 2017. http://www.theses.fr/2017PA01E012/document.
Full textAbstract:
Cette thèse porte sur l’analyse de graphes dynamiques, définis en temps discret ou continu. Nous introduisons une nouvelle extension dynamique du modèle a blocs stochastiques (SBM), appelée dSBM, qui utilise des processus de Poisson non homogènes pour modéliser les interactions parmi les paires de nœuds d’un graphe dynamique. Les fonctions d’intensité des processus ne dépendent que des classes des nœuds comme dans SBM. De plus, ces fonctions d’intensité ont des propriétés de régularité sur des intervalles temporels qui sont à estimer, et à l’intérieur desquels les processus de Poisson redeviennent homogènes. Un récent algorithme d’estimation pour SBM, qui repose sur la maximisation d’un critère exact (ICL exacte) est ici adopté pour estimer les paramètres de dSBM et sélectionner simultanément le modèle optimal. Ensuite, un algorithme exact pour la détection de rupture dans les séries temporelles, la méthode «pruned exact linear time» (PELT), est étendu pour faire de la détection de rupture dans des données de graphe dynamique selon le modèle dSBM. Enfin, le modèle dSBM est étendu ultérieurement pour faire de l’analyse de réseau textuel dynamique. Les réseaux sociaux sont un exemple de réseaux textuels: les acteurs s’échangent des documents (posts, tweets, etc.) dont le contenu textuel peut être utilisé pour faire de la classification et détecter la structure temporelle du graphe dynamique. Le modèle que nous introduisons est appelé «dynamic stochastic topic block model» (dSTBM)This thesis focuses on the statistical analysis of dynamic graphs, both defined in discrete or continuous time. We introduce a new extension of the stochastic block model (SBM) for dynamic graphs. The proposed approach, called dSBM, adopts non homogeneous Poisson processes to model the interaction times between pairs of nodes in dynamic graphs, either in discrete or continuous time. The intensity functions of the processes only depend on the node clusters, in a block modelling perspective. Moreover, all the intensity functions share some regularity properties on hidden time intervals that need to be estimated. A recent estimation algorithm for SBM, based on the greedy maximization of an exact criterion (exact ICL) is adopted for inference and model selection in dSBM. Moreover, an exact algorithm for change point detection in time series, the "pruned exact linear time" (PELT) method is extended to deal with dynamic graph data modelled via dSBM. The approach we propose can be used for change point analysis in graph data. Finally, a further extension of dSBM is developed to analyse dynamic net- works with textual edges (like social networks, for instance). In this context, the graph edges are associated with documents exchanged between the corresponding vertices. The textual content of the documents can provide additional information about the dynamic graph topological structure. The new model we propose is called "dynamic stochastic topic block model" (dSTBM).Graphs are mathematical structures very suitable to model interactions between objects or actors of interest. Several real networks such as communication networks, financial transaction networks, mobile telephone networks and social networks (Facebook, Linkedin, etc.) can be modelled via graphs. When observing a network, the time variable comes into play in two different ways: we can study the time dates at which the interactions occur and/or the interaction time spans. This thesis only focuses on the first time dimension and each interaction is assumed to be instantaneous, for simplicity. Hence, the network evolution is given by the interaction time dates only. In this framework, graphs can be used in two different ways to model networks. Discrete time […] Continuous time […]. In this thesis both these perspectives are adopted, alternatively. We consider new unsupervised methods to cluster the vertices of a graph into groups of homogeneous connection profiles. In this manuscript, the node groups are assumed to be time invariant to avoid possible identifiability issues. Moreover, the approaches that we propose aim to detect structural changes in the way the node clusters interact with each other. The building block of this thesis is the stochastic block model (SBM), a probabilistic approach initially used in social sciences. The standard SBM assumes that the nodes of a graph belong to hidden (disjoint) clusters and that the probability of observing an edge between two nodes only depends on their clusters. Since no further assumption is made on the connection probabilities, SBM is a very flexible model able to detect different network topologies (hubs, stars, communities, etc.)
33
Jha, Mayank Shekhar. "Diagnostic et Pronostic de Systèmes Dynamiques Incertains dans un contexte Bond Graph." Thesis, Ecole centrale de Lille, 2015. http://www.theses.fr/2015ECLI0027/document.
Full textAbstract:
Cette thèse développe des approches pour le diagnostic et le pronostic de systèmes dynamiques incertains en utilisant la technique de modélisation Bond Graph (BG). Tout d'abord, une représentation par intervalles des incertitudes paramétriques et de mesures est intégrée à un modèle BG-LFT (Linear Fractional Transformation). Une méthode de détection robuste de défaut est développée en utilisant les règles de l'arithmétique d'intervalle pour la génération de seuils robustes et adaptatifs sur les résidus nominaux. La méthode est validée en temps réel sur un système de générateur de vapeur.Deuxièmement, une nouvelle méthodologie de pronostic hybride est développée en utilisant les Relations de Redondance Analytique déduites d'un modèle BG et les Filtres Particulaires. Une estimation de l'état courant du paramètre candidat pour le pronostic est obtenue en termes probabilistes. La prédiction de la durée de vie résiduelle est atteinte en termes probabilistes. Les incertitudes associées aux mesures bruitées, les conditions environnementales, etc. sont gérées efficacement. La méthode est validée en temps réel sur un système mécatronique incertain.Enfin, la méthodologie de pronostic développée est mise en œuvre et validée pour le suivi efficace de la santé d'un sous-système électrochimique d’une pile à combustible à membrane échangeuse de protons (PEMFC) industrielle à l’aide de données de dégradation réellesThis thesis develops the approaches for diagnostics and prognostics of uncertain dynamic systems in Bond Graph (BG) modeling framework. Firstly, properties of Interval Arithmetic (IA) and BG in Linear Fractional Transformation, are integrated for representation of parametric and measurement uncertainties on an uncertain BG model. Robust fault detection methodology is developed by utilizing the rules of IA for the generation of adaptive interval valued thresholds over the nominal residuals. The method is validated in real time on an uncertain and highly complex steam generator system.Secondly, a novel hybrid prognostic methodology is developed using BG derived Analytical Redundancy Relationships and Particle Filtering algorithms. Estimations of the current state of health of a system parameter and the associated hidden parameters are achieved in probabilistic terms. Prediction of the Remaining Useful Life (RUL) of the system parameter is also achieved in probabilistic terms. The associated uncertainties arising out of noisy measurements, environmental conditions etc. are effectively managed to produce a reliable prediction of RUL with suitable confidence bounds. The method is validated in real time on an uncertain mechatronic system.Thirdly, the prognostic methodology is validated and implemented on the electrical electro-chemical subsystem of an industrial Proton Exchange Membrane Fuel Cell. A BG of the latter is utilized which is suited for diagnostics and prognostics. The hybrid prognostic methodology is validated, involving real degradation data sets
34
Gonzalez, Vieyra Joel Abraham. "Estimation et Contrôle des Systèmes Dynamiques à Entrées Inconnues et Energies Renouvelables." Thesis, Ecole centrale de Lille, 2019. http://www.theses.fr/2019ECLI0012/document.
Full textAbstract:
De nos jours, les processus industriels se doivent d’être efficaces, en particulier au niveau de leur production et/ou consommation énergétique.Ce travail vise à améliorer l’efficacité des processus en analysant l’influence des perturbations sur leur comportement, de la phase de conception à la synthèse des contrôleurs/observateurs, ceci dans une approche intégrée.Le problème du Rejet de Perturbation est introduit ainsi que différents types de contrôles permettant d’atténuer et/ou rejeter ces perturbations. Le système de Barre de Torsion est présenté. Une loi de commande basée sur le concept d’état dérivé est présentée et ensuite validée avec comme application le rejet de perturbation. Il est nécessaire d’estimer les grandeurs physiques utilisées dans les différentes expressions de loi de commande. Un observateur à entrées inconnues basé sur la représentation bond graph est rappelé et ensuite étendu au cas multi-variable. C’est la première contribution théorique de ce travail de recherche.Nous comparons ensuite l’efficacité de différentes techniques de commandes pour le rejet de perturbation par simulation sur le système barre de torsion et analysons ainsi l’efficacité de la technique proposée. Une extension théorique au problème du découplage entrée-sortie nous permet de généraliser le problème du rejet de perturbation dans une même démarche intégrée d’analyse et de synthèse. Enfin, ces techniques sont exploitées et analysées sur le système réel. Nous validons ainsi expérimentalement nos résultats.Un modèle très simplifié de centrale hydroélectrique est développé afin d’appliquer les résultats de nos travaux. Un modèle bond graph simplifié est validé par simulationNowadays, industrial processes must be efficient, particularly at the production level and/or energy consumption.This research work aims at improving the process efficiency by analysing the influences of disturbances on their behaviour, from the conception phase to the synthesis of controller/observer, in an integrated approach.The disturbance rejection problem is first introduced as well as different control laws allowing attenuate/reject these disturbances. A control law based on the concept of derivative state variable is presented and validated while applied as disturbance rejection.In order to reject the disturbance, different physical variables must be estimated, such as state variables, derivative state variables as disturbance variables. An unknown input observer based on the bond graph representation is recalled and extended in the multivariable case. It is the first theoretical contribution of this work.We thus compare the efficiency of different so-called «modern control laws» for the disturbance rejection problems by simulation with the Torsion-Bar system example. We analyse the efficiency of our approach. One extension to the Input-Output decoupling problem allows us to extend the disturbance rejection problem to other control law type in an integrated approach. At least, these techniques are applied on the real Torsion-Bar system and compared. We validate our approach.Since this work aims at analysing and developing efficient control laws for industrial processes, a simplified model of a hydroelectric plant is developed, in order to apply our results. A simplified bond graph model is validated with simulations
35
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.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.
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.
36
Venant, Fabienne. "Représentation et calcul dynamique du sens : exploration du lexique adjectival du français." Phd thesis, Ecole des Hautes Etudes en Sciences Sociales (EHESS), 2006. http://tel.archives-ouvertes.fr/tel-00067902.
Full textAbstract:
Ce travail de thèse présente un modèle de construction du sens d'un genre nouveau, défini dans le cadre des mathématiques du continu. Le langage y est vu comme un système morphodynamique, obéissant aux principes de base de la Gestalttheorie. Les unités linguistiques découpent leur sens dans un espace sémantique possédant une structure de variété différentiable. Nous avons implémenté ce modèle et l'avons testé sur le lexique adjectival français. Une méthode de construction automatique des espaces sémantiques, reposant sur l'analyse d'un graphe de synonymie, permet d'explorer le lexique adjectival dans son ensemble, ou de construire des espaces locaux. Les espaces sémantiques locaux servent de base à une méthode dynamique de calcul du sens, permettant de prendre en compte les différents facteurs de polysémie adjectivale. L'utilisation des espaces sémantiques globaux ouvre de belles perspectives, tant dans le domaine du calcul du sens que celui de l'exploration de graphes petit monde.
37
Bougueroua, Sana. "Caractérisation de structures explorées dans les simulations de dynamique moléculaire." Thesis, Université Paris-Saclay (ComUE), 2017. http://www.theses.fr/2017SACLV099/document.
Full textAbstract:
L’objectif de cette thèse est d’analyser et prédire les conformations d’un système moléculaire en combinant la théorie des graphes et la chimie computationnelle.Dans le cadre des simulations de dynamique moléculaire, une molécule peut avoir une ou plusieurs conformations au cours du temps. Dans les trajectoires de simulation de dynamique moléculaire, on peut avoir des trajectoires n’explorant qu’une seule conformation ou des trajectoires explorant plusieurs conformations, donc plusieurs transitions entre conformations sont observées. L’exploration de ces conformations dépend du temps de la simulation et de l'énergie (température) fixée dans le système. Pour avoir une bonne exploration des conformations d’un système moléculaire, il faut générer et analyser plusieurs trajectoires à différentes énergies. Notre objectif est de proposer un algorithme universel qui permet d’analyser la dynamique conformationnelle de ces trajectoires d’une façon rapide et automatique. Les trajectoires fournissent les positions cartésiennes des atomes du système moléculaire à des intervalles de temps réguliers. Chaque intervalle contenant un ensemble de positions est appelé image. L’algorithme utilise des règles de géométrie (distances, angles, etc.) sur les positions pour trouver les liaisons (liaisons covalentes, liaisons hydrogène et interactions électrostatiques) créées entre les atomes, permettant par la suite d’obtenir le graphe mixte qui modélise une conformation. Nous ne considérons un changement conformationnel que s’il y a un changement dans les liaisons calculées à partir des positions données. L’algorithme permet de donner l’ensemble des conformations explorées sur une ou plusieurs trajectoires, la durée d’exploration de chaque conformation, ainsi que le graphe de transitions qui contient tous les changements conformationnels observés.Les conformations se caractérisent par une énergie appelée énergie potentielle. Cette énergie est représentée par une courbe appelée surface d’énergie potentielle. En chimie théorique et computationnelle, certains s’intéressent à trouver des points particuliers sur cette surface. Il s'agit des minima qui représentent les conformations les plus stables et des maxima ou états de transition qui représentent les points de passage d'une conformation à une autre. En effet, d'une part, la conformation la plus stable est celle de plus basse énergie. D'autres part, pour aller d’une conformation à une autre il faut une énergie supplémentaire, le point maximum représente l'état de transition. Les méthodes développées pour calculer ces points nécessitent une connaissance de l’énergie potentielle ce qui est coûteux en temps et en calculs. Notre objectif est de proposer une méthode alternative en utilisant des mesures ah doc basées sur des propriétés des graphes qu’on a utilisées dans le premier algorithme et sans faire appel à la géométrie ni aux calculs moléculaires. Ces mesures permettent de générer des conformations avec un classement énergétique ainsi de définir le coût énergétique de chaque transition permise. Les conformations possibles avec les transitions représentent respectivement les sommets et les arcs de ce qu’on appelle le “graphe des possibles”. Les hypothèses utilisées dans le modèle proposé est que seules les liaisons hydrogène peuvent changer entre les conformations et que le nombre de liaisons hydrogène présentes dans le système permet de déterminer son coût énergétique.L’algorithme d'analyser des trajectoires a été testé sur trois types de systèmes moléculaires en phase gazeuse de taille et de complexité croissantes. Bien que la complexité théorique de l’algorithme est exponentielle (tests d’isomorphisme) les résultats ont montré que l’algorithme est rapide (quelques secondes). De plus, cet algorithme peut être facilement adapté et appliqué à d’autres systèmes. Pour la prédiction conformationnelle, le modèle proposé a été testé sur des peptides isolésThis PhD is part of transdisciplinary works, combining graph theory and computational chemistry.In molecular dynamics simulations, a molecular system can adopt different conformations over time. Along a trajectory, one conformation or more can thus be explored. This depends on the simulation time and energy within the system. To get a good exploration of the molecular conformations, one must generate and analyse several trajectories (this can amount to thousands of trajectories). Our objective is to propose an automatic method that provides rapid and efficient analysis of the conformational dynamics explored over these trajectories. The trajectories of interest here are in cartesian coordinates of the atoms that constitute the molecular system, recorded at regular time intervals (time-steps). Each interval containing a set of positions is called a snapshot. At each snapshot, our developed algorithm uses geometric rules (distances, angles, etc.) to compute bonds (covalent bonds, hydrogen bonds and any other kind of intermolecular criterium) formed between atoms in order to get the mixed graph modelling one given conformation. Within our current definitions, a conformational change is characterized by either a change in the hydrogen bonds or in the covalent bonds. One choice or the other depends on the underlying physics and chemistry of interest. The proposed algorithm provides all conformations explored along one or several trajectories, the period of time for the existence of each one of these conformations, and also provides the graph of transitions that shows all conformational changes that have been observed during the trajectories. A user-friendly interface has been developed, that can de distributed freely.Our proposed algorithm for analysing the trajectories of molecular dynamics simulations has been tested on three kinds of gas phase molecular systems (peptides, ionic clusters). This model can be easily adapted and applied to any other molecular systems as well as to condensed matter systems, with little effort. Although the theoretical complexity of the algorithm is exponential (isomorphism tests), results have shown that the algorithm is rapid.We have also worked on computationally low cost graph methods that can be applied in order to pre-characterize specific conformations/points on a potential energy surface (it describes the energy of a system in terms of positions of the atoms). These points are the minima on the surface, representing the most stable conformations of a molecular system, and the maxima on that surface, representing transition states between two conformers. Our developed methods and algorithms aim at getting these specific points, without the prerequisite knowledge/calculation of the potential energy surface by quantum chemistry methods (or even by classical representations). By avoiding an explicit calculation of the potential energy surface by quantum chemistry methods, one saves computational time and effort. We have proposed an alternative method using ad doc measures based on properties of the graphs (already used in the first part of the PhD), without any knowledge of energy and/or molecular calculations. These measures allow getting the possible conformations with a realistic energy classification, as well as transition states, at very low computational cost. The algorithm has been tested on gas phase peptides
38
Desmier, Elise. "Co-evolution pattern mining in dynamic attributed graphs." Thesis, Lyon, INSA, 2014. http://www.theses.fr/2014ISAL0071/document.
Full textAbstract:
Cette thèse s'est déroulée dans le cadre du projet ANR FOSTER, "FOuille de données Spatio-Temporelles : application à la compréhension et à la surveillance de l'ERosion" (ANR-2010-COSI-012-02, 2011-2014). Dans ce contexte, nous nous sommes intéressés à la modélisation de données spatio-temporelles dans des graphes enrichis de sorte que des calculs de motifs sur de telles données permettent de formuler des hypothèses intéressantes sur les phénomènes à comprendre. Plus précisément, nous travaillons sur la fouille de motifs dans des graphes relationnels (chaque noeud est identifié de fa\c con unique), attribués (chaque noeud du graphe est décrit par des attributs qui sont ici numériques), et dynamiques (les valeurs des attributs et les relations entre les noeuds peuvent évoluer dans le temps). Nous proposons un nouveau domaine de motifs nommé motifs de co-évolution. Ce sont des triplets d'ensembles de noeuds, d'ensembles de pas de temps et d'ensembles d'attributs signés, c'est à dire des attributs associés à une tendance (croissance,décroissance). L'intérêt de ces motifs est de décrire un sous-ensemble des données qui possède un comportement spécifique et a priori intéressant pour conduire des analyses non triviales. Dans ce but, nous définissons deux types de contraintes, une contrainte sur la structure du graphe et une contrainte sur la co-évolution de la valeur des attributs portés par les noeuds. Pour confirmer la spécificité du motif par rapport au reste des données, nous définissons trois mesures de densité qui tendent à répondre à trois questions. À quel point le comportement des noeuds en dehors du motif est similaire à celui des noeuds du motif ? Quel est le comportement du motif dans le temps, est-ce qu'il apparaît soudainement ? Est-ce que les noeuds du motif ont un comportement similaire seulement sur les attributs du motif ou aussi en dehors ? Nous proposons l'utilisation d'une hiérarchie sur les attributs comme connaissance à priori de l'utilisateur afin d'obtenir des motifs plus généraux et adaptons l'ensemble des contraintes à l'utilisation de cette hiérarchie. Finalement, pour simplifier l'utilisation de l'algorithme par l'utilisateur en réduisant le nombre de seuils à fixer et pour extraire uniquement l'ensemble des motifs les plus intéressants, nous utilisons le concept de ``skyline'' réintroduit récemment dans le domaine de la fouille de données. Nous proposons ainsi trois algorithmes MINTAG, H-MINTAG et Sky-H-MINTAG qui sont complets pour extraire l'ensemble de tous les motifs qui respectent les différentes contraintes. L'étude des propriétés des contraintes (anti-monotonie, monotonie/anti-monotonie par parties) nous permet de les pousser efficacement dans les algorithmes proposés et d'obtenir ainsi des extractions sur des données réelles dans des temps raisonnablesThis thesis was conducted within the project ANR FOSTER, ``Spatio-Temporal Data Mining: application to the understanding and monitoring of erosion'' (ANR-2010-COSI-012-02, 2011-2014). In this context, we are interested in the modeling of spatio- temporal data in enriched graphs so that computation of patterns on such data can be used to formulate interesting hypotheses about phenomena to understand. Specifically, we are working on pattern mining in relational graphs (each vertex is uniquely identified), attributed (each vertex of the graph is described by numerical attributes) and dynamic (attribute values and relations between vertices may change over time). We propose a new pattern domain that has been called co-evolution patterns. These are trisets of vertices, times and signed attributes, i.e., attributes associated with a trend (increasing or decreasing). The interest of these patterns is to describe a subset of the data that has a specific behaviour and a priori interesting to conduct non-trivial analysis. For this purpose, we define two types of constraints, a constraint on the structure of the graph and a constraint on the co-evolution of the value worn by vertices attributes. To confirm the specificity of the pattern with regard to the rest of the data, we define three measures of density that tend to answer to three questions. How similar is the behaviour of the vertices outside the co-evolution pattern to the ones inside it? What is the behaviour of the pattern over time, does it appear suddenly? Does the vertices of the pattern behave similarly only on the attributes of the pattern or even outside? We propose the use of a hierarchy of attributes as an a priori knowledge of the user to obtain more general patterns and we adapt the set of constraints to the use of this hierarchy. Finally, to simplify the use of the algorithm by the user by reducing the number of thresholds to be set and to extract only all the most interesting patterns, we use the concept of ``skyline'' reintroduced recently in the domain of data mining. We propose three constraint-based algorithms, called MINTAG, H-MINTAG and Sky-H-MINTAG, that are complete to extract the set of all patterns that meet the different constraints. These algorithms are based on constraints, i.e., they use the anti-monotonicity and piecewise monotonicity/anti-monotonicity properties to prune the search space and make the computation feasible in practical contexts. To validate our method, we experiment on several sets of data (graphs) created from real-world data
39
Parmentier, Frédéric. "Modélisation et prédiction de la dynamique moléculaire de la maladie de Huntington par la théorie des graphes au travers des modèles et des espèces, et priorisation de cibles thérapeutiques." Thesis, Sorbonne Paris Cité, 2015. http://www.theses.fr/2015PA05T030.
Full textAbstract:
La maladie de Huntington est une maladie neurodégénérative héréditaire qui est devenue un modèle d'étude pour comprendre la physiopathologie des maladies du cerveau associées à la production de protéines mal conformées et à la neurodégénérescence. Bien que plusieurs mécanismes aient été mis en avant pour cette maladie, dont plusieurs seraient aussi impliqués dans des pathologies plus fréquentes comme la maladie d’Alzheimer ou la maladie de Parkinson, nous ne savons toujours pas quels sont les mécanismes ou les profils moléculaires qui déterminent fondamentalement la dynamique des processus de dysfonction et de dégénérescence neuronale dans cette maladie. De même, nous ne savons toujours pas comment le cerveau peut résister aussi longtemps à la production de protéines mal conformées, ce qui suggère en fait que ces protéines ne présentent qu’une toxicité modérée ou que le cerveau dispose d'une capacité de compensation et de résilience considérable. L'hypothèse de mon travail de thèse est que l'intégration de données génomiques et transcriptomiques au travers des modèles qui récapitulent différentes phases biologiques de la maladie de Huntington peut permettre de répondre à ces questions. Dans cette optique, l'utilisation des réseaux de gènes et la mise en application de concepts issus de la théorie des graphes sont particulièrement bien adaptés à l'intégration de données hétérogènes, au travers des modèles et au travers des espèces. Les résultats de mon travail suggèrent que l'altération précoce (avant les symptômes, avant la mort cellulaire) et éventuellement dès le développement cérébral) des grandes voies de développement et de maintenance neuronale, puis la persistance voire l'aggravation de ces effets, sont à la base des processus physiopathologiques qui conduisent à la dysfonction puis à la mort neuronale. Ces résultats permettent aussi de prioriser des gènes et de générer des hypothèses fortes sur les cibles thérapeutiques les plus intéressantes à étudier d'un point de vue expérimental. En conclusion, mes recherches ont un impact à la fois fondamental et translationnel sur l'étude de la maladie de Huntington, permettant de dégager des méthodes d'analyse et des hypothèses qui pourraient avoir valeur thérapeutique pour les maladies neurodégénératives en généralHuntington’s disease is a hereditary neurodegenerative disease that has become a model to understand physiopathological mechanisms associated to misfolded proteins that ocurs in brain diseases. Despite exciting findings that have uncover pathological mechanisms occurring in this disease and that might also be relevant to Alzheimer’s disease and Parkinson’s disease, we still do not know yet which are the mechanisms and molecular profiles that rule the dynamic of neurodegenerative processes in Huntington’s disease. Also, we do not understand clearly how the brain resist over such a long time to misfolded proteins, which suggest that the toxicity of these proteins is mild, and that the brain have exceptional compensation capacities. My work is based on the hypothesis that integration of ‘omics’ data from models that depicts various stages of the disease might be able to give us clues to answer these questions. Within this framework, the use of network biology and graph theory concepts seems particularly well suited to help us integrate heterogeneous data across models and species. So far, the outcome of my work suggest that early, pre-symptomatic alterations of signaling pathways and cellular maintenance processes, and persistency and worthening of these phenomenon are at the basis of physiopathological processes that lead to neuronal dysfunction and death. These results might allow to prioritize targets and formulate new hypotheses that are interesting to further study and test experimentally. To conclude, this work shall have a fundamental and translational impact to the field of Huntington’s disease, by pinpointing methods and hypotheses that could be valuable in a therapeutic perspective
40
Cheng, Zhi. "Mining recurrent patterns in a dynamic attributed Graph. : Application on aquaculture pond monitoring by satellite images." Thesis, Nouvelle Calédonie, 2018. http://www.theses.fr/2018NCAL0004.
Full textAbstract:
Dans cette thèse, nous nous sommes intéressés à l'analyse de données spatio-temporelles. Plusieurs algorithmes de fouille de données ont été développés pour extraire des modèles locaux (appelés aussi "motifs") tels que les motifs séquentiels ou les sous-graphes dynamiques. Cependant, ces approches souffrent de plusieurs limitations lorsqu 'on traite des phénomènes spatio-temporels complexes. Ces domaines de motifs ne prennent pas en compte toutes les interactions spatio-temporelles possibles ou ne considèrent que des informations limitées sur les objets étudiés. Par exemple, les motifs séquentiels se concentrent sur les évolutions temporelles sans tenir compte des évolutions spatiales. En outre, la plus part des algorithmes d'extraction de sous-graphes étudient des graphes dynamiques labélisés. Cependant, ils ne considèrent qu'un seul attribut par nœud et ignorent les autres caractéristiques des objets étudiés. Dans ce manuscrit, nous proposons d'étudier un graphe dynamique attribué pour fournir une représentation plus riche des phénomènes spatio-temporels. L'extraction de motifs dans des graphes dynamiques attribués est une tâche particulièrement complexe car la structure du graphe, les nœuds et les attributs associés à chaque nœud peuvent changer dans le temps. Pour cela, nous avons défini un nouveau domaine de motifs appelé motifs récurrents. Ces motifs, qui sont des séquences de sous-graphes connexes, représentent des évolutions récurrentes des sous-ensembles d'attributs associés à des sous-ensembles de nœuds. Pour extraire ces motifs, nous avons développé un nouvel algorithme, appelé RPMiner, utilisant une stratégie originale basée sur des intersections successives de composantes connexes apparaissant dans la séquence. Nous avons utilisé plusieurs contraintes pour réduire l 'espace de recherche et rendre le calcul possible. Une étude expérimentale sur des jeux de données synthétiques et réels (réseau de co-auteurs DBLP et données de trafic aérien US Flight) montre la généricité de notre approche, l 'intérêt des motifs extraits et l'efficacité de notre algorithme. Nous avons effectué également une évaluation poussée de notre approche sur les données du projet INDESO (suivi de bassins aquacoles en Indonésie par imagerie satellitaire). Pour cela, un processus d' extraction de connaissances (KDD) complet a été développé : du prétraitement des données à la visualisation et à l 'interprétation des résultats. Il vise à mieux comprendre les pratiques des fermiers pour un développement durable de ces ressources côtières en Indonésie. Ce processus s'appuie tout d'abord sur une méthode automatique et robuste pour extraire les bassins d'aquacoles à partir d'images satellitaires à faible contraste. Ensuite, il utilise des méthodes d'extraction de motifs fréquents afin de mettre en avant certaines pratiques des fermiers. Pour cela, nous avons appliqué dans un premier temps un algorithme d'extraction de motifs séquentiels pour analyser l'évolution des bassins dans le temps et comprendre les pratiques des fermiers. En parallèle nous avons aussi appliqué notre algorithme RPMiner, qui prend en compte à la fois les dimensions spatiales et temporelles. Les motifs extraits ont été interprétés par des experts en aquaculture. Les résultats obtenus ont permis de confirmer certaines pratiques et d'en mettre en avant d'autresIn this thesis, we are interested in analyzing spatio-temporal data. Numerous algorithms have been developed to extract local models (also called "patterns") such as sequential patterns or dynamic subgraphs. However, these approaches suffer from severa!limitations when dealing with complex spatio-temporal phenomena. These pattern demains do not consider all possible spatio-temporal interactions or only consider limited information about studied objects. For example, sequential pattern mining methods focus on temporal evolutions without considering spatial ones. Besicles, most of graph mining algorithms study labeled graphs. They only consider one attribute per vertex instead of all object's characteristics. In our work, we propose to study dynamic attributed graph, because they provide a richer representation of spatio-temporal phenomena. Extraction of patterns in dynamic attributed graph is a particularly complex task because graph structure, vertices and attributes associated with each vertex can change over time. For this purpose, we define a new pattern domain called recurrent patterns. These patterns, which are sequences of connected ubgraph, œpreent recurrent evolutions of subsets of attributes associated to vertices. To extract these patterns, we develop a new algorithm, RPMiner, using an original strategy based on successive intersections of connected components. We use severa! constraints to reduce the search space and make the computation feasible. Experimental study on both syndetic and two real-world datasets (DBLP dataset and Domestic US Flight dataset) show the genericity of our approach, the interest of extracted patterns and the efficiency of our algorithm. We also do an in-depth experimental evaluation of our approach on the INDESO project data (aquaculture pond monitoring in lndonesia by satellite images). A complete KDD process has been developed: from pre-processing of data to visualization and interpretation of results. It aims to better understand farming practices for sustainable development of these coastal resources in Indonesia.This process is firstly based on an automatic and robust method to extract aquaculture ponds from low contrast satellite images. Next, this process extracts frequent patterns to highlight sorne farming practices. For this, we have firstly applied a sequential pattern mining to analyze temporal evolutions of aquaculture ponds and to understand farming practices. In parallel, we also apply our algorithm, RPMiner, which considers both spatial and temporal aspects. Extracted patterns were interpreted by aquaculture experts. Results confirm severa!practices and highlight ethers
41
Dion, Dominique. "Dynamique d'évolution de graphes de cooccurrences lexicales : application à l'analyse de comptes rendus en prévention spécialisée entre 1972 et 2010." Phd thesis, Université Victor Segalen - Bordeaux II, 2012. http://tel.archives-ouvertes.fr/tel-00842790.
Full textAbstract:
Ces dix dernières années, l'étude des réseaux petits-mondes a montré une grande stabilité de certaines métriques issues de la théorie des graphes formels. Elle porte sur l'analyse de réseaux traduisant des activités de l'homme : réseaux d'échanges téléphoniques, de connexions aériennes, de navigation sur le Web, de structure des lexiques linguistiques, mais également de réseaux de diffusion des épidémies ou de réseaux de relations sociales. En revanche, peu d'études ont porté sur l'analyse de la dynamique de ces graphes et leur évolution au cours du temps. C'est cette approche que nous développons dans ce document. Nous nous intéressons ici à des graphes obtenus à partir de comptes rendus professionnels de travailleurs sociaux. Ces graphes modélisent les cooccurrences des mots au sein des phrases. Notre analyse porte sur un lexique professionnel et sur l'évolution de son usage sur une période de près de 40 ans. Après avoir constitué notre matériel à partir des textes écrits (environ 1500 pages dactylographiées), ce corpus d'étude a été quantifié, vérifié, homogénéisé et traité orthographiquement sur un mode semi-automatique. Puis ce corpus normalisé a donné lieu à la constitution d'un graphe global pour la période complète, et d'une quarantaine de graphes pour chacune des sous-périodes étudiées. C'est sur ceux-ci que porte l'analyse de la dynamique d'évolution de graphe issu d'un lexique professionnel. Au final, notre travail permet de pointer le paradoxe existant, entre d'une part la contrainte d'écriture liée à un objet qui ne change que très peu dans la nature de sa mission (le travail d'un éducateur de rue) et d'autre part la permissivité du langage oral qui ne cesse d'évoluer (le langage professionnel). Par ailleurs notre approche propose une certaine automatisation pour dégager l'essentiel d'un "dire professionnel" dans un corpus de comptes rendus.
42
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 introduitWe 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
43
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'applicationsGraph 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
44
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éesCausal 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
45
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'anonymisationData 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
46
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'anonymisationData 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
47
Loubier, Éloïse. "Analyse et visualisation de données relationnelles par morphing de graphe prenant en compte la dimension temporelle." Toulouse 3, 2009. http://thesesups.ups-tlse.fr/2264/.
Full textAbstract:
Avec la mondialisation, l'entreprise doit faire face aux menaces de plus en plus fortes de la concurrence et à l'accélération des flux d'information. Pour cela, elle est amenée à rester continuellement informée des innovations, des stratégies de la concurrence et de l'état du marché tout en gardant la maîtrise de son environnement. Le développement d'Internet et la globalisation ont à la fois renforcé cette exigence, et fourni les moyens de collecter l'information qui, une fois synthétisée, prend souvent une forme relationnelle. Pour analyser le relationnel, le recours à la visualisation par des graphes apporte un réel confort aux utilisateurs, qui, de façon intuitive, peuvent s'approprier une forme de connaissance difficile à appréhender autrement. Nos travaux conduisent à l'élaboration des techniques graphiques permettant la compréhension des activités humaines, de leurs interactions mais aussi de leur évolution, dans une perspective décisionnelle. Nous concevons un outil alliant simplicité d'utilisation et précision d'analyse se basant sur deux types de visualisations complémentaires : statique et dynamique. L'aspect statique de notre modèle de visualisation repose sur un espace de représentation, dans lequel les préceptes de la théorie des graphes sont appliqués. Le recours à des sémiologies spécifiques telles que le choix de formes de représentation, de granularité, de couleurs significatives permet une visualisation plus juste et plus précise de l'ensemble des données. L'utilisateur étant au cœur de nos préoccupations, notre contribution repose sur l'apport de fonctionnalités spécifiques, qui favorisent l'identification et l'analyse détaillée de structures de graphes. Nous proposons des algorithmes qui permettent de cibler le rôle des données au sein de la structure, d'analyser leur voisinage, tels que le filtrage, le k-core, la transitivité, de retourner aux documents sources, de partitionner le graphe ou de se focaliser sur ses spécificités structurelles. Une caractéristique majeure des données stratégiques est leur forte évolutivité. Or l'analyse statistique ne permet pas toujours d'étudier cette composante, d'anticiper les risques encourus, d'identifier l'origine d'une tendance, d'observer les acteurs ou termes ayant un rôle décisif au cœur de structures évolutives. Le point majeur de notre contribution pour les graphes dynamiques représentant des données à la fois relationnelles et temporelles, est le morphing de graphe. L'objectif est de faire ressortir les tendances significatives en se basant sur la représentation, dans un premier temps, d'un graphe global toutes périodes confondues puis en réalisant une animation entre les visualisations successives des graphes attachés à chaque période. Ce procédé permet d'identifier des structures ou des événements, de les situer temporellement et d'en faire une lecture prédictive. Ainsi notre contribution permet la représentation des informations, et plus particulièrement l'identification, l'analyse et la restitution des structures stratégiques sous jacentes qui relient entre eux et à des moments donnés les acteurs d'un domaine, les mots-clés et concepts qu'ils utilisentWith word wide exchanges, companies must face increasingly strong competition and masses of information flows. They have to remain continuously informed about innovations, competition strategies and markets and at the same time they have to keep the control of their environment. The Internet development and globalization reinforced this requirement and on the other hand provided means to collect information. Once summarized and synthesized, information generally is under a relational form. To analyze such a data, graph visualization brings a relevant mean to users to interpret a form of knowledge which would have been difficult to understand otherwise. The research we have carried out results in designing graphical techniques that allow understanding human activities, their interactions but also their evolution, from the decisional point of view. We also designed a tool that combines ease of use and analysis precision. It is based on two types of complementary visualizations: statics and dynamics. The static aspect of our visualization model rests on a representation space in which the precepts of the graph theory are applied. Specific semiologies such as the choice of representation forms, granularity, and significant colors allow better and precise visualizations of the data set. The user being a core component of our model, our work rests on the specification of new types of functionalities, which support the detection and the analysis of graph structures. We propose algorithms which make it possible to target the role of the data within the structure, to analyze their environment, such as the filtering tool, the k-core, and the transitivity, to go back to the documents, and to give focus on the structural specificities. One of the main characteristics of strategic data is their strong evolution. However the statistical analysis does not make it possible to study this component, to anticipate the incurred risks, to identify the origin of a trend, and to observe the actors or terms having a decisive role in the evolution structures. With regard to dynamic graphs, our major contribution is to represent relational and temporal data at the same time; which is called graph morphing. The objective is to emphasize the significant tendencies considering the representation of a graph that includes all the periods and then by carrying out an animation between successive visualizations of the graphs attached to each period. This process makes it possible to identify structures or events, to locate them temporally, and to make a predictive reading of it. Thus our contribution allows the representation of advanced information and more precisely the identification, the analysis, and the restitution of the underlying strategic structures which connect the actors of a domain, the key words, and the concepts they use; this considering the evolution feature
48
Jarkass, Iman. "Reconnaissance de l'état d'un système dynamique à l'aide d'un réseau de Petri crédibiliste." Compiègne, 1998. http://www.theses.fr/1998COMP1136.
Full textAbstract:
L'objectif de ce travail de thèse consiste à déterminer l'état d'un système dynamique séquentiel à partir d'informations provenant des capteurs. Nous avons choisi la théorie des réseaux de Petri pour la modélisation de l'évolution du système, chaque place correspond à un état et chaque transition est associée à la proposition ou à l'événement qui permet un changement d'état. La particularité de cette étude réside dans le peu d'informations que l'on a : la méconnaissance de l'état initial du système et les informations capteurs peu fiables. Nous avons utilisé le formalisme de la théorie de l'évidence pour modéliser cette méconnaissance. Le marquage est étendu sur l'ensemble des parties formées à partir de toutes les places du réseau représentatif de l'évolution du système, d'ou la définition d'un réseau de Petri crédibiliste. Les équations logiques qui permettent la résolution globale de l'état du système amenant au problème d'explosion combinatoire, nous proposons donc une décomposition du réseau en sous-réseaux. Des essais simulés ont donné de bons résultats. Nous proposons aussi une première approche de résolutions quand l'incertitude sur les transitions est modélisée par une probabilité. L'application réelle envisagée concerne les véhicules intelligents.
49
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é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
50
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 grapheCellular 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