11 |
Characterizing edges in signed and vector-valued graphs / Caractérisation des arêtes dans les graphes signés et attribuésLe Falher, Géraud 16 April 2018 (has links)
Nous proposons des méthodes pour caractériser efficacement les arêtes au sein de réseaux complexes. Dans les graphes simples, les nœuds sont liés par une sémantique unique, tels deux utilisateurs amis dans un réseau social. De plus, ces arêtes sont guidées par la similarité entre les nœuds (homophilie). Ainsi, les membres deviennent amis à cause de caractéristiques communes. En revanche, les réseaux complexes sont des graphes où chaque arête possède une sémantique parmi k possibles. Ces arêtes sont de plus basées à la fois sur une homophilie et une hétérophilie partielle. Cette information supplémentaire permet une analyse plus fine de graphes issus d’applications réelles. Cependant, elle peut être coûteuse à acquérir, ou même être indisponible. Nous abordons donc le problème d’inférer la sémantique des arêtes. Nous considérons d'abord les graphes dont les arêtes ont deux sémantiques opposées, et où seul une fraction des étiquettes est visibles. Ces «graphes signés» sont une façon élégante de représenter des interactions polarisées. Nous proposons deux biais d’apprentissage, adaptés respectivement aux graphes signés dirigés ou non, et plusieurs algorithmes utilisant la topologie du graphe pour résoudre un problème de classification binaire. Ensuite, nous traitons les graphes avec k > 2 sémantiques possibles. Dans ce cas, nous ne recevons pas d’étiquette d’arêtes, mais plutôt un vecteur de caractéristiques pour chaque nœud. Face à ce problème non supervisé, nous concevons un critère de qualité exprimant dans quelle mesure une k-partition des arêtes et k vecteurs sémantiques expliquent les arêtes observées. Nous optimisons ce critère sous forme vectorielle et matricielle. / We develop methods to efficiently and accurately characterize edges in complex networks. In simple graphs, nodes are connected by a single semantic. For instance, two users are friends in a social networks. Moreover, those connections are typically driven by node similarity, according to homophily. In the previous example, users become friends because of common features. By contrast, complex networks are graphs where every connection has one semantic among k possible ones. Those connections are moreover based on both partial homophily and heterophily of their endpoints. This additional information enable finer analysis of real world graphs. However, it can be expensive to acquire, or is sometimes not known beforehand. We address the problems of inferring edge semantics in various settings. First, we consider graphs where edges have two opposite semantics, and where we observe the label of some edges. These so-called signed graphs are a common way to represent polarized interactions. We propose two learning biases suited for directed and undirected signed graphs respectively. This leads us to design several algorithms leveraging the graph topology to solve a binary classification problem that we call edge sign prediction. Second, we consider graphs with k > 2 available semantics for edge. In that case of multilayer graphs, we are not provided with any edge label, but instead are given one feature vector for each node. Faced with such an unsupervised problem, we devise a quality criterion expressing how well an edge k-partition and k semantical vectors explains the observed connections. We optimize this goodness of explanation criterion in vectorial and matricial forms.
|
12 |
Un paradigme de programmation multi-niveaux pour le calcul numérique sur les machines post-petascales et exascales / A multi-level programming paradigm for numerical computing on post-petascale and exascale machinesHugues, Maxime 13 May 2011 (has links)
L'arrivée des supercalculateurs post-petascales and exascales offre la perspective d'accélérer la résolution des problèmes d'ingénierie et aux modélisations hautement complexes. Cependant, ces futurs systèmes posent des problèmes aux informaticiens pour construire de telles machines. De nombreux problèmes doivent être résolus comme la tolérance aux pannes, la consommation énergétique et la programmation de ces systèmes complexes composés de milliard de coeurs.Dans cette thèse, nous nous sommes concentrés sur l'aspect programmation et proposons un paradigme de programmation multi-niveaux composé de trois niveaux. Pour le bas niveau, un paradigme data parallèle est proposé pour programmer les processeurs à nombreux coeurs pour sa focalisation sur la distribution et le mouvement des données. Nous avons implémenté et évalué le produit matrice vecteur creux suivant différents formats de matrice creuse sur un GPU pour illustrer ce point. Pour le niveau intermédiaire, nous proposons un paradigme à passage de messages de manière à optimiser les communications inter-processeurs et inter-noeuds. Pour le haut niveau, un paradigme de description de graphe est proposé pour programmer et gérer le parallélisme entre les noeuds.Avec une méthode d'inversion matricielle dense développée en YML, nous soulignons l'intérêt des graphes pour la réduction du temps à la solution et pour le support des communications asynchrones de facon transparente. L'intérêt des graphes est également démontré pour les optimisations d'entrées/sorties et leur support dans un modèle de programmation. Nous concluons finalement en analysant une telle proposition de paradigme de programmation pour les machines exascale et présentons la direction des travaux futurs. / The coming of post-petscale and exascale supercomputers offers the perspective to accelerate the solving of engineering problems and to highly complex modeling. However, these future systems challenge computer scientists to built such machines. Many issues must be faced such as fault-tolerance, energy consumption and the programming of these complex systems composed of billion cores.In this thesis, we have focused on the programming aspect and propose a multi-level programming paradigm composed of three levels. For the low level, a data parallel paradigm is proposed to program many-cores processors for its focus on data mapping and movements. We have implemented and evaluated the SpMV with various sparse matrix formats on GPU to illustrate this point. For the intermediate level, we propose a message passing paradigm in order to optimize inter-sockets and inter-nodes communications. For the high level, a graph description paradigm is proposed to program and manage the parallelism between nodes.With a dense matrix inversion method developed in YML, we underline the interest of graph for the Time-To-Solution reduction and for the support of asynchronous communications in a transparent way. The interest of graph is also demonstrated for I/O optimizations and for their direct support into the programming model. We finally conclude by analyzing a such proposition of programming paradigm for exascale machines and outlines the future work direction.
|
13 |
Système d'argumentation pour la collaboration en télémédecine / Argumentation Framework for Collaboration In TelemedicineDoumbouya, Mamadou Bilo 08 December 2016 (has links)
La télémédecine consiste en la pratique d’actes médicaux à distance par l’usage des nouvelles technologies de l’information et de la communication. Parmi ces actes médicaux, nous nous sommes intéressés à la téléexpertise qui est une sorte d’activité collaborative consistant aux recueils d’avis d’experts médicaux face à un problème de santé donné. Dans notre travail, nous avons fait le choix de modéliser ces activités collaboratives par le système d’argumentation de Dung basé sur des fondements mathématiques et qui permet d’illustrer les interactions entre les différentes parties prenantes et par la même occasion fournir des outils mathématiques de prises de décisions. Nous avons opté pour une modélisation sémantique avec des graphes conceptuels car l’un de nos objectifs est de garantir une interopérabilité sémantique. Cette modélisation peut inclure souvent des incohérences (mauvaises relations d’attaques dans le système d’argumentation) qui seront vérifiées par l’usage des contraintes en graphes conceptuels. Pour résoudre ces problèmes d’incohérences deux solutions majeures ont été proposées : (i) la pondération des arguments des différents professionnels de santé, (ii) la modélisation de quelques aspects de droit médical comme contraintes. Ce travail démontre une application informatique du raisonnement logique dans un cadre médical judiciaire où il apporte des éclairages sur la vérification d’information, l’argumentation et l’interaction. Il vise ainsi à garantir une bonne collaboration dans le but de se prémunir d’éventuelles conséquences financières et juridiques. / Telemedicine involves the practice of medical procedures remotely through the use of new information and communications technology. Among these medical procedures, we looked at the tele-expertise which is a kind of collaborative activity consisting of collecting the opinions of medical experts facing a particular health problem. In our work, we have chosen to model these collaborative activities by Dung argumentation system based on mathematical foundations and illustrates the interactions between the different stakeholders and at the same time provides mathematical tools decisions. We opted for a semantic modeling with conceptual graphs as one of our objectives is to ensure semantic interoperability. This modeling can often include inconsistencies (poor relations of attacks in argumentation system) which will be verified by the use of constraints in conceptual graphs. To solve these inconsistency problems, two major solutions have been proposed : (i) the weight of the arguments of different health professionals, (ii) modeling some aspects of medical law as constraints. This work demonstrates a computer application of logical reasoning in a judicial medical setting where it sheds light on the verification of information, argumentation and interaction. It aims to ensure good cooperation in order to guard against possible financial and legal consequences.
|
14 |
Propagation Analysis based on Software Graphs and Synthetic Data / Analyse de la propagation basée sur les graphes logiciels et les données synthétiquesMusco, Vincenzo 03 November 2016 (has links)
Les programmes sont partout dans notre vie quotidienne : les ordinateurs et les téléphones, mais aussi les frigo, les avions et ainsi de suite. L'acteur principal dans la création de ces programmes est humain les êtres. Aussi minutie qu'ils peuvent être, les humains sont connus pour faire des erreurs involontaires sans leur conscience. Ainsi, une fois une phase déjà difficile d'écriture d'un programme, ils doivent faire face à la phase de maintenance sur laquelle ils doivent faire face aux erreurs qu'ils ont eu précédemment réalisé. Toute la durée de leur tâche de développement, les développeurs doivent faire face continuellement leurs erreurs (ou leurs collègues). Cette observation clé soulève la nécessité d'aider les développeurs dans leurs tâches de développement / maintenance. / Programs are everywhere in our daily life: computers and phones but also fridges, planes and so on. The main actor in the process of creating these programs is human beings. As thorough as they can be, humans are known to make involuntary errors without their awareness. Thus, once finished an already hard phase of writing a program. they have to face the maintenance phase on which they have to deal with errors they had previously made. All long their development task, developers have to continuously face their (or their colleagues) errors. This key observation arises the need of aiding developers in their development/maintenance tasks.
|
15 |
Représentations dynamiques de graphesCrespelle, Christophe 28 September 2007 (has links) (PDF)
Ce travail de thèse traite du maintien dynamique de représentations géométriques de graphes. Le manuscrit met en avant des connexions fortes entre trois types de représentation de graphes : les décompositions de graphes, les modèles géométriques et les représentations arborescentes à degrés de liberté (PQ-arbres, PC-arbres et autres structures du même type). De nouvelles relations entre ces objets sont mises en évidence et d'autres déjà connues sont approfondies. Notamment, il est établi une équivalence mathématique et algorithmique entre la décomposition modulaire des graphes d'intervalles et le PQ-arbre de leurs cliques maximales.<br /><br />Les connexions entre les trois types de représentation précités sont exploitées pour la conception d'algorithmes de reconnaissance entièrement dynamiques pour les cographes orientés, les graphes de permutation et les graphes d'intervalles. Pour les cographes orientés, l'algorithme présenté est de complexité optimale, il traite les modifications de sommet en temps O(d), où d est le degré du sommet en question, et les modifications d'arête en temps constant. Les algorithmes pour les graphes de permutation et les graphes d'intervalles ont la même complexité : les modifications d'arête et de sommet sont traitées en temps O(n), où n est le nombre de sommets du graphe. Une des contributions du mémoire est de mettre en lumière des similarités très fortes entre les opérations d'ajout d'un sommet dans un graphe de permutation et dans un graphe d'intervalles. <br />L'approche mise en oeuvre dans ce mémoire est assez générale pour laisser entrevoir les mêmes possibilités algorithmiques pour d'autres classes de graphes définies géométriquement.
|
16 |
Static and dynamic graph partitioning : a comparative study of existing algorithms /Elsner, Ulrich. January 1900 (has links)
Diss.--Mathematik--Chemnitz--Technischen universität, 2002.
|
17 |
Décompositions de graphes et algorithmes efficacesRao, Michaël Kratsch, Dieter. January 2006 (has links) (PDF)
Thèse de doctorat : Informatique : Metz : 2006. / Thèse soutenue sur ensemble de travaux. Bibliogr. p. [131]-138. Index p. [125]. Liste des symboles p.[129]-130.
|
18 |
Méthodes algébriques dans l'analyse spectrale d'opérateurs sur les graphes et les variétésGolenia, Sylvain Georgescu, Vladimir January 2007 (has links) (PDF)
Reproduction de : Thèse doctorat : Mathématiques : Cergy-Pontoise : 2004. / Titre provenant de l'écran titre. Notes bibliogr.
|
19 |
La théorie de l'équilibre structural revisitéeBarthelemy, Louis Dubois, Nicole. January 2007 (has links)
Thèse de doctorat : Psychologie : Nancy 2 : 2007. / Titre provenant de l'écran-titre.
|
20 |
Fragmentation de graphes et applications au génie logiciel /Charlton, Martin, January 2005 (has links)
Thèse (M.Inf.) -- Université du Québec à Chicoutimi, programme en extension de l'Université du Québec à Montréal, 2005. / Bibliogr.: f. 125-130. Document électronique également accessible en format PDF. CaQCU
|
Page generated in 0.0679 seconds