Rozprawy doktorskie na temat „Réseaux de graphes”
Utwórz poprawne odniesienie w stylach APA, MLA, Chicago, Harvard i wielu innych
Sprawdź 50 najlepszych rozpraw doktorskich naukowych na temat „Réseaux de graphes”.
Przycisk „Dodaj do bibliografii” jest dostępny obok każdej pracy w bibliografii. Użyj go – a my automatycznie utworzymy odniesienie bibliograficzne do wybranej pracy w stylu cytowania, którego potrzebujesz: APA, MLA, Harvard, Chicago, Vancouver itp.
Możesz również pobrać pełny tekst publikacji naukowej w formacie „.pdf” i przeczytać adnotację do pracy online, jeśli odpowiednie parametry są dostępne w metadanych.
Przeglądaj rozprawy doktorskie z różnych dziedzin i twórz odpowiednie bibliografie.
Tremblay, Nicolas. "Réseaux et signal : des outils de traitement du signal pour l'analyse des réseaux". Thesis, Lyon, École normale supérieure, 2014. http://www.theses.fr/2014ENSL0938/document.
Pełny tekst źródłaThis thesis describes new tools specifically designed for the analysis of networks such as social, transportation, neuronal, protein, communication networks... These networks, along with the rapid expansion of electronic, IT and mobile technologies are increasingly monitored and measured. Adapted tools of analysis are therefore very much in demand, which need to be universal, powerful, and precise enough to be able to extract useful information from very different possibly large networks. To this end, a large community of researchers from various disciplines have concentrated their efforts on the analysis of graphs, well define mathematical tools modeling the interconnected structure of networks. Among all the considered directions of research, graph signal processing brings a new and promising vision : a signal is no longer defined on a regular n-dimensional topology, but on a particular topology defined by the graph. To apply these new ideas on the practical problems of network analysis paves the way to an analysis firmly rooted in signal processing theory. It is precisely this frontier between signal processing and network science that we explore throughout this thesis, as shown by two of its major contributions. Firstly, a multiscale version of community detection in networks is proposed, based on the recent definition of graph wavelets. Then, a network-adapted bootstrap method is introduced, that enables statistical estimation based on carefully designed graph resampling schemes
Halftermeyer, Pierre. "Connexité dans les Réseaux et Schémas d’Étiquetage Compact d’Urgence". Thesis, Bordeaux, 2014. http://www.theses.fr/2014BORD0140/document.
Pełny tekst źródłaWe aim at assigning each vertex x of a n-vertices graph G a compact O(log n)-bit label L(x) in order to :1. construct, from the labels of the vertices of a forbidden set X C V (G), a datastructure S(X)2. decide, from S(X), L(u) and L(v), whether two vertices u and v are connected in G n X.We give a solution to this problem for the family of 3-connected graphs whith bounded genus.— We obtain O(g log n)-bit labels.— S(X) is computed in O(Sort([X]; n)) time.— Connection between vertices is decided in O(log log n) optimal time.We finally extend this result to H-minor-free graphs. This scheme requires O(polylog n)-bit labels
Togni, Olivier. "Force des graphes : indice optique des réseaux". Bordeaux 1, 1998. http://www.theses.fr/1998BOR10596.
Pełny tekst źródłaAïder, Méziane. "Réseaux d'interconnexion bipartis : colorations généralisées dans les graphes". Phd thesis, Grenoble 1, 1987. http://tel.archives-ouvertes.fr/tel-00325779.
Pełny tekst źródłaFraisse, Pierre. "Longs cycles dans les graphes : applications aux réseaux de Pétri". Paris 11, 1986. http://www.theses.fr/1986PA112037.
Pełny tekst źródłaThis thesis is constituted by several chapters. The first one deals with the existence of certain cycles in graphs of large degree. It gives sufficient conditions for the existence of cycles of length greater than a given number m, or dominating cycles, or circuits containing a set of s vertices and of length at most 2s. The second one gives sufficient conditions for the existence of f-factors in graphs, with conditions on the independence number, connectivity and number of edges, and also by assuming the existence of f-factors in some subgraphs. The third deals with covering of edges and vertices of a graph by cycles, the sum of the length of the cycles being minimal. The fourth attempts to find the chromatic index of random regular graphs. Finally, the fifth is an application of the graph theory to Petri nets. It gives sufficient conditions for liveness on a class of nets
Fraisse, Pierre. "Cycles et facteurs dans les graphes : application de la théorie des graphes aux réseaux de Pétri". Paris 11, 1985. http://www.theses.fr/1985PA112100.
Pełny tekst źródłaThis thesis is constituted by several chapters. The first one deals with the existence of certain cycles in graphs of large degree. It gives sufficient conditions for the existence of cycles of length greater than a given number m, of dominating cycles, of circuits containing a set of s vertices and of length at most 2s. The second one gives sufficient conditions for the existence of f-factors in graphs, with conditions of independence number and connectivity, of number of edges, and also by assuming the existence of f-factors in some subgraphs. The third deals with covering of edges and vertices of a graph by cycles, the sum of the length of the cycles being minimal. Finally, the fourth is an application of the graph theory to Petri nets. It gives sufficient conditions for liveness on a class of nets
Dhandapani, Yogeshwaran. "Réseaux géométriques aléatoires : connexité et comparaison". Paris 6, 2010. http://www.theses.fr/2010PA06A621.
Pełny tekst źródłaCoupechoux, Emilie. "Analyse de grands graphes aléatoires". Paris 7, 2012. http://www.theses.fr/2012PA077184.
Pełny tekst źródłaSeveral kinds of real-world networks can be represented by graphs. Since such networks are very large, their detailed topology is generally unknown, and we model them by large random graphs having the same local statistical properties as the observed networks. An example of such properties is the fact that real-world networks are often highly clustered : if two individuals have a friend in common, they are likely to also be each other's friends. Studying random graph models that are both appropriate and tractable from a mathematical point of view is challenging, that is why we consider several clustered random graph models. The spread of epidemics in random graphs can be used to model several kinds of phenomena in real-world networks, as the spread of diseases, or the diffusion of a new technology. The epidemic model we consider depends on the phenomenon we wish to represent :. An individual can contract a disease by a single contact with any of his friends (such contacts being independent),. But a new technology is likely to be adopted by an individual if many of his friends already have the technology in question. We essentially study these two cases. In each case, one wants to know if a small proportion of the population initially infected (or having the technology in question) can propagate the epidemic to a large part of the population
Bauguion, Pierre-Olivier. "Décomposition de multi-flots et localisation de caches dans les réseaux". Electronic Thesis or Diss., Evry, Institut national des télécommunications, 2014. http://www.theses.fr/2014TELE0010.
Pełny tekst źródłaStreaming requirements on internet network are even more driven by new actors, new services and new digital contents. This leads to high probability of congestion, latency and therefore, a critical decrease of quality of service and/or experience for customers. An internet service provider (ISP) whose goal is to guarantee a first-class performance, needs to take measures to constantly enhance the fluidity of the traffic streaming on its network. One way to face the problem, is to build a Content Delivery Network (CDN). A CDN mainly consists in the deployment of different devices on an existing network. First of all, this thesis presents dynamic programming approaches to tackle server location problems in tree networks. Then, we address a variation of the matroïd intersection algorithm to solve the k-server/cache location problem. We start by giving the definition and characteristics of transparent-caching, as well as the hypothesis that we will use it to build models for transparent cache location in tree network. We tract it to a Mixed Integer Program, and formulate a new paradigm of dynamic programming. We show the relevance of such approach for our problem, and to what extent it can be tractable in other related problems. From a more theoretical point of view, we manage to measure the capacity of a network which is given by the optimal routing strategy, and hence, to identify its critical links. We deal with the Maximum Concurrent Flow (MCF), a classical combinatorial optimization problem. We propose new models and formulations to solve this problem exactly, and more general multi-flows problems as well. A heuristic is also given, to adapt the model to the specific instance values. We experiment these formulations to show the improvements they can provide. Finally, we describe the first strongly polynomial algorithm to solve the maximum concurrent flow to optimality, in the single source case. We show the efficiency of such an approach, even compared to the best models previously presented
Chakroun, Nasr Ali. "Problèmes de circuits, chemins et diamètres dans les graphes : routage dans les réseaux". Paris 11, 1986. http://www.theses.fr/1986PA112354.
Pełny tekst źródłaAlbano, Alice. "Dynamique des graphes de terrain : analyse en temps intrinsèque". Electronic Thesis or Diss., Paris 6, 2014. http://www.theses.fr/2014PA066260.
Pełny tekst źródłaWe are surrounded by a multitude of interaction networks from different contexts. These networks can be modeled as graphs, called complex networks. They have a community structure, i.e. groups of nodes closely related to each other and less connected with the rest of the graph. An other phenomenon studied in complex networks in many contexts is diffusion. The spread of a disease is an example of diffusion. These phenomena are dynamic and depend on an important parameter, which is often little studied: the time scale in which they are observed. According to the chosen scale, the graph dynamics can vary significantly. In this thesis, we propose to study dynamic processes using a suitable time scale. We consider a notion of relative time which we call intrinsic time, opposed to "traditional" time, which we call extrinsic time. We first study diffusion phenomena using intrinsic time, and we compare our results with an extrinsic time scale. This allows us to highlight the fact that the same phenomenon observed at two different time scales can have a very different behavior. We then analyze the relevance of the use of intrinsic time scale for detecting dynamic communities. Comparing communities obtained according extrinsic and intrinsic scales shows that the intrinsic time scale allows a more significant detection than extrinsic time scale
Lécuyer, Fabrice. "Ordonner les nœuds pour passer à l'échelle sur les grands réseaux réels". Electronic Thesis or Diss., Sorbonne université, 2023. http://www.theses.fr/2023SORUS172.
Pełny tekst źródłaThis thesis focuses on using theoretical tools of computer science to improve algorithms in practice, specifically algorithms that process data in the form of graphs. A graph represents elements (nodes) and their interactions (edges). Computer scientists have designed theoretical algorithms for arbitrary graphs, such as finding shortest paths or identifying inter-connected nodes. However, real-world networks have specific properties that are unknown in advance due to the situations from which they arise. They can be very large, which presents a challenge for processing them in reasonable time. To help design scalable algorithms for real-world networks, we focus on the technique of node ordering, which consists in processing the nodes in a specific order that depends on local or global properties of the network. We provide a review on the different mechanisms and methods that have been used to design orderings across various application domains. Then, we present three contributions that use node orderings to make algorithms more efficient. First, we replicate a paper that designs an ordering to make cache systems more effective, which accelerates different graph algorithms. Second, we create new orderings that diminish the number of operations in an existing algorithm for triangle listing. Third, we use greedy algorithms with certain orderings to bound the size of a minimum vertex cover on a specific instance, which allows us to certify the quality of approximate values. These findings insist on scalability issues, time measurements, mathematical grounding and validation by experiments. Finally, we present a collaboration on network analysis that consists in describing the mobility of researchers within the space of knowledge
Tanasescu, Mihaela-Cerasela. "Graphes, Partitions et Classes : G-graphs et leurs applications". Thesis, Antilles-Guyane, 2014. http://www.theses.fr/2014AGUY0787/document.
Pełny tekst źródłaInteractions 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
Jarry, Aubin. "Connexité dans les réseaux de télécommunications". Phd thesis, Université de Nice Sophia-Antipolis, 2005. http://tel.archives-ouvertes.fr/tel-00263555.
Pełny tekst źródłaCrumière, Anne. "Circuits de rétroaction dans les réseaux génétiques de régulation intercellulaires". Aix-Marseille 2, 2008. http://theses.univ-amu.fr.lama.univ-amu.fr/2008AIX22091.pdf.
Pełny tekst źródłaBiologists often represent genetic interactions by directed graphs, named genetic regulatory graphs. Vertices represent genes, whereas edges represent regulatory effects from one gene on another. Edges are labelled with a positive sign in the case of an activation and negative for an inhibition. This thesis deals with relationships between the structure of such graphs and their dynamical properties. The biologist R. Thomas has enounced the following general rule: a necessary condition for multistability is the presence of a positive circuit in the regulatory graph, the sign of a circuit being the product of the signs of its edges. This rule is about the dynamic of a single cell, and it has given rise to mathematical statements and proofs in a differential dynamical formalism, and more recently in a discrete formalism. This thesis aims at extending this rule to regulatory interactions spanning within cells and between cells in the discrete formalism. At first, we consider as a starting point the case of fixed cells located on a one-dimensional-infinite grid. Intercellular communication is assumed to be local: a gene may interact only with genes in its own cell and neighbouring cells (left or right). This assumption, which is biologically reasonable is standard and at the basis of cellular automata. Secondly we generalize the model above. We study an intercellular genetic network: the location of cells is done by a lattice, i. E, a discret subgroup of Rd, the expression level of genes is multivaluated and intercellular communication is extended to some neighbourhood. With this general framework, we obtain the Thomas'rule with a spatial condition on stable states. We then apply our model through two examples of the Drosophila, in particular the formation of sense organs
Albano, Alice. "Dynamique des graphes de terrain : analyse en temps intrinsèque". Thesis, Paris 6, 2014. http://www.theses.fr/2014PA066260/document.
Pełny tekst źródłaWe are surrounded by a multitude of interaction networks from different contexts. These networks can be modeled as graphs, called complex networks. They have a community structure, i.e. groups of nodes closely related to each other and less connected with the rest of the graph. An other phenomenon studied in complex networks in many contexts is diffusion. The spread of a disease is an example of diffusion. These phenomena are dynamic and depend on an important parameter, which is often little studied: the time scale in which they are observed. According to the chosen scale, the graph dynamics can vary significantly. In this thesis, we propose to study dynamic processes using a suitable time scale. We consider a notion of relative time which we call intrinsic time, opposed to "traditional" time, which we call extrinsic time. We first study diffusion phenomena using intrinsic time, and we compare our results with an extrinsic time scale. This allows us to highlight the fact that the same phenomenon observed at two different time scales can have a very different behavior. We then analyze the relevance of the use of intrinsic time scale for detecting dynamic communities. Comparing communities obtained according extrinsic and intrinsic scales shows that the intrinsic time scale allows a more significant detection than extrinsic time scale
Berthomé, Pascal. "Contribution à l'algorithmique des graphes: quelques représentations pertinentes de graphes". Habilitation à diriger des recherches, Université Paris Sud - Paris XI, 2006. http://tel.archives-ouvertes.fr/tel-00460292.
Pełny tekst źródłaBenchettara, Nasserine. "Prévision de nouveaux liens dans les réseaux d'interactions bipartis : Application au calcul de recommandation". Paris 13, 2011. http://scbd-sto.univ-paris13.fr/secure/edgalilee_th_2011_benchettara.pdf.
Pełny tekst źródłaIn this work, we handle the problem of new link prediction in dynamic complex networks. We mainly focus on studying networks having a bipartite underlaying structure. We propose to apply a propositionnalization approach where each couple of nodes in the network is described by a set of topological measures. One first contribution in this thesis is to consider measures computed in the bipartite graph and also in the associated projected graphs. A supervised machine learning approach is applied. This approach though it gives some good results, suffers from the obvious problem of class skewness. We hence focus on handling this problem. Informed sub-sampling approaches are first proposed. A semi-supervised machine learning approach is also applied. All proposed approaches are applied and evaluated on real datasets used in real application of academic collaboration recommendation and product recommendation in an e-commerce site
König, Jean-Claude. "Les réseaux d'interconnexion et les algorithmes distribués". Paris 11, 1987. http://www.theses.fr/1987PA112069.
Pełny tekst źródłaThis 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)
Gambette, Philippe. "Méthodes combinatoires de reconstruction de réseaux phylogénétiques". Phd thesis, Université Montpellier II - Sciences et Techniques du Languedoc, 2010. http://tel.archives-ouvertes.fr/tel-00608342.
Pełny tekst źródłaLesfari, Hicham. "Fondements réseaux et l'IA". Electronic Thesis or Diss., Université Côte d'Azur, 2022. http://www.theses.fr/2022COAZ4056.
Pełny tekst źródłaThe field of Artificial Intelligence (AI) has brought a broad impact on today's society, leading to a gripping interaction between several scientific disciplines. In this respect, there has been a strong twofold interest across the literature.On the one hand, a growing trend in telecommunication networks consists in revisiting classic optimization problems using machine learning techniques in order to exploit their potential benefits. We focus on some challenges brought by the detection of anomalies in networks, and the allocation of resources within software-defined networking (SDN) and network function virtualization (NFV).On the other hand, a substantial effort has been devoted towards the theoretical understanding of the collective behavior of networks. We focus on some challenges brought by the study of majority dynamics within multi-agent systems, and the compression of artificial neural networks with the aim at increasing their efficiency.In this study, we contextualize the above focal points in the framework of investigating some foundations of networks; viewed through the lens of telecommunications networks and neural networks. We first focus our attention on developing graph similarity measures for network anomaly detection. Next, we study deterministic and stochastic majority dynamics in multi-agent systems. Then, we discuss the random subset sum problem in the context of neural network compression. Finally, we walk through some other miscellaneous problems
Essoh, Célestin Dejoli. "Réseaux de résistances aléatoires". Aix-Marseille 1, 1990. http://www.theses.fr/1990AIX11316.
Pełny tekst źródłaSamy, Modeliar Mouny. "Graphes et contraintes". Thesis, Artois, 2017. http://www.theses.fr/2017ARTO0402/document.
Pełny tekst źródłaThis thesis presents anoriginal filtering approach, called SND(Scoring- based Neighborhood Dominance), for the subgraph isomorphism problem. By reasoning on vertex dominance properties based on various scoring and neigh- borhood functions, SND appears to be a filtering mechanism of strong inference potential. For example, the recently proposed method LAD is a particular case of SND. A specialization is studied of SND : by considering the number of k-length paths in graphs and three ways of relating sets of vertices. With this specialization, we prove that SND is stronger than LAD and incomparable to SAC (Single- ton Arc Consistency). Our experimental results show that SND achieves most of the time the same filtering performances as SAC (while being several orders of magnitude faster), which allows one to find subisomorphism functions far more efficiently than MAC, while slightly outperforming LAD
Latouche, Pierre. "Modèles de graphes aléatoires à structure cachée pour l'analyse des réseaux". Phd thesis, Université d'Evry-Val d'Essonne, 2010. http://tel.archives-ouvertes.fr/tel-00623088.
Pełny tekst źródłaKhalife, Sammy. "Graphes, géométrie et représentations pour le langage et les réseaux d'entités". Thesis, Institut polytechnique de Paris, 2020. http://www.theses.fr/2020IPPAX055.
Pełny tekst źródłaThe automated treatment of familiar objects, either natural or artifacts, always relies on a translation into entities manageable by computer programs. The choice of these abstract representations is always crucial for the efficiency of the treatments and receives the utmost attention from computer scientists and developers. However, another problem rises: the correspondence between the object to be treated and "its" representation is not necessarily one-to-one! Therefore, the ambiguous nature of certain discrete structures is problematic for their modeling as well as their processing and analysis with a program. Natural language, and in particular its textual representation, is an example. The subject of this thesis is to explore this question, which we approach using combinatorial and geometric methods. These methods allow us to address the problem of extracting information from large networks of entities and to construct representations useful for natural language processing.Firstly, we start by showing combinatorial properties of a family of graphs implicitly involved in sequential models. These properties essentially concern the inverse problem of finding a sequence representing a given graph. The resulting algorithms allow us to carry out an experimental comparison of different sequential models used in language modeling.Secondly, we consider an application for the problem of identifying named entities. Following a review of recent solutions, we propose a competitive method based on the comparison of knowledge graph structures which is less costly in annotating examples dedicated to the problem. We also establish an experimental analysis of the influence of entities from capital relations. This analysis suggests to broaden the framework for applying the identification of entities to knowledge bases of different natures. These solutions are used today in a software library in the banking sector.Then, we perform a geometric study of recently proposed representations of words, during which we discuss a geometric conjecture theoretically and experimentally. This study suggests that language analogies are difficult to transpose into geometric properties, and leads us to consider the paradigm of distance geometry in order to construct new representations.Finally, we propose a methodology based on the paradigm of distance geometry in order to build new representations of words or entities. We propose algorithms for solving this problem on some large scale instances, which allow us to build interpretable and competitive representations in performance for extrinsic tasks. More generally, we propose through this paradigm a new framework and research leadsfor the construction of representations in machine learning
Miao, Huifang. "Connectixité, forte orientation des graphes et réseaux de capteurs sans fil". Paris 11, 2008. http://www.theses.fr/2008PA112095.
Pełny tekst źródłaThis thesis is mainly about some parameters of graphs--connectivity, strong distance, the orientation of graphs and some applications in wireless sensor networks. In Chapter 2, we model that each sensor nodes monitors exact one target. We present the disjoint sets coverage and connectivity problem, and prove it is NP-complete. In Chapter 3, we consider the wireless sensor networks satisfying that each node monitors one target or just for connection. Assume G is l(k-1)+1-connected, then we can find k (the maximum number) disjoint sets each of which completely covers all the targets and remains connected to one of the central processing nodes. And we also give the related algorithms to find the k disjoint sets. In Chapter 4, based on the model described in Chapter 3, assume the working time of the node only for connection is d times as the one both for monitoring and connection. We show that it is NP-complete to attain energy efficiency. An algorithm is designed for it. Chapter 5 is about the strong distance in oriented complete k-partite graphs. In Chapter 6, we determine the lower orientable strong radius and diameter of complete k-partite graphs, and give the upper orientable strong diameter and the bounds on the upper orientable strong radius of complete k-partite graphs. In Chapter 7, we show that each complete k-partite graph has an optimal strong (k, d)-orientation
Morales, Varela Nelson Víctor. "Algorithmique des réseaux de communication radio modélisés par de [sic] graphes". Nice, 2007. http://www.theses.fr/2007NICE4032.
Pełny tekst źródłaThis thesis studies the algorithmics anc complexity of communications in a radio network. Radio networks are particular, because the transmission distance is limited and because certain transmissions may interfere with each other. We model this constraints by assuming that two nodes (radio equipment) can communicate with each other if they are at a distance smaller or equal than d_T and that a node interferes with any other that is at a distance smaller or equal than "d_I. This distances are considered in both cases: when they nodes belong to the Euclidean space and the distance between the nodes is the usual Euclidean distance, and when the distances are measured over a graph representing the network. A round being a set of transmissions that are compatible (do not interfere) we interest ourselves in the problem of gathering information originated at the nodes in the network into a central node called the sink. Our goal is to find the minimum number of rounds required to gather all the information and to devise algorithms that calculate this minimum. This problem is motivated by a question asked by France Telecom about providing internet to villages in France (internet dans les villages). The nodes represent houses (clients) that communicate with each other by means of radio signals, their objective being to access internet using a central gateway which, in turn, is connected to the internet with by satellite. The same problem is found in sensor networks, where information is collected in sensors (the nodes) and has to be gathered in a base station. We considered the case where each node has a fixed number of packets to transmit and the distances are measured over a base-graph. We have shown that the problem of finding an optimal solution is Np-Hard in the general case, but we provided a four approximation algorithm, valid for any base-graph. We have also studied either optimal or nearly optimal solutions for particular topologies like the path and the 2-D grid. We have also studied the systolic case where packets are transmitted permanently, the objective being to satisfy arbitrary traffic demands, per unit of time, with the smallest possible delay. We have studied this variant of the problem in the case where distances are measured on a graph, but also then they are measured in the Euclidean space. We have shown that the problem is NP-Hard, have established a four approximation and obtained either optimal or nearly optimal solutions for the path, trees and subsets of the 2-D grid
Faÿ, Armelle. "Sur la propagation de l'information dans les réseaux probabilistes". Paris 6, 1997. http://www.theses.fr/1997PA066770.
Pełny tekst źródłaCharbey, Raphaël. "Sociabilités en ligne, usages et réseaux". Thesis, Paris, ENST, 2018. http://www.theses.fr/2018ENST0049/document.
Pełny tekst źródłaWith the digital advent, it is now possible for researchers to collect important amounts of data and online social network platforms are surely part of it. Sociologists, among others, seized those new resources to investigate over interaction modalities between individuals as well as their impact on the structure of sociability. Following this lead, this thesis work aims at analyzing a large number of Facebook accounts, through data analysis and graph theory classical tools, and to bring methodological contributions. Two main factors encourage to study Facebook social activities. On one hand, the importance of time spent on this platform by many Internet users justifies by itself the sociologists interest. On the other, and contrarily to what we observe on other social network websites, ties between individuals are similar to the ones that appear offline. First, the thesis proposes to detangle the multiple meanings that are behind the fact of ”being on Facebook”. The uses of our surveyed are not compacted in fantasized normative practices but vary depending on how they appropriate the different composers of the platform tools. These uses, as we will see it, do not concern all the socioprofessional categories in the same way and they also influence how the respondents interact with their online friends. The manuscript also explores these interactions, as well as the lover role into the relational structure. Second part of the thesis builds a typology of these relational structures. They are said as egocentred, which means that they are taken from the perspective of the respondent. This typology of social networks is based on their graphlet counts, that are the number of times each type of subnetwork appear in them. This approach offers a meso perspective (between micro and macro), that is propitious to underline some new social phenomena. With a high pluri-disciplinary potential, the graphlet methodology is also discussed and explored itself
Canu, Maël. "Détection de communautés orientée sommet pour des réseaux mobiles opportunistes sociaux". Electronic Thesis or Diss., Paris 6, 2017. http://www.theses.fr/2017PA066378.
Pełny tekst źródłaOur research is in the field of complex network analysis and mining, specifically addressing the communit detection task, ie. algorithms aiming to uncover particularly dense subgraphs. We focus on the implementation of such an algorithm in a decentralised and distributed context : opportunistic MANET constituted of small wireless devices using peer-to-peer communication. To tackle the implementation constraints in such networks, we propose several methods designed according to the novel and trending vertex-centred paradigm, by combining Think-Like-a-Vertex graph processing with vertex-centred community detection methods based on leaders or seeds : they show specific properties allowing dsitributed implementations suiting the opportunistic MANET case. In this context, we first a global working principle and implement it in three different algorithms dedicated to three different configurations of community detection : the VOLCAN algorithm manages the classical disjoint community detection task in a static graph. We extend it with the LOCNeSs algorithm, that is dealing with overlapping communities which means that one vertex can belong to several communities. It adds more flexibility to the method and more significance to produced results. We also tackle the dynamic graphe case (graph evolving over time), addressed by the DynLOCNeSs algorithm.Each algorithm comes with a decentralised implementation and theoretical as well as experimental studies conducted both on real and synthetic benchmark data, allowing to evaluate the quality of the results and compare to existing state-of-the-art methods. Finally, we consider a special case of opportunistic decentralised MANET developped as a part of a research project about smart and communicating clothing. We formalise a task of path finding between smart t-shirts holders and propose a recommandation strategy using community structure, that we model and evaluate through an algorithm named SWAGG
Creusefond, Jean. "Caractériser et détecter les communautés dans les réseaux sociaux". Thesis, Normandie, 2017. http://www.theses.fr/2017NORMC203/document.
Pełny tekst źródłaN this thesis, I first present a new way of characterising communities from a network of timestamped messages. I show that its structure is linked with communities : communication structures are over-represented inside communities while diffusion structures appear mainly on the boundaries.Then, I propose to evaluate communities with a new quality function, compacity, that measures the propagation speed of communications in communities. I also present the Lex-Clustering, a new community detection algorithm based on the LexDFS graph traversal that features some characteristics of information diffusion.Finally, I present a methodology that I used to link quality functions and ground-truths. I introduce the concept of contexts, sets of ground-truths that are similar in some way. I implemented this methodology in a software called CoDACom (Community Detection Algorithm Comparator, codacom.greyc.fr) that also provides many community detection tools
Retoré, Christian. "Réseaux et séquents ordonnés". Phd thesis, Université Paris-Diderot - Paris VII, 1993. http://tel.archives-ouvertes.fr/tel-00585634.
Pełny tekst źródłaCanu, Maël. "Détection de communautés orientée sommet pour des réseaux mobiles opportunistes sociaux". Thesis, Paris 6, 2017. http://www.theses.fr/2017PA066378/document.
Pełny tekst źródłaOur research is in the field of complex network analysis and mining, specifically addressing the communit detection task, ie. algorithms aiming to uncover particularly dense subgraphs. We focus on the implementation of such an algorithm in a decentralised and distributed context : opportunistic MANET constituted of small wireless devices using peer-to-peer communication. To tackle the implementation constraints in such networks, we propose several methods designed according to the novel and trending vertex-centred paradigm, by combining Think-Like-a-Vertex graph processing with vertex-centred community detection methods based on leaders or seeds : they show specific properties allowing dsitributed implementations suiting the opportunistic MANET case. In this context, we first a global working principle and implement it in three different algorithms dedicated to three different configurations of community detection : the VOLCAN algorithm manages the classical disjoint community detection task in a static graph. We extend it with the LOCNeSs algorithm, that is dealing with overlapping communities which means that one vertex can belong to several communities. It adds more flexibility to the method and more significance to produced results. We also tackle the dynamic graphe case (graph evolving over time), addressed by the DynLOCNeSs algorithm.Each algorithm comes with a decentralised implementation and theoretical as well as experimental studies conducted both on real and synthetic benchmark data, allowing to evaluate the quality of the results and compare to existing state-of-the-art methods. Finally, we consider a special case of opportunistic decentralised MANET developped as a part of a research project about smart and communicating clothing. We formalise a task of path finding between smart t-shirts holders and propose a recommandation strategy using community structure, that we model and evaluate through an algorithm named SWAGG
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.
Pełny tekst źródłaThe 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
Tackx, Raphaël. "Analyse de la structure communautaire des réseaux bipartis". Electronic Thesis or Diss., Sorbonne université, 2018. https://accesdistant.sorbonne-universite.fr/login?url=https://theses-intra.sorbonne-universite.fr/2018SORUS550.pdf.
Pełny tekst źródłaIn the real world, numerous networks appear naturally, they are everywhere, in many disciplines, for example in computer science with router networks, satellite networks, webpage networks, in biology with neural networks, in ecology with biological interaction networks, in linguistic with synonym networks, in law with legal decision networks, in economy with interbank networks, in social sciences and humanities with social networks. Generally, a network reflects the interactions between many entities of a system. These interactions have different sources, a social link or a friendship link in a social network, a cable in a router network, a chemical reaction in a protein-protein interaction network, a hyperlink in a webpage network. Furthermore, the rapid democratization of digital technology in our societies, with internet in particular, leads to create new systems which can be seen as networks. Finally, all these networks depict very specific features : they come from pratical contexts, most of the time they are big (they may be comprised of several billion of nodes and links, containing a large amount of information), they share statistical properties. In this regard, they are called real-world networks or complex networks. Nowaday, network science is a research area in its own right focusing on describing and modeling these networks in order to reveal their main features and improve our understanding of their mecanisms. Most of the works in this area use graphs formalism which provides a set of mathematical tools well suited for analyzing the topology of these networks. It exists many applications, for instance applications in spread of epidemy or computer viruses, weakness of networks in case of a breakdown, attack resilience, study for link prediction, recommandation, etc. One of the major issue is the identification of community structure. The large majority of real-world networks depicts several levels of organization in their structure. Because of there is a weak global density coupled with a strong local density, we observe that nodes are usually organized into groups, called communities, which are more internally connected than they are to the rest of the network. Moreover, these structures have a meaning in the network itself, for example communities of a social network may correspond to social groups (friends, families, etc.), communities of a protein-protein network may translate fonctions of a cell, communities may be also related to similar subjects in a webpage network [...]
Kchikech, Mustapha. "Algorithmes de multicoloration, de coloration de chemins, et de radio k-étiquetage de graphes : applications aux réseaux tout-optiques WDM et aux réseaux cellulaires". Dijon, 2005. http://www.theses.fr/2005DIJOS030.
Pełny tekst źródłaRifi, Mouna. "Modélisation et Analyse des Réseaux Complexes : application à la sûreté nucléaire". Thesis, Sorbonne Paris Cité, 2019. http://www.theses.fr/2019USPCD049.
Pełny tekst źródłaThis work aims to propose an adequate graph modeling approach for nuclear safety accident systems and sequences.These systems and sequences come from "Probabilistic Safety Analysis" (PSA) which is an exhaustive analysis of all possible accident scenarios, to estimate their probabilities of occurrence (by grouping them by families) and the associated consequences.Then, an analysis of the resulting networks is performed by network centrality measures. A first application consists on predicting the nuclear Risk Increase Factor, which is a PSA importance factor, using supervised learning algorithms : classification tree methods, logistic regression and ensemble learning methods, on un balanced data. Furthermore, a new synthetic centrality coefficient and a similarity measure are developed to compare the networks structures and their topological characteristics, based on their centrality vectors interdependencies. This new approach uses statistical techniques (sampling,correlation and homogeneity).The relevance and appreciation of this new measure of similarity are validated on the clustering of most popular theoretical graphs and on the prediction of the type of these graphs. Finally, an application of this approach has been conducted for the clustering of nuclear safety systems networks
Fertin, Guillaume. "Etude des communications dans les réseaux d'interconnexion". Bordeaux 1, 1999. http://www.theses.fr/1999BOR10535.
Pełny tekst źródłaLimnios, 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.
Pełny tekst źródłaExtracting 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
Berthomé, Pascal. "Contribution à l'algorithmique des architectures parallèles : des réseaux point-à-point aux réseaux optiques". Lyon 1, 1995. http://www.theses.fr/1995LYO10031.
Pełny tekst źródłaChelly, Magda Lilia. "Propagation d'une position dans les réseaux connectés". Electronic Thesis or Diss., Evry, Institut national des télécommunications, 2011. http://www.theses.fr/2011TELE0018.
Pełny tekst źródłaPositioning systems have undeniably progressed. Currently, in an outdoor environment, the accuracy reaches a few centimetres under certain conditions: open space, clear sky, specific measurement techniques, etc. Nevertheless, the problem of positioning in an indoor environment remains persistent: multipath, attenuation, etc. Different systems for indoor positioning have been developed, using technologies such as UWB, WiFi or Infrared. These systems provide interesting results that could allow to reach one meter accuracy. But, this accuracy is related to many criteria: infrastructure, technology, calibration, technical computing, etc. To reduce these constraints, we propose a new approach for positioning. Our approach utilizes all the network equipments present in an environment. The approach is based on two fundamental steps: the study of visibility and the development of geographical links. The study of visibility estimates the visible equipments in the environment. We have studied several models of visibility and we carried out a comparison of the results. A three-dimensional graph is build using the study of geographical links between equipments. This graph allows us to visualize the distribution of equipments and to estimate the geographic positions of each device. To implement our approach, we developed a simulator in Matlab. The simulator first studies the visible equipments for the unknown device. Then, it estimates the distances between the device and the visible equipments. Finally, it constructs a graph and calculates the geographical positions. Simulation results are presented to validate our approach. Our approach is a positioning system capable of operating without additional infrastructure in an indoor environment
Reyes, Valenzuela Patricio Alejandro. "Collecte d'information dans les réseaux radio". Nice, 2009. http://www.theses.fr/2009NICE4069.
Pełny tekst źródłaThis thesis concerns the study of the algorithmic and the complexity of the communication in radio networks. In particular, we were interested in the problem of gathering information from the nodes of a radio network in a central node. This problem is motivated by a question of France Telecom (Orange Labs) “How to bring Internet in villages”. Nodes represent the houses of the villages which communicate between them by radio, the goal being to reach a gateway connected to Internet by a satellite link. The same problem can be found in sensor networks where the question is to collect data from sensors to a base station. A peculiarity of radio networks is that the transmission distance is limited and that the transmissions interfere between them (interference phenomena). We model these constraints by saying that two nodes (radio devices) can communicate if they are at distance at most dT and a node interferes with another one if their distance is at most dI. The distances are considered in a graph representing the network. Thus, a communication step will consist in a compatible (non interfering) set of transmissions. Our goal is to find the minimum number of steps needed to achieve such a gathering and design algorithms achieving this minimum. For special topologies such as the path and the grid, we have proposed optimal or near optimal solutions. We also considered the systolic (or continuous) case where we want to maximize the throughput (bandwidth) offered to each node
Hagenbach, Jeanne. "Communication stratégique et réseaux". Phd thesis, Université Panthéon-Sorbonne - Paris I, 2009. http://tel.archives-ouvertes.fr/tel-00450632.
Pełny tekst źródłaPigné, Yoann. "Modélisation et traitement décentralisé des graphes dynamiquesApplication aux réseaux mobiles ad hoc". Phd thesis, Université du Havre, 2008. http://tel.archives-ouvertes.fr/tel-00371962.
Pełny tekst źródłaNous étudions la résolution de problèmes dans ces graphes à l'aide de méthodes inspirées de mécanismes d'intelligence collective.
Les modèles proposés sont validés dans le contexte applicatif des réseaux mobiles ad hoc. Une approche originale de construction et de maintien de chemins de communication sous plusieurs contraintes est proposée. Le problème de la construction et du maintien d'une forêt couvrante dans un réseau mobile ad hoc est également étudié.
Soto, Gomez Mauricio Abel. "Quelques propriétés topologiques des graphes et applications à internet et aux réseaux". Paris 7, 2011. http://www.theses.fr/2011PA077228.
Pełny tekst źródłaThis thesis focuses on topological properties of graphs and their application on communication networks, specifically on graphs reflecting Internet structure. We first look how far from a tree a graph may be by the study of two parameters: hyperbolicity and treewidth. For hyperbolicity, we analyse the relation with others graph parameters, we also show that some graph decompositions allow its efficient computation. We compute both parameters o Internet snapshots at different levels of granularity and time periods. We propose some structural and algorithmic consequences of obtained values. Then, we study the graph clustering problem from the perspective of modularity, which measures a clustering quality and is largely studied in the literature. We analyse modularity from a theoretical point of view and [describe] its asymptotic behaviour for some graph families. Finally, we deal with adversarial queueing theory, a combinatorial framework derived from classic queueing theory where injection process is und the control of an adversary. We propose a new model generalisation by considering request of distinct types
Baert, Anne-Elisabeth. "Graphes aléatoires et diffusion dans les réseaux cellulaires : modélisation combinatoire et probabiliste". Amiens, 2003. http://www.theses.fr/2003AMIE0304.
Pełny tekst źródłaMontassier, Mickaël. "Colorations de graphes sous contraintes, conception de réseaux embarqués tolérants aux pannes". Bordeaux 1, 2005. http://www.theses.fr/2005BOR13045.
Pełny tekst źródłaTabourier, Lionel. "Méthode de comparaison des topologies de graphes complexes : applications aux réseaux sociaux". Paris 6, 2010. http://www.theses.fr/2010PA066335.
Pełny tekst źródłaCanales, Reveco Miguel. "Simulation parallèle de réseaux de Petri stochastiques : le cas de graphes d'événements". Nice, 1994. http://www.theses.fr/1994NICE4717.
Pełny tekst źródłaA new parallel simulation method is proposed for the class of stochastic marked graphs, that is amenable to an SIMD implementation. This method is based on the (R, max, +) linear structure of recurrence equations that were established for this type of systems. Three variants are presented, the temporal one, the spatial one and the one by levels. The temporal variant, which generalizes to Petri nets a method that was introduced recently for queues, is of more use for simulating systems for along time interval. The spatial variant allows the simulation of larger nets, and it also provides a simpler way of estimating the statistics of the making process. The variant by levels allows the simulation of even larger systems, but using more memory on each processor. The theoretical parallel complexity of the algorithms associated to each variant has been studied. A few examples of practical interest are provided (blocking queues in tandem, a stochastic job shop model) for which the cost of simulating O(NT) events of a net of size T is in O(N log T) with the spatial variant, while the classical sequential discrete event simulation is in O(NT) at least. These theoretical considerations are confirmed by experimental results obtained from a prototype that was implemented on the Connection Machine-2
Lemmouchi, Slimane. "Etude de la robustesse des graphes sociaux émergents". Phd thesis, Université Claude Bernard - Lyon I, 2012. http://tel.archives-ouvertes.fr/tel-00944441.
Pełny tekst źródła