Letteratura scientifica selezionata sul tema "Génération de graphes dynamiques"

L’article propose d’outiller, par le recours à l’analyse de réseaux, l’étude des références, c’est-à-dire les mentions et les citations d’autorités dans les textes métalinguistiques. Il s’agit, d’une part, de présenter les principes méthodologiques qui ont présidé à l’élaboration d’une visualisation sous forme de graphes de réseau : la modélisation et la construction d’une base de données de références et la génération du graphe dans un logiciel approprié. Il est question, d’autre part, de décrire les aspects liés à l’interprétation des graphes de réseaux, le but étant d’explorer le potentiel de l’outil dans l’histoire des idées linguistiques.

Résumé Dans le cadre de cette étude exploratoire, nous interrogeons les processus d’identification transnationale de jeunes adultes iraniens de seconde génération vivant à Montréal. En mettant l’accent sur le caractère relationnel de l’identité, cet article explore les dynamiques intra- et extrafamiliales influentes dans la formation identitaire de nos répondants. Ainsi, à la lumière de la dizaine d’entrevues semi-directives réalisées jusqu’à présent, nous avons mis en évidence les rôles exercés par la famille – définie par ses dynamiques internes, mais aussi comme une institution traversée par de multiples contraintes structurelles – par les réseaux transnationaux développés par nos répondants, ainsi que de l’environnement sociopolitique local.

Résumé Une base de connaissance terminologique (BCT) est à la fois une banque de terminologie conceptuellement et sémantiquement structurée et une base de connaissances. Les informations terminologiques, que nous qualifions de connaissances, y sont décrites sous la forme de réseaux conceptuels et sémantiques que nous appelons "réseaux sémantico-terminologiques" (RST). Les RST permettent de représenter, sous la forme de graphes, les unités terminologiques d'un domaine et les relations sémantiques qui les unissent au sein d'un système notionnel. Ces relations, au nombre de six dans notre modèle, possèdent la double fonction de regrouper les notions qui ont un certain degré de parenté pour mieux les distinguer par leurs traits distinctifs au sein de classes et de sous-classes.

Pouget, J. (2010). Intégrer et manager la génération Y, Vuibert, 208 p. Gagnon, C. (sous la dir.) (2012). Territoires durables en devenir, Québec, Presses de l’Université du Québec/Numérique, 255 p. Hamdouch, A., Depret, M.-H. et Tanguy, C. (sous la dir.) (2012). Mondialisation et résilience des territoires : Trajectoires, dynamiques d’acteurs et expériences, Québec, Presses de l’Université du Québec, 318 p.

La génération d’harmoniques laser d’ordre élevé dans les cristaux semiconducteurs est une nouvelle source de rayonnement ultra-bref (femtoseconde à attoseconde) cohérent et de courte longueur d’onde (de l’ordre de quelques dizaines de nanomètres) à très haute cadence. Outre la versatilité de cette source pour les applications, offerte notamment par les progrès en nano-structuration, l’étude du rayonnement émis permet de suivre les dynamiques électroniques ultrarapides au sein de matériaux complexes.

Dans le triple contexte de la baisse du recrutement sacerdotal, du concile Vatican II et de sa réception, et de la « montée des jeunes » issus de la génération du baby-boom, le Centre Richelieu, nom de l’aumônerie des étudiants de la Sorbonne dans les années 1950-1960, s’est trouvé pris au sein de dynamiques très diverses. Il est cependant un pourvoyeur de vocations religieuses d’autant plus important qu’elles ont alors tendance à baisser globalement. On se demande dans cet article en quoi il a constitué un environnement favorable à l’épanouissement de vocations religieuses, après avoir tenté d’en évaluer le nombre. On propose ainsi d’étudier un exemple de lieu de formation d’élites qui participe au recrutement de nombreuses vocations religieuses.

Résumé S’appuyant sur une enquête de terrain réalisée dans deux quartiers de Dakar (Sénégal) différant fortement quant à leur constitution historique et leur profil socioéconomique, cette recherche documente les nouvelles dynamiques des solidarités familiales dans un contexte global marqué par une précarité socioéconomique grandissante. Elle s’organise autour de trois éléments majeurs : la place toujours centrale occupée par les solidarités familiales, mais relevant davantage aujourd’hui du symbolique et du référentiel ; leur structuration différentielle selon la catégorie sociale, le genre et la génération ; enfin, leur mise à l’épreuve porteuse de nouvelles dynamiques. Celles-ci ont notamment trait à un renforcement de la solidarité dans l’espace conjugal, à un renversement des flux de solidarité entre « générations de la crise » et « aînés sociaux », ainsi qu’à des discours critiques débouchant sur une remise en cause des solidarités familiales avec l’apparition de nouvelles aspirations et pratiques reflétant plus la vie économique et sociale de la famille.

Nous étudions le problème de maintenir une distribution donnée de graphes aléatoires après une séquence arbitraire d’insertions et de suppressions de sommets. Dans l’objectif de modéliser l’évolution de réseaux logiques dynamiques,nous travaillons dans un modèle local où l’accès à la liste des sommets est restreint. À la place, nous faisons l’hypothèse d’un accès à une primitive globale qui retourne un sommet aléatoire, choisi uniformément dans l’ensemble total des sommets. Le problème de maintenance a été exploré sur plusieurs modèles simples de graphes aléatoires (graphes d’Erdos–Rényi, graphes basés sur le modèle par paires, graphes k-sortants uniformes). Pour chacun des modèles, un ou plusieurs algorithmes pour la tâche de maintenance ont été décris et analysés ; les plus élaborés de ces algorithmes sont asymptotiquement optimaux. Le problème de maintenance soulève plusieurs problèmes de simulation liés à notre contexte distribué. Nous nous sommes intéressé en particulier à la maintenabilité de distributions de graphes et à la simulabilité de familles de distributions de probabilité sur les entiers, dans le modèle d’aléa présenté.Une attention particulière a été portée sur la simulation efficace de lois spécifiques nous intéressant (certaines lois binomiales). Cette dernière a pu être obtenue en exploitant les propriétés d’un nouvel arbre de génération pour les permutations, que nous avons introduit
We study the problem of maintaining a given distribution of randomgraphs under an arbitrary sequence of vertex insertions and deletions. Keeping inmind our objective to model the evolution of dynamic logical networks, we work ina local model where we do not have direct access to the list of all vertices. Instead,we assume access to a global primitive that returns a random vertex, chosen uniformlyfrom the whole vertex set. The maintenance problem has been explored onseveral simple random graph models (Erdos–Rényi random graphs, pairing modelbased random graphs, uniform k-out graphs). For each model, one or several updatealgorithms for the maintenance task have been described and analyzed ; the mostelaborate of them are asymptically optimal. The maintenance task rise several simulationissues linked to our distributed context. In particular, we have focused onmaintenability of random graph distributions and simulability of families of probabilitydistributions over integers in our local random model. Special attention hasbeen paid to efficient simulation of particular distributions we were interested in(certain binomial distributions). The latter has been obtained through the use ofproperties of a new generation tree for permutations, which has been introducedalong the way

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 temporels
In 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

Ce travail de thèse présente différentes contributions pour la génération automatique de modèles représentant les Systèmes Dynamiques Hybrides (SDH) caractérisés par plusieurs modes de fonctionnement. Les composants du système (notamment les capteurs) peuvent être manuellement sélectionnée ou automatiquement exportés à partir des données de Conception Assistée par Ordinateur (CAO) ; ces éléments sont ensuite interconnectés pour reproduire le modèle complet du système industriel. Une fois le modèle créé, des schémas-blocs de simulation et de diagnostic, ainsi que la Matrice de Signature de Fautes (FSM) seront produits. Le logiciel est basé sur les Bonds Graph Hybrides ; la présence de commutations engendre des dynamiques variables (notamment des changements de causalité). Pour lever ces verrous, différents algorithmes sont proposés. En comparaison des logiciels existants, les algorithmes proposés sont valides pour les systèmes continus, discrets ou hybrides. Les théories et algorithmes développés sont appliqués sur un système ferroviaire de freinage électropneumatique
This thesis work contributes to perform a automed model builder for Hybrid Dynamic Systems (HDS) with numerous modes. Technological components including sensors with an iconic format can be automatically export from a computer-aided design (CAD) scheme or manually drag from database and interconnected, so as to produce the overall HDS model, following industrial technological schemes. Once the model has been created, block diagram for simulation and diagnosis and a Fault Signature Matrix (FSM) could be generated.The theory and algorithm behind the software are based on Hybrid Bond Graphs (HBG). The switching behaviour engenders variables dynamics (particularly causal changes). To solve this problematic, news algorithm are performed. Compared with developed programs for automated modelling, the presented algorithm are valid for continuous, discrete and hybrid systems. The theory is illustrated by an industrial application which consists of the pneumo-electrical control of rolling stock

Le travail de thèse concerne la conception intégrée d'un système de détection et localisation de fautes robuste aux incertitudes paramétriques pour les systèmes hybrides à base de modèle bond graph hybride(BGH) sous la forme LFT (Transformations linéaires fractionnelles). Sur la base de la littérature consultée, les systèmes hybrides sont principalement modélisés pour chaque mode de fonctionnement pour lequel sont générés des indicateurs de fautes déterministes. L'intérêt scientifique de la présente recherche peut être résumé comme suit : (1) l’utilisation d’un seul modèle BGH incertain basé sur les jonctions contrôlées et représentant l’ensemble des modes de fonctionnement, (2) exploitation des propriétés structurelles et causales du BGH LFT pour la génération systématique de Relations de Redondance Analytiques Globales (RRAG) et des seuils de détection robustes aux incertitudes paramétriques et, valides pour tous les modes de fonctionnement, et enfin (3) l’utilisation d’un seul outil : le modèle BGH de Diagnostic (BGHD), pour non seulement la modélisation mais aussi la surveillance en ligne. La démarche développée a été illustrée par un exemple pédagogique représentant un circuit électrique à commutation et par une application à un système hydraulique
The present PH.D thesis deals with integrated design of robust Fault Detection and Isolation system (FDI) based on Hybrid Bond Graph (HBG) in Linear Fractional Transformation (LFT) form. Based on consulted literature about hybrid systems, each operating mode is mainly modelled by specific model for which are generated determinist fault indicators. The innovative interest of developed research can be summarized as follows: (1) use only one HBG uncertain model based on controlled junctions and representing all operating modes, (2) structural and causal properties of the LFT HBG are exploited for systematic generation of Global Analytical Redundancy Relations (GARRs), and detection thresholds, robust to parameter uncertainties, and (3) finally use of only one tool: the Diagnosis Hybrid Bond Graph (DHBG) for not only modelling but also for online surveillance. The developed approach is illustrated by electrical circuit pedagogical example and application to hydraulic system

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. [...]

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.

Les travaux de recherche présentés dans ce mémoire montrent deux approches de la théorie des graphes. Dans un premier temps, nous caractérisons certains graphes en utilisant la coloration de graphes. Ainsi nous étudions deux paramètres de coloration qui maximisent le nombre de couleurs utilisées et mettent en évidence certains ensembles dominants de sommets pour les graphes étudiés (graphes puissances, somme cartésienne de graphes). Dans un second temps, nous étudions divers algorithmes de génération pour des arbres binaires particuliers. En effet, le morphing de polygones (problème sous-jacent au morphing d'images) peut être réalisé par une suite de rotations d'arbres binaires étiquetés. Nous présentons également des algorithmes de génération des arbres binaires étiquetés et des arbres binaires non ordonnés.

Les problèmes de graphes ont été largement étudiés dans le cas des graphes statiques. Cependant, ces graphes ne permettent pas de prendre en compte la dimension temporelle, qui est souvent une donnée importante pour les situations à modéliser. Les graphes dynamiques viennent combler ces lacunes en permettant de modéliser des évolutions dans le temps. On peut alors s'interroger sur ces mêmes problèmes de graphes dans un contexte dynamique. Cela passe d'abord par la définition du modèle de graphes dynamiques le plus approprié et la modélisation précise du problème sur ces graphes. Lorsque le problème ne peut pas être résolu efficacement en appliquant directement des méthodes connues sur les graphes statiques, il faut alors concevoir un algorithme de résolution spécifique aux graphes dynamiques et l'analyser théoriquement et expérimentalement.En suivant cette démarche, l'objectif de cette thèse est de s'interroger sur l'extension aux graphes dynamiques des problèmes bien connus sur les graphes statiques. Ce travail s'intéresse à plusieurs problèmes de graphes en contexte dynamique en se focalisant sur les aspects algorithmiques et en s'abstrayant des domaines d'applications
Graph problems have been widely studied in the case of static graphs. However, these graphs do not allow a time dimension to be considered, even though time is an important variable for the situations to model. Dynamic graphs make it possible to model evolution over time. This is a reason to wonder about graph problems in a dynamic context. First, it is necessary to define the most appropriate dynamic graphs model and the precise problem on those graphs. When the problem cannot be efficiently solved directly using known static graph methods, an algorithm specific to dynamic graphs must be designed and analyzed theoretically and practically.With that approach, this thesis' objective is to study graph problems' extensions to dynamic graphs. This works deals with several graph problems in a dynamic context by focusing on algorithmic aspects and without considering application domains

Les dynamiques causales de graphes sont une double extension des automates cellulaires : la grille sous-jacente est étendue à un graphe arbitraire de degré borné et le graphe lui-même peut évoluer dans le temps.Dans le régime réversible, nous prouvons qu’une dynamique causale de graphes peut être réversible tout en créant/détruisant des sommets, à travers trois différents modèles, que nous prouvons équivalents.En s'appuyant sur ces résultats, nous exhibons des dynamiques causales à la fois réversibles et croissantes en espace, ce qui apporte un nouveau regard sur la compatibilité entre la flèche du temps et la réversibilité. Nous définissons une notion de \subshift de graphes, qui peut être utilisée pour étudier les dynamiques causales de graphes en unifiant les dimensions temporelles et spatiales, de la même manière que les automates cellulaires 1D peuvent être étudiés par des \subshifts de type fini 2D.Dans le régime quantique, notre première contribution est de fournir une définition rigoureuse de l'espace d'état. Une question notable était de savoir si les noms des sommets sont nécessaires; nous prouvons que c'est le cas afin d'empêcher une propagation de l'information plus rapide que la lumière. Nous soulignons également que les renommages sur les graphes sont l'analogue nativement discret des changements de coordonnées
Causal graph dynamics are a twofold extension of cellular automata: the underlying grid is extended to an arbitrary graph of bounded degree and the graph itself can evolve in time.In the reversible regime, we prove that causal graph dynamics can be reversible while creating/destroying vertices, through three different models that we prove to be equivalent.Based on these results, we exhibit causal dynamics that are both reversible and increasing in space, which brings new insights into the compatibility between the time arrow and reversibility. We define a notion of graph subshifts, which can be used to study causal dynamics of graphs by unifying temporal and spatial dimensions, in the same way that 1D cellular automata can be studied with 2D subshifts of finite type.In the quantum regime, our first contribution is to provide a rigorous definition of state space. A notable question was whether vertex names are necessary; we prove they are indeed necessary in order to prevent faster-than-light signaling. We also point out that renaming on graphs is the natively discrete analog of coordinate changes

La confidentialité des données est un problème majeur qui doit être considéré avant de rendre publiques les données ou avant de les transmettre à des partenaires tiers avec comme but d'analyser ou de calculer des statistiques sur ces données. Leur confidentialité est principalement préservée en utilisant des techniques d'anonymisation. Dans ce contexte, un nombre important de techniques d'anonymisation a été proposé dans la littérature. Cependant, des méthodes génériques capables de s'adapter à des situations variées sont souhaitables. Nous adressons le problème de la confidentialité des données représentées sous forme de graphe, données qui nécessitent, pour différentes raisons, d'être rendues publiques. Nous considérons que l'anonymiseur n'a pas accès aux méthodes utilisées pour analyser les données. Une méthodologie générique est proposée basée sur des techniques d'apprentissage artificiel afin d'obtenir directement une fonction d'anonymisation et d'optimiser la balance entre le risque pour la confidentialité et la perte dans l'utilité des données. La méthodologie permet d'obtenir une bonne procédure d'anonymisation pour une large catégorie d'attaques et des caractéristiques à préserver dans un ensemble de données. La méthodologie est instanciée pour des graphes simples et des graphes dynamiques avec une composante temporelle. La méthodologie a été expérimentée avec succès sur des ensembles de données provenant de Twitter, Enron ou Amazon. Les résultats sont comparés avec des méthodes de référence et il est montré que la méthodologie proposée est générique et peut s'adapter automatiquement à différents contextes d'anonymisation
Data privacy is a major problem that has to be considered before releasing datasets to the public or even to a partner company that would compute statistics or make a deep analysis of these data. Privacy is insured by performing data anonymization as required by legislation. In this context, many different anonymization techniques have been proposed in the literature. These techniques are difficult to use in a general context where attacks can be of different types, and where measures are not known to the anonymizer. Generic methods able to adapt to different situations become desirable. We are addressing the problem of privacy related to graph data which needs, for different reasons, to be publicly made available. This corresponds to the anonymized graph data publishing problem. We are placing from the perspective of an anonymizer not having access to the methods used to analyze the data. A generic methodology is proposed based on machine learning to obtain directly an anonymization function from a set of training data so as to optimize a tradeoff between privacy risk and utility loss. The method thus allows one to get a good anonymization procedure for any kind of attacks, and any characteristic in a given set. The methodology is instantiated for simple graphs and complex timestamped graphs. A tool has been developed implementing the method and has been experimented with success on real anonymized datasets coming from Twitter, Enron or Amazon. Results are compared with baseline and it is showed that the proposed method is generic and can automatically adapt itself to different anonymization contexts

Au cours des dernières décennies, l'approche basée sur les modèles pour détecter les défauts dans les systèmes dynamiques a gagné en importance. Cette méthode utilise des résidus pour signaler les écarts entre le modèle et le processus réel. Ce chapitre explore diverses méthodes de détection de défauts, mettant l'accent sur les techniques de détection et d'isolation de défauts. La précision du modèle est cruciale, étant donné les disparités entre le modèle et la réalité. Des problèmes liés à la génération de résidus sont également discutés, ainsi que différentes méthodes de génération et d'évaluation des résidus.