Résumé : Les graphes définis à partir de structures algébriques possèdent d’excellentes propriétés de symétries particulièrement intéressantes. L’exemple le plus flagrant est la notion de graphe de Cayley qui s’est révélée très riche non seulement du point de vue théorique mais aussi pratique par ses applications à de nombreux domaines incluant l’architecture des réseaux ou les machines parallèles. Néanmoins, la régularité des graphes de Cayley se révèle parfois être une limite étant donné qu’ils sont toujours sommet-transitifs et donc en particulier non pertinents pour générer des réseaux semiréguliers.Cette observation a motivé, en 2005, la définition d’une nouvelle classe de graphes définis à partir d’un groupe, appelés G-graphes. Ils possèdent aussi de nombreuses propriétés de régularité mais de manière moins restrictive.Cette thèse propose un nouveau regard sur cette classe de graphes par une approche plutôt orientée recherche opérationnelle alors que la grande majorité des études précédentes est dominée par des approches essentiellement algébriques. Nous-nous sommes alors intéressés à plusieurs questions :— La caractérisation des G-graphes : nous proposons des améliorations par rapport aux précédents résultats.— Identifier des classes de graphes comme des G-graphes grâce à des isomorphismes ou en utilisant le théorème de caractérisation.— Etudier la structure et les propriétés de ces graphes, en particulier pour de possibles applications aux réseaux : colorations semi-régulières, symétries et robustesse.— Une approche algorithmique pour la reconnaissance de cette classe avec notamment un premier exemple de cas polynomial lorsque le groupe est abélien.
Interactions between graph theory and group theory have already led to interesting results for both domains. Graphs defined from algebraic groups have highly symmetrical structure giving birth to interesting properties. The most famous example is Cayley graphs, which revealed to be particularly interesting both from a theoretical and a practical point of view due to their applications in several domains including network architecture or parallel machines. Nevertheless, the regularity of Cayley graphs is also a limit as they are always vertex-transitive and therefore not relevant to generate semi-regular networks. This observation motivated the definition, in 2005, of a new family of graphs defined from a group, called G-graphs. They also have many regular properties but are less restrictive. These graphs are in particular semi-regular k-partite, with a chromatic number k directly given in the group representation and they can be either transitive or not.This thesis proposes a new insight into this class of graphs using an approach based on operational research while most of previous studies have been so far dominated by algebraic approaches. Then, the thesis addresses different kind of questions:— Characterizing G-graphs: we propose improvements of previous results.— Identifying some classes of graphs as G-graphs through isomorphism or using the characterization theorem.— Studying the structure and properties of these graphs, in particular for possible applications to networks: semi-regular coloring, symmetries and robustness.— Algorithmic approach for recognizing this class with a first example of polynomial case when the group is abelian.

http://www.theses.fr/2014AGUY0787/document

Éditeur(s) : HAL CCSD
Résumé : International audience
Several assessments of vulnerability and resilience have been attempted at a country level through composite indices but they are barely in accord with a holistic view of sustainable development. We suggest graph theory to structure a network of variables that depict vulnerability and resilience from a sustainable development perspective. Vulnerability is defined as the propensity to incur adverse shocks whereas resilience is the capacity to cope with their negative effects. We identify two control dimensions of vulnerability–resilience (economic and political) and three contingency factors (the social, environmental and the peripheral dimensions). The specificity of the control dimensions is rooted in their impact on all other sides of the pentagon. We propose an algorithm to select the key variables useful in building a composite index that conforms to the structure of these five dimensions while preventing loss of information. An application is provided on Singapore, which has been specified as a typical case of resilience.
Economic Modelling

hal-01291338
https://hal.archives-ouvertes.fr/hal-01291338

Éditeur(s) : HAL CCSD
Résumé : International audience
More and more animal species are endangered. In order to study and protect them, several measures have been taken, which now seem to show their limit. This work focuses on the counting process, a key issue for any project that aims to protect animals. Indeed, this paper proposes an algorithm for automatic counting of singing birds in their habitat by using wireless sensors fitted with microphone. Sensors are used to record audio samples of bird songs. These samples are used to extract some kinds of song fingerprint that are thereafter used to recognize the bird species, through a classification process. Afterwards, by analyzing data which have been collected by a central base, the network structure derived from detection fields of sensors, allows our algorithm to propose an estimate of singing birds in the habitat. This paper details the counting algorithm which uses graph theory and audio inputs comparison. Finally, we demonstrate our scheme efficiency through experimentations.
Local Computer Networks (LCN)
Clearwater, United States

hal-00786165
https://hal.archives-ouvertes.fr/hal-00786165
DOI : 10.1109/LCNW.2012.6424060

Éditeur(s) : HAL CCSD
Résumé : International audience
Vulnerability–resilience indexes fail to grasp all dimensions of sustainability, whereas sustainable development has gained momentum. We fill this gap with a hierarchical multimetric composite index (Net Vulnerability Resilience Index: NVRI) whose robustness relies on a mathematical algorithm based on graph theory. A worldwide application shows that (i) both vulnerability and resilience are policy-responsive and that (ii) there is no determinism for a country to remain vulnerable or resilient. The NVRI enables us to identify a country’s strengths and weaknesses and determine the policy orientations that should be implemented to achieve sustainability.
World Development

hal-01291345
https://hal.archives-ouvertes.fr/hal-01291345
DOI : 10.1016/j.worlddev.2015.02.011

Éditeur(s) : HAL CCSD Elsevier
Résumé : International audience
The tree model and tree-based methods have played a major, fruitful role in evolutionary studies. However, with the increasing realization of the quantitative and qualitative importance of reticulate evolutionary processes, affecting all levels of biological organization, complementary network-based models and methods are now flourishing, inviting evolutionary biology to experience a network-thinking era. We show how relatively recent comers in this field of study, that is, sequence-similarity networks, genome networks, and gene families–genomes bipartite graphs, already allow for a significantly enhanced usage of molecular datasets in comparative studies. Analyses of these networks provide tools for tackling a multitude of complex phenomena, including the evolution of gene transfer, composite genes and genomes, evolutionary transitions, and holobionts.
ISSN: 0966-842X

Droits : http://creativecommons.org/licenses/by-nc-nd/
hal-01300043
http://hal.upmc.fr/hal-01300043
http://hal.upmc.fr/hal-01300043/document
http://hal.upmc.fr/hal-01300043/file/Network-Thinking.pdf
DOI : 10.1016/j.tim.2015.12.003

Éditeur(s) : HAL CCSD Wiley
Résumé : International audience
In this paper we investigate finite-frequency effects in crustal tomography. We developed an inversion procedure based on an exact numerical computation of the sensitivity kernels. In this approach we compute the 3D travel-time sensitivity kernels by using (1) graph theory and an additional bending to estimate accurately both rays and travel-times between source/receiver and diffraction points and (2) paraxial ray theory to estimate the amplitude along theses rays. We invert both the velocity and the hypocentre parameters, using these so-called banana-doughnut kernels and the LSQR iterative solver. We compare the ray-theoretical and the finite-frequency tomography to image the intermediate structures beneath the Gulf of Corinth (Greece), which has long been recognized as the most active continental rifting zone in the Mediterranean region. Our dataset consists of 451 local events with 9233 P- firstarrival times recorded in the western part of the Gulf (Aigion area) in the framework of the 3F-Corinth European project. Previous tomographic images showed a complex velocity crustal model and a low-dip surface that may accommodate the deformation. Accurate velocity models will help to better constrain the rifting process, which is still a subject of debate. The main results of this study show that finite-frequency tomography improves crustal tomographic images by providing better resolved images of the 3D complicated velocity structure. Because the kernels spread the information over a volume, finite-frequency tomography results in a sharpening of layer boundaries as we observed for the shallower part of the crust (down to 5 km depth) beneath the Gulf of Corinth.
ISSN: 0016-8025

insu-00354702
https://hal-insu.archives-ouvertes.fr/insu-00354702
DOI : 10.1111/j.1365-2478.2007.00683.x

Éditeur(s) : HAL CCSD
Résumé : The recent accumulation of genomic sequence data has shown that gene evolution is not strictly tree-Like. Many evolutionary processes, like exon shuffling, gene fusion or nonhomologous recombination remodel genes by creating composite structures that are made from parts with different evolutionary histories. The development of sequence similarity networks provides an analytical framework to study the impact of these processes on molecular evolution, by structuring the resemblance relationships between sequences and by formalizing, in terms of graph theory, the detection of composite genes (intransitive triplets) and gene families (clique minimal separators). The size of current data sets, typically several million sequences, has also required the development of new tools and methods: sequence comparison parallelization, large networks visualization with Louvain communities and large cycles identification. When applied to eukaryotic and viral genome data sets, these methods have shown that composite genes are found throughout cellular organisms and mobile genetic elements. Proportionally, composite genes are more numerous in eukaryotic genomes; in absolute number, they are more numerous in viruses. In the latter, composite genes functional distribution is biased (enrichment of genes families that are essential for the perpetuation of the viral cycle), and the various parts of composite genes sometimes even originate from the genetic material of different viral classes. More generally, the extent of combinatorial processes, by unravelling other evolutionary bonds than homology bonds in the strictest sense, legitimates a pluralistic study of similarity relationships between sequences.
L’accumulation récente de données de séquences génomiques a montré que l’évolution des gènes n’est pas strictement arborescente. De nombreux processus évolutifs, comme l’exon shuffling, la fusion de gènes ou la recombinaison illégitime remodèlent les gènes, créant des structures composites, formées de parties dont les histoires évolutives sont différentes. Le développement de réseaux de similarité de séquences fournit un cadre analytique permettant d’étudier l’impact de ces processus sur l’évolution moléculaire, en structurant les relations de ressemblance entre séquences et en formalisant en termes de graphes la détection de gènes (triplets intransitifs) et de familles de gènes (cliques minimales séparatrices) composites. La taille des jeux de données actuels, de l’ordre de plusieurs millions de séquences, a également requis le développement de nouveaux outils et méthodes : parallélisation des comparaisons de séquences, visualisation de très grands réseaux par simplification en communautés de Louvain et identification de grands cycles. Appliquées à des jeux de données de génomes eucaryotes et viraux, ces méthodes ont démontré la présence de gènes composites dans tout le vivant et les éléments génétiques mobiles. En proportion, les gènes composites sont plus nombreux dans les génomes eucaryotes ; en nombre absolu, ils sont plus nombreux à être portés par des virus. Chez ces derniers, la distribution fonctionnelle des gènes composites est biaisée (enrichissement dans les familles essentielles pour la perpétuation du cycle viral), et les éléments des gènes composites trouvent même parfois leurs origines dans le matériel génétique de classes virales différentes. Plus généralement, l’étendue des processus combinatoires, en révélant des liens évolutionnaires autres que les liens d’homologie au sens fort, justifie une étude pluraliste des relations de similarité entre séquences.
https://tel.archives-ouvertes.fr/tel-01127379

NNT : 2014PA066358
tel-01127379
https://tel.archives-ouvertes.fr/tel-01127379
https://tel.archives-ouvertes.fr/tel-01127379/document
https://tel.archives-ouvertes.fr/tel-01127379/file/2014PA066358.pdf

Éditeur(s) : HAL CCSD Society for Molecular Biology and Evolution
Résumé : International audience
Complex nongradual evolutionary processes such as gene remodeling are difficult to model, to visualize, and to investigate systematically. Despite these challenges, the creation of composite (or mosaic) genes by combination of genetic segments from unrelated gene families was established as an important adaptive phenomena in eukaryotic genomes. In contrast, almost no general studies have been conducted to quantify composite genes in viruses. Although viral genome mosaicism has been well-described, the extent of gene mosaicism and its rules of emergence remain largely unexplored. Applying methods from graph theory to inclusive similarity networks, and using data from more than 3,000 complete viral genomes, we provide the first demonstration that composite genes in viruses are 1) functionally biased, 2) involved in key aspects of the arm race between cells and viruses, and 3) can be classified into two distinct types of composite genes in all viral classes. Beyond the quantification of the widespread recombination of genes among different viruses of the same class, we also report a striking sharing of genetic information between viruses of different classes and with different nucleic acid types. This latter discovery provides novel evidence for the existence of a large and complex mobilome network, which appears partly bound by the sharing of genetic information and by the formation of composite genes between mobile entities with different genetic material. Considering that there are around 10E31 viruses on the planet, gene remodeling appears as a hugely significant way of generating and moving novel sequences between different kinds of organisms on Earth.
ISSN: 1759-6653

Droits : http://creativecommons.org/licenses/by/
hal-01324848
http://hal.upmc.fr/hal-01324848
http://hal.upmc.fr/hal-01324848/document
http://hal.upmc.fr/hal-01324848/file/Genome%20Biol%20Evol-2014-Jachiet-2195-205.pdf
DOI : 10.1093/gbe/evu168

Éditeur(s) : HAL CCSD Elsevier
Résumé : International audience
ISSN: 0362-546X

hal-00816761
https://hal.univ-antilles.fr/hal-00816761
DOI : 10.1016/0362-546X(93)90065-Z

Éditeur(s) : HAL CCSD
Résumé : International audience
A key issue for any project that aims to study endangered animals is the counting process. In this work, we propose an algorithm for automatic counting of singing birds in their habitat by using wireless sensors fitted with microphone. Sensors are used to record audio samples of bird songs and samples are analyzed to extract fingerprints that permit to recognize bird species. This paper details the counting algorithm that uses graph theory and audio inputs comparison. Finally, we demonstrate our scheme efficiency through experimentations.
International Symposium on a World of Wireless, Mobile and Multimedia Networks
Lucca, Italy

hal-00618563
https://hal.archives-ouvertes.fr/hal-00618563
DOI : 10.1109/WoWMoM.2011.5986215