Rapport de stage de fin d’études Pour l’obtention du grade de MASTER DE L’INSTITUT DE LA FRANCOPHONIE POUR L’INFORMATIQUE Réalisé par Tran The Hung "Complex Networks" et la structure multipartie des graphes Directeur de stage: M. Christophe Crespelle(Lip6, Université Paris 6, France) Mme.Phan Thi Ha Duong(Université Paris 7-Institut de Mathématique du Vietnam- IFI-MSI) Hanoi le 31/10/2009 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Table des matières Table des figures 2 Liste des tableaux 2 I Introduction 1 1 Problématique. 3 5 Environnement de stage. 4 II Propriétés statistiques des graphes de terrain 5 1 Propriétés des graphes de terrain .2 Propriétés statistiques des graphes de terrain.
6 2 Analyse statistique des données expérimentales. 7 III Graphe biparti pour encoder les graphes de terrain 9 1 Graphe biparti .1 Encodage d’un graphe quelconque en un graphe biparti .2 Propriétés des graphes bipartis encodés de graphes de terrain .3 Génération aléatoire d’un graphe biparti .4 Décodage d’un graphe biparti. 11 2 Résultats expérimentaux et Analyse. 11 IV Graphe multiparti 13 1 Encodage d’un graphe quelconque en graphe multiparti .1 Analyse d’un exemple .2 Graphe multiparti de facteur faible .3 Graphe multiparti de facteur .4 Graphe multiparti de facteur propre.
16 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com V Nouvelle vision pour les graphes multipartis 17 1 Analyse d’un exemple. 17 2 Définition d’une nouvelle vision .1 Certaines notations sur l’ensemble ordonné .2 Définition d’une série d’ensembles ordonnés .3 La correspondance entre le graphe de facteur k-parti et la série d’ensembles ordonnés {(Lk , )}k0 .4 Correspondance entre le graphe multiparti de facteur faible et la série d’ensembles ordonnés {Rk } .5 Correspondance entre le graphe multiparti de facteur propre et la série d’ensembles ordonnés {Tk }. 25 3 Proposition de la série d’ensembles ordonnés {Fk }. 28 4 Proposition du graphe multiparti de facteur fort .2 Correspondance du graphe multiparti de facteur fort et la série d’ensembles ordonnés {Fk }.
30 VI Problème de convergence des graphes multipartis 31 1 Divergence du graphe multiparti de facteur faible. 31 2 Divergence du graphe multiparti de facteur. 31 3 Convergence du graphe multiparti de facteur fort. 35 VII Implémentation 37 1 Pas d’implémentation pour construire un graphe triparti .1 Algorithme pour lister les cliques d’un graphe .2 L’algorithme pour lister les intersections de cliques.
39 2 Algorithme de génération des graphes aléatoires. 39 VIIIRésultats expérimentaux et Analyse 41 1 Environnement d’implémentation et données de test. 41 2 Résultats expérimentaux et la comparaison avec le modèle biparti. 41 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Remerciement Je tiens d’abord à remercier Matthieu Latapy, Phan Thi Ha duong et Christophe Crespelle, qui ont dirigé mon mémoire de fin d’études.
Leurs commentaires éclairés, leurs judicieux conseils, leur disponibilité d’encouragements m’ont considérablement aidé à mener à terme mes travaux. Ma reconnaissance s’adresse aussi aux professeurs à l’Institut de la Francophonie pour l’Informatique. Leurs cours m’ont apporté des connaissances et des suggestions qui sont utiles pour mon mémoire. Finalement, j’exprime mon entière reconnaissance à ma famille et mes amis pour leur soutien, leur aide et leurs encouragements.
Sans leur aide, je n’aurais pas pu achever ce mémoire. LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Résumé Il est récemment apparu que la plupart des grands graphes rencontrés en pra- tique 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 mul- tipartis). 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’en- sembles 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.
LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Abstract It appeared recently that most real-world complex networks have some properties in common. As a consequence, an intense activity is nowadays devoted to the defi- nition of models which capture these properties. Among the most promising ones, it has been proposed to encode complex networks into bipartite graphs. However, we found that this model does not capture enough properties on the cliques of the network actually.
We explore here the possibility to go beyond these limitations by introducing a multipartite encoding(encode complex networks into multipartite graphs ). It is a generalization of the bipartite encoding. Several definitions are possible, however, it is difficult to find an effective multipartite encoding. It means to assure the conver- gence property of encoding.
In our work, we proposed a method which fully resolves this problem by es- tablishing a bijection of a multipartite graph towards a series of ordered sets. So instead of studying directly the convergence of the multipartite model, we studied it on this series of ordered sets. We also installed the effective algorithms to generate a random model of a G graph given. The achieved experimental results show that the random graph ge- nerated could not only capture properties on cliques, but also have the properties which are very close to those generated by graph G.
LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Table des figures I.1 Génération d’un modèle de graphe grâce à l’encodage biparti .2 Le processus d’encodage d’un graphe G en graphe 2-parti, 3-parti, 4-parti.1 Distribution de degré des graphes de terrain.1 Un exemple pour construire un graphe biparti.2 Graphe biparti correspondant du graphe G.3 Méthode de génération aléatoire d’un graphe biparti.4 Distribution de la taille des intersections des cliques.1 Structure d’un graphe G étant donné.2 Encodage biparti de G.3 Encodage triparti de G.4 Processus infini de la construction des parties du graphe multiparti.1 Représentation des ensembles R0 et R1 .2 Représentation des ensembles L0 , L1 , L2 .1 Algorithme pour chercher une plus grande clique .2 Algorithme pour chercher les cliques d’un graphe .3 Algorithme pour lister les intersections des cliques .1 Comparaison de distribution de la taille des intersections des cliques des G0,G1,G2.2 Comparaison des distributions de degrés des graphes G0,G1,G2. 44 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Liste des tableaux II.1 Statistiques principales des graphes de terrain .1 Comparaison du coefficient de clustering du graphe original et du graphe aléatoire .2 Comparaison de la distance moyenne du graphe original et du graphe aléatoire .1 Comparaison de la structure d’un élément des trois types d’encodage multiparti .1 Comparaison des coefficients de clustering c0,c1,c2 du graphe origi- nal, du graphe généré par l’encodage biparti et du graphe généré par l’encodage triparti .2 Comparaison des distances moyennes d0,d1,d2 graphe original, du graphe généré par l’encodage biparti et du graphe généré par l’enco- dage triparti. 43 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Chapitre I Introduction 1 Problématique De nombreux graphes de terrain(ou "Complex network" en anglais) jouent un rôle important dans divers contextes. On peut citer le graphe physique d’Internet (graphe des connexions physiques entre machines), le graphe du Web (induit par les liens hypertextes contenus dans les pages Web), ou les graphes issus des appli- cations pair-à-pair (par exemple le graphe des échanges dans un réseau pair-à-pair), mais aussi les réseaux d’interactions biologiques (gènes, protéines, neurones, espèces, .), ou les réseaux sociaux (relations professionnelles ou amicales, communautés vir- tuelles,.
La recherche directe sur les graphes réels très grands est en général difficile alors une tendance commune est que l’on cherche à construire des modèles artificiels de ces graphes de terrain et puis on peut réaliser indirectement le travail de recherche sur ces modèles artificiels. il y a deux directions pour construire un tel modèle : 1. A partir des informations sur les propriétés fondamentales observées des graphes de terrain en pratique, on cherche à générer aléatoirement un graphe qui a ces pro- priétés. On définit un processus de construire un modèle en se basant sur des infor- mations sur la structure des graphes de terrain en pratique.
La première direction est avantageuse pour l’analyse et la recherche des graphes réels de terrain parce que ce graphe a assuré des propriétés fondamentales des ob- jets réels. Cependant, la génération aléatoire est difficile. Par contre, la deuxième direction est avantageuse pour la génération aléatoire parce que l’on a la suggestion sur la structure de l’objet réel mais il est difficile d’assurer que l’objet obtenu a des propriétés des objets réels. Chaque direction a des avantages et des désavantages mais ici on se concentre à la première direction.
C’est-à-dire qu’on se concentrera sur la construction des graphes ayant strictement les propriétés données. L’analyse statistique montre que la plupart de ces graphes ont des propriétés non-triviales. Ce sont la faible densité, la faible distance moyenne, la distribution de degré qui suit une loi de puissance, le coefficient de clustering qui n’arrive pas à 0 1 LUAN VAN CHAT LUONG download : add luanvanchat@agmail. Introduction quand le nombre de sommets du graphe se grandit [1,9](on les définira exactement après).
Ce sont les propriétés les plus importantes des réseaux complexes. Pour générer un modède de graphe ayant ces propriétés, il y a eu plusieurs résultats, les résultats typiques sont le modèle (ER, 1959) de Erdos-Rényi[10], le modèle (AB, 1990) de Albert- Babarasi[1,2], le modèle (MR, 1995) de Molloy- Reed[16,17],.Malgré de nombreuses contributions intéressantes comme ça il n’existe aujourd’hui pas d’une solution complète qui satisfait des propriétés fondamentales des graphes de terrain. [12] propose une méthode efficace qui permet de générer le modèle aléatoire ayant des 4 propriétés rencontrées en pratique. Cette méthode se base sur l’encodage d’un graphe G quelconque par un graphe biparti[12,13].1 – Génération d’un modèle de graphe grâce à l’encodage biparti.
2 Motivation Cependant, malheuresement, ce modèle ne capture pas suffisamment le recou- vrement des cliques(des sous-graphes complets) et des voisins (d’un sommet) des graphes de terrain. Cette propriété est répandue en pratique. Pour résoudre ce pro- blème et pour rechercher un meilleur modèle , [24] ont récemmet introduit l’enco- dage multiparti qui est une généralisation de l’encodage biparti. Avec cet encodage Figure I.2 – Le processus d’encodage d’un graphe G en graphe 2-parti, 3-parti, 4-parti.
complexe, on espère très bien qu’elle apporte plus beaucoup d’informations sur des propriétés des graphes de terrain que l’encodage biparti. Surtout, il peut résoudre le recouvrement des cliques. [24] a obtenu des premiers résultats pour l’encodage d’un graphe G étant donné en un graphe multiparti. Il y a trois encodages proposés : l’encodage d’un graphe 2 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.
Introduction quelconque en graphe multiparti de facteur faible, en graphe multiparti de facteur et en graphe multiparti de facteur propre. Un problème important de l’encodage mul- tiparti est d’assurer la propriété de convergence parce qu’il est très possible qu’un graphe multiparti obtenu a le nombre de parties infini) Dans ces types d’encodage, l’encodage en graphe multiparti de facteur faible est divergent. Alors, c’est inefficace. [24] a prouvé que le type d’encodage en graphe multiparti de facteur propre est convergent.
En plus, cette preuve suggère beaucoup d’idées pour résoudre des problèmes ouverts des graphes multipartis.
