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 Matthieu Latapy, 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 Table des matières Table des figures Liste des tableaux I Introduction Problématique Motivation Objectifs Contribution Environnement de stage 1 3 II Propriétés statistiques des graphes de terrain Propriétés des graphes de terrain 1.1 Définitions 1.2 Propriétés statistiques des graphes de terrain Analyse statistique des données expérimentales Conclusion 5 6 III Graphe biparti pour encoder les graphes de terrain Graphe biparti 1.1 Encodage d’un graphe quelconque en un graphe biparti 1.2 Propriétés des graphes bipartis encodés de graphes de terrain 1.3 Génération aléatoire d’un graphe biparti 1.4 Décodage d’un graphe biparti Résultats expérimentaux et Analyse 9 10 11 11 11 IV Graphe multiparti Encodage d’un graphe quelconque en graphe multiparti 1.1 Analyse d’un exemple 1.2 Graphe multiparti de facteur faible 1.3 Graphe multiparti de facteur 1.4 Graphe multiparti de facteur propre Conclusion 13 13 13 15 16 16 16 V Nouvelle vision pour les graphes multipartis Analyse d’un exemple Définition d’une nouvelle vision 2.1 Certaines notations sur l’ensemble ordonné 2.2 Définition d’une série d’ensembles ordonnés 2.3 La correspondance entre le graphe de facteur k-parti et la série d’ensembles ordonnés {(Lk , )}k 2.4 Correspondance entre le graphe multiparti de facteur faible et la série d’ensembles ordonnés {Rk } 2.5 Correspondance entre le graphe multiparti de facteur propre et la série d’ensembles ordonnés {Tk } Proposition de la série d’ensembles ordonnés {Fk } Proposition du graphe multiparti de facteur fort 4.1 Définition 4.2 Correspondance du graphe multiparti de facteur fort et la série d’ensembles ordonnés {Fk } Conclusion 17 17 18 18 19 20 24 25 28 28 28 28 30 VI Problème de convergence des graphes multipartis Divergence du graphe multiparti de facteur faible Divergence du graphe multiparti de facteur Convergence du graphe multiparti de facteur fort 31 31 31 35 VII Implémentation Pas d’implémentation pour construire un graphe triparti 1.1 Algorithme pour lister les cliques d’un graphe 1.2 L’algorithme pour lister les intersections de cliques Algorithme de génération des graphes aléatoires 37 37 37 39 39 VIIIRésultats expérimentaux et Analyse 41 Environnement d’implémentation et données de test 41 Résultats expérimentaux et la comparaison avec le modèle biparti 41 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 Résumé 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 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 definition 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 convergence property of encoding In our work, we proposed a method which fully resolves this problem by establishing 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 generated could not only capture properties on cliques, but also have the properties which are very close to those generated by graph G Table des figures I.1 I.2 Génération d’un modèle de graphe grâce l’encodage biparti Le processus d’encodage d’un graphe G en graphe 2-parti, 3-parti, 4-parti II.1 Distribution de degré des graphes de terrain III.1 III.2 III.3 III.4 Un exemple pour construire un graphe biparti Graphe biparti correspondant du graphe G Méthode de génération aléatoire d’un graphe biparti Distribution de la taille des intersections des cliques 10 10 11 13 IV.1 IV.2 IV.3 IV.4 Structure d’un graphe G étant donné Encodage biparti de G Encodage triparti de G Processus infini de la construction des parties du graphe multiparti 13 14 15 15 VI.1 Représentation des ensembles R0 et R1 32 VI.2 Représentation des ensembles L0 , L1 , L2 33 VII.1 Algorithme pour chercher une plus grande clique 38 VII.2 Algorithme pour chercher les cliques d’un graphe 38 VII.3 Algorithme pour lister les intersections des cliques 39 VIII.1 Comparaison de distribution de la taille des intersections des cliques des G0,G1,G2 42 VIII.2 Comparaison des distributions de degrés des graphes G0,G1,G2 44 Liste des tableaux II.1 Statistiques principales des graphes de terrain III.1 Comparaison du coefficient de clustering du graphe original et du graphe aléatoire 12 III.2 Comparaison de la distance moyenne du graphe original et du graphe aléatoire 12 V.1 Comparaison de la structure d’un élément des trois types d’encodage multiparti 27 VIII.1 Comparaison des coefficients de clustering c0,c1,c2 du graphe original, du graphe généré par l’encodage biparti et du graphe généré par l’encodage triparti 43 VIII.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’encodage triparti 43 Chapitre I Introduction 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 applications 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 virtuelles, ) 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 : 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 propriétés On définit un processus de construire un modèle en se basant sur des informations 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 objets 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 Chapitre I 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 MolloyReed[16,17], Malgrộ de nombreuses contributions intộressantes comme ỗa il nexiste aujourdhui 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 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] Figure I.1 – Génération d’un modèle de graphe grâce l’encodage biparti Motivation Cependant, malheuresement, ce modèle ne capture pas suffisamment le recouvrement 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 problème et pour rechercher un meilleur modèle , [24] ont récemmet introduit l’encodage 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 Chapitre VI Problème de convergence des graphes multipartis L2 = L2 {Y5 , Y6 } où Y5 = Inf {Y4 , Y8 } et Y6 = Inf {Y10 , Y4 , Y8 } On continue construire l’ensemble L3 suivant : Z1 = (Inf {Y1 , Y10 , Y4 , Y8 }, M ax{Y1 , Y10 , Y4 , Y8 }) = (Y6 , Y1 ) Z2 = (Inf {Y1 , Y2 , Y4 , Y7 , Y8 }, M ax{Y1 , Y2 , Y4 , Y7 , Y8 }}) = (Y5 , Y1 ) Z3 = (Inf {Y1 , Y4 }, M ax{Y1 , Y4 }) = (Y4 , Y1 ) Z4 = (Inf {Y3 , Y1 }, M ax{Y3 , Y1 }) = (Y3 , Y1 ) Z5 = (Inf {Y2 , Y4 }, M ax{Y2 , Y4 }) = (Y4 , Y2 ) Z6 = (Inf {Y2 , Y1 }, M ax{Y2 , Y1 }) = (Y2 , Y1 ) Z7 = (Inf {Y3 , Y2 }, M ax{Y3 , Y2 }) = (Y3 , Y2 ) Z8 = (Inf {Y2 , Y4 , Y7 , Y8 }, M ax{Y2 , Y4 , Y7 , Y8 }}) = (Y5 , Y2 ) Z9 = (Inf {Y3 , Y4 }, M ax{Y3 , Y4 }) = (Y4 , Y3 ) C’est clair que L3 et L1 sont mêmes Alors, le processus est infini Donc, la série Figure VI.2 – Représentation des ensembles L0 , L1 , L2 {Lk } ne converge pas Donc, le graphe de facteur correspondant de {Lk } ne converge pas De cette série, nous trouvons le graphe ayant l’ensemble de cliques suivantes : v1 = abcdef gx1 v2 = abcdef gx2 v3 = abcdef x3 v4 = abcdex4 v5 = abcdx5 v6 = abcx6 v7 = abx7 33 Chapitre VI Problème de convergence des graphes multipartis Nous continuons construire le sous-ensemble de V2 : w1 = v1 v2 abcdef g w2 = v1 v2 v3 abcdef w3 = v1 v2 v3 v4 abcde w4 = v1 v2 v3 v4 v5 abcd w5 = v1 v2 v3 v4 v5 v6 abc w6 = v1 v2 v3 v4 v5 v6 v7 ab x1 x2 x3 x4 x5 x6 x7 x8 x9 Un sous-ensemble de V3 est comme suit : = w1 w2 w3 w4 w5 w6 v1 v2 ab = w1 w2 w3 w4 w5 v1 v2 abc = w1 w2 w3 w4 v1 v2 abcd = w1 w2 w3 v1 v2 abcde = w2 w3 w4 v1 v2 v3 abcd = w1 w2 v1 v2 abcdef = w2 w3 v1 v2 v3 abcde = w2 w3 w4 w5 v1 v2 v3 abc = w3 w4 v1 v2 v3 v4 abcd Un sous-ensemble de V4 est comme suit : y = x1 x2 w1 w2 w3 w4 w5 v1 v2 ab y = x1 x2 x3 w1 w2 w3 w4 v1 v2 ab y = x1 x2 x3 x4 w1 w2 w3 v1 v2 ab y = x1 x2 x3 x4 x6 w1 w2 v1 v2 ab y = x1 x2 x3 x5 w2 w3 w4 v1 v2 ab y8 = x1 x2 x3 x4 x5 x7 w2 w3 v1 v2 ab y = x1 x2 x8 w2 w3 w4 w5 v1 v2 ab y10 = x1 x2 x3 x5 x8 x9 w3 w4 v1 v2 ab Un sous-ensemble de V5 est comme suit : z1 = y1 y2 y3 y4 y7 y8 y9 y10 x1 x2 v1 v2 ab z2 = y1 y2 y3 y4 y7 y8 x1 x2 w2 v1 v2 ab z3 = y1 y2 y3 y4 x1 x2 w1 w2 v1 v2 ab z4 = y1 y2 y3 x1 x2 w1 w2 w3 v1 v2 ab z5 = y2 y3 y4 x1 x2 x3 w1 w2 v1 v2 ab z6 = y1 y2 x1 x2 w1 w2 w3 w4 v1 v2 ab z7 = y2 y3 x1 x2 x3 w1 w2 w3 v1 v2 ab z8 = y2 y3 y4 y7 y8 x1 x2 x3 w2 v1 v2 ab z9 = y3 y4 x1 x2 x3 x4 w w v1 v2 ab Et c’est clair que les éléments de V3 et V5 que nous avons construits sont les mêmes Bien que ce sont seulement des sous-ensembles de V3 et V5 mais si dans la structure entière de V3 et V5 , il existe une partie répétée Il suffit d’affirmer que le graphe multiparti de facteur diverge 34 Chapitre VI Problème de convergence des graphes multipartis Convergence du graphe multiparti de facteur fort Le type de graphe multiparti de facteur et de facteur faible ne convergent pas C’est raison que le graphe multiparti de fort facteur est une solution efficace parce que ce type de graphe converge En effet : Definition 27 Soit O1 , O2 , , On ∈ Fk , quelconque et n ≥ On s’appelle (O1 , O2 , , On ) une séquence si et seulement si O1 ≺ O2 ≺ On On note |(O1 , O2 , , On )| = n, la longueur de la séquence Lemme Soit (a1 , b1 ), (a2 , b2 ), , (an , bn ) ∈ Fl , quelconque de sorte que : – a1 a2 an – bn bn−1 b1 Alors, ∃c1 , c2 , , cn+1 et ci ∈ {a1 , a2 , , an } ∪ {b1 , b2 , , bn } pour ∀1 ≤ i ≤ (n + 1) de sorte que (c1 , c2 , , cn+1 ) est une séquence Preuve Avec n = 2, on a : a1 a2 et b2 b1 On considère tous les cas possibles : – Si a1 = a2 alors il est nécessaire que b2 ≺ b1 On a donc une séquence (a1 , b1 , b2 ) – Si b1 = b2 alors il est nécessaire que a1 ≺ a2 On a donc une séquence (a1 , a2 , b2 ) – Si a1 ≺ a2 et b2 ≺ b1 , alors bien entendu, on a une séquence (a1 , a2 , b2 , b1 ) Par conséquent, dans tous les cas, il existe toujours une séquence qui a la longueur égale Supposons que l’hyspothèse est vraie pour n = k, on prouvera que cette hypothèse est aussi correcte pour n = (k + 1) C’est dire que : Soit (a1 , b1 ), (a2 , b2 ), , (ak+1 , bk+1 ) ∈ Ll , quelconque de sorte que : – a1 a2 ak+1 – bk+1 bn−1 b1 Alors, ∃c1 , c2 , , ck+2 , ci ∈ {a1 , a2 , , ak+1 } ∪ {b1 , b2 , , bk+1 } pour ∀1 ≤ i ≤ (k + 2) de sorte que (c1 , c2 , , ck+2 ) est une séquence En effet, on considère k paires (a2 , b2 ), , (ak+1 , bk+1 ), par hypothèse, on a : – a2 ak+1 – bk+1 bk b2 Car la hypothèse est vraie pour n = k, alors ∃c1 , c2 , , ck+1 et ci ∈ {a2 , , ak+1 } ∪ {b2 , , bk+1 } pour ∀1 ≤ i ≤ (k + 1) de sorte que c1 ≺ c2 ≺ ck+1 – Si a1 = a2 alors il est certain que b1 b2 D’autre part, on a : ci ∈ {a2 , , ak+1 }∪ {b2 , , bk+1 } pour ∀1 ≤ i ≤ (k + 1) Il est donc nécessaire que ci ≺ b1 On obtient donc une séquence c1 ≺ c2 ≺ ck+1 ≺ b1 – Si b1 = b2 alors il est certain que a1 a2 D’autre part, on a : ci ∈ {a2 , , ak+1 }∪ {b2 , , bk+1 } pour ∀1 ≤ i ≤ (k + 1) Il est donc nécessaire que a1 ≺ ci On obtient donc une séquence a1 ≺ c1 ≺ c2 ≺ ck+1 – Si a1 ≺ a2 et b2 ≺ b1 alors On obtient une séquence a1 ≺ c1 ≺ c2 ≺ ck+1 ≺ b1 Par conséquent, dans tous les cas, il existe toujours une séquence qui a la longueur égale (k + 2) Le lemme est prouvé Théorème La série {Fk }k≥0 converge Preuve Soit O = (A, B) ∈ Fk quelconque En appliquant le lemme 1, ∃O1 , O2 , Ot ∈ Fk−1 de sorte que : 35 Chapitre VI Problème de convergence des graphes multipartis – A = M in{O1 , O2 , , Ot } – B = M ax{O1 , O2 , , Ot } Alors, sur Fk−1 , on peut construire une séquence (A, B) qui a la longueur égale On suppose que sur Fk−i on a construit une séquence qui a la longueur égale (i+1) Maintenant, On prouvera que sur Fk−(i+1) , il existe une séquence qui a la longueur égale (i + 2) En effet : Soit la séquence qui a la longueur égale (i + 1) que l’on a construit sur Fk−i est O1 , O2 , , Oi+1 Alors bien entendu on aura O1 = (a1 , b1 ), O2 = (a2 , b2 ), , Oi+1 = (ai+1 , bi+1 ) où aj , bj ∈ Fk−i−1 pour ∀1 ≤ j ≤ i + Car (O1 , O2 , , Oi+1 ) est une séquence alors on a : O1 ≺ O2 ≺ Oi+1 Il est donc nécessaire que : – a1 a2 ai+1 – bi+1 bi b1 En appliquant le lemme 7, on a : ∃e1 , e2 , , ei+2 et ej ∈ {a1 , a2 , , ai+1 }∪{b1 , b2 , , bi+1 } pour ∀1 ≤ j ≤ (i + 2) de sorte que (e1 , e2 , , ei+2 ) est une séquence Enfin, on a que sur Fk−i , il existe toujours une séquence qui a la longueur égale (i + 1) En particulier, sur F0 il existe une séquence qui a la longueur égale (k + 1) Car le nombre d’éléments de F0 est fini alors il est certain que série {Fk }k≥0 converge Le théorème est prouvé Alors, c’est clair que les séries d’ensembles ordonnés ont un rôle important pour le problème de convergence des graphes multipartis Elles apportent une nouvelle vision où nous pouvons trouver les relations des sommets des graphes multipartis Alors, c’est certain qu’elles sont un outil efficace pour rechercher la nature du graphe multiparti et aussi ses propriétés Cependant, dans le cadre du stage, pour le travail théorique, nous s’arrêtons ici pour arriver au travail pratique C’est aussi un travail très important pour affirmer notre théorie 36 Chapitre VII Implémentation Pour montrer que le type d’encodage multiparti sert efficacement de générer des modèles aléatoires, nous implémentons un programme de générer aléatoirement en utilisant l’encodage triparti Le graphe triparti est un cas particulier du graphe multiparti Bien qu’il ait seulement trois parties, il peut encore exprimer le sens de l’encodage multiparti C’est de capturer le recouvrement des cliques des graphes de terrain Pas d’implémentation pour construire un graphe triparti Le graphe triparti est construit sur le graphe biparti Soit G un graphe original Alors, la construction est la suivante : Construire les sommets de la deuxième partie C’est l’ensemble des cliques de G Construire les sommets de la troisième partie C’est l’ensemble d’intersections des cliques dans l’étape Il faut noter que nous utilisons le graphe de facteur pour encoder G 1.1 Algorithme pour lister les cliques d’un graphe Dans le chapitre 3, nous avons parlé de cet ensemble des cliques Nous le notons C Il a la propriété : avec une arête quelconque de G, il existe toujours une clique de C qui la contient Il est possible qu’il y a plusieurs ensembles qui ont cette propriété Il nous faut seulement trouver un ensemble comme ỗa Il y a un algorithme efficace pour rechercher cet ensemble On considère certaines propriétés suivantes : On note l’ensemble de voisin d’un sommet u : N (u) = {v ∈ V |(u, v) ∈ E} et l’ensemble de voisins d’une arête (u,v) : N (u, v) = N (u) ∩ N (v) Il est facile de voir que la clique qui contient l’arête (u,v) doit appartenir l’ensemble : N (u, v) ∪ {u, v} Alors, le problème de chercher une clique qui contient l’arête (u,v) est correspondant au problème de chercher une clique du sous-graphe de G ayant l’ensemble de sommets qui appartient au N (u, v) − {u, v} L’algorithme de chercher une clique est représenté dans la figure VII.1 L’algorithme pour chercher un ensemble de cliques C est représenté dans la figure VII.2 37 Chapitre VII Implémentation Procedure: cliquemaximum(G) Entrée:le graphe G Sortie: La plus grande clique de G Nous notons #E le nombre d’élément de E # # Rechercher une clique C_m (maximum local) # Trier l’ensemble des noeuds selon leur degré C_m