Дисертації з теми "Réseaux de graphes"
Щоб переглянути інші типи публікацій з цієї теми, перейдіть за посиланням: Réseaux de graphes.
Оформте джерело за APA, MLA, Chicago, Harvard та іншими стилями
Ознайомтеся з топ-50 дисертацій для дослідження на тему "Réseaux de graphes".
Біля кожної праці в переліку літератури доступна кнопка «Додати до бібліографії». Скористайтеся нею – і ми автоматично оформимо бібліографічне посилання на обрану працю в потрібному вам стилі цитування: APA, MLA, «Гарвард», «Чикаго», «Ванкувер» тощо.
Також ви можете завантажити повний текст наукової публікації у форматі «.pdf» та прочитати онлайн анотацію до роботи, якщо відповідні параметри наявні в метаданих.
Переглядайте дисертації для різних дисциплін та оформлюйте правильно вашу бібліографію.
1
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.
Анотація:
Cette thèse propose de nouveaux outils adaptés à l'analyse des réseaux : sociaux, de transport, de neurones, de protéines, de télécommunications... Ces réseaux, avec l'essor de certaines technologies électroniques, informatiques et mobiles, sont de plus en plus mesurables et mesurés ; la demande d'outils d'analyse assez génériques pour s'appliquer à ces réseaux de natures différentes, assez puissants pour gérer leur grande taille et assez pertinents pour en extraire l'information utile, augmente en conséquence. Pour répondre à cette demande, une grande communauté de chercheurs de différents horizons scientifiques concentre ses efforts sur l'analyse des graphes, des outils mathématiques modélisant la structure relationnelle des objets d'un réseau. Parmi les directions de recherche envisagées, le traitement du signal sur graphe apporte un éclairage prometteur sur la question : le signal n'est plus défini comme en traitement du signal classique sur une topologie régulière à n dimensions, mais sur une topologie particulière définie par le graphe. Appliquer ces idées nouvelles aux problématiques concrètes d'analyse d'un réseau, c'est ouvrir la voie à une analyse solidement fondée sur la théorie du signal. C'est précisément autour de cette frontière entre traitement du signal et science des réseaux que s'articule cette thèse, comme l'illustrent ses deux principales contributions. D'abord, une version multiéchelle de détection de communautés dans un réseau est introduite, basée sur la définition récente des ondelettes sur graphe. Puis, inspirée du concept classique de bootstrap, une méthode de rééchantillonnage de graphes est proposée à des fins d'estimation statistiqueThis 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
2
Halftermeyer, Pierre. "Connexité dans les Réseaux et Schémas d’Étiquetage Compact d’Urgence." Thesis, Bordeaux, 2014. http://www.theses.fr/2014BORD0140/document.
Анотація:
L’objectif de cette thèse est d’attribuer à chaque sommet x d’un graphe G à n sommets une étiquette L(x) de taille compacte O(log n) bits afin de pouvoir :1. construire, à partir des étiquettes d’un ensemble de sommets en panne X C V (G), une structure de donnée S(X)2. décider, à partir de S(X) et des étiquettes L(u) et L(v), si les sommets u et v sont connectés dans le graphe G n X.Nous proposons une solution à ce problème pour la famille des graphes 3-connexes de genre g (via plusieurs résultats intermédiaires).— Les étiquettes sont de taille O(g log n) bits— Le temps de construction de la structure de donnée S(X) est O(Sort([X]; n)).— Le temps de décision est O(log log n). Ce temps est optimal.Nous étendons ce résultat à la famille des graphes excluant un mineur H fixé. Les étiquettes sont ici de taille O(polylog n) bitsWe 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
3
Togni, Olivier. "Force des graphes : indice optique des réseaux." Bordeaux 1, 1998. http://www.theses.fr/1998BOR10596.
Анотація:
Cette these se situe en theorie des graphes et comporte deux parties independantes. Nous definissons tout d'abord deux compositions de graphes que nous utiliserons dans les deux parties de la these : la composition par couplage qui generalise le produit cartesien de graphes et la composition par inflation. La premiere partie est consacree a l'etude d'un parametre appele force d'un graphe simple. Le but est de trouver des valuations minimales rendant le graphe irregulier. On etudie la force des graphes composes par couplage. Nous obtenons des resultats asymptotiquement optimaux pour certains composes de cycles et pour le produit cartesien de deux graphes complets. Nous demontrons egalement une conjecture de cammack schelp et schrag de 1991 sur la force des arbres sans sommet de degre 2. Dans la deuxieme partie, on s'interesse au parametre indice optique, intervenant dans les reseaux de communication tout-optique utilisants le multiplexage en longueurs d'ondes (wdm). Ce parametre mesure le nombre minimum de longueurs d'ondes necessaires pour que tous les noeuds du reseau puissent communiquer en meme temps. Ce probleme se ramene a des problemes de colorations de graphes. Nous etudions l'indice optique des graphes composes par couplage et par inflation. Nous obtenons des resultats exacts pour certains composes de graphes complets. Dans le dernier chapitre, nous montrons un majorant de l'indice optique des graphes circulants 4-reguliers par l'arc-indice de transmission.
4
Aï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.
Анотація:
Étude sur les graphes bipartis orientes de Moore montrant que de tels graphes existent, pour certaines valeurs du diamètre, et servent a la construction d'une classe de graphes bipartis orientes, asymptotiquement optimaux. Dans la deuxième partie du travail, quelques notions de coloration des graphes sont présentées. Celles-ci permettent de généraliser certains résultats déjà connus dans le cadre de la coloration habituelle et d'en obtenir d'autres plutôt spécifiques a ces notions. La généralisation de la notion de perfection en b-perfection est proposée ce qui permet l'obtention des graphes triangules représentant la seule classe de graphes b-parfaits
5
Fraisse, Pierre. "Longs cycles dans les graphes : applications aux réseaux de Pétri." Paris 11, 1986. http://www.theses.fr/1986PA112037.
Анотація:
Cette thèse se compose de plusieurs chapitres. Le premier porte sur l’existence de certains longs cycles dans des graphes de grand degré, cycles hamiltoniens et p-dominants en particulier. Il se compose des articles 1 à 5. Le second porte sur les facteurs de graphes, et contient les articles 6 à 7. Le troisième porter sur les couvertures des arêtes et des sommets d’un graphe par une famille de cycles de longueur totale minimale (article 8). Le quatrième donne un premier résultat sur l’index chromatique des graphes aléatoires réguliers. Il permet de conjecturer que presque tout graphe r-régulier est r-arête-coloriable (article 9). Enfin le cinquième traite d’une application de la théorie des graphes à la théorie des réseaux de Pétri (article 10)This 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
6
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.
Анотація:
Cette thèse se compose de plusieurs chapitres/ le premier porte sur l’existence de certains cycles dans des graphes de grand degré. Il donne des résultats de conditions suffisantes d’existence du cycle de longueur supérieure à un nombre m fixé, de cycle dominant, de circuit contenant s sommets et de longueur au plus 2s. Le second porte sur des conditions suffisantes d’existence de f-facteurs de graphes, avec condition de stabilité et connexité, d’une part, nombre d’arcs, d’autre part, existence de f-facteurs dans certains sous-graphes, enfin. Le troisième porte sur les couvertures des arêtes et des sommets d’un graphe par une famille de cycles de longueur totale minimale. Enfin le quatrième traite d’une application de la théorie des graphes à la théorie des réseaux de Petri. Il donne des conditions suffisantes de vivacité pour certains réseauxThis 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
7
Dhandapani, Yogeshwaran. "Réseaux géométriques aléatoires : connexité et comparaison." Paris 6, 2010. http://www.theses.fr/2010PA06A621.
Анотація:
Cette thèse porte sur deux thèmes : 1)Percolation et connexité sur les graphes géométriques aléatoires dits "type AB". 2)Comparaison stochastique directionnellement convexe de processus ponctuels et leurs propriétés de percolation et connexité. Dans le premier sujet, nous définissons un graphe biparti, dit "de type AB", sur deux processus ponctuels de Poisson indépendants. Cet graphe est une extension continue de graphe dit "type AB" sur une grille régulière. Nous montrons l'existence de percolation pour toute dimension supérieure à deux et nous établissons des bornes pour l'intensité critique. Dans le cas de dimensions deux, nous caractérisons exactement l'intensité critique. Pour le problème de connexité, nous étudions le modelé sur les processus ponctuels de Poisson indépendant dans le cube de volume un avec des intensités n et c_n pour une constante c > 0. Nous établissons des bornes asymptotiques presque sûres pour le seuil de connexité. 2) Le but du deuxième sujet de travail est de définir l'ordre directionnellement convexe de processus ponctuels est de lier cet ordre aux propriétés de regroupement des points de processus ponctuels et, dans un contexte applicatif, aux caractéristiques de la performance des réseaux de communication sans fil. La dernière partie de cette thèse porte sur la comparaison des intensités critiques de percolation pour les processus ponctuels ordonnés selon cet ordre et les applications de ces résultats de comparaison pour les réseaux sans fils. Nous concluons en montrant que les processus ponctuels inférieurs, selon cet ordre, à un processus ponctuel de Poisson ont une transition de phase non-triviale dans plusieurs modelés des percolation.
8
Coupechoux, Emilie. "Analyse de grands graphes aléatoires." Paris 7, 2012. http://www.theses.fr/2012PA077184.
Анотація:
Plusieurs types de réseaux du monde réel peuvent être représentés par des graphes. Comme il s'agit de réseaux de très grande taille, leur topologie détaillée est généralement inconnue, et nous les modélisons par de grands graphes aléatoires ayant les mêmes propriétés statistiques locales que celles des réseaux observés. Un exemple de telle propriété est la présence de regroupements dans les réseaux réels : si deux individus ont un ami en commun, ils ont également tendance à être amis entre eux. Etudier des modèles de graphes aléatoires qui soient à la fois appropriés et faciles à aborder d'un point de vue mathématique représente un challenge, c'est pourquoi nous considérons plusieurs modèles de graphes aléatoires possédant ces propriétés. La propagation d'épidémies dans les graphes aléatoires peut être utilisée pour modéliser plusieurs types de phénomènes présents dans les réseaux réels, comme la propagation de maladies, ou la diffusion d'une nouvelle technologie. Le modèle épidémique que nous considérons dépend du phénomène que nous voulons représenter :. Un individu peut contracter une maladie par un simple contact avec un de ses amis (ces contacts étant indépendants),. Mais une nouvelle technologie est susceptible d'être adoptée par un individu lorsque beaucoup de ses amis ont déjà la technologie en question. Nous étudions essentiellement ces deux différents cas de figure. Dans chaque cas, nous cherchons à savoir si une faible proportion de la population initialement atteinte (ou ayant la technologie en question) peut propager l'épidémie à une grande partie de la populationSeveral 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
9
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.
Анотація:
Les nouveaux acteurs, les nouveaux services et les nouveaux contenus multimédias qui transitent sur le réseau internet génèrent un trafic et des débits de plus en plus élevés. Ceci peut occasionner une congestion, source de latence et de dépréciation de la qualité de service ressentie par les utilisateurs. Un fournisseur d'accès à internet dont l'objectif est de garantir un réseau d'excellence doit donc prendre des mesures pour améliorer sans cesse la fluidité de son réseau. Cela passe notamment par la mise en place d'un réseau de distribution de contenus (déploiement de dispositifs sur le réseau existant). Dans un premier temps cette thèse s'articule à présenter des approches de programmation dynamique de localisation de serveurs optimales dans des arborescences. Nous présentons également un approche pour résoudre le problème de déploiement de CDN et de k serveurs/caches à l'aide de l'algorithme exact et polynomial d'intersection de matroïdes. Nous explicitons ensuite ce qu'est un cache et quelles sont ses caractéristiques. Nous définissons ensuite les hypothèses effectuées et la modélisation associée pour le déploiement de caches transparents dans une arborescence, et le liens avec les algorithmes existants présentés précédemment. Nous présentons alors un modèle complet pour un programme linéaire en nombres entiers (PLNE) et un nouveau paradigme de programmation dynamique pour résoudre ce même problème. Nous montrons alors en quoi cette approche se généralise à des problèmes connexes de localisation dans les arborescences, ainsi que les performances pratiques d'une telle approche. D'un regard plus théorique, nous mesurons la capacité d'un réseau donné par le routage optimal de ses demandes, et, de ce fait, ses liens critiques. Nous manipulons alors le problème de flot concurrent maximal (FCM), un problème classique de la littérature de recherche opérationnelle. Nous exhibons alors de nouvelles formulations exactes pour résoudre ce problème, ainsi que les problèmes de multi-flots de manière plus générale. Une heuristique de construction de formulation pour le FCM est également proposée, pour tirer parti de la distribution spécifique des capacités d'une instance. Nous montrons alors la supériorité des performances de ces nouvelles formulations par le biais de comparaisons. Enfin, nous décrivons le premier algorithme exact et fortement polynomial pour résoudre le problème de flot concurrent maximal dans le cas d'une seule source; et nous montrons l'efficacité pratique d'une telle approche, comparée aux meilleures formulations explicitées précédemmentStreaming 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
10
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.
Анотація:
Cette thèse traite de différents problèmes liés à la théorie des graphes. La plupart des résultats sont liés à l’existence de circuits et de chemins, le reste est consacré à l’étude du diamètre et du routage. Le premier chapitre est consacré à l’étude du pancyclisme dans les graphes vérifiant une condition du type de celle de V. Chvatal et P. Erdos : la connectivité du graphe est supérieure ou égale à sa stabilité. Dans le deuxième chapitre nous nous intéressons aux graphes antisymétriques dont les degrés sont minorés. On y traite principalement des liens existants entre degrés et diamètre dans les graphes antisymétriques. Le troisième chapitre est axé sur la recherche de chemins et circuits dans les graphes bipartis orientés dont le nombre d’arcs ou les degrés sont minorés. Dans le quatrième chapitre, nous précisions la structure des graphes fortement connexes sans C≥₄. Le cinquième chapitre est la synthèse d’une étude sur le routage dans les réseaux d’interconnexion effectuée chez Thomson-C. S. F dans le cadre d’un projet de Réseau Numérique à Intégration de Service (RNIS), permettant de commuter des signaux à débits variables.
11
Albano, Alice. "Dynamique des graphes de terrain : analyse en temps intrinsèque." Electronic Thesis or Diss., Paris 6, 2014. http://www.theses.fr/2014PA066260.
Анотація:
Nous sommes entourés par une multitude de réseaux d'interactions, issus de contextes très différents. Ces réseaux peuvent être modélisés par des graphes, appelés graphes de terrain. Ils possèdent une structure en communautés, c'est-à-dire en groupes de nœuds très liés entre eux, et peu liés avec les autres. Un phénomène que l'on étudie sur les graphes dans de nombreux contextes est la diffusion. La propagation d'une maladie en est un exemple. Ces phénomènes dépendent d'un paramètre important, mais souvent peu étudié : l'échelle de temps selon laquelle on les observe. Selon l'échelle choisie, la dynamique du graphe peut varier de manière très importante.Dans cette thèse, nous proposons d'étudier des processus dynamiques en utilisant une échelle de temps adaptée. Nous considérons une notion de temps relatif, que nous appelons le temps intrinsèque, par opposition au temps "classique", que nous appelons temps extrinsèque. Nous étudions en premier lieu des phénomènes de diffusion selon une échelle de temps intrinsèque, et nous comparons les résultats obtenus avec une échelle extrinsèque. Ceci nous permet de mettre en évidence le fait qu'un même phénomène observé dans deux échelles de temps différentes puisse présenter un comportement très différent. Nous analysons ensuite la pertinence de l'utilisation du temps intrinsèque pour la détection de communautés dynamiques. Les communautés obtenues selon les échelles de temps extrinsèques et intrinsèques nous montrent qu'une échelle intrinsèque permet la détection de communautés beaucoup plus significatives et détaillées que l'échelle extrinsèqueWe are surrounded by a multitude of interaction networks from different contexts. These networks can be modeled as graphs, called complex networks. They have a community structure, i.e. groups of nodes closely related to each other and less connected with the rest of the graph. An other phenomenon studied in complex networks in many contexts is diffusion. The spread of a disease is an example of diffusion. These phenomena are dynamic and depend on an important parameter, which is often little studied: the time scale in which they are observed. According to the chosen scale, the graph dynamics can vary significantly. In this thesis, we propose to study dynamic processes using a suitable time scale. We consider a notion of relative time which we call intrinsic time, opposed to "traditional" time, which we call extrinsic time. We first study diffusion phenomena using intrinsic time, and we compare our results with an extrinsic time scale. This allows us to highlight the fact that the same phenomenon observed at two different time scales can have a very different behavior. We then analyze the relevance of the use of intrinsic time scale for detecting dynamic communities. Comparing communities obtained according extrinsic and intrinsic scales shows that the intrinsic time scale allows a more significant detection than extrinsic time scale
12
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.
Анотація:
Cette thèse porte sur l'utilisation des outils théoriques de l'informatique pour améliorer les algorithmes dans la pratique, en particulier ceux qui traitent des données sous forme de graphes. Un graphe représente des éléments (nœuds) et leurs interactions (arêtes). L'informatique théorique a conçu des algorithmes pour des graphes arbitraires, tels que la recherche des chemins les plus courts ou l'identification des nœuds interconnectés. Cependant, les réseaux réels ont des propriétés spécifiques qui sont inconnues à l'avance en raison des situations du monde réel dont ils sont issus. Ils peuvent être très volumineux, ce qui pose un problème pour les traiter en un temps raisonnable. Pour aider à concevoir des algorithmes qui passent à l'échelle sur de gros graphes, nous nous concentrons sur la technique qui consiste à réordonner les nœuds selon un ordre spécifique qui dépend des propriétés locales ou globales du graphe. Nous classifions les différents mécanismes et méthodes qui ont été utilisés pour concevoir des ordres dans divers domaines d'application. Ensuite, nous présentons trois contributions qui utilisent l'ordre des nœuds pour rendre les algorithmes plus efficaces. Tout d'abord, nous reproduisons un article qui conçoit un ordre pour rendre les systèmes de cache plus efficaces, ce qui accélère différents algorithmes de graphes. Deuxièmement, nous créons de nouveaux ordres qui réduisent le nombre d'opérations dans un algorithme existant pour lister les triangles. Troisièmement, nous utilisons des algorithmes simples avec des ordres appropriés pour limiter la taille d'une couverture minimale par les sommets sur une instance spécifique de graphe, ce qui nous permet de certifier la qualité des résultats obtenus par des valeurs approchées. Ces résultats insistent sur les questions de passage à l'échelle, les mesures de temps, les fondements mathématiques et la validation par l'expérience. Enfin, nous présentons une collaboration sur l'analyse des réseaux qui consiste à décrire la mobilité des chercheurs et chercheuses dans l'espace de la connaissanceThis 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
13
Tanasescu, Mihaela-Cerasela. "Graphes, Partitions et Classes : G-graphs et leurs applications." Thesis, Antilles-Guyane, 2014. http://www.theses.fr/2014AGUY0787/document.
Анотація:
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élienInteractions 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
14
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.
15
Crumiè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.
Анотація:
Les biologistes représentent souvent les interactions génétiques par des graphes dirigés, appelés graphes de régulation génétique. Les sommets désignent les gènes du système et les arêtes, les effets de régulation d'un gène sur un autre. Elles sont munies d'un signe positif dans le cas d'une activation et négatif pour une inhibition. Cette thèse traite des relations entre la structure des graphes et leurs propriétés dynamiques. Dans les années 80, le biologiste R. Thomas a énoncé la règle suivante : une condition nécessaire pour la multistabilité est la présence d'un circuit positif dans un graphe de régulation, le signe d'un circuit étant le produit des signes de ces arêtes. Cette règle a été démontrée dans un formalisme différentiel et plus récemment dans un cadre discret, mais toujours dans le cas où les gènes font partie d'une seule cellule. On peut s'interroger sur la validité de cette règle pour un système d'interactions génétiques intracellulaires et intercellulaires. Dans un premier temps, on considère le cas simplifié où les cellules sont réparties sur une grille infinie unidimensionnelle et on se place dans un cadre booléen. La communication intercellulaire est supposée locale : un gène interagit avec des gènes de sa propre cellule et des cellules voisines (gauche ou droite). Cette supposition, qui est raisonnable biologiquement, est standard dans la définition des automates cellulaires. Puis, on généralise le modèle précédent en supposant que les cellules sont localisées suivant un réseau, i. E, un sous-groupe discret de Rd. De plus, on se place dans le cadre où le niveau d'expression des gènes est multivalué et la communication intercellulaire s'étend à un voisinage quelconque. Dans ce cadre général, on obtient la première règle de Thomas avec une condition spatiale sur les états stables. Ce modèle est illustré par deux applications liées au développement de la Drosophile: la segmentation de l'embryon et la formation de l'organe sensorielBiologists 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
16
Albano, Alice. "Dynamique des graphes de terrain : analyse en temps intrinsèque." Thesis, Paris 6, 2014. http://www.theses.fr/2014PA066260/document.
Анотація:
Nous sommes entourés par une multitude de réseaux d'interactions, issus de contextes très différents. Ces réseaux peuvent être modélisés par des graphes, appelés graphes de terrain. Ils possèdent une structure en communautés, c'est-à-dire en groupes de nœuds très liés entre eux, et peu liés avec les autres. Un phénomène que l'on étudie sur les graphes dans de nombreux contextes est la diffusion. La propagation d'une maladie en est un exemple. Ces phénomènes dépendent d'un paramètre important, mais souvent peu étudié : l'échelle de temps selon laquelle on les observe. Selon l'échelle choisie, la dynamique du graphe peut varier de manière très importante.Dans cette thèse, nous proposons d'étudier des processus dynamiques en utilisant une échelle de temps adaptée. Nous considérons une notion de temps relatif, que nous appelons le temps intrinsèque, par opposition au temps "classique", que nous appelons temps extrinsèque. Nous étudions en premier lieu des phénomènes de diffusion selon une échelle de temps intrinsèque, et nous comparons les résultats obtenus avec une échelle extrinsèque. Ceci nous permet de mettre en évidence le fait qu'un même phénomène observé dans deux échelles de temps différentes puisse présenter un comportement très différent. Nous analysons ensuite la pertinence de l'utilisation du temps intrinsèque pour la détection de communautés dynamiques. Les communautés obtenues selon les échelles de temps extrinsèques et intrinsèques nous montrent qu'une échelle intrinsèque permet la détection de communautés beaucoup plus significatives et détaillées que l'échelle extrinsèqueWe are surrounded by a multitude of interaction networks from different contexts. These networks can be modeled as graphs, called complex networks. They have a community structure, i.e. groups of nodes closely related to each other and less connected with the rest of the graph. An other phenomenon studied in complex networks in many contexts is diffusion. The spread of a disease is an example of diffusion. These phenomena are dynamic and depend on an important parameter, which is often little studied: the time scale in which they are observed. According to the chosen scale, the graph dynamics can vary significantly. In this thesis, we propose to study dynamic processes using a suitable time scale. We consider a notion of relative time which we call intrinsic time, opposed to "traditional" time, which we call extrinsic time. We first study diffusion phenomena using intrinsic time, and we compare our results with an extrinsic time scale. This allows us to highlight the fact that the same phenomenon observed at two different time scales can have a very different behavior. We then analyze the relevance of the use of intrinsic time scale for detecting dynamic communities. Comparing communities obtained according extrinsic and intrinsic scales shows that the intrinsic time scale allows a more significant detection than extrinsic time scale
17
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.
Анотація:
Ce document est divisé en deux parties principales. La première partie concerne les résultats que nous avons obtenu au travers de diverses collaborations sur les communications dans les réseaux. Afin de ne pas multiplier les chapitres dans cette partie, nous avons choisi en premier lieu de présenter l'évolution du contexte des réseaux sur lesquels j'ai travaillé durant ces 10 dernières années. En particulier, nous montrons plusieurs facettes que peut recouvrir l'expression \textbf{communications optiques}. Dans un deuxième temps, nous avons regroupé les problèmes abordés en deux chapitres: - le premier s'intéresse à des aspects structurels des graphes utiles pour la construction de protocoles de communication dans les réseaux. - le second aborde une problématique importante dans le contexte actuel de la recherche de la compétitivité: l'optimisation de ressources. La deuxième partie s'intéresse à deux représentations de graphes qui s'avèrent pertinentes pour les problèmes considérés. Elle présente deux problèmes principaux donnant deux chapitres indépendants. Le premier problème abordé dans cette partie concerne un très vieux (au sens informatique) problème issu de la théorie de flots: les flots multi-terminaux. Nous nous sommes attachés à montrer la puissance d'un outil permettant de représenter ces types de flots: les arbres de Gomory-Hu, ainsi que leur utilité dans une version paramétrée du problème. Le second problème présente au travers du calcul du polynôme chromatique une représentation des graphes sous la forme d'arbre de cliques augmenté.
18
Benchettara, 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.
Анотація:
Dans cette thèse, nous étudions le problème de la prévision d'apparition de nouveaux liens dans les réseaux d'interactions. Nous nous intéressons en particulier aux réseaux dynamiques ayant une structure bipartite. Nous proposons un modèle de prévision de liens utilisant les techniques d'apprentissage automatique supervisé. Le problème de prévision de liens est considéré dans ce cas comme un problème de classification binaire. Notre approche applique un schéma de propositionnalisation où chaque paire de noeuds est décrite par un ensemble d'attributs représentant des mesures topologiques. Ces mesures sont calculées dans le graphe biparti et dans les graphes projetés qui en découlent. Nous montrons que ces nouvelles similarités dites " indirectes " apportent un gain d'information bénéfique par rapport aux seules similarités directes. Cette thèse apporte aussi de nouvelles solutions au problème de déséquilibre des données dû à la disproportion inhérente entre le nombre de liens qui peuvent se former et le nombre de liens qui se forment réellement. Nous proposons tout d'abord d'utiliser des méthodes de sous-échantillonnage informé pour réduire le déséquilibre. Une deuxième solution au niveau algorithmique consiste en une approche d'apprentissage semi-supervisé. Dans ce cas, le problème de prévision de liens est vu comme un problème d'apprentissage à partir d'un ensemble d'instances étiquetées (classe minoritaire) et un ensemble d'instances non-étiquetées (classe majoritaire). Nous montrons que cette nouvelle approche permet d'améliorer les performances du classifieur sur la classe minoritaire. Les différentes approches proposées sont appliquées sur les données réelles dans le cadre de deux applications : recommandation de collaborations académiques et recommandation de produits dans un site de vente de musique en ligneIn 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
19
König, Jean-Claude. "Les réseaux d'interconnexion et les algorithmes distribués." Paris 11, 1987. http://www.theses.fr/1987PA112069.
Анотація:
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)
20
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.
Анотація:
Les réseaux phylogénétiques généralisent le modèle de l'arbre pour décrire l'évolution, en permettant à des arêtes entre les branches de l'arbre d'exprimer des échanges de matériel génétique entre espèces coexistantes. De nombreuses approches combinatoires - fondées sur la manipulation d'ensembles finis d'objets mathématiques - ont été conçues pour reconstruire ces réseaux à partir de données extraites de plusieurs arbres de gènes contradictoires. Elles se divisent en plusieurs catégories selon le type de données en entrée (triplets, quadruplets, clades ou bipartitions) et les restrictions de structure sur les réseaux reconstruits. Nous analysons en particulier la structure d'une classe de réseaux restreints, les réseaux de niveau k, et adaptons ce paramètre de niveau au contexte non enraciné. Nous donnons aussi de nouvelles méthodes combinatoires pour reconstruire des réseaux phylogénétiques, à partir de clades - méthode implémentée dans le logiciel Dendroscope - ou de quadruplets. Nous étudions les limites de ces méthodes combinatoires (explosion de complexité, bruit et silence dans les données, ambiguïté des réseaux reconstruits) et la façon de les prendre en compte, en particulier par un pré-traitement des données. Finalement, nous illustrons les résultats de ces méthodes de reconstruction sur des données réelles avant de conclure sur leur utilisation dans une méthodologie globale qui intègre des aspects statistiques
21
Lesfari, Hicham. "Fondements réseaux et l'IA." Electronic Thesis or Diss., Université Côte d'Azur, 2022. http://www.theses.fr/2022COAZ4056.
Анотація:
Le domaine de l'Intelligence Artificielle (IA) a un large impact sur la société d'aujourd'hui, ayant conduit notamment à une interaction passionnante entre plusieurs disciplines scientifiques. À cet égard, un double intérêt émerge dans la littérature.D'une part, une tendance croissante dans les réseaux de télécommunication consiste à revisiter les problèmes d'optimisation classiques en utilisant des techniques d'apprentissage automatique afin d'exploiter leurs avantages potentiels. Nous nous focaliserons sur certains défis posés par la détection d'anomalies dans les réseaux ainsi que l'allocation des ressources dans le cadre des réseaux logiciels (SDN) et de la virtualisation des fonctions réseau (NFV). D'autre part, un effort substantiel a été consacré dans le but d'apporter une compréhension théorique du comportement collectif des réseaux. Nous nous focaliserons sur certains défis posés par l'étude de la dynamique majoritaire au sein des systèmes multi-agents ainsi qu'à la compression des réseaux de neurones artificiels dans le but d'augmenter leur efficacité.Dans cette étude, nous contextualisons les points focaux ci-dessus dans le cadre de l'étude de certains fondements de réseaux; vus sous l'angle des réseaux de télécommunications et des réseaux neuronaux. Nous nous concentrons d'abord sur le développement de mesures de similarité de graphes pour la détection d'anomalies dans les réseaux. Ensuite, nous étudions la dynamique majoritaire déterministe et stochastique dans les systèmes multi-agents. Ensuite, nous discutons du problème de la somme de sous-ensembles aléatoires dans le contexte de la compression des réseaux neuronaux. Enfin, nous passons en revue quelques problèmes généraux diversThe 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
22
Essoh, Célestin Dejoli. "Réseaux de résistances aléatoires." Aix-Marseille 1, 1990. http://www.theses.fr/1990AIX11316.
Анотація:
Une grande partie de ce travail porte sur l'etude rigoureuse de reseaux de resistances aleatoires et sur la description d'un nouveau formalisme base sur la theorie des graphes. Nous montrons dans la limite thermodynamique de reseau euclidien de resistances que la conductance normalisee moyenne est superieure a l'inverse de sa resistance normalisee moyenne. Nous etablissons une loi forte des grands nombres, lorsque leur produit vaut 1. Dans le meme cadre nous avons etudie rigoureusement la resistance et la fluctuation de resistance et demontrons non seulement une loi forte des grands nombres, mais aussi que la fluctuation relative normalisee converge en distribution vers la loi gaussienne normale. D'autre part nous utilisons la theorie du milieu effectif et des simulations numeriques basees sur l'algorithme de lobb et frank pour etudier la conductance de reseaux euclidiens avec distribution binaire de conductances complexes, modelisant des materiaux heterogenes et des milieux composites. Notre etude porte essentiellement sur le comportement de la probabilite de transition optique, definie comme la probabilite de la distribution binaire ou la partie imaginaire de la conductance du reseau s'annule. Nous avons egalement etudie, certaines grandeurs physiques de l'optique, tels que la reflexion et l'absorption, et les resonances des echantillons de taille finie. Enfin nous utilisons egalement la theorie du milieu effectif pour estimer les exposants critiques de la conductance et du bruit de resistances de reseaux euclidiens avec distributions continues et singulieres de resistances et de bruits. Nous mettons en relief un phenomene de changement de loi d'echelle au voisinage de la probabilite de percolation. L'algorithme de lobb et frank et l'analyse de loi d'echelle de taille finie nous permettent d'obtenir une nouvelle estimation de l'exposant critique de bruit du reseau euclidien de dimension 2
23
Samy, Modeliar Mouny. "Graphes et contraintes." Thesis, Artois, 2017. http://www.theses.fr/2017ARTO0402/document.
Анотація:
Cette thèse propose une approche de filtrage originale, SND en abrégé pour Scoring-based Neighborhood Dominance, pour le problème d’isomorphisme de sous- graphe. En raisonnant sur des propriétés de dominance entre sommets basées sur diverses fonctions de score et de voisinage, SND apparait comme un puissant mécanisme de filtrage. Une spécialisation de SND est étudiée, elle est basée sur le nombre de chemins de longueur k comme fonction de score ainsi que trois manières de considérer le voisinage. Avec cette spécialisation, il est montré que SND est plus puissant que LAD et incomparable à SAC (Singleton Arc Consistency). L'étude expérimentale montre que SND atteint dans la plupart des cas les mêmes performances en terme de filtrage que SAC tout en étant plus rapide de plusieurs ordres de grandeurs. Cela permet de résoudre le problème d’isomorphisme de sous-graphe en étant beaucoup plus efficace que MAC et légèrement meilleur que LAD.Un solveur de contraintes est également proposé ainsi qu'une optimisation du processus de propagation de MACThis 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
24
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.
Анотація:
Les réseaux sont très largement utilisés dans de nombreux domaines scientifiques afin de représenter les interactions entre objets d'intérêt. Ainsi, en Biologie, les réseaux de régulation s'appliquent à décrire les mécanismes de régulation des gènes, à partir de facteurs de transcription, tandis que les réseaux métaboliques permettent de représenter des voies de réactions biochimiques. En sciences sociales, ils sont couramment utilisés pour représenter les interactions entre individus. Dans le cadre de cette thèse, nous nous intéressons à des méthodes d'apprentissage non supervisé dont l'objectif est de classer les noeuds d'un réseau en fonction de leurs connexions. Il existe une vaste littérature se référant à ce sujet et un nombre important d'algorithmes ont été proposés depuis les premiers travaux de Moreno en 1934. Notre point de départ est le modèle à blocs stochastiques, Stochastic Block Model (SBM) (Nowicki et Snijders, 2001) en anglais, qui permet la recherche de classes topologiques hétérogènes. Nous considérons un contexte Bayésien et proposons un algorithme de type variational Bayes pour approcher la loi a posteriori des paramètres. Cette approche permet d'obtenir un nouveau critère de sélection de modèles afin d'estimer le nombre de composantes dans un réseau. Par ailleurs, il apparaît que SBM ainsi que la plupart des modèles existants de classification sont limités puisqu'ils partitionnent les noeuds dans des classes disjointes. Or, de nombreux objets d'étude dans le cadre d'applications réelles sont connus pour appartenir à plusieurs groupes en même temps. Par exemple, en Biologie, des protéines appelées moonlighting proteins en anglais ont plusieurs fonctions dans les cellules. Nous introduisons donc un nouveau modèle de graphe aléatoire que nous appelons modèle à blocs stochastiques chevauchants, Overlapping Stochastic Block Model (OSBM) en anglais. Il autorise les noeuds d'un réseau à appartenir à plusieurs groupes simultanément et peut prendre en compte des topologies de connexion très différentes. Deux algorithmes d'estimation sont proposés ainsi qu'un critère de sélection de modèles.
25
Khalife, 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.
Анотація:
Le traitement informatique des objets qui nous entourent, naturels ou créés par l'homme, demande toujours de passer par une phase de traduction en entités traitables par des programmes. Le choix de ces représentations abstraites est toujours crucial pour l'efficacité des traitements et est le terrain d'améliorations constantes. Mais il est un autre aspect émergeant : le lien entre l'objet à représenter et "sa" représentation n'est pas forcément bijectif ! Ainsi la nature ambiguë de certaines structures discrètes pose problème pour la modélisation ainsi que le traitement et l'analyse à l'aide d'un programme informatique. Le langage dit ``naturel'', et sous sa forme en particulier de représentation textuelle, en est un exemple. Le sujet de cette thèse consiste à explorer cette question, que nous étudions à l'aide de méthodes combinatoires et géométriques. Ces méthodes nous permettent de formaliser le problème d'extraction d'information dans des grands réseaux d'entités ainsi que de construire des représentations géométriques utiles pour le traitement du langage naturel. Dans un premier temps, nous commençons par démontrer des propriétés combinatoires des graphes de séquences intervenant de manière implicite dans les modèles séquentiels. Ces propriétés concernent essentiellement le problème inverse de trouver une séquence représentant un graphe donné. Les algorithmes qui en découlent nous permettent d'effectuer une comparaison expérimentale de différents modèles séquentiels utilisés en modélisation du langage. Dans un second temps, nous considérons une application pour le problème d'identification d'entités nommées. A la suite d'une revue de solutions récentes, nous proposons une méthode compétitive basée sur la comparaison de structures de graphes de connaissances et moins coûteuse en annotations d'exemples dédiés au problème. Nous établissons également une analyse expérimentale d'influence d'entités à partir de relations capitalistiques. Cette analyse suggère l'élargissement du cadre d'application de l'identification d'entités à des bases de connaissances de natures différentes. Ces solutions sont aujourd'hui utilisées au sein d'une librairie logicielle dans le secteur bancaire. Ensuite, nous développons une étude géométrique de représentations de mots récemment proposées, au cours de laquelle nous discutons une conjecture géométrique théoriquement et expérimentalement. Cette étude suggère que les analogies du langage sont difficilement transposables en propriétés géométriques, et nous amène a considérer le paradigme de la géométrie des distances afin de construire de nouvelles représentations. Enfin, nous proposons une méthodologie basée sur le paradigme de la géométrie des distances afin de construire de nouvelles représentations de mots ou d'entités. Nous proposons des algorithmes de résolution de ce problème à grande échelle, qui nous permettent de construire des représentations interprétables et compétitives en performance pour des tâches extrinsèques. Plus généralement, nous proposons à travers ce paradigme un nouveau cadre et piste d'explorations pour la construction de représentations en apprentissage machineThe 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
26
Miao, Huifang. "Connectixité, forte orientation des graphes et réseaux de capteurs sans fil." Paris 11, 2008. http://www.theses.fr/2008PA112095.
Анотація:
Cette thèse étudie principalement quelques paramètres de connectivité, de distance forte et d'orientation de graphes et donne quelques applications dans le domaine des réseaux de capteurs sans fil. Dans le chapitre 2, nous modélisons le cas où chaque nœud peut contrôler au plus une cible. Nous recherchons des ensembles disjoints contrôlant toutes les cibles et connectés à un sommet central ; nous montrons que la recherche du nombre maximum de tels ensembles disjoints est NP-complet. Dans le chapitre 3, nous considérons les réseaux de capteurs sans fil tels que chaque nœud surveille une cible et sert à la connexion du réseau. En supposant que le graphe est (m(k-1)+1)-connexe, nous montrons qu'on peut trouver un nombre maximum k d'ensembles disjoints, chacun d'eux couvrant toutes les m cibles et étant connecté à un des nœuds centraux. Nous donnons aussi l'algorithme correspondant qui détermine les k ensembles disjoints. Dans le chapitre 4, basé sur le modèle trouvé dans chapitre 3, on suppose que le temps de travail du nœud seulement pour la connexion est d fois égal à celui nécessaire à la fois pour la surveillance et pour la connexion. Nous montrons que c'est aussi un problème NP-complet. Dans le chapitre 5 on s'intéresse à la distance forte dans les graphes orientés k-parti-complets. Dans le chapitre 6, on donne des généralisations de notions de rayon et diamètre et on étudie les plus petits et plus grands "rayon fort" et "diamètre fort" des graphes k-parti-complets. Dans le chapitre 7, on montre que chaque graphe k-parti-complet a une (k, d)-forte orientation optimaleThis 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
27
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.
Анотація:
Cette thèse concerne l'étude de l'algorithmique et de la complexité des communications dans les réseaux radio. La particularité des réseaux radio est que la distance de transmission est limitée et que les transmissions interfèrent entre elles (phénomènes de brouillage). Nous modélisons ces contraintes en disant que deux sommets (équipements radio) peuvent communiquer s'ils sont à distance au plus d_T et qu'un noeud interfère avec un autre si leur distance est au plus d_I. Les distances sont considérées soit dans un graphe représentant le réseau, soit dans le plan euclidien. Une étape de communication consistera en un ensemble de transmissions compatibles (n'interférant pas). Nous nous sommes intéressés au problème de rassembler les informations des sommets du réseau en un noeud central appelé puits. Notre objectif est de trouver le nombre minimum d'étapes nécessaires pour réaliser un tel rassemblement et de concevoir des algorithmes réalisant ce minimum. Ce problème est motivé par une question de France Telecom "comment amener Internet dans les villages". Les sommets représentent les maisons des villages qui communiquent entre elles par radio, le but étant d'atteindre une passerelle centrale connectée à Internet par une liaison satellite. Le même problème se rencontre dans les réseaux de senseurs ou il s'agit de collecter les informations des senseurs dans une station de base. Nous avons considéré le cas où chaque sommet a un nombre fixé de paquets à transmettre et où les distances sont mesurées sur le graphe. Nous avons montré que trouver une solution optimale est en général un problème NP-difficile. Nous avons donné un algorithme 4-approché pour un graphe quelconque. Nous avons aussi établi des résultats optimaux ou quasi optimaux pour des topologies particulières comme la grille ou le chemin. Nous avons aussi considéré le cas systolique où on veut transmettre continuellement des paquets, l'objectif étant de minimiser l'écart entre l'envoi de deux paquets d'un même noeud. Nous avons étudié ce problème quand les distances sont mesurées sur le graphe et aussi dans le cas de sommets dans le plan avec distances euclidiennes. Nous avons montré que ce problème était NP-difficile, avons établi un algorithme 4-approché et obtenu des solutions quasi optimales pour les chemins, arbres et grillesThis 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
28
Faÿ, Armelle. "Sur la propagation de l'information dans les réseaux probabilistes." Paris 6, 1997. http://www.theses.fr/1997PA066770.
29
Charbey, Raphaël. "Sociabilités en ligne, usages et réseaux." Thesis, Paris, ENST, 2018. http://www.theses.fr/2018ENST0049/document.
Анотація:
Avec l’avènement du numérique, il est désormais possible aux chercheurs d’amasser des grandes quantités de données et les plateformes de réseaux sociaux en ligne ne font pas exception à cela. Les sociologues, comme d’autres, se sont emparés de ces nouvelles ressources afin de poursuivre leurs enquêtes sur les modalités de l’interaction entre individus et leur impact sur la structuration de la sociabilité. Suivant cette voie, ce travail de thèse vise à l’analyse d’un grand nombre de comptes Facebook, aussi bien au travers des outils classiques de l’analyse de données que de la théorie des graphes, à laquelle des contributions méthodologiques sont apportées. Deux facteurs principaux encouragent l’étude de l’activité et de la sociabilité en ligne. D’une part, le temps important dédié à cette plateforme par de nombreux internautes justifie l’intérêt porté par les sociologues aux échanges qui s’y construisent. Par ailleurs, et contrairement à ce que l’on peut observer sur d’autre sites de réseaux sociaux en ligne, les liens entre individus sur Facebook sont proches de ceux hors-lignes. Dans un premier temps, la thèse s’évertue à démêler les multiples facettes de ce à quoi ”être sur Facebook” correspond. Distribués autour de pratiques normatives fabulées, les usages de nos enquêtés fluctuent au gré de leur appropriation ou non des composantes de l’importante variété de moyens de communication proposés par la plateforme. Ces usages, comme on le verra, sont ainsi différemment adoptés selon les catégories socioprofessionnelles et influent par ailleurs sur les modalités d’échanges et d’interactions des enquêtés avec leurs amis en ligne. Ces modalités sont également explorées dans ce travail, tout comme le rôle du conjoint et sa place dans la structure relationnelle. La seconde partie de la thèse se propose de construire une typologie de ces structures relationnelles dites égocentrées, c’est-à-dire depuis le point de vue de l’enquêté. Cette typologie des réseaux de sociabilité en ligne se base sur l’énumération de leurs sous-graphes induits, les graphlets, initialement développée par des chercheurs en bioinformatique. Cette approche offre une vision méso (entre micro et macro) des réseaux, propice à souligner des phénomènes inédits de sociologie des réseaux. A fort potentiel pluri-disciplinaire, la méthodologie graphlets elle même est également discutée et exploréeWith 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
30
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.
Анотація:
Les travaux présentés dans la thèse s'inscrivent dans le cadre de l'analyse des graphes de terrain (complex networks) et plus précisément de la tâche de détection de communautés, c'est-à-dire la reconnaissance algorithmique de sous-graphes particulièrement denses. Nous nous intéressons spécifiquement à l'implémentation d'une telle méthode dans un contexte fortement décentralisé et distribué : des réseaux MANET opportunistes formés par de petits objets connectés communiquant en pair-à-pair. Afin de tenir compte des contraintes d'exécution d'algorithme dans de tels réseaux, les travaux présentés dans la thèse proposent des méthodes conçues selon le paradigme récent et actif nommé orienté sommet, en alliant le traitement de graphes Think-Like-a-Vertex aux méthodes de détection de communautés basées sur des leaders ou des graines : celles-ci présentent en effet des propriétés de décentralisation qui autorisent des implémentations parallèles et distribuées appropriées au cadre applicatif considéré. Dans ce contexte, nous proposons d'une part un principe global de fonctionnement original que nous mettons en oeuvre et déclinons dans trois algorithmes dédiés à trois configurations différentes de la tâche de détection de communautés : l'algorithme VOLCAN considère le cas de référence des communautés disjointes dans un graphe statique. Nous l'étendons ensuite avec l'algorithme LOCNeSs au cas des communautés recouvrantes, qui autorisent un sommet à appartenir à plusieurs communautés simultanément : cette généralisation donne plus de flexibilité à la détection et la rend plus appropriée au cadre applicatif considéré. Nous examinons également le cas des graphes dynamiques, c'est-à-dire dont les sommets et les arêtes évoluent au cours du temps, auquel est consacré l'algorithme DynLOCNeSs. Chacun des algorithmes est associé à une implémentation décentralisée et fait l'objet d'une étude théorique ainsi qu'expérimentale sur des données artificielles et réelles permettant d'évaluer la qualité des résultats fournis et de les comparer aux méthodes de l'état de l'art. Nous considérons également, dans un cas particulier de réseau mobile ad-hoc spontané et décentralisé issu d'une application réelle de vêtements intelligents et communicants, une tâche de cheminement permettant d'identifier des interlocuteurs. Nous proposons une stratégie de recommandation utilisant la structure communautaire, modélisée et évaluée à travers un algorithme nommé SWAGGOur research is in the field of complex network analysis and mining, specifically addressing the communit detection task, ie. algorithms aiming to uncover particularly dense subgraphs. We focus on the implementation of such an algorithm in a decentralised and distributed context : opportunistic MANET constituted of small wireless devices using peer-to-peer communication. To tackle the implementation constraints in such networks, we propose several methods designed according to the novel and trending vertex-centred paradigm, by combining Think-Like-a-Vertex graph processing with vertex-centred community detection methods based on leaders or seeds : they show specific properties allowing dsitributed implementations suiting the opportunistic MANET case. In this context, we first a global working principle and implement it in three different algorithms dedicated to three different configurations of community detection : the VOLCAN algorithm manages the classical disjoint community detection task in a static graph. We extend it with the LOCNeSs algorithm, that is dealing with overlapping communities which means that one vertex can belong to several communities. It adds more flexibility to the method and more significance to produced results. We also tackle the dynamic graphe case (graph evolving over time), addressed by the DynLOCNeSs algorithm.Each algorithm comes with a decentralised implementation and theoretical as well as experimental studies conducted both on real and synthetic benchmark data, allowing to evaluate the quality of the results and compare to existing state-of-the-art methods. Finally, we consider a special case of opportunistic decentralised MANET developped as a part of a research project about smart and communicating clothing. We formalise a task of path finding between smart t-shirts holders and propose a recommandation strategy using community structure, that we model and evaluate through an algorithm named SWAGG
31
Creusefond, Jean. "Caractériser et détecter les communautés dans les réseaux sociaux." Thesis, Normandie, 2017. http://www.theses.fr/2017NORMC203/document.
Анотація:
Dans cette thèse, je commence par présenter une nouvelle caractérisation des communautés à partir d'un réseau de messages inscrits dans le temps. Je montre que la structure de ce réseau a un lien avec les communautés : on trouve majoritairement des échanges d'information à l'intérieur des communautés tandis que les frontières servent à la diffusion.Je propose ensuite d'évaluer les communautés par la vitesse de propagation des communications qui s'y déroulent avec une nouvelle fonction de qualité : la compacité. J'y présente aussi un algorithme de détection de communautés, le Lex-Clustering, basé sur un algorithme de parcours de graphe qui reproduit des caractéristiques des modèles de diffusion d'information. Enfin, je présente une méthodologie permettant de faire le lien entre les fonctions de qualité et les vérités de terrain. J'introduis le concept de contexte, des ensembles de vérités de terrain qui présentente des ressemblances. Je mets à disposition un logiciel nommé CoDACom (Community Detection Algorithm Comparator, codacom.greyc.fr) permettant d'appliquer cette méthodologie ainsi que d'utiliser un grand nombre d'outils de détection de communautésN 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
32
Retoré, Christian. "Réseaux et séquents ordonnés." Phd thesis, Université Paris-Diderot - Paris VII, 1993. http://tel.archives-ouvertes.fr/tel-00585634.
Анотація:
Cette thèse présente un calcul des séquents pour la logique linéaire enrichie d'un connecteur non commutatif et autodual "précède" situé entre le "par" et le "tenseur". Il est défini pour des séquents dont les formules sont orientées par un ordre partiel. Un calcul de réseaux de démonstration quotientant ce calcul des séquents est défini en termes de graphes orientés. Ce calcul est doté d'une sémantique dénotationnelle dans les espaces cohérents, préservée par élimination des coupures, un processus convergent et confluent. Des résultats combinatoires nécessaires sur les ordres partiels et sur la structure des graphes de démonstrations sont établies ainsi que quelques propriétés du calcul commutatif avec la règle MIX.
33
Canu, Maël. "Détection de communautés orientée sommet pour des réseaux mobiles opportunistes sociaux." Thesis, Paris 6, 2017. http://www.theses.fr/2017PA066378/document.
Анотація:
Les travaux présentés dans la thèse s'inscrivent dans le cadre de l'analyse des graphes de terrain (complex networks) et plus précisément de la tâche de détection de communautés, c'est-à-dire la reconnaissance algorithmique de sous-graphes particulièrement denses. Nous nous intéressons spécifiquement à l'implémentation d'une telle méthode dans un contexte fortement décentralisé et distribué : des réseaux MANET opportunistes formés par de petits objets connectés communiquant en pair-à-pair. Afin de tenir compte des contraintes d'exécution d'algorithme dans de tels réseaux, les travaux présentés dans la thèse proposent des méthodes conçues selon le paradigme récent et actif nommé orienté sommet, en alliant le traitement de graphes Think-Like-a-Vertex aux méthodes de détection de communautés basées sur des leaders ou des graines : celles-ci présentent en effet des propriétés de décentralisation qui autorisent des implémentations parallèles et distribuées appropriées au cadre applicatif considéré. Dans ce contexte, nous proposons d'une part un principe global de fonctionnement original que nous mettons en oeuvre et déclinons dans trois algorithmes dédiés à trois configurations différentes de la tâche de détection de communautés : l'algorithme VOLCAN considère le cas de référence des communautés disjointes dans un graphe statique. Nous l'étendons ensuite avec l'algorithme LOCNeSs au cas des communautés recouvrantes, qui autorisent un sommet à appartenir à plusieurs communautés simultanément : cette généralisation donne plus de flexibilité à la détection et la rend plus appropriée au cadre applicatif considéré. Nous examinons également le cas des graphes dynamiques, c'est-à-dire dont les sommets et les arêtes évoluent au cours du temps, auquel est consacré l'algorithme DynLOCNeSs. Chacun des algorithmes est associé à une implémentation décentralisée et fait l'objet d'une étude théorique ainsi qu'expérimentale sur des données artificielles et réelles permettant d'évaluer la qualité des résultats fournis et de les comparer aux méthodes de l'état de l'art. Nous considérons également, dans un cas particulier de réseau mobile ad-hoc spontané et décentralisé issu d'une application réelle de vêtements intelligents et communicants, une tâche de cheminement permettant d'identifier des interlocuteurs. Nous proposons une stratégie de recommandation utilisant la structure communautaire, modélisée et évaluée à travers un algorithme nommé SWAGGOur research is in the field of complex network analysis and mining, specifically addressing the communit detection task, ie. algorithms aiming to uncover particularly dense subgraphs. We focus on the implementation of such an algorithm in a decentralised and distributed context : opportunistic MANET constituted of small wireless devices using peer-to-peer communication. To tackle the implementation constraints in such networks, we propose several methods designed according to the novel and trending vertex-centred paradigm, by combining Think-Like-a-Vertex graph processing with vertex-centred community detection methods based on leaders or seeds : they show specific properties allowing dsitributed implementations suiting the opportunistic MANET case. In this context, we first a global working principle and implement it in three different algorithms dedicated to three different configurations of community detection : the VOLCAN algorithm manages the classical disjoint community detection task in a static graph. We extend it with the LOCNeSs algorithm, that is dealing with overlapping communities which means that one vertex can belong to several communities. It adds more flexibility to the method and more significance to produced results. We also tackle the dynamic graphe case (graph evolving over time), addressed by the DynLOCNeSs algorithm.Each algorithm comes with a decentralised implementation and theoretical as well as experimental studies conducted both on real and synthetic benchmark data, allowing to evaluate the quality of the results and compare to existing state-of-the-art methods. Finally, we consider a special case of opportunistic decentralised MANET developped as a part of a research project about smart and communicating clothing. We formalise a task of path finding between smart t-shirts holders and propose a recommandation strategy using community structure, that we model and evaluate through an algorithm named SWAGG
34
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.
Анотація:
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 domaineThe 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
35
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.
Анотація:
Il existe dans le monde réel un nombre important de réseaux qui apparaissent naturellement, on les retrouve un peu partout, dans de nombreuses disciplines, par exemple en informatique avec les réseaux de routeurs, les réseaux de satellites, les réseaux de pages Web, en biologie avec les réseaux des neurones, en écologie avec les réseaux d’interactions biologiques, en linguistiques avec les réseaux de synonymes, en droit avec les réseaux de décisions juridiques, en économie avec les réseaux interbancaires, en sciences humaines avec les réseaux sociaux. De manière générale, un réseau reflète les interactions entre les nombreuses entités d’un système. Ces interactions peuvent être de différentes natures, un lien social ou un lien d’amitié dans un réseau social constitué de personnes, un câble dans un réseau de routeurs, une réaction chimique dans un réseau biologique de protéines, un hyperlien dans un réseau de pages Web, etc. Plus encore, la rapide démocratisation du numérique dans nos sociétés, avec Internet notamment, a pour conséquence de produire de nouveaux systèmes qui peuvent être représentés sous forme de réseaux. Finalement, tous ces réseaux présentent des particularités bien spécifiques : ils sont issus de contextes pratiques, ils sont le plus souvent de grande taille (on retrouve quelques fois des réseaux constitués de plusieurs milliards de nœuds et de liens, contenant donc une grande quantité d’information), ils présentent des propriétés statistiques communes. À cet égard, ils sont regroupés sous l’appellation de réseaux réels, graphes de terrain ou encore réseaux complexes. Aujourd'hui, la science des réseaux est un domaine de recherche à part entière dont l’enjeu principal est de parvenir à décrire et modéliser ces réseaux avec précision afin de révéler leurs caractéristiques générales et de mieux comprendre leurs mécanismes. La plupart des travaux dans ce domaine utilisent le formalisme des graphes qui fournit un ensemble d’outils mathématiques particulièrement adaptés à l’analyse topologique et structurelle des réseaux. Il existe de nombreuses applications dans ce domaine, par exemple des applications concernant la propagation d’épidémie ou de virus informatique, la fragilité du réseau en cas de panne, sa résilience en cas d’attaque, l’étude de la dynamique pour prédire l’apparition de nouveaux liens, la recommandation, etc. L’un des problèmes complexes actuels, qui a beaucoup d’applications, est l’identification de la structure communautaire. La grande majorité des réseaux réels sont caractérisés par des niveaux d’organisation dans leur structure mésoscopique. Du fait de la faible densité globale des réseaux réels couplée à la forte densité locale, on observe la présence de groupes de nœuds fortement liés entre eux et plus faiblement liés avec le reste du réseau, que l’on appelle communautés. Ces structures ont également du sens dans le réseau lui-même, par exemple les communautés d’un réseau social peuvent correspondre à des groupes sociaux (amis, familles, etc.), les communautés d’un réseau de protéines peuvent traduire des réponses fonctionnelles, elles peuvent correspondre à des sujets similaires dans un réseau de pages Web, pour donner quelques exemples [...]In 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 [...]
36
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.
37
Rifi, 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.
Анотація:
Ce travail propose une modélisation adéquate en graphes pour les systèmes et séquences accidentelles de sûreté nucléaire. Ces systèmes et séquences proviennent des "Etudes Probabilistes de Sûreté" (EPS) qui consistent à analyser de façon exhaustive tous les scénarios accidentels envisageables, d’estimer leurs probabilités d’occurrence (en les regroupant par famille) et les conséquences associées.Ensuite une analyse des réseaux complexes résultants est effectuée par des mesures de centralités.Une première application consiste à la prédiction du Facteur d’Accroissement du Risque nucléaire en utilisant les algorithmes d’apprentissages supervisé : méthodes à base d’arbre de classification, régression logistique et méthodes ensemblistes, sur des données déséquilibrées.Par ailleurs, un nouveau coefficient synthétique de centralité et une mesure de similarité sont conçus pour comparer les structures de réseaux, indépendamment de leurs caractéristiques topologiques, en se basant sur les interdépendances entre leurs vecteurs de centralités.Cette nouvelle approche utilise des techniques statistiques (échantillonnage, corrélation ethomogénéité).La pertinence et l’efficacité de cette nouvelle mesure de similarité sont validées sur le clustering de graphes théoriques classiques et la prédiction du type de graphes. Enfin, une application de cette approche est réalisée pour le clustering des réseaux complexes des systèmes de sûreté nucléaireThis 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
38
Fertin, Guillaume. "Etude des communications dans les réseaux d'interconnexion." Bordeaux 1, 1999. http://www.theses.fr/1999BOR10535.
Анотація:
De nos jours, les reseaux jouent un role de plus en plus important. On les retrouve dans la telephonie mobile (reseaux terrestres ou constellation de satellites), dans l'internet, dans les machines paralleles (reseaux de processeurs), etc. Chaque unite composant ces reseaux possede une certaine information, et, en cours d'utilisation, ces informations doivent etre communiquees : principalement, ces communications sont la diffusion (ou one-to-all), l'echange total (ou all-to-all), et le multicast (ou one-to-many). L'objet de cette these est d'etudier la diffusion et l'echange total dans ces reseaux. Plus precisement, nous passons en revue un certain nombre de modeles (full-duplex, simplex, temps constant, temps lineaire, etc. ), et, pour chacun d'entre eux, nous realisons une etude sur deux aspects fondamentaux mesurant l'efficacite des ces reseaux : le temps de communication dans un reseau compose de n unites et entierement connecte ; et le nombre minimum de liens effectivement utilises par le reseau pour communiquer en temps minimum. Dans certains modeles ou le temps de communication n'est pas connu precisement, nous ameliorons cette connaissance (echange total simplex), ou determinons avec exactitude ce temps (echange total full-duplex temps lineaire). Dans l'echange total full-duplex temps lineaire, nous etudions egalement les compromis possibles entre nombre d'etapes et nombre de pas. Nous determinons avec exactitude le nombre minimum de liens dans un reseau a n entites pour certaines valeurs infinies de n (diffusion simplex pour tout n = 2#k 1 et n = 2#k 2). De plus, nous presentons une methode efficace de composition de graphes permettant d'obtenir des bornes superieures sur le nombre minimum de liens (echange total full-duplex temps constant et temps lineaire). Enfin, nous obtenons divers resultats exacts pour quelques valeurs particulieres de n. Dans un deuxieme temps, nous exhibons une famille de graphes possedant de bonnes proprietes en terme de diffusion et d'echange total, dans quasiment tous les modeles etudies. Ces graphes sont appeles graphes de knodel, et sont etudies extensivement dans ce memoire.
39
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.
Анотація:
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'architectureExtracting 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
40
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.
Анотація:
Nous avons étudié dans un premier temps quelques problèmes fondamentaux sur les réseaux point à point basés sur les graphes de Cayley. La complexité de certains problèmes de formulation simple n'a pas encore été trouvée pour certaines machines parallèles. Par exemple, on ne connaît pas actuellement la complexité du tri sur un hyper cube. Nous avons présenté divers algorithmes autour de la sélection sur les réseaux hyper cubiques en utilisant les algorithmes de tri les plus rapides actuellement connus. Nous avons aussi défini certaines décompositions des graphes de Cayley qui permettent de décrire des algorithmes de communication générale simples et efficaces, comme la diffusion et le commérage pour le star-graph. Dans un second temps, nous avons étudié les réseaux basés sur des interconnexions optiques. Le problème des machines parallèles de réseau d'interconnexion point -à -point provient de la faiblesse des communications générales qui sont souvent sollicitées dans la plupart des programmes scientifiques actuels. Les interconnexions optiques permettent de créer des réseaux plus denses avec des débits plus importants que les technologies classiques. Dans ce type de réseau, nous avons reconsidéré diverses problématiques du parallélisme. Nous avons regardé le comportement de quelques opérations de communication générale, comme la diffusion. Nous avons d'autre part donné les propriétés d'extensibilité de ces réseaux
41
Chelly, 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.
Анотація:
Les systèmes de positionnement ont connu un progrès indéniable. Actuellement, la précision atteint quelques centimètres sous certaines conditions : espace ouvert, ciel dégagé, technique très spécifique, etc. Néanmoins, le problème du positionnement dans un environnement intérieur demeure persistant : les trajets multiples qui compliquent les modèles de propagation, l'atténuation, etc. Différents systèmes ont vu le jour, utilisant des technologies telles que l'UWB, le WiFi ou l'Infrarouge. Ces systèmes apportent des résultats de positionnement intéressants, atteignant l'ordre du mètre. Cette précision reste liée à certaines contraintes : une infrastructure, une technologie utilisée, une calibration, une technique de calcul, etc. Afin de réduire toutes ces contraintes, nous proposons une nouvelle approche de positionnement. Notre approche utilise tous les équipements réseaux présents dans un environnement. Elle se base sur deux étapes fondamentales : l'étude de visibilité et l'élaboration de liens géographiques. L'étude de visibilité permet d'obtenir les équipements visibles par un équipement. Nous avons exposé plusieurs modèles de visibilité et nous avons effectué une comparaison des résultats. L'élaboration de liens géographiques permet de construire un graphe géographique tridimensionnel reliant tous les équipements de l'environnement. Ce graphe nous permet de visualiser la répartition des équipements et d'estimer les positions géographiques de chaque équipement. Pour la mise en œuvre de notre approche, nous avons développé un simulateur sous Matlab. Le simulateur élaboré évalue d'abord le nombre d'équipements visibles. Il estime les distances séparant cet équipement de chaque équipement visible. Enfin, il construit un graphe géographique et calcul les positions géographiques. Des résultats de simulations sont présentés pour valider notre approche qui permet d'aboutir à un système capable d'opérer, sans aucune infrastructure additionnelle, un positionnement dans un environnement intérieur et extérieurPositioning 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
42
Reyes, Valenzuela Patricio Alejandro. "Collecte d'information dans les réseaux radio." Nice, 2009. http://www.theses.fr/2009NICE4069.
Анотація:
Cette thèse concerne l’étude de l’algorithmique et de la complexité des communications radio. En particulier, nous nous sommes intéressés au problème de rassembler les informations des sommets d’un réseau radio en nœud central. Ce problème est motivé par une question de France Telecom (Orange Labs) : « comment amener Internet dans les villages ». Les sommets représentent les maisons des villages qui communiquent entre elles par radio, le but étant d’atteindre une passerelle connectée à Internet par une liaison satellite. Le même problème se rencontre dans les réseaux de senseurs où il s’agit de collecter les informations des senseurs dans une station de base. Une particularité des réseaux radio est que la distance de transmission est limitée et que les transmissions interfèrent entre elles (phénomènes d’interférences). Nous modélisons ces contraintes en disant que deux sommets (équipements radio) peuvent communiquer s’ils sont à distance au plus dT et qu’un nœud interfère avec un autre si leur distance est au plus dI. Les distances sont considérées dans un graphe représentant le réseau. Une étape de communication consistera donc en un ensemble de transmissions compatibles (n’interférant pas). Notre objectif est de trouver le nombre minimum d’étapes nécessaires pour réaliser un tel rassemblement et de concevoir des algorithmes réalisant ce minimum. Pour des topologies particulières comme le chemin et la grille, nous avons établi des résultats optimaux ou quasi optimaux. Nous avons aussi considéré le cas systolique (ou continu) où on veut maximiser le débit offert à chaque nœudThis 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
43
Hagenbach, Jeanne. "Communication stratégique et réseaux." Phd thesis, Université Panthéon-Sorbonne - Paris I, 2009. http://tel.archives-ouvertes.fr/tel-00450632.
Анотація:
Depuis une dizaine d'années, l'étude des réseaux est une branche très active de la recherche en économie. Il est désormais largement admis que ceux-ci jouent un rôle central dans la transmission décentralisée des informations entre les individus. Les informations communiquées par ces derniers concernent aussi bien les opportunités d'emplois que l'état du marché dans lequel une équipe de travailleurs évolue. Cette thèse propose une nouvelle approche du lien entre la manière dont les agents transmettent stratégiquement leurs informations privées et la structure du réseau dont ils font partie. La théorie des jeux non coopérative a été appliquée à l'étude des réseaux sociaux et économiques dans les deux branches suivantes: d'une part, les Jeux en Réseaux considèrent que les joueurs sont les membres d'un réseau donné et analysent la manière dont les comportements stratégiques et les résultats économiques sont influencés par l'architecture de ce réseau ; d'autre part, les Jeux de Formation de Réseaux modélisent la construction stratégique des connections entre les individus. Ce travail apporte une contribution µa ces deux domaines de recherche. Dans la première partie de ma thèse, que forme le Chapitre 1 intitulé Centralisation des Informations dans les Réseaux, les joueurs appartiennent à un réseau qui affectent leur manière de transmettre leurs informations. Dans la seconde partie, constituée des Chapitres 2 et 3 et intitulée Réseaux de Communication Stratégique, la structure des liens entre les agents découle de leur communication stratégique.
44
Pigné, 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.
Анотація:
Les graphes dynamiques sont un outil de plus en plus utilisé dans des contextes variés où il s'avère nécessaire de modéliser des environnements changeants ou incertains. Les modèles aujourd'hui proposés sont dédiés à ces applications précises. Il n'existe pas de modèle général reprenant, hors de tout contexte applicatif, ces caractéristiques. D'autre part la résolution de problèmes liés à ces environnements dynamiques et incertains est problématique. Nous proposons, ici, la formalisation d'un modèle général de graphe dynamique. Nous é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é.
45
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.
Анотація:
Ce travail étudie des propriétés topologiques des graphes et leurs applications aux réseaux de communications, notamment aux graphes représentant structure d'Internet. Dans un premier temps, on s'intéresse à l'arborescence des graphes par l'étude de deux paramètres : l'hyperbolicité et la largeur arborescente (treewidth). Pour l' hyperbolicité, on analyse sa relation avec d'autres paramètres de graphes et on montre que certaines décompositions de graphes en permettent un calcul efficace. On calcule ces deux paramètres dans des instantanés d'Internet pour différents niveaux hiérarchiques et différentes périodes de temps. On y apporte des interprétations structurelles et algorithmiques pour les valeurs obtenues. On aborde ensuite le problème de partitionnement de graphes (clustering) sous l'angle de la modularité, paramètre qui mesure la qualité d'un partitionnement, largement utilisé dans la littérature. On analyse la modularité du point de vue théorique et son comportement asymptotique pour certaines familles de graphes. Enfin, on s'intéresse à une approche comminatoire de la théorie des files d'attente où les injections de paquets sont effectuées par un adversaire. On propose une généralisation de ce modèle par l'introduction de différentes classes de requêtesThis 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
46
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.
Анотація:
Le modèle utilisé classiquement pour les réseaux mobiles cellulaires est le maillage hexagonal. Nous présentons ici un modèle plus réaliste basé sur le diagramme de Voronoi͏̈ et la triangulation de Delaunay. La taille des cellules dans le réseau mobile cellulaire de Voronoi͏̈ est déterminée par deux facteurs de base : la position géographique des stations de base et de leur zone de couverture. Ce réseau mobile cellulaire peut être vu comme un graphe planaire triangulaire où les triangles ne sont pas réguliers. Soit le diamètre de ce réseau avec n stations de base. Nous montrons dans cet article que le diamètre moyen du réseau mobile cellulaire basé sur les cellules de Voronoi͏̈, , vérifie la relation suivante :
47
Montassier, 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.
Анотація:
Dans ce mémoire, nous nous intéressons à deux notions de coloration sous contraintes -- coloration acyclique par listes et coloration (d,1)-totale -- ainsi qu'à un problème de conception de réseaux embarqués tolérants aux pannes. Les notions de coloration acyclique par listes et de coloration (d,1)-totale sont des notions récentes (2002). Nous apportons de nouveaux résultats concernant le calcul du nombre chromatique acyclique de listes et du nombre (d,1)-total de certaines familles de graphes (graphes de degré borné, graphes de degré moyen maximum donné,. . . ) ainsi que de nouvelles perspectives de recherche. La fiabilité des réseaux embarqués dans les satellites de télécommunication, maillons essentiels dans la chaîne de la diffusion d'information, est un enjeu important. Comment concevoir des réseaux embarqués à faible coût capables de tolérer un certain nombre de pannes et de continuer à propager l'information ? Nous donnons des éléments de réponse à cette problématique posée par Alcatel Space Industries en présentant des réseaux de coût minimal supportant un nombre de pannes donné.
48
Tabourier, Lionel. "Méthode de comparaison des topologies de graphes complexes : applications aux réseaux sociaux." Paris 6, 2010. http://www.theses.fr/2010PA066335.
Анотація:
Les graphes des réseaux d'interactions sociales révèlent des propriétés topologiques dont nous cherchons à comprendre l'origine. Dans ce but nous manquons de références qui permettraient de construire une échelle de comparaison de leurs caractéristiques géométriques. Cette thèse propose une méthode générique pour produire des graphes synthétiques dont les propriétés sont ajustables, dans l'ambition de réaliser un balisage de l'espace des graphes. La méthode proposée dérive de procédures markoviennes dont l'étape élémentaire consiste à échanger les extrêmités de liens du graphe. Selon les contraintes imposées, une telle procédure doit être adaptée; nous discutons alors des difficultés inhérentes à sa réalisation pratique et les moyens à notre disposition pour estimer sa validité. Puis nous rendons compte d'applications pratiques sur des réseaux technologiques, de collaborations, ou d'échanges commerciaux. Le principe mis en oeuvre dans ces illustrations consiste à construire une suite d'ensembles de graphes obéissant à des contraintes de plus en plus exigeantes; puis à comparer les propriétés de chacun aux données réelles afin de déterminer quels éléments topologiques ont un rôle essentiel. Au fil des exemples, nous proposons des améliorations techniques de nos algorithmes qui permettraient d'en élargir les utilisations possibles. Cette méthode serait suffisamment générale pour pouvoir décrire des réseaux d'interactions d'une autre nature, mais aussi pour intégrer des informations supplémentaires à la description graphique telles que l'activité temporelle des agents; nous proposons pour conclure quelques éléments de réflexion pour réaliser ces objectifs.
49
Canales, 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.
Анотація:
On présente ici une nouvelle approche de simulation pour les graphes d'événements stochastiques, qui est particulièrement appropriée pour une implémentation sur une architecture SIMD. Cette approche est fondée sur des équations de récurrence, linéaires dans (R, max, +), récemment établies pour ce type de système. Trois variantes sont présentées : la variante temporelle, la variante spatiale et la variante par niveaux. La variante temporelle, qui généralise pour les réseaux de Petri une méthode introduite pour des files d'attente, est appropriée pour la simulation de petits systèmes pendant des intervalles longs. La variante spatiale permet la simulation de réseaux plus grands et le calcul simple des statistiques du processus de marquage. La variante par niveaux permet la simulation de systèmes encore plus grands, mais avec l'utilisation de plus de mémoire par processeur. On étudie la complexité parallèle théorique des algorithmes associes à chaque variante. Quelques exemples d'intérêt pratique sont présentés (réseaux de files d'attente avec blocage, un modèle d'atelier stochastique) pour lesquels le cout de simulation de o(nt) événements d'un réseau de taille T, est de O(N log T) avec la variante spatiale. Avec une méthode traditionnelle, le coût de simulation du même système est d'au moins O(NT). Ces considérations théoriques ont été confirmées par un prototype qui implémente la nouvelle approche sur une Connection Machine-2A 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
50
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.
Анотація:
Les réseaux sont présents dans pratiquement tous les aspects de la vie. Le monde quinous entoure comporte énormément de réseaux. Par exemple, les réseaux de communicationconstitués de téléphones, les réseaux électriques, les réseaux d'ordinateurs, le réseaudes lignes aériennes, ... etc, sont autant de réseaux importants dans la vie de chaque jour.Le cadre mathématique des réseaux est bien approprié pour décrire plusieurs systèmescomposés d'un grand nombre d'entités qui interagissent entre elles. Chaque entité est représentéepar un noeud du réseau et chaque interaction par un lien entre deux noeuds. Ilest donc possible de modéliser ces réseaux par des graphes. Pour la plupart de ces réseaux,la difficulté provient principalement du grand nombre d'entités, ainsi que de la façon dontelles sont interconnectées. Une approche naturelle pour simplifier de tels systèmes consistedonc à réduire leur taille. Cette simplification n'est pas faite aléatoirement, mais de tellefaçon à ce que les noeuds de la même composante aient plus de liens entre eux qu'avec lesautres composantes. Ces groupes de noeuds ou composantes sont appelés communautésd'intérêt. Notre thèse se positionne dans le domaine de l'étude des graphes sociaux. Elle s'intéresseprincipalement à l'étude de la robustesse des structures sociales émergentes dansles réseaux d'interactions. L'aspect de la robustesse des réseaux constitue un challengetrès important pour comprendre leur fonctionnement, le comportement des entités lesconstituant et surtout pour comprendre les interactions qui peuvent se produire entreelles, permettant l'émergence de certains comportements qui n'étaient pas du tout prévisiblesau préalable. Actuellement, les études de la robustesse des réseaux qui existentdans la littérature traitent cet aspect du point de vue purement structurel, i.e. toutes lesperturbations sont appliquées soit sur les noeuds, soit sur les arêtes du graphe. Pour cequi est de notre étude, nous nous sommes intéressés à définir une nouvelle stratégie qui sebase sur des perturbations appliquées sur les paramètres qui permettent l'émergence desgraphes sociaux dans les réseaux d'interaction. Cette façon d'aborder l'aspect robustessedes graphes constitue une nouvelle manière d'évaluer et de quantifier les changements quipeuvent intervenir dans les structures de ces graphes.