Vous êtes ici : UVSQ RechercheDoctorat

Systèmes complexes et systèmes de santé. Défis calculatoires par Zifan Liu

Présentée par : Zifan Liu Discipline : informatique Laboratoire : PRISM

Résumé :
Le calcul des valeurs propres intervient dans des modèles de maladies d’épidémiques et pourrait être utilisé comme un allié des campagnes de vaccination dans les actions menées par les organisations de soins de santé. La modélisation épidémique peut être considérée, par analogie, comme celle des virus d’ordinateur qui dépendent de l’état de graphe sous-jacent à un moment donné. Nous utilisons PageRank comme méthode pour étudier la propagation de l’épidémie et d’envisager son calcul dans le cadre de phénomène petit-monde.
Une mise en œuvre parallèle de méthode multiple de "implicitly restarted Arnoldi method" (MIRAM) est proposée pour calculer le vecteur propre dominant de matrices stochastiques issues de très grands réseaux réels. La grande valeur de "damping factor" pour ce problème fait de nombreux algorithmes existants moins efficaces, tandis que MIRAM pourrait être prometteuse. Nous proposons également dans cette thèse un générateur de graphe parallèle qui peut être utilisé pour générer des réseaux synthétisés distribués qui présentent des structures "scale-free" et petit-monde. Ce générateur pourrait servir de données pour d’autres algorithmes de graphes également.
MIRAM est mis en œuvre dans le cadre de trilinos, en ciblant les grandes données et matrices creuses représentant des réseaux sans échelle, aussi connu comme les réseaux de loi de puissance. Hypergraphe approche de partitionnement est utilisé pour minimiser le temps de communication. L’algorithme est testé sur une grille nationale de Grid5000. Les expériences sur les très grands réseaux tels que Twitter et Yahoo avec plus de 1 milliard de nœuds sont exécutées. Avec notre mise en œuvre parallèle, une accélération de 27× est satisfaite par rapport au solveur séquentiel.

Abstract :
The eigenvalue equation intervenes in models of infectious disease propagation and could be used as an ally of vaccination campaigns in the actions carried out by health care organizations. The epidemiological modeling techniques can be considered by analogy, as computer viral propagation which depends on the underlying graph status at a given time. We point out PageRank as method to study the epidemic spread and consider its calculation in the context of small-world phenomenon.
A parallel implementation of multiple implicitly restarted Arnoldi method (MIRAM) is proposed for calculating dominant eigenpair of stochastic matrices derived from very large real networks. Their high damping factor makes many existing algorithms less efficient, while MIRAM could be promising. We also propose in this thesis a parallel graph generator that can be used to generate distributed synthesized networks that display scale-free and small-world structures. This generator could serve as a testbed for graph related algorithms.
MIRAM is implemented within the framework of Trilinos, targeting big data and sparse matrices representing scale-free networks, also known as power law networks. Hypergraph partitioning approach is employed to minimize the communication overhead. The algorithm is tested on a nationwide cluster of clusters Grid5000. Experiments on very large networks such as twitter and yahoo with over 1 billion nodes are conducted. With our parallel implementation, a speedup of 27× is met compared to the sequential solver.
Informations complémentaires
Michel DAYDE, Professeur des Universités, à l’Université Paul Sabatier 3/Institut de Recherche en Informatique de Toulouse (IRIT) - UMR 5505 - Toulouse - Rapporteur
Joel SALTZ, Professeur des Universités, à l’Université de Stony Brook/Department of Biomedical Informatics - New-York (Etats-Unis) - Rapporteur
Nahid EMAD, Professeur des Universités, à l’Université de Versailles Saint-Quentin-en-Yvelines/Laboratoire Parallélisme, Réseaux, Système, Modélisation (PRISM) - Versailles - Directeur de thèse
Soufian BEN-AMOR, Maître de Conférences, à l’Université de Versailles Saint-Quentin-en-Yvelines/Laboratoire Parallélisme, Réseaux, Système, Modélisation (PRISM) - Versailles - Examinateur
Alain BUI, Professeur des Universités, à l’Université de Versailles Saint-Quentin-en-Yvelines/Laboratoire Parallélisme, Réseaux, Système, Modélisation (PRISM) - Versailles - Examinateur
Christophe CALVIN, Chercheur, au CEA - Gif/Yvette - Examinateur
Didier GUILLEMOT, Professeur des Universités/Praticien Hospitalier, à l’Institut Pasteur/Unité Pharmacoépidémiologie et Maladies Infectieuses - Inserm 657 - Paris - Examinateur
Michel KERN, Chargé de Recherche, à l’INRIA - Le Chesnay - Examinateur
Contact :
dredval service FED :