"Complex Networks" et la structure multipartie des graphes

• Main Author: Tran, The Hung
• Other Authors: Phan, Thi Ha Duong
• Format: Theses and Dissertations
• Language: French
• Published: 2015
• Online Access: http://repository.vnu.edu.vn/handle/VNU_123/348
• Institution: Vietnam National University, Hanoi

Il est récemment apparu que la plupart des grands graphes rencontrés en pratique appelés graphes de terrain (ou "Complex network" en anglais), ont des propriétés non-triviales en commun. En conséquence, une intense activité est aujourd’hui consacrée à la définition des modèles qui capturent ces propriétés. Parmi les plus prometteurs travaux, on a été proposé d’encoder des graphes de terrain par des graphes bipartis. Cependant, on a constaté que ce modèle obtenu ne capture pas suffisamment des propriétés sur les cliques des graphes de terrain en réalité. Nous explorons ici la possibilité de sortir de cette limite en introduisant un encodage multiparti (un encodage des graphes de terrain comme des graphes multipartis). C’est une généralisation de l’encodage biparti. Plusieurs définitions sont possibles, cependant, il est difficile de trouver un encodage multiparti efficace, c’est à dire d’assurer la propriété de convergence de l’encodage. Dans notre travail, nous avons proposé une méthode pour résoudre pleinement ce problème en construisant une bijection d’un graphe multiparti vers une série d’ensembles ordonnés. Alors, au lieu d’étudier directement la convergence du graphe multiparti, nous l’avons étudié sur cette série d’ensembles ordonnés. Nous avons aussi implémenté les algorithmes efficaces pour la génération d’un modèle aléatoire d’un graphe G étant donné. Les résultats expérimentaux montrent que non seulement le graphe aléatoire généré peuvent capturer des propriétés sur les cliques mais encore il possède des propriétés qui sont très proches de celles du graphe G.