Dissertations / Theses: 'Connectivité des graphes'

1

Kang, Haiyan. "Arêtes suppressibles, cycles et connectivité." Paris 11, 2010. http://www.theses.fr/2010PA112060.

Abstract:

Soit G un graphe k-connexe et e = uv une arête de G. G/e nous noterons le graphe obtenu à partir de G en supprimant les sommets u, v et en ajoutant un nouveau sommet v_e tels que v_e est adjacent à tous les anciens voisins de u et v. Si G/e est encore k-connexe, e est appelé un bord de k-contractile. La première partie de la thèse étudie une propriété d'un bord contractile en k-connexe graphiques sans triangle. Soit G un graphe k-connexe, et soit e une arête de G. Soit GӨe désigner le graphe obtenu à partir de G par l'opération suivante: (1) supprimer e de G pour obtenir G-e; (2) pour tout sommet fin de e avec un degré k-1, disons x, x supprimer, puis ajouter des bordures entre toute paire de sommets non- adjacents dans N_ (G-e)(x). Si GӨe est k-connexe, e est dit être une arête suppressible de G. La deuxième partie de la thèse étudie la répartition des arêtes suppressibles dans les graphes 3-connexes ou des graphes 5-connexes. En outre, nous confirmons la conjecture Thomassen pour deux classes de graphes 3-connexes avec des limites de bords amovibles ou de descendre du cycle le plus long. La dernière partie de la thèse est consacrée à la cyclabilité prisme de graphiques. Le prisme de plus d’un graphe G est le produit cartésien GK_2 de la graphe G et K_2. Un graphe G est appelé hamiltonien prisme si le prisme de plus de G est hamiltonien. Nous disons qu'une série H V (G) de sommets est cyclable dans G s'il existe un cycle C de G contenant tous les sommets de H. Pour H V (G), on dit que H est cyclable prisme dans GK_2 si H ∪ H’ est cyclable dans GK_2 où H' est la copie de H. Nous prolongeons la suite Ozeki sur hamiltonicité prisme cyclabilité prisme de S. Il est également avancé pour les graphes sans griffe, la borne peut être réduite de 3 avec un expection
Let G be a k-connected graph and e=uv an edge of G. By G/e we denote the graph obtained from G by deleting the vertices u,v and adding a new vertex v_e such that v_e is adjacent to all the former neighbors of u and v. If G/e is still k-connected, then e is called a k-contractible edge. The first part of the thesis studies a property of a contractible edge in k-connected triangle-free graphs. Let G be a k-connected graph, and let e be an edge of G. Let GӨe denote the graph obtained from G by the following operation: (1) delete e from G to get G-e; (2) for any end vertex of e with degree k-1, say x, delete x, and then add edges between any pair of non-adjacent vertices in N_{G-e}(x). If GӨe is k-connected, then e is said to be a removable edge of G. The second part of the thesis investigates the distribution of removable edges in 3-connected graphs or 5-connected graphs. In addition, we confirm Thomassen’s conjecture for two classes of 3-connected graphs with bounds of removable edges on or off a longest cycle. The last part of the thesis is devoted to the prism cyclability of graphs. The prism over a graph G is the Cartesian product GK_2 of G with the complete graph K_2. G is said to be prism hamiltonian if GK_2 is hamiltonian. We say that a set H V(G) of vertices is cyclable in G if there is a cycle C in G containing all vertices of H. For H V(G), we say that H is prism cyclable in GK_2 if H∪H' where H' is the copy of H is cyclable in GK_2. We extend Ozeki’s result on prism hamiltonicity to prism cyclability of S. It is also argued for claw-free graphs, the bound can be reduced 3 with one expection

APA, Harvard, Vancouver, ISO, and other styles

2

Yang, Weihua. "Supereulerian graphs, Hamiltonicity of graphes and several extremal problems in graphs." Phd thesis, Université Paris Sud - Paris XI, 2013. http://tel.archives-ouvertes.fr/tel-00877793.

Full text

Abstract:

In this thesis, we focus on the following topics: supereulerian graphs, hamiltonian line graphs, fault-tolerant Hamiltonian laceability of Cayley graphs generated by transposition trees, and several extremal problems on the (minimum and/or maximum) size of graphs under a given graph property. The thesis includes six chapters. The first one is to introduce definitions and summary the main results of the thesis, and in the last chapter we introduce the furture research of the thesis. The main studies in Chapters 2 - 5 are as follows. In Chapter 2, we explore conditions for a graph to be supereulerian.In Section 1 of Chapter 2, we characterize the graphs with minimum degree at least 2 and matching number at most 3. By using the characterization, we strengthen the result in [93] and we also address a conjecture in the paper.In Section 2 of Chapter 2, we prove that if $d(x)+d(y)\geq n-1-p(n)$ for any edge $xy\in E(G)$, then $G$ is collapsible except for several special graphs, where $p(n)=0$ for $n$ even and $p(n)=1$ for $n$ odd. As a corollary, a characterization for graphs satisfying $d(x)+d(y)\geq n-1-p(n)$ for any edge $xy\in E(G)$ to be supereulerian is obtained. This result extends the result in [21].In Section 3 of Chapter 2, we focus on a conjecture posed by Chen and Lai [Conjecture~8.6 of [33]] that every 3-edge connected and essentially 6-edge connected graph is collapsible. We find a kind of sufficient conditions for a 3-edge connected graph to be collapsible.In Chapter 3, we mainly consider the hamiltonicity of 3-connected line graphs.In the first section of Chapter 3, we give several conditions for a line graph to be hamiltonian, especially we show that every 3-connected, essentially 11-connected line graph is hamilton- connected which strengthens the result in [91].In the second section of Chapter 3, we show that every 3-connected, essentially 10-connected line graph is hamiltonian-connected.In the third section of Chapter 3, we show that 3-connected, essentially 4-connected line graph of a graph with at most 9 vertices of degree 3 is hamiltonian. Moreover, if $G$ has 10 vertices of degree 3 and its line graph is not hamiltonian, then $G$ can be contractible to the Petersen graph.In Chapter 4, we consider edge fault-tolerant hamiltonicity of Cayley graphs generated by transposition trees. We first show that for any $F\subseteq E(Cay(B:S_{n}))$, if $|F|\leq n-3$ and $n\geq4$, then there exists a hamiltonian path in $Cay(B:S_{n})-F$ between every pair of vertices which are in different partite sets. Furthermore, we strengthen the above result in the second section by showing that $Cay(S_n,B)-F$ is bipancyclic if $Cay(S_n,B)$ is not a star graph, $n\geq4$ and $|F|\leq n-3$.In Chapter 5, we consider several extremal problems on the size of graphs.In Section 1 of Chapter 5, we bounds the size of the subgraph induced by $m$ vertices of hypercubes. We show that a subgraph induced by $m$ (denote $m$ by $\sum\limits_{i=0}^ {s}2^{t_i}$, $t_0=[\log_2m]$ and $t_i= [\log_2({m-\sum\limits_{r=0}^{i-1}2 ^{t_r}})]$ for $i\geq1$) vertices of an $n$-cube (hypercube) has at most $\sum\limits_{i=0}^{s}t_i2^{t_i-1} +\sum\limits_{i=0}^{s} i\cdot2^{t_i}$ edges. As its applications, we determine the $m$-extra edge-connectivity of hypercubes for $m\leq2^{[\frac{n}2]}$ and $g$-extra edge-connectivity of the folded hypercube for $g\leq n$.In Section 2 of Chapter 5, we partially study the minimum size of graphs with a given minimum degree and a given edge degree. As an application, we characterize some kinds of minimumrestricted edge connected graphs.In Section 3 of Chapter 5, we consider the minimum size of graphs satisfying Ore-condition.

APA, Harvard, Vancouver, ISO, and other styles

3

Carboni, Lucrezia. "Graphes pour l’exploration des réseaux de neurones artificiels et de la connectivité cérébrale humaine." Electronic Thesis or Diss., Université Grenoble Alpes, 2023. http://www.theses.fr/2023GRALM060.

Full text

Abstract:

L'objectif principal de cette thèse est d'explorer la connectivité cérébrale et celle des réseaux de neurones artificiels d'un point de vue de leur connectivité. Un modèle par graphes pour l'analyse de la connectivité structurelle et fonctionnelle a été largement étudié dans le contexte du cerveau humain mais, un tel cadre d'analyse manque encore pour l'analyse des systèmes artificiels. Avec l'objectif d'intégrer l'analyse de la connectivité dans les système artificiels, cette recherche se concentre sur deux axes principaux. Dans le premier axe, l'objectif principal est de déterminer une caractérisation de la signature saine de la connectivité fonctionnelle de repos du cerveau humain. Pour atteindre cet objectif, une nouvelle méthode est proposée, intégrant des statistiques de graphe traditionnelles et des outils de réduction de réseau, pour déterminer des modèles de connectivité sains. Ainsi, nous construisons une comparaison en paires de graphes et un classifieur pour identifier les états pathologiques et identifier les régions cérébrales perturbées par une pathologie. De plus, la généralisation et la robustesse de la méthode proposée ont été étudiées sur plusieurs bases de données et variations de la qualité des données. Le deuxième axe de recherche explore les avantages de l'intégration des études de la connectivité inspirée du cerveau aux réseaux de neurones artificiels (ANNs) dans la perspective du développement de systèmes artificiels plus robustes. Un problème majeur de robustesse dans les modèles d'ANN est représenté par l'oubli catastrophique qui apparaît lorsque le réseau oublie dramatiquement les tâches précédemment apprises lors de l'adaptation à de nouvelles tâches. Notre travail démontre que la modélisation par graphes offre un cadre simple et élégant pour étudier les ANNs, comparer différentes stratégies d'apprentissage et détecter des comportements nuisibles tels que l'oubli catastrophique. De plus, nous soulignons le potentiel d'une adaptation à de nouvelles tâches en contrôlant les graphes afin d'atténuer efficacement l'oubli catastrophique et jetant ainsi les bases de futures recherches et explorations dans ce domaine
The main objective of this thesis is to explore brain and artificial neural network connectivity from agraph-based perspective. While structural and functional connectivity analysis has been extensivelystudied in the context of the human brain, there is a lack of a similar analysis framework in artificialsystems.To address this gap, this research focuses on two main axes.In the first axis, the main objective is to determine a healthy signature characterization of the humanbrain resting state functional connectivity. To achieve this objective, a novel framework is proposed,integrating traditional graph statistics and network reduction tools, to determine healthy connectivitypatterns. Hence, we build a graph pair-wise comparison and a classifier to identify pathological statesand rank associated perturbed brain regions. Additionally, the generalization and robustness of theproposed framework were investigated across multiple datasets and variations in data quality.The second research axis explores the benefits of brain-inspired connectivity exploration of artificialneural networks (ANNs) in the future perspective of more robust artificial systems development. Amajor robustness issue in ANN models is represented by catastrophic forgetting when the networkdramatically forgets previously learned tasks when adapting to new ones. Our work demonstrates thatgraph modeling offers a simple and elegant framework for investigating ANNs, comparing differentlearning strategies, and detecting deleterious behaviors such as catastrophic forgetting.Moreover, we explore the potential of leveraging graph-based insights to effectively mitigatecatastrophic forgetting, laying a foundation for future research and explorations in this area

APA, Harvard, Vancouver, ISO, and other styles

4

Suprano, Ilaria. "Étude de la connectivité cérébrale par IRM fonctionnelle et de diffusion dans l’intelligence." Thesis, Lyon, 2019. http://www.theses.fr/2019LYSE1282.

Full text

Abstract:

L'idée que l'intelligence s’appuie non seulement sur des régions spécifiques du cerveau, mais également sur des réseaux cérébraux efficaces s’est récemment affirmée. En effet, on pense que l'organisation du cerveau humain repose sur des réseaux complexes et dynamiques dans lesquels la communication entre les régions cérébrales garantit un transfert efficace d'informations. Ces concepts nous ont amené à explorer les bases neurales de l'intelligence en combinant des techniques avancées d'IRM et la théorie des graphes. D'un côté, les techniques avancées d'IRM, telles que l'IRM fonctionnelle au repos (IRMf-rs) et l'IRM par diffusion (IRMd), permettent d'explorer respectivement la connectivité cérébrale fonctionnelle et structurale, tandis que la théorie des graphes permettent la caractérisation des propriétés des réseaux à différentes échelles, grâce à des métriques globales et locales. L'objectif de cette thèse est de caractériser la topologie des réseaux cérébraux fonctionnels et structurels chez les enfants et les adultes avec un quotient intellectuel supérieur (HIQ) par rapport aux sujets de niveau standard (SIQ). Premièrement, nous avons concentré notre attention sur une population d’enfants présentant différentes caractéristiques cognitives. Deux profils HIQ, à savoir homogène (Hom-HIQ) et hétérogène HIQ (Het-HIQ), ont été définis sur la base d'observations cliniques et de sous-tests du quotient intellectuel (QI). En utilisant des techniques d’IRMf-rs, nous avons examiné la topologie du réseau fonctionnel par « l’indice de rupture de nœud ». Nous avons trouvé des différences topologiques significatives dans les propriétés d'intégration et de ségrégation des réseaux chez les enfants HIQ par rapport aux enfants SIQ, pour le graphe cérébral entier, pour chaque graphe hémisphérique et pour la connectivité homotopique. De plus, ces changements de topologie étaient plus prononcés dans le sous-groupe Het-HIQ. Enfin, nous avons trouvé des corrélations significatives entre les changements des métriques de graphes et le QI total et d’autres indices du QI. Ces résultats ont démontré pour la première fois que les deux profils HIQ sont liés à une organisation différente du substrat neuronal. Ensuite, la connectivité structurale du réseau cérébral, mesurée par IRMd chez l’ensemble des enfants HIQ, est significativement différente de celle des enfants SIQ. Nous avons également aussi de fortes corrélations entre la densité des réseaux cérébraux des enfants et leurs scores d'intelligence. De plus, plusieurs corrélations ont été trouvées entre les métriques de graphe d'intégration suggérant que les performances de l'intelligence peuvent être liées à une organisation homogène des réseaux. Ces résultats ont démontré que le substrat neuronal de l'intelligence repose sur une microarchitecture de la substance blanche de forte densité et sur une organisation homogène des réseaux. Cette population a finalement été étudiée par IRMf avec une tâche de mémorisation de mots. Des changements significatifs ont été observés entre les groupes HIQ et SIQ. Cette étude confirme notre hypothèse selon laquelle les deux profils HIQ sont caractérisés par une activité cérébrale différente, avec un effet plus prononcé chez les enfants Het-HIQ. Enfin, nous avons étudié la connectivité fonctionnelle et structurale dans une population d’adultes HIQ. Nous avons trouvé plusieurs corrélations entre les métriques de graphe et les autres indices du QI. De même que pour la population d’enfants, les capacités cognitives élevées des adultes sont corrélées à une organisation homogène des réseaux structurels et fonctionnels et une modularité réduite. En conclusion, on a démontré que la sensibilité des métriques de graphes basées sur des techniques 'IRM avancées et de connectivité, telles que l’IRMf-rs et l'IRMd, était très utile pour mieux caractériser les réseaux cérébraux des enfants et des adultes, ainsi que pour distinguer différents profils d'intelligence chez les enfants
The idea that intelligence is embedded not only in specific brain regions, but also in efficient brain networks has grown up. Indeed, human brain organization is believed to rely on complex and dynamic networks in which the communication between cerebral regions guarantees an efficient transfer of information. These recent concepts have led us to explore the neural bases of intelligence using both advanced MRI techniques in combination with graph analysis. On one hand, advanced MRI techniques, such as resting-state functional MRI (rs-fMRI) and diffusion MRI (dMRI) allow the exploration of respectively the functional and the structural brain connectivity while on the other hand, graph theory models allow the characterization of brain networks properties at different scales, thanks to global and local metrics. The aim of this thesis is to characterize the topology of functional and structural brain networks in children and in adults with an intelligence quotient higher (HIQ) than standard levels (SIQ). First, we focused our attention on a children population with different cognitive characteristics. Two HIQ profiles, namely homogeneous (Hom-HIQ) and heterogeneous HIQ (Het-HIQ), have been defined based on clinical observations and Intelligence Quotient (IQ) sub-tests. Using resting-state fMRI techniques, we examined the functional network topology changes, estimating the "hub disruption index", in these two HIQ profiles. We found significant topological differences in the integration and segregation properties of brain networks in HIQ compared to SIQ children, for the whole brain graph, for each hemispheric graph, and for the homotopic connectivity. These brain networks changes resulted to be more pronounced in Het-HIQ subgroup. Finally, we found significant correlations between the graph networks’ changes and the full-scale IQ, as well as some intelligence subscales. These results demonstrated for the first time, that different HIQ profiles are related to a different neural substrate organization. Then, the structural brain network connectivity, measured by dMRI in all HIQ children, were significantly different than in SIQ children. Also, we found strong correlations between the children brain networks density and their intelligence scores. Furthermore, several correlations were found between integration graph metrics suggesting that intelligence performances are probably related to a homogeneous network organization. These findings demonstrated that intelligence neural substrate is based on a strong white matter microarchitecture of the major fiber-bundles and a well-balanced network organization between local and global scales. This children population was finally studied using a memory-word task of fMRI. Significant changes were observed between both HIQ and SIQ groups. This study confirms our hypothesis that both HIQ profiles are characterized by a different brain activity, with stronger evidences in Het-HIQ children. Finally, we investigated both functional and structural connectivity in a population of adults HIQ. We found several correlations between graph metrics and intelligence sub-scores. As well as for the children population, high cognitive abilities of adults seem to be related brain structural and functional networks organization with a decreased modularity. In conclusion, the sensitivity of graph metrics based on advanced MRI techniques, such as rs-fMRI and dMRI, was demonstrated to be very helpful to provide a better characterization of children and adult HIQ, and further, to distinguish different intelligence profiles in children

APA, Harvard, Vancouver, ISO, and other styles

5

Dai, Tianjiao. "Some vertex colouring problems and a generalisation of Hamilton-connectivity in graphs." Electronic Thesis or Diss., université Paris-Saclay, 2023. http://www.theses.fr/2023UPASG067.

Full text

Abstract:

La décomposition des graphes fait référence au processus de décomposer un graphe complexe en composantes plus simples et plus petites, souvent dans le but d'analyser ou de résoudre des problèmes liés au graphe. Il s'agit d'un outil important pour représenter la structure globale et les propriétés d'une manière plus détaillée. Il est aussi également utile pour résoudre des problèmes impliquant la recherche de structures spécifiques dans un graphe. Il existe plusieurs types courants de techniques de décomposition de graphe largement utilisées en théorie des graphes et dans des domaines connexes, notamment la décomposition en arbres, la décomposition en blocs, la décomposition modulaire, la décomposition hiérarchique, etc. Cette thèse étudie deux types de décomposition de sommets d'un graphe : les colorations propres (décomposition en ensembles indépendants) et la Hamilton-connectivité (décomposition en chemins internement disjoints entre deux ensembles où les chemins couvrent tous les sommets du graphe)
The decomposition of graphs refers to the process of breaking down a complex graph into simpler, smaller components, often with the goal of analysing or solving problems related to the graph. It is an important tool to display the global structure and properties in a more fine-grained manner, and also useful in solving problems that involve finding specific structures in a graph. There are several common types of graph decomposition techniques that are widely used in graph theory and related fields, including tree decomposition, block decomposition, modular decomposition, hierarchical decomposition, etc. This thesis studies two kinds of vertex decomposition of a graph: proper colourings (decomposition into independent sets) and Hamilton-connectivity (decomposition into internally-disjoint paths between two sets where the paths cover all the vertices of graphs)

APA, Harvard, Vancouver, ISO, and other styles

6

Gargouri, Fatma. "Etude de la connectivité fonctionnelle dans les pathologies de mouvement de Parkinson et de Huntington en utilisant l’approche par graine et la théorie des graphes." Thesis, Paris 6, 2017. http://www.theses.fr/2017PA066487/document.

Full text

Abstract:

L’imagerie par résonance magnétique fonctionnelle permet d’explorer l’activité neuronale en utilisant un contraste endogène appelé BOLD. Il a été montré que les fluctuations du signal BOLD au repos corrélaient dans des régions cérébrales distantes. C’est la connectivité fonctionnelle. Elle représente l’activité spontanée du cerveau et elle est mesurée par l’IRMf au repos. Notre projet de recherche a donc combiné un aspect méthodologique et deux applications dans le domaine des pathologies du mouvement. Nous avons étudié les stratégies de prétraitement des données. L'objectif était d'étudier l'influence du type de prétraitement ainsi que leur ordre d'application sur l'optimisation de la topologie des réseaux cérébraux. Nous avons comparé 12 stratégies différentes de prétraitement. Dans ces stratégies nous avons appliqué les techniques standards avec un ordre d'application différent. Les deux études suivantes ont utilisé l'IRMf au repos pour étudier la physiopathologie de deux pathologies du mouvement : la maladie de Huntington et la maladie de Parkinson. Dans ces pathologies, nous nous sommes centrés sur l'étude des réseaux cérébraux grâce à l'étude de la connectivité fonctionnelle. Nous avons déterminé si l'IRMf au repos et les mesures de la théorie des graphes permettaient d'identifier des biomarqueurs robustes de l'évolution de la maladie de Huntington dans une étude longitudinale. Ensuite, nous avons étudié le rôle des noyaux cholinergiques du cerveau basal antérieur et de leurs connexions dans la survenue des troubles cognitifs présentés par les patients atteints de maladie de Parkinson. L'approche par graine est une méthode adaptée à ce type de question
Functional magnetic resonance imaging (fMRI) is a technique that allows exploring neuronal activity using an endogenous contrast based on the oxygenation level of hemoglobin. This contrast is called BOLD (Blood oxygenated Level Dependent). It has been shown that fluctuations in the BOLD signal at rest, correlated in distant brain regions, defining long-distance brain functional networks. This is called functional connectivity. The latter represents the spontaneous activity of the brain and it is measured by fMRI at rest. Our research project has therefore combined a methodological aspect and two applications in the field of movement pathologies. In the first part of our project we studied data preprocessing strategies. The objective was to study the influence of the preprocessing steps and their order of application on the brain networks’ topology. We compared 12 different pretreatment strategies. In these strategies we applied the standard and most used techniques but with a different order of application. The following two studies used resting-state fMRI to study: Huntington's disease and Parkinson's disease. In these pathologies, we focused on the study of the brain networks addressed through the study of functional connectivity. We determined whether resting-state fMRI and graph theory measures were able to identify robust biomarkers of Huntington's disease progression in a longitudinal study. In the second study, we investigated the role of cholinergic basal nuclei of the forebrain and their connections in the onset of cognitive problems presented in Parkinson's disease. The seed-based analysis is a suitable method for this type of question

APA, Harvard, Vancouver, ISO, and other styles

7

Oujamaa, Lydia. "Evolution topologique des hubs dans l'état de conscience altérée post-traumatique : un marqueur de récupération fonctionnelle." Thesis, Université Grenoble Alpes, 2020. http://www.theses.fr/2020GRALS013.

Full text

Abstract:

Ce travail doctoral s’inscrit dans le champ de la recherche translationnelle. Nous avonsvoulu explorer la plasticité cérébrale post-lésionnelle qui sous-tend la restauration de la conscience après un coma traumatique. L’étude de la connectivité fonctionnelle de repos, c’est à dire de la corrélation temporelle du signal BOLD (blood oxygenationlevel dependent) entre régions cérébrales, a été appliquée à une cohorte de 36 patients traumatisés crâniens graves sortant de réanimation. A cette date, les patients pouvaient se trouver en état de conscience altérée ou être conscients. Nous avons réalisé une étude transversale et longitudinale : une 1ère IRM fonctionnelle en condition de veille de repos était réalisée à la sortie des soins intensifs et une seconde après un séjour de un moisen rééducation post-réanimation. Ainsi, à l’aide de la méthode des graphes, nous avons exploré l’intérêt diagnostique et pronostique de la connectivité fonctionnelle lors de la réémergence de la conscience après coma traumatique.Nous avons centré notre analyse sur un index de perturbation des hubs qui traduitla redistribution des connexions fonctionnelles dans le graphe. Les hubs du réseau cérébral,qui physiologiquement concentrent le plus de connexions, ont été caractérisésavec plusieurs métriques d’intégration, de ségrégation et de centralité dans le transfertd’information.Nos résultats suggèrent qu’une perturbation de la topologie des hubs fonctionnels estobjectivement "cartographiable" et qu’elle est corrélée à l’évolution neurologique cliniqueaprès agression cérébrale. En effet, notre étude a montré que, chez le traumatisé crâniengrave adulte, ce marqueur de perturbation fonctionnelle du réseau cérébral est sensible,dans une analyse de groupe, à l’état de conscience (patients conscients vs en état deconscience altérée) et à sa restauration au cours du temps. L’index de perturbation deshubs est également sensible à une autre dimension clinique : la prédiction du handicap neurologique à 6 mois post-coma.La computation des données de connectivité en une méta-donnée, l’index de perturbationdes hubs de l’ensemble du réseau cérébral, permet d’aller plus loin qu’un modèle descriptif de la plasticité cérébrale après coma (d’altération ou de restitution de connectivité dans un ou plusieurs réseaux). Ainsi, la restitution de la capacité du cerveau à traiterde l’information locale dans les hubs fonctionnels serait nécessaire à la ré-émergence de la conscience après coma traumatique. Ce résultat est original car dans la littérature actuelle, basée sur les théories de l’espace de travail global et de l’intégration de l’information,l’atteinte traumatique cérébrale est modélisée comme une altération de laconnectivité à longue distance et donc de l’intégration fonctionnelle.Cette étude pilote était un pré-requis pour évaluer à l’avenir cet index de perturbation fonctionnelle cérébrale à l’échelle individuelle et objectiver la réponse thérapeutique(psychostimulants, électrostimulation cérébrale....) de patients en état de conscience altérée
This work takes part in the field of translational research. Our aim was to explore thepost-lesional brain plasticity necessary to recover consciousness after a traumatic coma.The study of resting state functional connectivity, meaning the temporal correlation ofBOLD signal (blood oxygenation level dependent) between remote cerebral areas, wasapplied to severe traumatic brain injured (sTBI) patients.Using graph method, we explored the diagnosis and prognosis value of resting statefunctional connectivity during recovery of consciousness after a traumatic coma.Thirty six sTBI patients were studied in a cross sectional and a longitudinal design.We recorded a resting state functional MRI sequence while sTBI patients were eitherconscious or in altered state of consciousness when discharged from intensive care unit(ICU). A second fMRI was recorded after one month spent in a post-ICU rehabilitationunit.Our analysis focused on a hub disruption index (HDI) which expresses the reallocationof functional connections inside the graph. In the brain network, the hubs, which are definedas highly connected to the brain network in healthy subjects, have been characterizedwith integration, segregation and centrality metrics for information transfer.Our results suggest that the topological disruption of functional hubs is an objectivemapping of the brain network changes that correlates with post-TBI neurological recovery.Indeed, in our group analysis, the hub disruption index of the post TBI brainnetwork was sensitive to the state of consciousness and to its recovery during a onemonth follow-up. This index was also relevant to predict the level of disability 6 monthsafter injury.The computation of connectivity data in a metadata, the hub disruption index ofthe brain network, enhances the classical approach describing the post-traumatic brainplasticity as a loss and recovery of connectivity in one or several cortical networks. Therecovery of the brain network ability to compute local information in the functionalhubs could be necessary to recover consciousness after a traumatic coma. This resultis original as the recent litterature, based on the information integration theory andthe global workspace theory of consciousness, is considering severe TBI as a long rangeconnectivity disruption inducing a functional integration impairment.This pilot study was necessary prior to the assessment of the HDI on a single-subjectlevel and to quantifie the response of brain injured patients with disorder of consciousnessto several therapeutic options (psychostimulant drugs, electrical stimulation..)

APA, Harvard, Vancouver, ISO, and other styles

8

König, Jean-Claude. "Les réseaux d'interconnexion et les algorithmes distribués." Paris 11, 1987. http://www.theses.fr/1987PA112069.

Full text

Abstract:

Cette thèse comprend deux parties. La première concerne les réseaux d'interconnexion et en particulier leur résistance aux pannes. Le premier chapitre traite d'extension de réseaux; on construit des réseaux de connexité et de degré maximum donnés en ajoutant des sommets p par p par p ceci avec un nombre minimum de remaillages. Dans le second chapitre on étudie la vulnérabilité des réseaux par bus ce qui nous conduit à étudier diverses notions de connexité dans les hypergraphes uniformes. La deuxième partie est consacrée à l'algorithme, distribuée et particulièrement à tout ce qui concerne les problèmes de messagerie (diffusion, routage). Le chapitre 3 traite de la diffusion d'information ou de requêtes dans un réseau distribué. On définit un nouvel algorithme : permettant de construire un arbre couvrant et on l'applique au problème de l'on mutuelle. Nous utilisons des méthodes de contrôle des transferts de connaissance ainsi que des techniques de synchronisation et de filtrage. Le chapitre 4 présente un «méta-algorithme» distribué basé sur la notion de phases. De plus on précise le rôle et l’importance de la topologie du réseau dans l'algorithmique distribuée. Dans ces deux derniers chapitres on détermine la complexité en nombre de messages et en temps des algorithmes. Enfin nous donnons en annexe un algorithme d'ordonnancement pour le calcul parallèle qui est optimal si le graphe de précédence des tâches est de type "2-steps' (élimination de Gauss dans une matrice dense)
This thesis contains two parts. Ln the first one we study interconnection networks and in particular their fault tolerance. The first chapter deals with the extensions of networks. We construct networks with given connectivity and maximum degree by adding the vertices p by p. In such a way that the minimum number possible of links is deleted. Ln chapter 2 we study the vulnerability of bus networks; this leads us to study various notions of connectivity in uniform hypergraphs. The second part concerns distributed algorithms, in particular problems of broadcasting and routing. Chapter 3 deals with the problem of broadcasting information or requests in a distributed net work. We give a new algorithm to construct a spanning tree and apply it to the problem of mutual exclusion. We use methods of control knowledge transfers and also synchronization and filtering methods. Ln chapter 4 we present a "meta-algorithm" based on the notion of phases. Furthermore we specify the use and the importance of the network topology in the distributed computing. Ln these two chapters we determine the complexity in number or messages and time of the proposed algorithms. Finally we give in the appendix a scheduling algorithm for parallel computing which is optimal for the 2-sceps precedence graph (Gaussian elimination in dense matrices)

APA, Harvard, Vancouver, ISO, and other styles

9

Cattai, Tiziana. "Leveraging brain connectivity networks to detect mental states during motor imagery." Electronic Thesis or Diss., Sorbonne université, 2021. http://www.theses.fr/2021SORUS081.

Full text

Abstract:

Le cerveau est un réseau complexe et nous savons que les mécanismes de synchronisation et de désynchronisation sont essentiels pour effectuer des taches motrices et cognitives. De nos jours, les interactions fonctionnelles cérébrales sont étudiées dans des applications d'interface cerveau-ordinateur (BCI) avec de plus en plus d'intérêt. Cela pourrait avoir un fort impact sur les systèmes BCI, généralement bases sur des caractéristiques univariées qui caractérisent séparément les activités régionales du cerveau. En effet, les fonctionnalités de connectivité cérébrale peuvent être utilisées pour développer des BCI alternatifs dans le but d'améliorer les performances et d'\'e9tendre leur applicabilité dans la vie r\'e9elle. L'ambition de cette thèse est l'étude des réseaux de connectivité fonctionnelle du cerveau lors de taches BCI basées sur l'imagerie motrice (IM). Il vise à identifier le fonctionnement cérébral complexe, les processus de réorganisation et les dynamiques variant dans le temps à la fois au niveau du groupe et de l'individu. Cette thèse présente différents développements qui enrichissent séquentiellement un modèle initialement simple afin d'obtenir une méthode robuste pour l'étude des réseaux de connectivité fonctionnelle. Les résultats expérimentaux sur des données EEG simulées et réelles enregistrés pendant les taches BCI prouvent que notre méthode proposée explique bien le comportement variegate des données EEG cérébrales. Plus précisément, il fournit une caractérisation des mécanismes fonctionnels du cerveau au niveau du groupe, ainsi qu'une mesure de la séparabilité des conditions mentales au niveau individuel. Nous présentons également une procédure de réduction du bruit de graphe pour filtrer les données qui préservent simultanément la structure de connectivité du graphe et améliorent le rapport signal sur bruit. Puisque l'utilisation d'un système BCI nécessite une interaction dynamique entre l'utilisateur et la machine, nous proposons enfin une méthode pour capturer l'évolution des données variant dans le temps. Essentiellement, cette thèse présente un nouveau cadre pour saisir la complexité de la connectivité fonctionnelle des graphes lors de tâches cognitives
The brain is a complex network and we know that inter-areal synchronization and de-synchronization mechanisms are crucial to perform motor and cognitive tasks. Nowadays, brain functional interactions are studied in brain-computer interface BCI) applications with more and more interest. This might have strong impact on BCI systems, typically based on univariate features which separately characterize brain regional activities. Indeed, brain connectivity features can be used to develop alternative BCIs in an effort to improve performance and to extend their real-life applicability. The ambition of this thesis is the investigation of brain functional connectivity networks during motor imagery (MI)-based BCI tasks. It aims to identify complex brain functioning, re-organization processes and time-varying dynamics, at both group and individual level. This thesis presents different developments that sequentially enrich an initially simple model in order to obtain a robust method for the study of functional connectivity networks. Experimental results on simulated and real EEG data recorded during BCI tasks prove that our proposed method well explains the variegate behaviour of brain EEG data. Specifically, it provides a characterization of brain functional mechanisms at group level, together with a measure of the separability of mental conditions at individual level. We also present a graph denoising procedure to filter data which simultaneously preserve the graph connectivity structure and enhance the signal-to-noise ratio. Since the use of a BCI system requires a dynamic interaction between user and machine, we finally propose a method to capture the evolution of time-varying data. In essence, this thesis presents a novel framework to grasp the complexity of graph functional connectivity during cognitive tasks

APA, Harvard, Vancouver, ISO, and other styles

10

Termenon, Conde Maite. "Analyse par graphes de la connectivité fonctionnelle de repos par IRM : vers de nouveaux biomarqueurs de la récupération fonctionnelle dans l'AVC." Thesis, Université Grenoble Alpes (ComUE), 2016. http://www.theses.fr/2016GREAS023/document.

Full text

APA, Harvard, Vancouver, ISO, and other styles

11

Roux, Marine. "Inférence de graphes par une procédure de test multiple avec application en Neuroimagerie." Thesis, Université Grenoble Alpes (ComUE), 2018. http://www.theses.fr/2018GREAT058/document.

Full text

Abstract:

Cette thèse est motivée par l’analyse des données issues de l’imagerie par résonance magnétique fonctionnelle (IRMf). La nécessité de développer des méthodes capables d’extraire la structure sous-jacente des données d’IRMf constitue un challenge mathématique attractif. A cet égard, nous modélisons les réseaux de connectivité cérébrale par un graphe et nous étudions des procédures permettant d’inférer ce graphe.Plus précisément, nous nous intéressons à l’inférence de la structure d’un modèle graphique non orienté par une procédure de test multiple. Nous considérons deux types de structure, à savoir celle induite par la corrélation et celle induite par la corrélation partielle entre les variables aléatoires. Les statistiques de tests basées sur ces deux dernières mesures sont connues pour présenter une forte dépendance et nous les supposerons être asymptotiquement gaussiennes. Dans ce contexte, nous analysons plusieurs procédures de test multiple permettant un contrôle des arêtes incluses à tort dans le graphe inféré.Dans un premier temps, nous questionnons théoriquement le contrôle du False Discovery Rate (FDR) de la procédure de Benjamini et Hochberg dans un cadre gaussien pour des statistiques de test non nécessairement positivement dépendantes. Nous interrogeons par suite le contrôle du FDR et du Family Wise Error Rate (FWER) dans un cadre gaussien asymptotique. Nous présentons plusieurs procédures de test multiple, adaptées aux tests de corrélations (resp. corrélations partielles), qui contrôlent asymptotiquement le FWER. Nous proposons de plus quelques pistes théoriques relatives au contrôle asymptotique du FDR.Dans un second temps, nous illustrons les propriétés des procédures contrôlant asymptotiquement le FWER à travers une étude sur simulation pour des tests basés sur la corrélation. Nous concluons finalement par l’extraction de réseaux de connectivité cérébrale sur données réelles
This thesis is motivated by the analysis of the functional magnetic resonance imaging (fMRI). The need for methods to build such structures from fMRI data gives rise to exciting new challenges for mathematics. In this regards, the brain connectivity networks are modelized by a graph and we study some procedures that allow us to infer this graph.More precisely, we investigate the problem of the inference of the structure of an undirected graphical model by a multiple testing procedure. The structure induced by both the correlation and the partial correlation are considered. The statistical tests based on the latter are known to be highly dependent and we assume that they have an asymptotic Gaussian distribution. Within this framework, we study some multiple testing procedures that allow a control of false edges included in the inferred graph.First, we theoretically examine the False Discovery Rate (FDR) control of Benjamini and Hochberg’s procedure in Gaussian setting for non necessary positive dependent statistical tests. Then, we explore both the FDR and the Family Wise Error Rate (FWER) control in asymptotic Gaussian setting. We present some multiple testing procedures, well-suited for correlation (resp. partial correlation) tests, which provide an asymptotic control of the FWER. Furthermore, some first theoretical results regarding asymptotic FDR control are established.Second, the properties of the multiple testing procedures that asymptotically control the FWER are illustrated on a simulation study, for statistical tests based on correlation. We finally conclude with the extraction of cerebral connectivity networks on real data set

APA, Harvard, Vancouver, ISO, and other styles

12

Faivre, Anthony. "Etude de la réorganisation de la connectivité cérébrale au repos dans la sclérose en plaques." Thesis, Aix-Marseille, 2014. http://www.theses.fr/2014AIXM5022/document.

Full text

Abstract:

L'IRMf de repos qui repose sur l'étude des fluctuations du signal BOLD chez un sujet au repos, pourrait permettre d'explorer les mécanismes du handicap dans la Sclérose En Plaques (SEP). En utilisant l'IRMf de repos, ce travail a eu pour objectif de caractériser la réorganisation fonctionnelle des patients atteints de SEP et ses liens avec leur handicap.Nous avons d'abord réalisé une étude combinant IRMf de repos et d'activation au stade précoce de la SEP et montré l'existence d'une corrélation entre la plasticité fonctionnelle du système moteur des patients au repos et durant la tâche. Nous avons ensuite montré l'existence d'une augmentation diffuse du niveau de connectivité fonctionnelle des patients présentant une SEP débutante, corrélée à leurs performances. Dans la 3ème partie, nous avons objectivé l'existence d'un déclin dynamique de la topologie fonctionnelle corrélée à la progression du handicap grâce à une étude longitudinale utilisant la théorie des graphes. Enfin, nous avons démontré que le gain fonctionnel obtenu par la rééducation chez les patients SEP était corrélé à une augmentation de connectivité fonctionnelle du réseau cérébral par défaut et central exécutif et de densité de substance grise dans le cortex frontal.Nos travaux montrent l'existence d'une réorganisation cérébrale fonctionnelle complexe et dynamique dans la SEP qui pourrait correspondre à des phénomènes compensatoires, dont le déclin avec l'évolution de la maladie participe à la progression du handicap. Ils démontrent l'intérêt de l'IRMf de repos pour la compréhension des substrats anatomo-fonctionnels du handicap dans la SEP et comme potentiel instrument futur d'évaluation thérapeutique
Resting-state fMRI (rs-fMRI) may provide important clue concerning disability in multiple sclerosis (MS) by exploring the spontaneous BOLD fluctuations at rest in the whole brain. The aim of this work is to depict the functional reorganization of resting-state networks in MS patients and to assess its potential relationships with disability.In the first part, we performed an fMRI protocol combining a rs-fMRI and task-associated fMRI during a motor task, in a group of early MS patients. This study evidenced a direct association between reorganization of connectivity at rest and during activation in the motor system of patients. In the second rs-fMRI study, we evidenced an increased of the global level of connectivity in most of the rs-networks, strongly associated with the level of disability of patients. In the third part, we evidenced in a 2-year longitudinal study using graph theoretical approach that MS patients exhibited a dynamical alteration of functional brain topology that significantly correlated with disability progression. In the last part, we evidenced that the transient clinical improvement following physical rehabilitation in MS patients is associated with reversible plasticity mechanisms located in the default mode network, the central executive network and in the left fronto-orbital cortex. These works evidence that MS patients exhibit a complex and dynamical functional reorganization of rs-networks, significantly associated with disability progression. This PhD thesis confirms that rs-fMRI is a relevant biomarker of pathophysiology leading to disability in MS and represents a promising tool for therapeutic assessment of MS patients in the future

APA, Harvard, Vancouver, ISO, and other styles

13

Saive, Anne-Lise. "Les odeurs, une passerelle vers les souvenirs : caractérisation des processus cognitifs et des fondements neuronaux de la mémoire épisodique olfactive." Thesis, Lyon 1, 2015. http://www.theses.fr/2015LYO10078/document.

Full text

Abstract:

La mémoire épisodique correspond à la reviviscence consciente d'expériences personnelles ancrées dans un contexte spécifique. Ce travail de thèse porte sur l'étude des processus cognitifs et des mécanismes neuronaux du rappel épisodique chez l'Homme. Les souvenirs rappelés par les odeurs sont plus détaillés et plus émotionnels que ceux évoqués par d'autres modalités sensorielles. Ces spécificités expliquent pourquoi nous nous intéressons à l'évocation des souvenirs par des odeurs. Tout d'abord, une tâche comportementale novatrice est développée pour permettre l'étude contrôlée de la mémoire d'épisodes complexes constitués d'odeurs non familières (Quoi), localisées à des emplacements distincts (Où), d'un environnement visuel donné (Quel contexte). A l'aide de cette tâche, nous montrons que, lorsque les dimensions d'un épisode sont étroitement liées, la perception de l'odeur permet le rappel de l'ensemble du souvenir. Le rappel épisodique est essentiellement fondé sur des processus de recollection, la familiarité n'étant pas suffisante pour récupérer l'ensemble du souvenir. De plus, les odeurs associées à une émotion, quelle que soit leur valence, facilitent le rappel épisodique correct. Fonctionnellement, la mémoire épisodique est sous-tendue par un large réseau neuronal, constitué de régions typiquement impliquées dans la mémoire de laboratoire et la mémoire autobiographique. Les souvenirs corrects sont associés à un réseau neuronal différent des souvenirs incorrects, de la perception de l'odeur à la ré-expérience du souvenir. Des analyses de modularité indiquent que les interactions fonctionnelles au sein du réseau de la mémoire épisodique dépendent également de l'exactitude du souvenir. L'ensemble de ces travaux suggère que le rappel épisodique est un processus dynamique complexe, initié dès la perception des odeurs, et interdépendant d'autres systèmes de mémoire tels que les mémoires perceptive et sémantique
Episodic memory is the memory that permits the conscious re-experience of specific personal events and associated with a specific context. This doctoral research aims at investigating the cognitive processes and the neural bases of episodic retrieval in humans. Odor-evoked memories are known to be more detailed and more emotional than memories triggered by other sensorial cues. These specificities explain why we studied odor-evoked memories. First, a novel behavioral task has been designed to study in a controlled way the memory of complex episodes comprising unfamiliar odors (What), localized spatially (Where), within a visual context (Which context). From this approach, we suggest that when the binding between the episodes’ dimensions is strong, the odor perception evokes the whole episodic memory. The episodic retrieval is mainly based on recollection processes, the feeling of knowing being insufficient to induce complete memory recovery. Moreover, emotion carried by odors, whatever its valence, promote accurate episodic retrieval. Functionally, episodic memory is underpinned by a distributed network, constituted of regions typically found in laboratory and autobiographical memory approaches. Accurate memories are associated with a specific neural network, from odor perception to memory re-experience. Modularity analyses show that neural interactions within this network also depend on memory accuracy. Altogether, results of this research suggest that episodic retrieval is a dynamic and complex process, triggered by odors perception, closely linked to other memory systems such as perceptual and semantic memories

APA, Harvard, Vancouver, ISO, and other styles

14

Marrelec, Guillaume. "Méthodes bayésiennes pour l'analyse de la réponse hémodynamique et de la connectivité fonctionnelle en IRM fonctionnelle : apport à l'étude de la plasticité dans la chirurgie des gliomes de bas grade intracérébraux." Paris 11, 2003. http://www.theses.fr/2003PA112260.

Full text

Abstract:

L'IRM fonctionnelle (IRMf) par effet BOLD est une modalité d'imagerie qui permet de suivre de manière dynamique et non invasive les évolutions hémodynamiques qui se produisent dans le cerveau suite à une activité neuronale. L'utilisation de l'IRMf permettrait en particulier de mieux comprendre les phénomènes de plasticité cérébrale qui se produisent dans les pathologies de gliomes de bas grades intracérébraux. Pour cela, il est nécessaire de développer de nouveaux modèles mathématiques. Après avoir présenté le cadre de nos recherches, nous développons le travail effectué sur deux modèles complémentaires dont l'objectif commun est l'étude des phénomènes de plasticité cérébrale. Le premier modèle considère le cerveau comme une boîte noire caractérisée par sa fonction dite de réponse hémodynamique. Nous avons proposé une méthode bayésienne robuste d'inférence de cette réponse, grâce à l'introduction d'information a priori simple mais pertinente sur le processus physiologique sous-jacent. Cette méthode a été généralisée pour pouvoir analyser la plupart des acquisitions d'IRMf mono-événementielles. Un autre modèle considère le réseau des régions qui interviennent dans une tâche donnée. Dans ce cadre, nous avons développé un modèle novateur, reposant sur la théorie des graphes indépendance, qui permet de quantifier les interactions au sein de ce réseau. Nous avons également proposé une méthode bayésienne d'estimation de ces grandeurs. Nous montrons finalement que ces deux approches peuvent être considérées comme deux cas particuliers d'un modèle plus général. Les deux méthodes développées ont été appliquées à des données cliniques afin d'étudier les phénomènes de plasticité cérébrale observé chez des patients atteints de gliomes de bas grades intra-cérébraux. La plupart des résultats obtenus concordent avec ceux de la littérature. D'autres permettent de jeter une nouvelle lumière sur la réorganisation fonctionnelle qui se produit chez les patients
BOLD functional MRI (fMAI) is a recent imaging technique that can be used to dynamically and non-invasively study brain hemodynamic evolutions induced by neuronal activity. Use of fMRI could in particular allow for a better understanding of the plasticity phenomena that occur in the pathology of law-grade gliomas. To this end, development of new mathematical models is necessary. We first briefly introduce functional neuroimaging and the methodological framework of our work. We then develop our research on two complementary models, whose common goal is the study of brain plasticity. The first model considers the brain as a black box characterized by its response function, the so-called hemodynamic response. We proposed a robust Bayesian method to inter this response, through introduction of basic yet relevant a priori information about the underlying physiological process. This method was then generalized to account for most event-related fMRI acquisitions. A second model considers the interactions between regions involved in a given task. We developed a novel model, relying on the theory of independence graphs, that enables the quantification of interactions within this network. We also proposed a Bayesian procedure to estimate these quantities. We finally show that both approaches can be considered as two special cases within a more general model whose further development would allow for a better understanding of brain functional processes as measured by fMRI. Both methods developed were applied to clinical data to investigate brain plasticity observed among patients with law-grade brain gliomas. Most results obtained agree with the litterature. Some cast a new light on the functional reorganization that occurs among patients

APA, Harvard, Vancouver, ISO, and other styles

15

Ait, Ali Kahina. "Modélisation et étude de performances dans les réseaux VANET." Phd thesis, Université de Technologie de Belfort-Montbeliard, 2012. http://tel.archives-ouvertes.fr/tel-00827552.

Full text

Abstract:

Les réseaux véhiculaires sont des systèmes de communication basés sur un échange d'informations de véhicules à infrastructures fixes installées au bord des routes, on parle alors de mode V2I (Vehicle-to-Infrastructure), ou de véhicules à véhicules dit mode V2V (Vehicle-to-Vehicle) ou VANET (Vehicular Ad hoc Network). L'objectif est de fournir aux conducteurs et aux opérateurs de transport des informations sur le trafic routier permettant d'améliorer l'efficacité des systèmes de transport, la sécurité et le confort des usagers. Depuis leur apparition, les VANET ont connu un très grand essor, de nombreux standards, applications et mécanismes de routage ont été proposés pour répondre aux spécificités de cette nouvelle classe de réseaux. Les défis à relever pour leur conception découlent principalement de la forte mobilité des véhicules, de la diversité spatio-temporelle de la densité du trafic et de la propagation des ondes radio en environnement extérieur défavorable à l'établissement des communications sans fil. La difficulté, aussi bien économique que logistique, de la mise en œuvre réelle des réseaux véhiculaires fait de la simulation le moyen le plus largement utilisé pour la conception et l'évaluation des solutions proposées. Cependant la validité des résultats de simulation dépend fortement de la capacité des modèles utilisés à reproduire le plus fidèlement possible les situations réelles. Deux aspects sont essentiellement importants dans les VANET : la mobilité des véhicules et la propagation des ondes radio. Nous proposons dans cette thèse un nouveau modèle de mobilité et un nouveau modèle de propagation d'ondes radio pour réseaux de véhicules en environnement urbain et suburbain. Pour définir des schémas réalistes, ces deux modèles se basent sur des données statiques et dynamiques réelles sur les caractéristiques topographiques et socio-économiques de l'environnement. Ces données décrivent particulièrement la distribution spatio-temporelle des véhicules et les infrastructures présentes dans l'environnement. Trois cas d'études sont présentés dans la thèse pour la validation des modèles développés ; un environnement théorique, urbain ou suburbain, défini par l'utilisateur, notamment le cas Manhattan très utilisé, et deux environnements réels qui représentent des agglomérations de taille moyenne. Une autre contribution de cette thèse est l'étude de la connectivité radio et des performances des protocoles de routage dans les VANET. A partir de graphes dynamiques de connexions représentant la variation des liens radio entre véhicules en déplacement, nous avons analysé et déterminé les propriétés de la topologie des liaisons radio des réseaux véhiculaires. Pour étudier les protocoles de routage, nous avons utilisé le modèle de mobilité et le modèle de propagation radio que nous avons développés en association avec le simulateur de réseaux ns-2. Nous avons comparé les performances des protocoles de routage les plus répandus et déterminé les mécanismes de routage les plus adaptés aux réseaux véhiculaires.

APA, Harvard, Vancouver, ISO, and other styles

16

Girardet, Xavier. "Paysage & [et] infrastructures de transport : modélisation des impacts des infrastructures sur les réseaux écologiques." Phd thesis, Université de Franche-Comté, 2013. http://tel.archives-ouvertes.fr/tel-01069242.

Full text

Abstract:

Le développement d'infrastructures linéaires de transport conduit, à toutes les échelles, à une artificialisation du territoire et au morcellement du milieu naturel. La fragmentation du paysage est un processus spatial qui s'accompagne d'une diminution progressive de la connectivité entre les différents éléments nécessaires au bon déroulement des processus écologiques. Ainsi, le maintien d'un bon niveau de connectivité entre les habitats naturels, s'il est compatible avec les activités humaines, est devenu un enjeu majeur pour la préservation de la biodiversité. En mobilisant des méthodes empruntées à la théorie des graphes et à l'écologie du paysage, la thèse cherche à démontrer l'intérêt de la modélisation des réseaux écologiques par les graphes paysagers, dans l'analyse des impacts des infrastructures à l'échelle régionale. Cette démarche, fondée sur la modélisation, a permis de démontrer l'influence du réseau écologique du chevreuil dans la localisation des collisions entre les individus de cette espèce et les véhicules empruntant le réseau de la DIR est en Franche-Comté. Le travail a également permis de proposer un cadre méthodologique pour localiser l'impact potentiel de la branche est de la LGV Rhin-Rhône sur la distribution d'une espèce, et estimer la distance de perturbation de cette infrastructure. Enfin, deux démarches sont proposées pour évaluer quantitativement et hiérarchiser des aménagements afin d'éviter ou d'atténuer ces impacts. Les résultats montrent la pertinence de l'intégration des réseaux écologiques dans les études d'impacts des infrastructures de transport.

APA, Harvard, Vancouver, ISO, and other styles

17

Obando, Forero Catalina. "Statistical graph models of temporal brain networks." Electronic Thesis or Diss., Sorbonne université, 2018. https://accesdistant.sorbonne-universite.fr/login?url=https://theses-intra.sorbonne-universite.fr/2018SORUS454.pdf.

Full text

Abstract:

La discipline encore naissante des réseaux complexes est vecteur d’un changement de paradigme dans la neuroscience. Les connectomes estimés à partir de mesures de neuroimagerie comme l’électroencéphalographie, la magnétoencéphalographie ou encore l’imagerie par résonance magnétique fonctionnelle fournissent une représentation abstraite du cerveau sous la forme d’un graphe, ce qui a permis des percées décisives dans la compréhension compacte et objective des propriétés topologiques et physiologiques des cerveaux sains. Cependant, les approches de pointe ignorent souvent l'incertitude et la nature temporelle de données de connectivité fonctionnelles. La plupart des méthodes disponibles dans la littérature ont en effet été développées pour caractériser les réseaux cérébraux fonctionnels comme des graphes statiques composés de nœuds (des régions cérébrales) et des liens (intensité de connectivité fonctionnelle) par métrique de réseau. En conséquence, la théorie des réseaux complexes a été principalement appliquée à des études transversales avec une unique mesure par sujet, produisant au final une caractérisation consistant en une moyenne de phénomènes neuronaux spatiotemporels. Nous avons implémenté des méthodes statistiques pour modéliser et simuler des réseaux cérébraux temporels. Nous avons utilisé des modèles de graphe qui permettent d'étudier simultanément à quel point les différentes propriétés des réseaux influencent la topologie observée dans les réseaux de connectivité cérébrale fonctionnelle. Nous avons identifié avec succès les mécanismes de connectivité locale fondamentaux qui gouvernent les propriétés des réseaux cérébraux. Nous avons proposé l'adaptation temporelle de ces mécanismes fondamentaux pour modéliser et simuler les changements physiologiques dynamiques d'un réseau cérébral. Plus spécifiquement, nous avons exploité des métriques temporelles pour construire des modèles temporels informatifs du rétablissement de patients ayant subit un accident vasculaire cérébral
The emerging area of complex networks has led to a paradigm shift in neuroscience. Connectomes estimated from neuroimaging techniques such as electroencephalography (EEG), magnetoencephalography (MEG) and functional magnetic resonance imaging (fMRI) results in an abstract representation of the brain as a graph, which has allowed a major breakthrough in the understanding of topological and physiological properties of healthy brains in a compact and objective way. However, state of the art approaches often ignore the uncertainty and temporal nature of functional connectivity data. Most of the available methods in the literature have been developed to characterize functional brain networks as static graphs composed of nodes (brain regions) and links (FC intensity) by network metrics. As a consequence, complex networks theory has been mainly applied to cross-sectional studies referring to a single point in time and the resulting characterization ultimately represents an average across spatiotemporal neural phenomena. Here, we implemented statistical methods to model and simulate temporal brain networks. We used graph models that allow to simultaneously study how different network properties influence the emergent topology observed in functional connectivity brain networks. We successfully identified fundamental local connectivity mechanisms that govern properties of brain networks. We proposed a temporal adaptation of such fundamental connectivity mechanisms to model and simulate physiological brain network dynamic changes. Specifically, we exploited the temporal metrics to build informative temporal models of recovery of patients after stroke

APA, Harvard, Vancouver, ISO, and other styles

18

Costa, Andrea. "Marine connectivity : exploring the role of currents and turbulent processes in driving it." Electronic Thesis or Diss., Aix-Marseille, 2017. http://www.theses.fr/2017AIXM0091.

Full text

Abstract:

La connectivité marine est le transfert de larves et/ou d'individus entre des habitats marins éloignés. Grâce à la connectivité, les populations marines éloignées peuvent faire face à la pression de l'habitat en s'appuyant sur le transfert qui vient des populations éloignées de la même espèce. Le transfert entre les populations éloignées dans l'océan est possible par le transport dû aux courants. Cependant, il est pas encore clair si le champ des courants détermine totalement la persistance des espèces marines ou si la démographie locale joue un rôle. Les mesures in situ de la connectivité sont extrêmement difficiles. Par conséquence, notre connaissance de la connectivité est déduite des simulations numériques de dispersion. Le but de cette thèse est de préciser si la persistance de la connaissance du champ des courants et d’étudier l'effet des paramétrisations numériques dans l'estimation de la connectivité. Premièrement, je compare la théorie des graphes et le modèle de métapopulation pour déterminer si les courants ont un rôle prédominant. Cela permet d'identifier quelles mesures de la théories des graphes identifient de manière fiable les sites reproductifs importants pour la persistance en s'appuyant sur la connaissance des seuls courants. Deuxièmement, j’étudie les avantages et les lacunes de différents schémas de fermeture de turbulence. Ceci permet de préciser quel schéma reproduit mieux l'activité de turbulence dans des modèles numériques. Troisièmement, j'étudie les mécanismes générateurs de turbulence aux limites du fond. Ceci permet de connaître le coefficient de traînée effectif dû aux flux sur la topographie brute et de mieux estimer les flux turbulents
Marine connectivity is the transfer of larvae and/or individuals between distant marine habitats. Thanks to connectivity, distant marine population can face habitat pressure by relying on the transfer from distant populations of the same species. The transfer between distant populations in the ocean is made possible by the transport due to the currents. However, it is still not clear if the current field totally determines the persistence of the marine species or if the local demography plays a role. Crucially, in situ measurements of connectivity are extremely difficult. Therefore, our knowledge about connectivity is inferred from numerical dispersal simulations. The aim of this thesis is to clarify if we can deduce the persistence from the knowledge of the current field and to investigate the effect of numerical turbulence parameterizations in estimating connectivity. Firstly, I compare graph theory and metapopulation model to determine if currents have a predominant role. This allows to identify which graph theory measures reliably identifies reproductive sites important for persistence by relying on the knowledge of currents only. Secondly, I investigate the advantages and shortcomings of different turbulence closure models. This allows to clarify which TCS better reproduces turbulence activity in numerical models. Thirdly, I investigate generating mechanisms of bottom boundary turbulence. This allows to know the effective drag coefficient due to flow over rough topography and better estimate turbulent fluxes

APA, Harvard, Vancouver, ISO, and other styles

19

Costa, Andrea. "Marine connectivity : exploring the role of currents and turbulent processes in driving it." Thesis, Aix-Marseille, 2017. http://www.theses.fr/2017AIXM0091/document.

Full text

Abstract:

La connectivité marine est le transfert de larves et/ou d'individus entre des habitats marins éloignés. Grâce à la connectivité, les populations marines éloignées peuvent faire face à la pression de l'habitat en s'appuyant sur le transfert qui vient des populations éloignées de la même espèce. Le transfert entre les populations éloignées dans l'océan est possible par le transport dû aux courants. Cependant, il est pas encore clair si le champ des courants détermine totalement la persistance des espèces marines ou si la démographie locale joue un rôle. Les mesures in situ de la connectivité sont extrêmement difficiles. Par conséquence, notre connaissance de la connectivité est déduite des simulations numériques de dispersion. Le but de cette thèse est de préciser si la persistance de la connaissance du champ des courants et d’étudier l'effet des paramétrisations numériques dans l'estimation de la connectivité. Premièrement, je compare la théorie des graphes et le modèle de métapopulation pour déterminer si les courants ont un rôle prédominant. Cela permet d'identifier quelles mesures de la théories des graphes identifient de manière fiable les sites reproductifs importants pour la persistance en s'appuyant sur la connaissance des seuls courants. Deuxièmement, j’étudie les avantages et les lacunes de différents schémas de fermeture de turbulence. Ceci permet de préciser quel schéma reproduit mieux l'activité de turbulence dans des modèles numériques. Troisièmement, j'étudie les mécanismes générateurs de turbulence aux limites du fond. Ceci permet de connaître le coefficient de traînée effectif dû aux flux sur la topographie brute et de mieux estimer les flux turbulents
Marine connectivity is the transfer of larvae and/or individuals between distant marine habitats. Thanks to connectivity, distant marine population can face habitat pressure by relying on the transfer from distant populations of the same species. The transfer between distant populations in the ocean is made possible by the transport due to the currents. However, it is still not clear if the current field totally determines the persistence of the marine species or if the local demography plays a role. Crucially, in situ measurements of connectivity are extremely difficult. Therefore, our knowledge about connectivity is inferred from numerical dispersal simulations. The aim of this thesis is to clarify if we can deduce the persistence from the knowledge of the current field and to investigate the effect of numerical turbulence parameterizations in estimating connectivity. Firstly, I compare graph theory and metapopulation model to determine if currents have a predominant role. This allows to identify which graph theory measures reliably identifies reproductive sites important for persistence by relying on the knowledge of currents only. Secondly, I investigate the advantages and shortcomings of different turbulence closure models. This allows to clarify which TCS better reproduces turbulence activity in numerical models. Thirdly, I investigate generating mechanisms of bottom boundary turbulence. This allows to know the effective drag coefficient due to flow over rough topography and better estimate turbulent fluxes

APA, Harvard, Vancouver, ISO, and other styles

20

Marie, Sylvain. "Déploiement optimal d’un réseau de capteurs sous des contraintes de couverture et de connectivité." Electronic Thesis or Diss., Paris, CNAM, 2019. http://www.theses.fr/2019CNAM1248.

Full text

Abstract:

L'objet de cette thèse sur les réseaux de capteurs est l'étude du déploiement minimal de capteurs lorsque ceux-ci doivent couvrir un ensemble discret de cibles plutôt que des superficies. Après la présentation des caractéristiques d'un réseau de capteurs, et l'intérêt d'un déploiement minimal, nous en proposons une modélisation en théorie des graphes. Nous présentons ensuite un état de l'art décrivant certaines techniques de résolution par la programmation mathématique de diverses problématiques dans ce type de réseau. Nous utilisons plusieurs programmes linéaires en variables mixtes afin de résoudre le problème du déploiement minimal des capteurs sous des contraintes de couverture de toutes les cibles et de connectivité des capteurs entre eux. Finalement, nous concevons une nouvelle heuristique de calcul de placement de capteurs lorsque les cibles sont placées sur une grille à motif carré et nous conjecturons que cette heuristique retourne une solution optimale dans tous les cas
The objectif of this thesis on wireless sensor networks is to study the deployment of a minimal number of sensors to cover specific targets instead of continuous areas. After a presentation of the characteristics of wireless sensor networks, and after justifying the interest of an optimal sensor deployment, we propose a graph-theory based model for wireless sensor networks. We then present a state of the art describing various mathematical programming models and resolution techniques regarding a number of optimization problems in such networks. We formulate several Mixed Integer Linear programs to solve the optimal sensor deployment problem under contraints related to the coverage of all targets and connectivity between sensors. Finally, we conceive a new heuristic for sensor placement when targets are placed in a square grid graph, and we conjecture that this heuristic returns an optimal solution in all cases

APA, Harvard, Vancouver, ISO, and other styles

21

Frusque, Gaëtan. "Inférence et décomposition modale de réseaux dynamiques en neurosciences." Thesis, Lyon, 2020. http://www.theses.fr/2020LYSEN080.

Full text

Abstract:

Les graphes dynamiques permettent de comprendre l'évolution de systèmes complexes qui évoluent dans le temps. Ce type de graphe a récemment fait l'objet d'une attention considérable. Cependant, il n'existe pas de consensus sur les manières d'inférer et d'étudier ces graphes. Dans cette thèse, on propose des méthodes d'analyse de graphes dynamiques spécifiques. Ceux-ci peuvent être vues comme une succession de graphes complets partageant les mêmes nœuds, mais dont les poids associés à chaque lien évoluent dans le temps. Les méthodes proposées peuvent avoir des applications en neurosciences ou dans l'étude des réseaux sociaux comme Twitter et Facebook par exemple. L'enjeu applicatif de cette thèse est l'épilepsie, l'une des maladies neurologiques les plus rependues dans le monde affectant environ 1% de la population.La première partie concerne l'inférence de graphe dynamique à partir de signaux neurophysiologiques. Cette inférence est généralement réalisée à l'aide de mesures de connectivité fonctionnelle permettant d'évaluer la similarité entre deux signaux. La comparaison de ces mesures est donc d'un grand intérêt pour comprendre les caractéristiques des graphes obtenus. On compare alors des mesures de connectivité fonctionnelle impliquant la phase et l'amplitude instantanée des signaux. On s'intéresse en particulier à une mesure nommée Phase-Locking-Value (PLV) qui quantifie la synchronie des phases entre deux signaux. On propose ensuite, afin d'inférer des graphes dynamiques robustes et interprétables, deux nouvelles mesures de PLV conditionnées et régulariséesLa seconde partie présente des méthodes de décomposition de graphes dynamiques. L'objectif est de proposer une méthode semi-automatique afin de caractériser les informations les plus importantes du réseau pathologique de plusieurs crises d'un même patient. Dans un premier temps on considère des crises qui ont des durées et des évolutions temporelles similaires. Une décomposition tensorielle spécifique est alors appliquée. Dans un second temps, on considère des crises qui ont des durées hétérogènes. Plusieurs stratégies sont proposées et comparées. Ce sont des méthodes qui en plus d'extraire les sous-graphes caractéristiques communs à toutes les crises, permettent d'observer leurs profils d'activation temporelle spécifiques à chaque crise. Finalement, on utilise la méthode retenue pour une application clinique. Les décompositions obtenues sont comparées à l'interprétation visuelle du clinicien. Dans l'ensemble, on constate que les sous-graphes extraits correspondent aux régions du cerveau impliquées dans la crise d'épilepsie. De plus l'évolution de l'activation de ces sous-graphes est cohérente avec l'interprétation visuelle
Dynamic graphs make it possible to understand the evolution of complex systems evolving over time. This type of graph has recently received considerable attention. However, there is no consensus on how to infer and study these graphs. In this thesis, we propose specific methods for dynamical graph analysis. A dynamical graph can be seen as a succession of complete graphs sharing the same nodes, but with the weights associated with each link changing over time. The proposed methods can have applications in neuroscience or in the study of social networks such as Twitter and Facebook for example. The issue of this thesis is epilepsy, one of the most common neurological diseases in the world affecting around 1% of the population.The first part concerns the inference of dynamical graph from neurophysiological signals. To assess the similarity between each pairs of signals, in order to make the graph, we use measures of functional connectivity. The comparison of these measurements is therefore of great interest to understand the characteristics of the resulting graphs. We then compare functional connectivity measurements involving the instantaneous phase and amplitude of the signals. We are particularly interested in a measure called Phase-Locking-Value (PLV) which quantifies the phase synchrony between two signals. We then propose, in order to infer robust and interpretable dynamic graphs, two new indexes that are conditioned and regularized PLV. The second part concerns tools for dynamical graphs decompositions. The objective is to propose a semi-automatic method in order to characterize the most important patterns in the pathological network from several seizures of the same patient. First, we consider seizures that have similar durations and temporal evolutions. In this case the data can be conveniently represented as a tensor. A specific tensor decomposition is then applied. Secondly, we consider seizures that have heterogeneous durations. Several strategies are proposed and compared. These are methods which, in addition to extracting the characteristic subgraphs common to all the seizures, make it possible to observe their temporal activation profiles specific to each seizures. Finally, the selected method is used for a clinical application. The obtained decompositions are compared to the visual interpretation of the clinician. As a whole, we found that activated subgraphs corresponded to brain regions involved during the course of the seizures and their time course were highly consistent with classical visual interpretation

APA, Harvard, Vancouver, ISO, and other styles

22

Malagurski, Brigitta. "Signatures neurales de l'abolition et de la récupération de conscience à partir du coma." Thesis, Toulouse 3, 2018. http://www.theses.fr/2018TOU30039/document.

Full text

Abstract:

Les objectifs de cette thèse étaient de caractériser les corrélats neuronaux fonctionnels et structurels de l'abolition de la conscience observés pendant le coma et d'identifier les signatures neuronales précoces de la récupération neurologique à partir de cet état. Pour atteindre ce but, nous avons étudié des patients cérébrolésés, recrutés au stade aigu du coma, à l'aide de l'IRM fonctionnelle au repos et IRM structurale. Nos résultats indiquent une réorganisation topologique globale du cerveau des patients, reflétée par une dédifférenciation et une réduction de la résilience des réseaux fonctionnels au repos d'ordre élevé. Ces anomalies sont accompagnées d'une perte de connexions fronto-pariétales à longue distance. Au niveau régional, nous avons observé un schéma complexe de diminution et d'augmentation de la densité de connexion fonctionnelle entre le cortex postéromédial et le cortex préfrontal médial : régions précédemment décrites pour avoir un rôle critique dans la conscience. De manière intéressante, ces modifications de densité de connexion étaient significativement liées à la récupération des patients trois mois après le coma. Enfin, l'analyse multimodale a permis de démontrer une association significative entre la connectivité fonctionnelle et l'intégrité structurelle cérébrales antéro-postérieure, fournissant des informations importantes sur le lien structure/fonction au décours de ces troubles acquis de la conscience
The aim of the present thesis was to characterize the functional and structural neural correlates of acute consciousness abolition induced by severe brain injury and identify early neural signatures of long-term neurological recovery. To do so, we studied brain-injured patients, recruited in the acute stage of coma, using resting-state functional and structural MRI. Our findings indicated a global topological brain reorganization in coma patients, reflected in dedifferentiated and less resilient high-order resting-state functional networks, paralleled with a loss of long-range fronto-parietal connections. On a regional level, we found a complex pattern of voxel-wise decrease and increase in functional connection density between the posteromedial cortex and the medial prefrontal cortex, regions previously described to have a critical role in conscious processing. These connection density patterns seemed to permit outcome prediction in patients, assessed three months post-coma. Furthermore, the multi-modal MRI analysis demonstrated a significant association between antero-posterior functional connectivity and structural integrity, providing further insights into the pathological underpinning of conscious processing

APA, Harvard, Vancouver, ISO, and other styles

23

Tabchi, Theresia. "Relation entre enseignement et recherche dans le travail documentaire des enseignants-chercheurs – cas de l’enseignement de la théorie des graphes." Thesis, Reims, 2020. http://www.theses.fr/2020REIMS024.

Full text

Abstract:

Notre travail porte sur les pratiques d’enseignement des enseignants-chercheurs en mathématiques à l’université. Celles-ci admettent des spécificités : l’articulation entre les activités d’enseignement et de recherche en est un exemple. Nous cherchons à caractériser la place de l’activité de recherche dans les pratiques d’enseignement des enseignants-chercheurs. Nous avons fait le choix d’explorer cette thématique à partir de l’interaction avec les ressources pour l’enseignement de la théorie des graphes. Le choix de la théorie des graphes est lié au fait qu’elle s’inscrit dans le cadre des mathématiques « contemporaines », et qu’elle est enseignée dans un large spectre de formation au Liban comme en France. Notre méthodologie prend appui tout d’abord sur des entretiens avec des enseignants-chercheurs. Nous nous appuyons sur l’approche documentaire du didactique, en particulier le concept de schème d’utilisation de ressources pour caractériser leurs interactions avec des ressources issues de l’enseignement et de la recherche. Nous proposons par ailleurs une analyse de ressources conçues collectivement par des enseignants-chercheurs interviewés avec appui sur le concept de « connectivité », suivie par des observations de séances d’une enseignante-chercheure, faisant partie des concepteurs des ressources analysées. Nous avons mis en évidence qu’une mise en regard des processus de conception des ressources et des processus de leur mise en œuvre nous permet de caractériser des différents facteurs qui impactent les pratiques des enseignants-chercheurs
Our work deals with the teaching practices of university mathematics professors. These concur specificities: the articulation between teaching and research is an example. We seek to characterize the research impact in the teaching practices at university. We have chosen to explore this theme through the lens of the interaction with resources for teaching graph theory. The choice of graph theory is due to the fact that it is a branch of mathematics that belongs to "contemporary" mathematics, and that is taught in a wide spectrum of university majors in Lebanon as in France. Our methodology first draws on interviews with university professors. We rely on the documentational approach, in particular the concept of the scheme of use of resources to characterize the interactions of university professors with resources issued from teaching and research. We also analyze resources designed collectively by some of the university professors interviewed using the concept of connectivity, followed by observations of sessions by a university professor, one of the designers of the resources analyzed. We have shown that a comparison of the processes of the design of resources and their implementation in class allows us to characterize the various factors that impact the practices of university professors

APA, Harvard, Vancouver, ISO, and other styles

24

Marie, Sylvain. "Déploiement optimal d’un réseau de capteurs sous des contraintes de couverture et de connectivité." Thesis, Paris, CNAM, 2019. http://www.theses.fr/2019CNAM1248/document.

Full text

Abstract:

L'objet de cette thèse sur les réseaux de capteurs est l'étude du déploiement minimal de capteurs lorsque ceux-ci doivent couvrir un ensemble discret de cibles plutôt que des superficies. Après la présentation des caractéristiques d'un réseau de capteurs, et l'intérêt d'un déploiement minimal, nous en proposons une modélisation en théorie des graphes. Nous présentons ensuite un état de l'art décrivant certaines techniques de résolution par la programmation mathématique de diverses problématiques dans ce type de réseau. Nous utilisons plusieurs programmes linéaires en variables mixtes afin de résoudre le problème du déploiement minimal des capteurs sous des contraintes de couverture de toutes les cibles et de connectivité des capteurs entre eux. Finalement, nous concevons une nouvelle heuristique de calcul de placement de capteurs lorsque les cibles sont placées sur une grille à motif carré et nous conjecturons que cette heuristique retourne une solution optimale dans tous les cas
The objectif of this thesis on wireless sensor networks is to study the deployment of a minimal number of sensors to cover specific targets instead of continuous areas. After a presentation of the characteristics of wireless sensor networks, and after justifying the interest of an optimal sensor deployment, we propose a graph-theory based model for wireless sensor networks. We then present a state of the art describing various mathematical programming models and resolution techniques regarding a number of optimization problems in such networks. We formulate several Mixed Integer Linear programs to solve the optimal sensor deployment problem under contraints related to the coverage of all targets and connectivity between sensors. Finally, we conceive a new heuristic for sensor placement when targets are placed in a square grid graph, and we conjecture that this heuristic returns an optimal solution in all cases

APA, Harvard, Vancouver, ISO, and other styles

25

Darishchev, Alexander. "Analyse de connectivité et techniques de partitionnement de données appliquées à la caractérisation et la modélisation d'écoulement au sein des réservoirs très hétérogènes." Thesis, Rennes 1, 2015. http://www.theses.fr/2015REN1S162.

Full text

Abstract:

Les techniques informatiques ont gagné un rôle primordial dans le développement et l'exploitation des ressources d'hydrocarbures naturelles ainsi que dans d'autres opérations liées à des réservoirs souterrains. L'un des problèmes cruciaux de la modélisation de réservoir et les prévisions de production réside dans la présélection des modèles de réservoir appropriés à la quantification d'incertitude et au le calage robuste des résultats de simulation d'écoulement aux réelles mesures et observations acquises du gisement. La présente thèse s'adresse à ces problématiques et à certains autres sujets connexes.Nous avons élaboré une stratégie pour faciliter et accélérer l'ajustement de tels modèles numériques aux données de production de champ disponibles. En premier lieu, la recherche s'était concentrée sur la conceptualisation et l'implémentation des modèles de proxy reposant sur l'analyse de la connectivité, comme une propriété physique intégrante et significative du réservoir, et des techniques avancées du partitionnement de données et de l'analyse de clusters. La méthodologie développée comprend aussi plusieurs approches originales de type probabiliste orientées vers les problèmes d'échantillonnage d'incertitude et de détermination du nombre de réalisations et de l'espérance de la valeur d'information d'échantillon. Afin de cibler et donner la priorité aux modèles pertinents, nous avons agrégé les réalisations géostatistiques en formant des classes distinctes avec une mesure de distance généralisée. Ensuite, afin d'améliorer la classification, nous avons élargi la technique graphique de silhouettes, désormais appelée la "séquence entière des silhouettes multiples" dans le partitionnement de données et l'analyse de clusters. Cette approche a permis de recueillir une information claire et compréhensive à propos des dissimilarités intra- et intre-cluster, particulièrement utile dans le cas des structures faibles, voire artificielles. Finalement, la séparation spatiale et la différence de forme ont été visualisées graphiquement et quantifiées grâce à la mesure de distance probabiliste.Il apparaît que les relations obtenues justifient et valident l'applicabilité des approches proposées pour améliorer la caractérisation et la modélisation d'écoulement. Des corrélations fiables ont été obtenues entre les chemins de connectivité les plus courts "injecteur-producteur" et les temps de percée d'eau pour des configurations différentes de placement de puits, niveaux d'hétérogénéité et rapports de mobilité de fluides variés. Les modèles de connectivité proposés ont produit des résultats suffisamment précis et une performance compétitive au méta-niveau. Leur usage comme des précurseurs et prédicateurs ad hoc est bénéfique en étape du traitement préalable de la méthodologie. Avant le calage d'historique, un nombre approprié et gérable des modèles pertinents peut être identifié grâce à la comparaison des données de production disponibles avec les résultats de
Computer-based workflows have gained a paramount role in development and exploitation of natural hydrocarbon resources and other subsurface operations. One of the crucial problems of reservoir modelling and production forecasting is in pre-selecting appropriate models for quantifying uncertainty and robustly matching results of flow simulation to real field measurements and observations. This thesis addresses these and other related issues. We have explored a strategy to facilitate and speed up the adjustment of such numerical models to available field production data. Originally, the focus of this research was on conceptualising, developing and implementing fast proxy models related to the analysis of connectivity, as a physically meaningful property of the reservoir, with advanced cluster analysis techniques. The developed methodology includes also several original probability-oriented approaches towards the problems of sampling uncertainty and determining the sample size and the expected value of sample information. For targeting and prioritising relevant reservoir models, we aggregated geostatistical realisations into distinct classes with a generalised distance measure. Then, to improve the classification, we extended the silhouette-based graphical technique, called hereafter the "entire sequence of multiple silhouettes" in cluster analysis. This approach provided clear and comprehensive information about the intra- and inter-cluster dissimilarities, especially helpful in the case of weak, or even artificial, structures. Finally, the spatial separation and form-difference of clusters were graphically visualised and quantified with a scale-invariant probabilistic distance measure. The obtained relationships appeared to justify and validate the applicability of the proposed approaches to enhance the characterisation and modelling of flow. Reliable correlations were found between the shortest "injector-producer" pathways and water breakthrough times for different configurations of well placement, various heterogeneity levels and mobility ratios of fluids. The proposed graph-based connectivity proxies provided sufficiently accurate results and competitive performance at the meta-level. The use of them like precursors and ad hoc predictors is beneficial at the pre-processing stage of the workflow. Prior to history matching, a suitable and manageable number of appropriate reservoir models can be identified from the comparison of the available production data with the selected centrotype-models regarded as the class representatives, only for which the full fluid flow simulation is pre-requisite. The findings of this research work can easily be generalised and considered in a wider scope. Possible extensions, further improvements and implementation of them may also be expected in other fields of science and technology

APA, Harvard, Vancouver, ISO, and other styles

26

Rannou, Léo. "Temporal Connectivity and Path Computation for Stream Graph." Electronic Thesis or Diss., Sorbonne université, 2020. http://www.theses.fr/2020SORUS418.

Full text

Abstract:

Les données structurelles et les données temporelles ont, pendant longtemps, été analysées séparément. De nombreux réseaux complexes contiennent une dimension temporelle, comme les contacts entre individus ou les transactions financières. La théorie des graphes fournit un large ensemble d'outils pour modéliser et analyser les connexions entre entités. Malheureusement, cette approche ne prend pas compte la nature temporelle des interactions. La théorie des stream graphs est un formalisme permettant de modéliser les réseaux dynamiques dans lesquels les nœuds et/ou les liens arrivent et/ou partent au fil du temps. Plusieurs concepts théoriques tels que les composantes connexes dans les stream graphs ont été définis récemment, mais aucun algorithme n'a été proposé pour les calculer. De plus, la complexité algorithmique de ces problèmes est inconnue, ainsi que les connaissances qu'ils peuvent apporter sur les stream graphs de terrain. Dans cette thèse, nous proposons plusieurs solutions pour le calcul de notions de connectivité et de chemins dans les stream graphs. Nous présentons également des représentations alternatives - des structures de données conçues pour faciliter certains calculs - stream graphs. Nous fournissons également des implémentations et comparons expérimentalement nos méthodes sur une grande variété de cas pratiques. Nous montrons que ces concepts apportent beaucoup d'informations sur les caractéristiques de ces ensembles de données. Straph, une bibliothèque python, a été développée afin de disposer d'une ressource fiable afin de manipuler, analyser et visualiser les stream graphs
For a long time, structured data and temporal data have been analysed separately. Many real world complex networks have a temporal dimension, such as contacts between individuals or financial transactions. Graph theory provides a wide set of tools to model and analyze static connections between entities. Unfortunately, this approach does not take into account the temporal nature of interactions. Stream graph theory is a formalism to model highly dynamic networks in which nodes and/or links arrive and/or leave over time. The number of applications of stream graph theory has risen rapidly, along with the number of theoretical concepts and algorithms to compute them. Several theoretical concepts such as connected components and temporal paths in stream graphs were defined recently, but no algorithm was provided to compute them. Moreover, the algorithmic complexities of these problems are unknown, as well as the insight they may shed on real-world stream graphs of interest. In this thesis, we present several solutions to compute notions of connectivity and path concepts in stream graphs. We also present alternative representations - data structures designed to facilitate specific computations - of stream graphs. We provide implementations and experimentally compare our methods in a wide range of practical cases. We show that these concepts indeed give much insight on features of large-scale datasets. Straph, a python library, was developed in order to have a reliable library for manipulating, analysing and visualising stream graphs, to design algorithms and models, and to rapidly evaluate them

APA, Harvard, Vancouver, ISO, and other styles

27

Nader, Noujoud. "Connectivity analysis of the EHG during pregnancy and labor." Thesis, Compiègne, 2017. http://www.theses.fr/2017COMP2329.

Full text

Abstract:

L’accouchement prématuré est l’un des problèmes majeurs en obstétrique. Par suite, il a été un sujet d'intérêt pour de nombreux chercheurs. Parmi les nombreuses méthodes utilisées pour enregistrer la contractilité utérine, le plus utilisé est l'EHG abdominal, comme étant un outil facile à utiliser et non invasif. De nombreuses études ont indiqué que l'utilisation de ce signal pourrait être un outil très puissant pour surveiller la grossesse et pour détecter le travail. Il permet en effet d'accéder à l'utérus ainsi que la synchronisation de l'activité utérine, en utilisant des signaux multiples. Il a été démontré que l'analyse de connectivité des signaux EHG a donné des résultats prometteurs en application clinique, comme la classification des contractions de travail et de grossesse. Cependant, dans presque toutes les études antérieures, les matrices de corrélation EHG étaient souvent réduites en ne gardant que leur moyenne et les écarts-types, ce qui a peut aboutir à perdre des informations pertinentes en raison de ce moyennage, ce qui peut induire le taux de classification relativement faible jusqu'à présent. Pour caractériser précisément la matrice de corrélation et quantifier la connectivité associée, nous avons proposé dans cette thèse d'utiliser une technique de mesure de réseau basée sur la théorie des graphes. Selon cette approche, la matrice de corrélation obtenue peut être représentée sous forme de graphiques constitués d'un ensemble de nœuds (électrodes) interconnectés par des arêtes (valeurs de connectivité / corrélation entre électrodes). La nouvelle procédure de l'analyse des signaux EHG enregistrés pendant la grossesse et le travail se base sur la caractérisation de la corrélation entre les activités électriques utérines et sur sa quantification précise en utilisant l'approche de la théorie des graphes. Le pipeline de traitement inclut i) l'estimation des dépendances statistiques entre les différents signaux EHG enregistrés, ii) la quantification des matrices de connectivité obtenues à l'aide de l'analyse théorique des graphes et iii) l'utilisation clinique des mesures de réseau pour la surveillance de la grossesse ainsi que la classification entre les éclosions d'EHG de grossesse et de travail. Une comparaison avec les paramètres déjà existants utilisés pour la détection du travail et la détection d’accouchement prématuré sera également effectuée. Nous étudions également une nouvelle méthode pour étudier la connectivité source EHG, afin de surmonter le problème du calcul de la connectivité au niveau de la surface abdominale. Les résultats de cette thèse montrent que cette approche basée sur la théorie de graphe est un outil très prometteur pour quantifier la synchronisation utérine, lorsqu'elle est appliquée à l'abdomen, pour une meilleure surveillance de la grossesse. Nous espérons que cette approche soit utilisée pour le suivi de la grossesse et contribuerait ainsi à la prédiction précoce de l’accouchement prématuré
Preterm birth remains a major problem in obstetrics. Therefore, it has been a topic of interest for many researchers. Among the many methods used to record the uterine contractility, the most used is the abdominal EHG, as being an easy to use and a non-invasive tool. Many studies have reported that the use of this signal could be a very powerful tool to monitor pregnancy and to detect labor. It indeed permits to access the uterine as well as the synchronization of the uterine activity, by using multiple signals. It has been shown that the connectivity analysis gave promising results when using EHG recordings in clinical application, such as the classification labor/pregnancy contractions. However, in almost all previous studies EHG correlation matrices were often reduced keeping only their mean and standard deviations thus relevant information may have been missed due to this averaging, which may induce the relatively low classification rate reported so far. To characterize precisely the correlation matrix and quantify the associated connectivity, we proposed in this thesis to use a network measure technique based on graph theory. According to this approach, the obtained correlation matrix can be represented as graphs consisting of a set of nodes (electrodes) interconnected by edges (connectivity/correlation values between electrodes). The new framework, to analyze the EHG signals recorded during pregnancy and labor, is based on the characterization of the correlation between the uterine electrical activities and on its precise quantification by using graph theory approach. The processing pipeline includes i) the estimation of the statistical dependencies between the different recorded EHG signals, ii) the quantification of the obtained connectivity matrices using graph theory-based analysis and iii) the clinical use of network measures for pregnancy monitoring as well as for the classification between pregnancy and labor EHG bursts. A comparison with the already existing parameters used in the state of the art for labor detection and preterm labor prediction will also be performed. We also investigate a new method to study the EHG source connectivity, to overcome the problem of computing the connectivity at the abdominal surface level. The results of this thesis showed that this network-based approach is a very promising tool to quantify uterine synchronization, when applied at the abdominal level, for a better pregnancy monitoring. We expect this approach to be further used for the monitoring of pregnancy and would thus help for the early prediction of preterm labor

APA, Harvard, Vancouver, ISO, and other styles

28

Durand, de Gevigney Olivier. "Orientations des graphes : structures et algorithmes." Thesis, Grenoble, 2013. http://www.theses.fr/2013GRENM027/document.

Full text

Abstract:

Orienter un graphe c'est remplacer chaque arête par un arc de mêmes extrémités. On s'intéresse à la connexité du graphe orienté ainsi obtenu. L'orientation avec des contraintes d'arc-connexité est maintenant comprise en profondeur mais très peu de résultats sont connus en terme de sommet-connexité. La conjecture de Thomassen avance que les graphes suffisament sommet-connexes ont une orientation k-sommet-connexe. De plus, la conjecture de Frank propose une caractérisation des graphes qui admettent une telle orientation. Les résultats de cette thèse s'articulent autour des notions d'orientation, de packing, de connexité et de matroïde. D'abord, nous infirmons une conjecture de Recski sur la décomposition d'un graphe en arbres ayant des orientations avec degrés entrants prescrits. Nous prouvons également un nouveau résultat sur le packing d'arborescences enracinées avec contraintes de matroïdes. Ceci généralise un résultat fondamental d'Edmonds. Enfin, nous démontrons un nouveau théorème de packing sur les bases des matroïdes de dénombrement qui nous permet d'améliorez le seul résultat connu sur la conjecture de Thomassen. D'autre part, nous donnons une construction et un théorème d'augmentation pour une famille de graphes liée à la conjecture de Frank. En conclusion, nous réfutons la conjecture de Frank et prouvons que, pour tout entier k >= 3, décider si un graphe a une orientation k-sommet-connexe est un problème NP-complet
Orienting an undirected graph means replacing each edge by an arc with the same ends. We investigate the connectivity of the resulting directed graph. Orientations with arc-connectivity constraints are now deeply understood but very few results are known in terms of vertex-connectivity. Thomassen conjectured that sufficiently highly vertex-connected graphs have a k-vertex- connected orientation while Frank conjectured a characterization of the graphs admitting such an orientation. The results of this thesis are structures around the concepts of orientation, packing, connectivity and matroid. First, we disprove a conjecture of Recski on decomposing a graph into trees having orientations with specified indegrees. We also prove a new result on packing rooted arborescences with matroid constraints. This generalizes a fundamental result of Edmonds. Moreover, we show a new packing theorem for the bases of count matroids that induces an improvement of the only known result on Thomassen's conjecture. Secondly, we give a construction and an augmentation theorem for a family of graphs related to Frank's conjecture. To conclude, we disprove the conjecture of Frank and prove that, for every integer k >= 3, the problem of deciding whether a graph admits a k-vertex-orientation is NP-complete

APA, Harvard, Vancouver, ISO, and other styles

29

Maceli, Peter Lawson. "Deciding st-connectivity in undirected graphs using logarithmic space." Columbus, Ohio : Ohio State University, 2008. http://rave.ohiolink.edu/etdc/view?acc%5Fnum=osu1211753530.

Full text

APA, Harvard, Vancouver, ISO, and other styles

30

Bader, El Dine Kamil. "Uterine synchronization analysis during pregnancy and labor using graph theory, classification based on machine learning." Thesis, Compiègne, 2022. http://www.theses.fr/2022COMP2680.

Full text

Abstract:

L'objectif global de cette thèse est d'étudier le phénomène de la propagation de l'activité électrique utérine par une approche basée sur la théorie de graphe. La première étape dans cette thèse est de trouver de nouveaux paramètres extraits des graphes qui conviennent pour représenter les évolutions physio-pathologiques de l'utérus. Ces paramètres seront testés directement sur les signaux EHG enregistrés au niveau de l'abdomen puis au niveau des sources identifiées à partir des EHG. Cette analyse sera appliquée sur le signal EHG i) globalement (en utilisant toute la contraction) et ii) dynamiquement (en utilisant des fenêtres temporelles dans la contraction pour caractériser à chaque fois le graphe correspondant). La deuxième étape sera de développer une nouvelle méthode basée sur les réseaux de neurones et de l'appliquer sur tous les paramètres déjà utilisés afin de sélectionner les meilleurs paramètres qui peuvent différencier les contractions de grossesse et de travail. Les résultats attendus seront utilisés à la fois pour enrichir les connaissances scientifiques dans ce domaine et pour essayer d'améliorer les performances de la prédiction de la prématurité chez les femmes
The overall objective of this thesis is to study the phenomenon of the propagation of uterine electrical activity by a approach based on graph theory. The first step in this thesis is to find new parameters extracted from the graphs which are suitable to represent the physio-pathological evolutions of the uterus. These parameters will be tested directly on th EHG signals recorded at the level of the abdomen then at the level of the sources identified from the EHGs. This analysis will be applied to the EHG signal i) globally (using the entire contraction) and ii) dynamically (using time windows in the contraction to characterize each time the corresponding graph). The second step will be to develop a new method based on neural networks and apply it on all the parameters already used in order to select the best parameters that can differentiate pregnancy and labor contractions. The expected results will be used both to enrich scientific knowledge in this field and to try to improve the performance of the prediction of prematurity in women

APA, Harvard, Vancouver, ISO, and other styles

31

Hennayake, Kamal P. "Generalized edge connectivity in graphs." Morgantown, W. Va. : [West Virginia University Libraries], 1998. http://etd.wvu.edu/templates/showETD.cfm?recnum=383.

Full text

Abstract:

Thesis (Ph. D.)--West Virginia University, 1998.
Title from document title page. Document formatted into pages; contains v, 87 p. : ill. Includes abstract. Includes bibliographical references (p. 64-72).

APA, Harvard, Vancouver, ISO, and other styles

32

Sammarco, Matteo. "Dissémination multi-contenus opportuniste : monitorage passif et adaptation aux conditions du réseau." Thesis, Paris 6, 2014. http://www.theses.fr/2014PA066573/document.

Full text

Abstract:

La pénétration du marché des appareils mobiles a connu une croissance impressionnante ces dernières années. Smartphones, tablettes et ordinateurs portables sont devenus soit producteurs soit consommateurs de contenus générés par les utilisateurs. Les communications opportunistes permettent une couverture étendue dans les endroits où il n'existe aucune infrastructure réseau disponible et des stratégies de délestage de données pour aider les opérateurs à soulager la charge de leurs infrastructures. Dans cette thèse, nous considérons le cas de la diffusion opportuniste de plusieurs grands contenus d'un point de vue expérimental. Dans la première partie nous commençons par implémenter EPICS, un protocole réseau conçu pour l'échange opportuniste de grands contenus, dans des terminaux Android. Après sa évaluation nous proposons DAD, un nouveau protocole, qui envoie une rafale de paquets de données de façon adaptative. Nous comparons les deux protocoles expérimentalement et, à l'aide des traces de contacts, soit réelles, soit synthétiques, nous obtenons des gains importants avec cette nouvelle approche. La deuxième partie est dédiée au passage à l'échelle des systèmes de surveillance passive. Nous proposons deux approches. La première est basée sur la similarité des traces et des algorithmes de détection de communautés. La deuxième est basée sur des mesures collaboratives
The market penetration of mobile devices has experienced an impressive growth. Smartphones, tablets, and laptops have become both producers and consumers of user-generated contents. They also motivate novel communication paradigms such as the possibility to establish, in an opportunistic fashion, direct device-to-device links whenever two mobile nodes enter within the wireless range of each other. In this thesis, we consider the case of opportunistic dissemination of multiple large contents from an experimental point of view. This implies revisiting, among others, the common assumption that contacts have enough capacity to transfer any amount of data.In the first part of this thesis, we start from an Android implementation of EPICS, a network protocol designed for exchanging large contents in opportunistic networks, on off-the-shelf devices. After an deep analysis of application-level logs and captured wireless traces we found out limitations and uncovered improving possibilities. We then propose DAD, a new content dissemination protocol that adaptively sends bursts of data instead of the per-fragment transmission strategy of EPICS.The second part of this thesis deals with the scalability of legacy WLAN monitoring systems. We propose two original approaches. With the first one, based on trace similarity and community detection algorithms, we are able to identify how many monitor we need in a target area and where to place them. The second approach in based on collaborative measurements. In this case we face the risk of biased measures due attacks of malicious users generating adulterated traces. We then propose a method to detect such malicious behaviors

APA, Harvard, Vancouver, ISO, and other styles

33

Gurung, Topraj. "Compact connectivity representation for triangle meshes." Diss., Georgia Institute of Technology, 2013. http://hdl.handle.net/1853/47709.

Full text

Abstract:

Many digital models used in entertainment, medical visualization, material science, architecture, Geographic Information Systems (GIS), and mechanical Computer Aided Design (CAD) are defined in terms of their boundaries. These boundaries are often approximated using triangle meshes. The complexity of models, which can be measured by triangle count, increases rapidly with the precision of scanning technologies and with the need for higher resolution. An increase in mesh complexity results in an increase of storage requirement, which in turn increases the frequency of disk access or cache misses during mesh processing, and hence decreases performance. For example, in a test application involving a mesh with 55 million triangles in a machine with 4GB of memory versus a machine with 1GB of memory, performance decreases by a factor of about 6000 because of memory thrashing. To help reduce memory thrashing, we focus on decreasing the average storage requirement per triangle measured in 32-bit integer references per triangle (rpt). This thesis covers compact connectivity representation for triangle meshes and discusses four data structures: 1. Sorted Opposite Table (SOT), which uses 3 rpt and has been extended to support tetrahedral meshes. 2. Sorted Quad (SQuad), which uses about 2 rpt and has been extended to support streaming. 3. Laced Ring (LR), which uses about 1 rpt and offers an excellent compromise between storage compactness and performance of mesh traversal operators. 4. Zipper, an extension of LR, which uses about 6 bits per triangle (equivalently 0.19 rpt), therefore is the most compact representation. The triangle mesh data structures proposed in this thesis support the standard set of mesh connectivity operators introduced by the previously proposed Corner Table at an amortized constant time complexity. They can be constructed in linear time and space from the Corner Table or any equivalent representation. If geometry is stored as 16-bit coordinates, using Zipper instead of the Corner Table increases the size of the mesh that can be stored in core memory by a factor of about 8.

APA, Harvard, Vancouver, ISO, and other styles

34

Limnios, Stratis. "Graph Degeneracy Studies for Advanced Learning Methods on Graphs and Theoretical Results Edge degeneracy: Algorithmic and structural results Degeneracy Hierarchy Generator and Efficient Connectivity Degeneracy Algorithm A Degeneracy Framework for Graph Similarity Hcore-Init: Neural Network Initialization based on Graph Degeneracy." Thesis, Institut polytechnique de Paris, 2020. http://www.theses.fr/2020IPPAX038.

Full text

Abstract:

L'extraction de sous-structures significatives a toujours été un élément clé de l’étude des graphes. Dans le cadre de l'apprentissage automatique, supervisé ou non, ainsi que dans l'analyse théorique des graphes, trouver des décompositions spécifiques et des sous-graphes denses est primordial dans de nombreuses applications comme entre autres la biologie ou les réseaux sociaux.Dans cette thèse, nous cherchons à étudier la dégénérescence de graphe, en partant d'un point de vue théorique, et en nous appuyant sur nos résultats pour trouver les décompositions les plus adaptées aux tâches à accomplir. C'est pourquoi, dans la première partie de la thèse, nous travaillons sur des résultats structurels des graphes à arête-admissibilité bornée, prouvant que de tels graphes peuvent être reconstruits en agrégeant des graphes à degré d’arête quasi-borné. Nous fournissons également des garanties de complexité de calcul pour les différentes décompositions de la dégénérescence, c'est-à-dire si elles sont NP-complètes ou polynomiales, selon la longueur des chemins sur lesquels la dégénérescence donnée est définie.Dans la deuxième partie, nous unifions les cadres de dégénérescence et d'admissibilité en fonction du degré et de la connectivité. Dans ces cadres, nous choisissons les plus expressifs, d'une part, et les plus efficaces en termes de calcul d'autre part, à savoir la dégénérescence 1-arête-connectivité pour expérimenter des tâches de dégénérescence standard, telle que la recherche d’influenceurs.Suite aux résultats précédents qui se sont avérés peu performants, nous revenons à l'utilisation du k-core mais en l’intégrant dans un cadre supervisé, i.e. les noyaux de graphes. Ainsi, en fournissant un cadre général appelé core-kernel, nous utilisons la décomposition k-core comme étape de prétraitement pour le noyau et appliquons ce dernier sur chaque sous-graphe obtenu par la décomposition pour comparaison. Nous sommes en mesure d'obtenir des performances à l’état de l’art sur la classification des graphes au prix d’une légère augmentation du coût de calcul.Enfin, nous concevons un nouveau cadre de dégénérescence de degré s’appliquant simultanément pour les hypergraphes et les graphes biparties, dans la mesure où ces derniers sont les graphes d’incidence des hypergraphes. Cette décomposition est ensuite appliquée directement à des architectures de réseaux de neurones pré-entrainés étant donné qu'elles induisent des graphes biparties et utilisent le core d'appartenance des neurones pour réinitialiser les poids du réseaux. Cette méthode est non seulement plus performant que les techniques d'initialisation de l’état de l’art, mais il est également applicable à toute paire de couches de convolution et linéaires, et donc adaptable à tout type d'architecture
Extracting Meaningful substructures from graphs has always been a key part in graph studies. In machine learning frameworks, supervised or unsupervised, as well as in theoretical graph analysis, finding dense subgraphs and specific decompositions is primordial in many social and biological applications among many others.In this thesis we aim at studying graph degeneracy, starting from a theoretical point of view, and building upon our results to find the most suited decompositions for the tasks at hand.Hence the first part of the thesis we work on structural results in graphs with bounded edge admissibility, proving that such graphs can be reconstructed by aggregating graphs with almost-bounded-edge-degree. We also provide computational complexity guarantees for the different degeneracy decompositions, i.e. if they are NP-complete or polynomial, depending on the length of the paths on which the given degeneracy is defined.In the second part we unify the degeneracy and admissibility frameworks based on degree and connectivity. Within those frameworks we pick the most expressive, on the one hand, and computationally efficient on the other hand, namely the 1-edge-connectivity degeneracy, to experiment on standard degeneracy tasks, such as finding influential spreaders.Following the previous results that proved to perform poorly we go back to using the k-core but plugging it in a supervised framework, i.e. graph kernels. Thus providing a general framework named core-kernel, we use the k-core decomposition as a preprocessing step for the kernel and apply the latter on every subgraph obtained by the decomposition for comparison. We are able to achieve state-of-the-art performance on graph classification for a small computational cost trade-off.Finally we design a novel degree degeneracy framework for hypergraphs and simultaneously on bipartite graphs as they are hypergraphs incidence graph. This decomposition is then applied directly to pretrained neural network architectures as they induce bipartite graphs and use the coreness of the neurons to re-initialize the neural network weights. This framework not only outperforms state-of-the-art initialization techniques but is also applicable to any pair of layers convolutional and linear thus being applicable however needed to any type of architecture

APA, Harvard, Vancouver, ISO, and other styles

35

Trakultraipruk, Somkiat. "Connectivity properties of some transformation graphs." Thesis, London School of Economics and Political Science (University of London), 2013. http://etheses.lse.ac.uk/624/.

Full text

Abstract:

Many combinatorial problems can be formulated as "can we transform configuration 1 into configuration 2 if certain transformations are allowed?" In order to study such questions, we introduce a so-called transformation graph. This graph has the set of all possible configurations as its vertex set, and there is an edge between two configurations if one configuration can be obtained from the other by one of the allowed transformations. Then a question like "can we go from one configuration to another one" becomes a question about connectivity properties of transformation graphs. In this thesis, we study the following types of transformation graphs in particular: Labelled Token Graphs: Here configurations are arrangements of labelled tokens on a given graph, and we can go from one arrangement to another one by moving one token at a time along an edge of the given graph. We classify all cases when labelled token graphs are connected, and classify all pairs of arrangements that are in the same component. We also look at the problem how hard it is to determine the length of the shortest path between two arrangements. Strong k-Colour Graphs: For this transformation graph, the configurations are the proper vertex-colourings of a given graph with k colours, in which all k colours are actually used. We call such a colouring a strong k-colouring. We study the problem when we can transform any strong k-colouring into any other one by recolouring one vertex at a time, always maintaining a strong k-colouring. For certain classes of graphs, we can completely determine when the transformation graph of strong k-colourings is connected.

APA, Harvard, Vancouver, ISO, and other styles

36

Fraiman, Nicolás. "Connectivity of random graphs and networks." Thesis, McGill University, 2013. http://digitool.Library.McGill.CA:80/R/?func=dbin-jump-full&object_id=119575.

Full text

Abstract:

In this manuscript we discuss connectivity and distance properties for several models of random graphs. The results we prove generalize well known theorems for the Erdös-Rényi model and percolation on a ﬁnite box. We show that for both Inhomogeneous Random Graphs and Distance Fading Grid Networks there is a sharp transition for connectivity and we ﬁnd the corresponding threshold values. We also provide a bound for the diameter for the Random Connection Model when the underlying space is the torus in d dimensions.
Dans cette thèse, on étudie les propriétés de connexité pour plusieurs modèles de graphes aléatoires. Les résultats généralisent des théorèmes bien connus pour le modèle Erdös-Rényi et la percolation dans une boîte ﬁnie. On montre que pour les "Inhomogeneous Random Graphs" et les "Distance Fading Grid Networks", il y a un seuil pour la propriété de connexité et on trouve les valeurs des seuils correspondants. On caractérise aussi le diamètre pour le "Random Connection Model" quand l'espace est le tore de dimension d.

APA, Harvard, Vancouver, ISO, and other styles

37

Bourgeois, Marc. "Impacts écologiques des formes d'urbanisation : modélisations urbaines et paysagères." Thesis, Besançon, 2015. http://www.theses.fr/2015BESA1029/document.

Full text

Abstract:

L’accélération du processus d’urbanisation, constatée à l’échelle mondiale depuis les dernières décennies, conduit à une artificialisation progressive des milieux naturels. La construction d’infrastructures de transport ou de nouveaux bâtiments fragmente les paysages de manière irréversible et cause une réduction des habitats écologiques et de leur connectivité. Le maintien de la fonctionnalité des réseaux écologiques, s’intègre désormais dans les politiques d’aménagement du territoire ou d’urbanisme soucieuses de la préservation de la biodiversité.En se focalisant plus particulièrement sur les évolutions urbaines à l’horizon 2030 dans l’Aire Urbaine de Besançon (développement résidentiel et variations de trafic routier), cette thèse cherche à évaluer l’impact potentiel des formes d’urbanisation sur la connectivité des réseaux écologiques des espèces animales. Ce travail de recherche privilégie l’approche par la modélisation en s’inscrivant à la fois dans le champ de la géographie théorique et quantitative et de l’écologie du paysage.L’application de cette démarche se fait en trois étapes : (1) simuler le développement résidentiel et ses évolutions de trafic associées à l’horizon 2030, à l’aide de cinq scénarios prospectifs présentant des formes urbaines différenciées ; (2) modéliser les réseaux écologiques de plusieurs espèces animales avec des graphes paysagers construits à partir de cartes d’occupation du sol et de données écologiques ; et (3) évaluer les impacts potentiels de chaque scénario sur les réseaux écologiques à partir de ces graphes à l’aide de métriques de connectivité, par mesure de la perte de connectivité imputable à chaque scénario de développement résidentiel.Les résultats obtenus montrent que les formes de villes denses et compactes, contrairement aux villes étalées, sont celles qui favorisent le mieux le maintien des connectivités écologiques pour la plupart des groupes d’espèces analysés. Des analyses plus approfondies mettent en avant la contribution importante des variations de trafic aux impacts écologiques de chaque scénario.D’après les analyses de sensibilité effectuées, le modèle utilisé est robuste, ce qui montre l’intérêt de la modélisation dans le processus d’aide à la décision pour la protection environnementale et la planification urbaine afin de penser la ville de demain de manière durable
The global increase of urbanization during the past decades have induced a progressive artificialization of natural environments. The building of transport infrastructures and new housings causes a landscape fragmentation in an irreversible way and a strong decrease of the connectivity of ecological habitats. Maintaining the functionality of ecological networks is becoming a major goal of sustainable urban planning policies. With a special focus on urban evolutions in the horizon 2030 in the urban area of Besançon in eastern France (residential development and road traffic evolutions), this thesis aims to assess the potential impact of urban forms on landscape connectivity of animal species’ ecological networks. This research work promotes a modelling approach both on the field of theoretical and quantitative geography and landscape ecology.This approach follows three main steps: (1) simulating residential development and its associated road traffic changes using five prospective scenarios of differentiated urban forms; (2) modelling landscape graphs of various animal species using land-cover maps and ecological data; (3) assessing the potential impacts of each scenario on ecological networks from these graphs using connectivity metrics, with measures of the connectivity decrease attributable to each residential development scenario. Contrary to sprawled cities, the results show that compact and dense urban forms best promote the maintenance of ecological connectivity for the majority of species groups. Further analysis highlights the great contribution of road traffic evolutions regarding the ecological impacts of each scenario.According to some sensitivity analysis, the model used is quite robust. It demonstrates the interest of modelling in the decision-making process for environmental conservation and urban planning to think out the city of tomorrow in a sustainable way

APA, Harvard, Vancouver, ISO, and other styles

38

Fortier, Quentin. "Aspects de la connexité avec contraintes de matroïdes dans les graphes." Thesis, Université Grenoble Alpes (ComUE), 2017. http://www.theses.fr/2017GREAM059/document.

Full text

Abstract:

La notion de connexité est fondamentale en théorie des graphes. Nous proposons une étude approfondie d'un récent développement dans ce domaine, en ajoutant des contraintes de matroïdes.Dans un premier temps, nous exhibons deux opérations de réduction sur les graphes connectés avec contraintes de matroïdes. Ces opérations permettent de généraliser le théorème de caractérisation de la connectivité de Menger et le théorème de packing d'arborescences d'Edmonds.Cependant, cette extension du théorème d'Edmonds ne garantie plus que les arborescences soient couvrantes. Il a été conjecturé que l'on peut toujours trouver de telles arborescences couvrantes. Nous prouvons cette conjecture dans certains cas particuliers, notamment pour les matroïdes de rang deux et pour les matroïdes transversaux. Nous réfutons cette conjecture dans le cas général en construisant un contre-exemple à plus de 300 sommets, sur une extension parallèle du matroïde de Fano.Enfin, nous explorons d'autres notions de connexité avec contraintes de matroïdes: pour des graphes mixtes, des hypergraphes, et avec condition d'atteignabilité
The notion of connectivity is fundamental in graph theory. We study thoroughly a recent development in this field, with the addition of matroid constraints.Firstly, we exhibit two reduction operations on connected graphs with matroid constraints. Using these operations, we generalize the Menger's theorem on connectivity and Edmond's theorem on packing of arborescences.However, this extension of Edmond's theorem does not ensure that the arborescences are spanning. It has been conjectured that one can always find such spanning arborescences. We prove this conjecture in some cases, including matroids of rank two and transversal matroids. We disprove this conjecture in the general case by providing a counter-example with more than 300 vertices, on a parallel extension of the Fano matroid.Finally, we explore other generalizations of connectivity with matroid constraints: in mixed graphs, hypergraphs and with reachability conditions

APA, Harvard, Vancouver, ISO, and other styles

39

Zhang, Xiankun. "Generalizations of colorability and connectivity of graphs." Morgantown, W. Va. : [West Virginia University Libraries], 1998. http://etd.wvu.edu/templates/showETD.cfm?recnum=333.

Full text

Abstract:

Thesis (Ph. D.)--West Virginia University, 1998.
Title from document title page. Document formatted into pages; contains vii, 97 p. : ill. Includes abstract. Includes bibliographical references (p. 93-96).

APA, Harvard, Vancouver, ISO, and other styles

40

Vernet, Mathilde. "Modèles et algorithmes pour les graphes dynamiques." Thesis, Normandie, 2020. http://www.theses.fr/2020NORMLH12.

Full text

Abstract:

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

APA, Harvard, Vancouver, ISO, and other styles

41

Neggaz, Mohammed Yessin. "Automatic classification of dynamic graphs." Thesis, Bordeaux, 2016. http://www.theses.fr/2016BORD0169/document.

Full text

Abstract:

Les réseaux dynamiques sont constitués d’entités établissant des contacts les unes avec les autres dans le temps. Un défi majeur dans les réseaux dynamiques est de prédire les modèles de mobilité et de décider si l’évolution de la topologie satisfait aux exigences du succès d’un algorithme donné. Les types de dynamique résultant de ces réseaux sont variés en échelle et en nature. Par exemple,certains de ces réseaux restent connexes tout le temps; d’autres sont toujours déconnectés mais offrent toujours une sorte de connexité dans le temps et dans l’espace(connexité temporelle); d’autres sont connexes de manière récurrente, périodique,etc. Tous ces contextes peuvent être représentés sous forme de classes de graphes dynamiques correspondant à des conditions nécessaires et/ou suffisantes pour des problèmes ou algorithmes distribués donnés. Étant donné un graphe dynamique,une question naturelle est de savoir à quelles classes appartient ce graphe. Dans ce travail, nous apportons une contribution à l’automatisation de la classification de graphes dynamiques. Nous proposons des stratégies pour tester l’appartenance d’un graphe dynamique à une classe donnée et nous définissons un cadre générique pour le test de propriétés dans les graphes dynamiques. Nous explorons également le cas où aucune propriété sur le graphe n’est garantie, à travers l’étude du problème de maintien d’une forêt d’arbres couvrants dans un graphe dynamique
Dynamic networks consist of entities making contact over time with one another. A major challenge in dynamic networks is to predict mobility patterns and decide whether the evolution of the topology satisfies requirements for the successof a given algorithm. The types of dynamics resulting from these networks are varied in scale and nature. For instance, some of these networks remain connected at all times; others are always disconnected but still offer some kind of connectivity over time and space (temporal connectivity); others are recurrently connected,periodic, etc. All of these contexts can be represented as dynamic graph classes corresponding to necessary or sufficient conditions for given distributed problems or algorithms. Given a dynamic graph, a natural question to ask is to which of the classes this graph belongs. In this work we provide a contribution to the automation of dynamic graphs classification. We provide strategies for testing membership of a dynamic graph to a given class and a generic framework to test properties in dynamic graphs. We also attempt to understand what can still be done in a context where no property on the graph is guaranteed through the distributed problem of maintaining a spanning forest in highly dynamic graphs

APA, Harvard, Vancouver, ISO, and other styles

42

Tarabon, Simon. "La prise en compte des fonctionnalités écologiques dans l'aménagement des territoires et l'application de la séquence Éviter-Réduire-Compenser : De l'échelle projet à la planification Environmental impact assessment of development projects improved by merging species distribution and habitat connectivity modelling Integrating a landscape connectivity approach into mitigation hierarchy planning by anticipating urban dynamics. Landscape and Urban Planning Améliorer la prise en compte des fonctionnalités écologiques dans la séquence Éviter-Réduire-Compenser Maximizing habitat connectivity in the mitigation hierarchy. A case study on three terrestrial mammals in an urban environment The effects of climate warming and urbanised areas on the future distribution of Cortaderia selloana, pampas grass, in France." Thesis, Avignon, 2020. http://www.theses.fr/2020AVIG0720.

Full text

Abstract:

La biodiversité est confrontée à une érosion accélérée et est devenue une préoccupation environnementale mondiale ces dernières décennies. En France, la séquence Éviter–Réduire–Compenser (ERC) est un des outils réglementaires mis en place dans un contexte de destruction et de fragmentation des habitats d’espèces. Elle permet le développement des territoires tout en visant une absence de perte nette de biodiversité. Cependant, malgré les récentes évolutions réglementaires européennes et françaises, le triptyque ERC présente de nombreuses limites et enjeux d’ordre opérationnel. En positionnant nos travaux à l’interface entre recherche et opérationnalité, nous proposons un cadre méthodologique basé sur plusieurs approches de modélisation afin d’améliorer les processus d’évaluation et décisionnels aux différentes étapes d’aménagement, de la planification à l’opérationnel au moment de l’autorisation des projets. Dans une première partie du travail, nous intégrons les enjeux spatio-temporels de la biodiversité à l’ensemble de la séquence ERC, de l’évaluation des impacts potentiels au dimensionnement des mesures écologiques. À partir du cas précis de l’aménagement du Grand Stade de Lyon, nous montrons l’intérêt de combiner les modèles de distribution d’espèces et les graphes paysager pour identifier les réseaux écologiques et poser un cadre de calcul de l’équivalence écologique basé sur le volet fonctionnel de la biodiversité. Intégrer les dimensions spatiales et temporelles permet d’accroitre la connectivité des habitats et améliorer la conception des projets. Nous montrons ensuite qu’organiser la compensation à l’échelle des territoires en les intégrant aux réseaux écologiques améliore davantage les bénéfices et réduit le risque d’échecs des mesures. Notre démarche est présentée dans le contexte périurbain de l’Ouest de Lyon. Enfin, nous démontrons les implications d’une démarche anticipée et planifiée de la séquence ERC dans la planification stratégique des territoires. Pour cela, nous montrons dans le cadre de la Métropole de Toulouse l’intérêt d’étudier conjointement les dynamiques urbaines et écologiques pour mettre en place une stratégie de conservation de la biodiversité à l’horizon 2040 en assurant l’absence de perte nette sur les habitats d’espèces et leur connectivité selon différentes trajectoires d’urbanisation et de ratio de compensation. Cette thèse offre une approche globale pour orienter les décideurs et améliorer la prise en compte des fonctionnalités écologiques à différentes échelles spatiales et temporelles dans l’aménagement des territoires et l’application de la séquence ERC. Ce travail est basé sur des logiciels novateurs et accessibles pour tous les acteurs et constitue une contribution intéressante à l’appui des maitres d’ouvrage qui souhaitent s’assurer de l’absence d'effets significatifs ou irréversibles sur la biodiversité, et des autorités environnementales qui veillent à ce que l’ensemble des enjeux environnementaux soient bien pris en compte dans la conception des projets d’aménagement
Over the past decades, biodiversity erosion has speeded up and become a global environmental concern since. Anthropization has led to. The mitigation hierarchy (avoidance, reduction and offsetting of impacts) is a regulatory tool implemented in a context of habitat destruction and fragmentation, disrupting species’ life cycle. The objective is to achieve “no net loss” of biodiversity following urban development. Although biodiversity conservation regulations have recently better addressed ecosystem functioning, the mitigation hierarchy is still being implemented with little concern for the spatial configuration of ecosystems in the landscape. This thesis hypothesizes that the major difficulties encountered by stakeholders are, in part, methodological and technical. Situating our research at the knowledge-action interface, we propose a methodological framework based on several modeling approaches, to respond to the different scientific and operational challenges. This thesis joins forces with other scientific projects and stakeholders’ networks by exploring complementary axes. To this end, we first integrate spatio-temporal issues of biodiversity into overall mitigation hierarchy application, focusing on potential impacts and dimensioning at “territorial development project” scale through a case study on the new stadium in Lyon (Southern France). Combining species distributions models and spatial graphs improves habitat connectivity and therefore the design of the development projects. Next, we demonstrate the positive impacts on peri-urban habitat connectivity of pooling and anticipating offsets in the suburbs of Lyon. In the last part, we demonstrate the implications of an anticipated and planned approach to the mitigation hierarchy on a planning scale. We consider both ecological connectivity and urban dynamics, in an attempt to minimize the ecological impacts of urban sprawl by avoiding urbanization of areas of highest ecological value and then enhance the application of biodiversity offsetting. This method is tested on projections for the Toulouse conurbation (Southern France) by 2040. Thus, this thesis presents an overall approach that can help to increase habitat connectivity and to improve the design of territorial development projects at different spatial and temporal scales. This methodology is based on freeware available to all practitioners. It will serve planners, designers, and decision-makers needing to ensure that there are no significant or irreversible effects on biodiversity, and environmental authorities making sure that all environmental issues are taken into account in the design of development projects

APA, Harvard, Vancouver, ISO, and other styles

43

Kartun-Giles, Alexander Paul. "Connectivity and centrality in dense random geometric graphs." Thesis, University of Bristol, 2017. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.720827.

Full text

APA, Harvard, Vancouver, ISO, and other styles

44

Malherbe, Caroline. "Imagerie des faisceaux de fibres et des réseaux fonctionnels du cerveau : application à l'étude du syndrome de Gilles de la Tourette." Phd thesis, Université Paris Sud - Paris XI, 2012. http://tel.archives-ouvertes.fr/tel-00980572.

Full text

Abstract:

L'objectif de cette thèse est d'identifier et caractériser les boucles anatomiques et fonctionnelles cortico-sous-corticales chez l'Homme, à partir de données d'imagerie par résonance magnétique fonctionnelle (IRMf) au repos et de diffusion. Une boucle est un ensemble de régions corticales, sous-corticales et cérébelleuses, qui interagissent afin d'effectuer ou de préparer une tâche.Le premier axe de ce travail vise à identifier les réseaux fonctionnels cortico-sous-corticaux en IRMf au repos. Nous proposons une méthode statistique robuste séparant l'analyse corticale de l'analyse sous-corticale. Une analyse en composantes indépendantes spatiales est d'abord réalisée individuellement sur les régions corticales, et suivie d'une classification hiérarchique. Les régions sous-corticales associées sont ensuite extraites par un modèle linéaire général dont les régresseurs comportent la dynamique des régions corticales, suivi d'une analyse de groupe à effets aléatoires. La méthode est validée sur deux jeux de données différents. Un atlas immunohistochimique des structures sous-corticales permet ensuite de déterminer la fonction sensorimotrice, associative ou limbique des réseaux obtenus. Nous montrons enfin que l'anatomie est un support pour la fonction chez des sujets sains.Le dernier axe étudie le syndrome de Gilles de la Tourette, qu'on pense être dû à un dysfonctionnement des boucles cortico-sous-corticales. Nous caractérisons d'abord les boucles cortico-sous-corticales fonctionnelles grâce à des métriques d'intégration et de théorie des graphes, et des différences en termes de connectivité sont mises en évidence entre patients adultes et volontaires sains. Nous montrons également que les boucles cortico-sous-corticales fonctionnelles chez les patients sont soutenues par l'anatomie sous-jacente.

APA, Harvard, Vancouver, ISO, and other styles

45

Sammarco, Matteo. "Dissémination multi-contenus opportuniste : monitorage passif et adaptation aux conditions du réseau." Electronic Thesis or Diss., Paris 6, 2014. http://www.theses.fr/2014PA066573.

Full text

Abstract:

La pénétration du marché des appareils mobiles a connu une croissance impressionnante ces dernières années. Smartphones, tablettes et ordinateurs portables sont devenus soit producteurs soit consommateurs de contenus générés par les utilisateurs. Les communications opportunistes permettent une couverture étendue dans les endroits où il n'existe aucune infrastructure réseau disponible et des stratégies de délestage de données pour aider les opérateurs à soulager la charge de leurs infrastructures. Dans cette thèse, nous considérons le cas de la diffusion opportuniste de plusieurs grands contenus d'un point de vue expérimental. Dans la première partie nous commençons par implémenter EPICS, un protocole réseau conçu pour l'échange opportuniste de grands contenus, dans des terminaux Android. Après sa évaluation nous proposons DAD, un nouveau protocole, qui envoie une rafale de paquets de données de façon adaptative. Nous comparons les deux protocoles expérimentalement et, à l'aide des traces de contacts, soit réelles, soit synthétiques, nous obtenons des gains importants avec cette nouvelle approche. La deuxième partie est dédiée au passage à l'échelle des systèmes de surveillance passive. Nous proposons deux approches. La première est basée sur la similarité des traces et des algorithmes de détection de communautés. La deuxième est basée sur des mesures collaboratives
The market penetration of mobile devices has experienced an impressive growth. Smartphones, tablets, and laptops have become both producers and consumers of user-generated contents. They also motivate novel communication paradigms such as the possibility to establish, in an opportunistic fashion, direct device-to-device links whenever two mobile nodes enter within the wireless range of each other. In this thesis, we consider the case of opportunistic dissemination of multiple large contents from an experimental point of view. This implies revisiting, among others, the common assumption that contacts have enough capacity to transfer any amount of data.In the first part of this thesis, we start from an Android implementation of EPICS, a network protocol designed for exchanging large contents in opportunistic networks, on off-the-shelf devices. After an deep analysis of application-level logs and captured wireless traces we found out limitations and uncovered improving possibilities. We then propose DAD, a new content dissemination protocol that adaptively sends bursts of data instead of the per-fragment transmission strategy of EPICS.The second part of this thesis deals with the scalability of legacy WLAN monitoring systems. We propose two original approaches. With the first one, based on trace similarity and community detection algorithms, we are able to identify how many monitor we need in a target area and where to place them. The second approach in based on collaborative measurements. In this case we face the risk of biased measures due attacks of malicious users generating adulterated traces. We then propose a method to detect such malicious behaviors

APA, Harvard, Vancouver, ISO, and other styles

46

Holtkamp, Andreas [Verfasser]. "Connectivity in graphs and digraphs : maximizing vertex-, edge- and arc-connectivity with an emphasis on local connectivity properties / Andreas Holtkamp." Aachen : Hochschulbibliothek der Rheinisch-Westfälischen Technischen Hochschule Aachen, 2013. http://d-nb.info/1038598796/34.

Full text

APA, Harvard, Vancouver, ISO, and other styles

47

Biyikoglu, Türker, and Josef Leydold. "Graphs of Given Order and Size and Minimum Algebraic Connectivity." WU Vienna University of Economics and Business, 2011. http://epub.wu.ac.at/3296/1/techreport%2D115.pdf.

Full text

Abstract:

The structure of connected graphs of given size and order that have minimal algebraic connectivity is investigated. It is shown that they must consist of a chain of cliques. Moreover, an upper bound for the number of maximal cliques of size 2 or larger is derived. (author's abstract)
Series: Research Report Series / Department of Statistics and Mathematics

APA, Harvard, Vancouver, ISO, and other styles

48

Reinwardt, Manja. "Combinatorial and graph theoretical aspects of two-edge connected reliability." Doctoral thesis, Technische Universitaet Bergakademie Freiberg Universitaetsbibliothek "Georgius Agricola", 2015. http://nbn-resolving.de/urn:nbn:de:bsz:105-qucosa-184297.

Full text

Abstract:

Die Untersuchung von Zuverlässigkeitsnetzwerken geht bis zum frühen 20. Jahrhundert zurück. Diese Arbeit beschäftigt sich hauptsächlich mit der Zweifach-Kantenzusammenhangswahrscheinlichkeit. Zuerst werden einfache Algorithmen, die aber für allgemeine Graphen nicht effizient sind, gezeigt, zusammen mit Reduktionen. Weiterhin werden Charakterisierungen von Kanten bezogen auf Wegemengen gezeigt. Neue strukturelle Bedingungen für diese werden vorgestellt. Neue Ergebnisse liegen ebenfalls für Graphen hoher Dichte und Symmetrie vor, genauer für vollständige und vollständig bipartite Graphen. Naturgemäß sind Graphen von geringer Dichte hier einfacher in der Untersuchung. Die Arbeit zeigt Ergebnisse für Kreise, Räder und Leiterstrukturen. Graphen mit beschränkter Weg- beziehungsweise Baumweite haben polynomiale Algorithmen und in Spezialfällen einfache Formeln, die ebenfalls vorgestellt werden. Der abschließende Teil beschäftigt sich mit Schranken und Approximationen.

APA, Harvard, Vancouver, ISO, and other styles

49

Abazid, Majd. "Topological study of the brain functional organization at the early stages of Alzheimer's disease using electroencephalography." Electronic Thesis or Diss., Institut polytechnique de Paris, 2022. http://www.theses.fr/2022IPPAS026.

Full text

Abstract:

L'électroencéphalographie (EEG) est encore considérée de nos jours comme une technique de neuroimagerie très utile dans les applications cliniques, adaptée aux patients souffrant de troubles cognitifs et physiques, ainsi qu'aux tests à grande échelle. L'EEG est une technologie non invasive, peu coûteuse et facilement accessible. Elle se caractérise par une haute résolution temporelle, ce qui est crucial pour le suivi de la dynamique cérébrale.Plusieurs travaux dans la littérature ont exploité l'EEG pour étudier les altérations de l'activité cérébrale liées aux maladies neurodégénératives, notamment la maladie d'Alzheimer (MA). La MA est une maladie neurodégénérative chronique qui entraîne un déclin progressif des fonctions cognitives, ainsi que des troubles du comportement et une perte insidieuse d'autonomie au quotidien. En l'absence de traitements curatifs, nous observons un intérêt croissant à la caractérisation de l'activité cérébrale aux stades précoces de la maladie. Le stade préclinique de la MA est asymptomatique, mais les lésions cérébrales dues à la MA sont présentes. A ce stade, on parle de troubles cognitifs subjectifs (subjective cognitive impairments, SCI). Au stade prodromal, les patients atteints de troubles cognitifs légers (mild cognitive impairment, MCI) présentent des troubles de la mémoire mesurables, mais leur capacité fonctionnelle est maintenue. Les patients atteints de troubles subjectifs ou légers présentent un risque élevé de développer la MA.Cette thèse s'intéresse au diagnostic précoce de la MA aux stades préclinique et prodromal en utilisant l'EEG au repos, et aborde l'analyse des réseaux cérébraux en étudiant la connectivité fonctionnelle à différents stades cliniques du déclin cognitif (SCI, MCI et MA au stade léger). Pour cela, nous avons mené une étude rétrospective en exploitant une base de données clinique qui contient des signaux EEG enregistrés en conditions réelles.En premier lieu, nous avons proposé d'exploiter une mesure d'entropie, appelée "Epoch-based Entropy" (EpEn), pour quantifier la connectivité fonctionnelle. Cette mesure repose sur une modélisation statistique fine des signaux EEG avec des modèles de Markov cachés. Cette mesure caractérise les changements spatio-temporels des signaux EEG en quantifiant le contenu d'information dans les signaux au niveau temporel et spatial.Par la suite, nous avons effectué une analyse topologique du réseau cérébral cortical de manière différentielle, en exploitant la théorie des graphes. La contribution de notre travail est double. En effet, il s'agit du premier travail qui : (i) aborde l'analyse du réseau cérébral chez les patients ayant des troubles subjectifs, des troubles légers et la MA au stade léger, et (ii) combine la mesure d'entropie à la théorie des graphes puisque nous avons démontré son efficacité à quantifier les changements spatio-temporels liés à la MA.Dans cette thèse, nous avons aussi abordé le problème de la grande quantité d'information extraite des signaux EEG, analysés sur plusieurs bandes de fréquences (delta, theta, alpha, beta), plusieurs électrodes, et plusieurs échelles de densité de réseau (seuillages multiples des graphes). Par conséquent, une autre contribution à ce travail de thèse concerne l'extraction de marqueurs EEG les plus pertinents pour discriminer automatiquement les trois groupes de patients. Ainsi, nous avons proposé une méthode hiérarchique pour l'analyse des signaux EEG, permettant d'identifier les descripteurs les plus pertinents à partir d'une grande quantité d'information issue d'une seule mesure de connectivité fonctionnelle. Enfin, nous avons évalué la corrélation entre les marqueurs numériques extraits des signaux EEG et les marqueurs cliniques à notre disposition (MMSE, RL/RI-16, BREF)
Electroencephalography (EEG) is still considered nowadays as a convenient neuroimaging technique in clinical applications, suitable for cognitively and physically disabled patients, as well as for serial tests. In fact, EEG is a non-invasive, cost-effective, and mobile technology. It is characterized by a high temporal resolution, which is crucial for the analysis of fast brain functional dynamics.There is a rich literature addressing the use of EEG to investigate brain activity alterations due to neurodegenerative diseases, especially Alzheimer's disease (AD). AD is a chronic neurodegenerative disease that leads to progressive decline of cognitive functions along with behavioral disorders and insidious loss of autonomy in daily living activities. We observe a growing interest in the earlier stages of the disease since curative treatments are still lacking. The preclinical stage of AD is asymptomatic, but the brain lesions due to AD are present. At this phase, the term of subjective cognitive impairment (SCI) has been recently defined. In the prodromal stage, mild cognitive impairment (MCI) patients show measurable memory impairments but their functional capacity is maintained. SCI and MCI patients are at high risk of developing AD.This thesis investigates the early diagnosis of AD at preclinical and prodromal stages using resting-state EEG, and addresses brain network analysis by studying the functional connectivity over several clinical stages of cognitive decline (SCI, MCI and Mild AD). To this end, we conduct a retrospective study using a clinical database that contains EEG signals recorded in real-life conditions.We first propose to exploit an entropy measure, termed “epoch-based entropy” (EpEn), as a measure of functional connectivity, that relies on a refined statistical modeling of EEG signals based on Hidden Markov Models. This measure characterizes the spatiotemporal changes in EEG signals by quantifying the information content of EEG signals, both at the time and spatial levels.Furthermore, we conduct a topological brain network analysis over the three stages of cognitive decline by employing the Graph Theory. The novelty of our work is twofold. Actually, this is the first work that: (i) addresses EEG brain network analysis over SCI, MCI and Mild AD stages simultaneously, and (ii) combines EpEn to Graph Theory since we have shown its effectiveness in quantifying the complete spatiotemporal alteration due to AD.In this thesis, we decided to invest the largest amount of EEG information for brain network analysis, by exploiting several frequency ranges (delta, theta, alpha, beta), several electrodes locations (instead of regions), and several network density scales (multiple graph thresholding). Therefore, another issue tackled in this thesis concerns the identification of relevant EEG markers to discriminate automatically between SCI, MCI and AD patients in the context of graph analysis framework. To this end, we propose an automatic hierarchical method for EEG analysis, which allows the extraction of relevant markers from large amount of information based on a single EEG connectivity measure.Finally, we also assess the correlation between the relevant EEG markers and the clinical markers at our disposal (MMSE, RL/RI-16, BREF)

APA, Harvard, Vancouver, ISO, and other styles

50

Camby, Eglantine. "Connecting hitting sets and hitting paths in graphs." Doctoral thesis, Universite Libre de Bruxelles, 2015. http://hdl.handle.net/2013/ULB-DIPOT:oai:dipot.ulb.ac.be:2013/209048.

Full text

Abstract:

Dans cette thèse, nous étudions les aspects structurels et algorithmiques de différents problèmes de théorie des graphes. Rappelons qu’un graphe est un ensemble de sommets éventuellement reliés par des arêtes. Deux sommets sont adjacents s’ils sont reliés par une arête.

Tout d’abord, nous considérons les deux problèmes suivants :le problème de vertex cover et celui de dominating set, deux cas particuliers du problème de hitting set. Un vertex cover est un ensemble de sommets qui rencontrent toutes les arêtes alors qu’un dominating set est un ensemble X de sommets tel que chaque sommet n’appartenant pas à X est adjacent à un sommet de X. La version connexe de ces problèmes demande que les sommets choisis forment un sous-graphe connexe. Pour les deux problèmes précédents, nous examinons le prix de la connexité, défini comme étant le rapport entre la taille minimum d’un ensemble répondant à la version connexe du problème et celle d’un ensemble du problème originel. Nous prouvons la difficulté du calcul du prix de la connexité d’un graphe. Cependant, lorsqu’on exige que le prix de la connexité d’un graphe ainsi que de tous ses sous-graphes induits soit borné par une constante fixée, la situation change complètement. En effet, pour les problèmes de vertex cover et de dominating set, nous avons pu caractériser ces classes de graphes pour de petites constantes.

Ensuite, nous caractérisons en termes de dominating sets connexes les graphes Pk- free, graphes n’ayant pas de sous-graphes induits isomorphes à un chemin sur k sommets. Beaucoup de problèmes sur les graphes sont étudiés lorsqu’ils sont restreints à cette classe de graphes. De plus, nous appliquons cette caractérisation à la 2-coloration dans les hypergraphes. Pour certains hypergraphes, nous prouvons que ce problème peut être résolu en temps polynomial.

Finalement, nous travaillons sur le problème de Pk-hitting set. Un Pk-hitting set est un ensemble de sommets qui rencontrent tous les chemins sur k sommets. Nous développons un algorithme d’approximation avec un facteur de performance de 3. Notre algorithme, basé sur la méthode primal-dual, fournit un Pk-hitting set dont la taille est au plus 3 fois la taille minimum d’un Pk-hitting set.
Doctorat en Sciences
info:eu-repo/semantics/nonPublished

APA, Harvard, Vancouver, ISO, and other styles

Dissertations / Theses on the topic 'Connectivité des graphes'

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles