Des réseaux sociaux aux réseaux historiques

  • Published on
    11-May-2015

  • View
    141

  • Download
    0

Embed Size (px)

DESCRIPTION

January 19th, 2012 Les cafs de lIMT, Institut de Mathmatiques de Toulouse

Transcript

<ul><li>1.Des rseaux sociaux aux rseaux historiques Nathalie Villa-Vialaneix http://www.nathalievilla.org nathalie.villa@univ-paris1.fr IUT de Perpignan &amp; SAMM, Universit Paris 1 Les cafs de lIMT, 19 Janvier 2012 Rseaux (Cafs de lIMT) Nathalie Villa-Vialaneix IMT, 19/01/2012 1 / 20 </li></ul><p>2. Quest-ce quun rseau/graphe ? Plan 1 Quest-ce quun rseau/graphe ? 2 Quelques outils de fouille de graphes Visualisation Charactristiques individuelles des sommets Recherche de Communauts 3 Fouille sur un grand graphe mdival Rseaux (Cafs de lIMT) Nathalie Villa-Vialaneix IMT, 19/01/2012 2 / 20 3. Quest-ce quun rseau/graphe ? Quest-ce quun rseau/graphe ? Objet mathmatique utilis pour modliser des relations entre des entits. Rseaux (Cafs de lIMT) Nathalie Villa-Vialaneix IMT, 19/01/2012 3 / 20 4. Quest-ce quun rseau/graphe ? Quest-ce quun rseau/graphe ? Objet mathmatique utilis pour modliser des relations entre des entits. Les entits sont appeles les nuds ou les sommets. Rseaux (Cafs de lIMT) Nathalie Villa-Vialaneix IMT, 19/01/2012 3 / 20 5. Quest-ce quun rseau/graphe ? Quest-ce quun rseau/graphe ? Objet mathmatique utilis pour modliser des relations entre des entits. Une relation entre deux entits est modlise par une arte. Rseaux (Cafs de lIMT) Nathalie Villa-Vialaneix IMT, 19/01/2012 3 / 20 6. Quest-ce quun rseau/graphe ? Exemples Rseaux sociaux : sommets : personnes - artes : lien entre deux personnes powered by Touchgraph TM 1 (Nattys facebook TM 2 network) 1 http://www.touchgraph.com 2 https://www.facebook.com Rseaux (Cafs de lIMT) Nathalie Villa-Vialaneix IMT, 19/01/2012 4 / 20 7. Quest-ce quun rseau/graphe ? Exemples Rseaux biologiques (un exemple, parmi dautres : rseau de co-expression): sommets : gnes - artes : les deux gnes fonctionnent de la mme manire [Liaubet et al., 2010, Villa-Vialaneix et al., 2011] Rseaux (Cafs de lIMT) Nathalie Villa-Vialaneix IMT, 19/01/2012 4 / 20 8. Quest-ce quun rseau/graphe ? Exemples Dautres types de donnes relationnelles Modliser un large corpus de documents moyennageux actes notaris (la plupart sont des baux ef) tablis dans la seigneurie de Castel- nau Montratier, entre 1250 et 1500, qui im- pliquent des tenanciers et des seigneurs.a a http://graphcomp.univ-tlse2.fr Rseaux (Cafs de lIMT) Nathalie Villa-Vialaneix IMT, 19/01/2012 4 / 20 9. Quest-ce quun rseau/graphe ? Exemples Dautres types de donnes relationnelles Modliser un large corpus de documents moyennageux sommets : transactions et individus (10 542 sommets) artes : un individu est directement impliqu dans une transaction (6 455 artes) Rseaux (Cafs de lIMT) Nathalie Villa-Vialaneix IMT, 19/01/2012 4 / 20 10. Quest-ce quun rseau/graphe ? Exemples Dautres types de donnes relationnelles Indivual Transaction Rseaux (Cafs de lIMT) Nathalie Villa-Vialaneix IMT, 19/01/2012 4 / 20 11. Quest-ce quun rseau/graphe ? Exemples Dautres types de donnes relationnelles Rseau de consommation sommets : 105 livres de politique amricains - artes modlisent le fait que le mme acheteur a achet les deux livres (sur Amazon). Rseaux (Cafs de lIMT) Nathalie Villa-Vialaneix IMT, 19/01/2012 4 / 20 12. Quest-ce quun rseau/graphe ? Modles relationnels plus complexes Les sommets peuvent tre tiquets par une information supplmentaire qualitative Rseaux (Cafs de lIMT) Nathalie Villa-Vialaneix IMT, 19/01/2012 5 / 20 13. Quest-ce quun rseau/graphe ? Modles relationnels plus complexes Les sommets peuvent tre tiquets par une information supplmentaire qualitative ... ou numrique. [Laurent and Villa-Vialaneix, 2011] Rseaux (Cafs de lIMT) Nathalie Villa-Vialaneix IMT, 19/01/2012 5 / 20 14. Quest-ce quun rseau/graphe ? Modles relationnels plus complexes Les sommets peuvent tre tiquets par une information supplmentaire qualitative ... ou numrique. [Laurent and Villa-Vialaneix, 2011] Artes peuvent tre tiquetes (type de la relation) ou pondres (force de la relation). Rseaux (Cafs de lIMT) Nathalie Villa-Vialaneix IMT, 19/01/2012 5 / 20 15. Quelques outils de fouille de graphes Plan 1 Quest-ce quun rseau/graphe ? 2 Quelques outils de fouille de graphes Visualisation Charactristiques individuelles des sommets Recherche de Communauts 3 Fouille sur un grand graphe mdival Rseaux (Cafs de lIMT) Nathalie Villa-Vialaneix IMT, 19/01/2012 6 / 20 16. Quelques outils de fouille de graphes Dans la suite... ... on considre un graphe avec : des sommets {x1, . . . , xn} ; des artes ; des poids sur les artes, symtriques et positifs Wij. Rseaux (Cafs de lIMT) Nathalie Villa-Vialaneix IMT, 19/01/2012 7 / 20 17. Quelques outils de fouille de graphes Visualisation Plan 1 Quest-ce quun rseau/graphe ? 2 Quelques outils de fouille de graphes Visualisation Charactristiques individuelles des sommets Recherche de Communauts 3 Fouille sur un grand graphe mdival Rseaux (Cafs de lIMT) Nathalie Villa-Vialaneix IMT, 19/01/2012 8 / 20 18. Quelques outils de fouille de graphes Visualisation Reprsenter le graphe Problme : Comment placer les sommets sur la feuille de manire avoir une reprsentation comprhensible et esthtique du graphe ? Rseaux (Cafs de lIMT) Nathalie Villa-Vialaneix IMT, 19/01/2012 9 / 20 19. Quelques outils de fouille de graphes Visualisation Reprsenter le graphe Problme : Comment placer les sommets sur la feuille de manire avoir une reprsentation comprhensible et esthtique du graphe ? Approche standard : algorithmes de forces (FDP) (par exemple : [Fruchterman and Reingold, 1991]) Rseaux (Cafs de lIMT) Nathalie Villa-Vialaneix IMT, 19/01/2012 9 / 20 20. Quelques outils de fouille de graphes Visualisation Reprsenter le graphe Problme : Comment placer les sommets sur la feuille de manire avoir une reprsentation comprhensible et esthtique du graphe ? Approche standard : algorithmes de forces (FDP) (par exemple : [Fruchterman and Reingold, 1991]) forces attractives : similaires des ressorts sur les artes Rseaux (Cafs de lIMT) Nathalie Villa-Vialaneix IMT, 19/01/2012 9 / 20 21. Quelques outils de fouille de graphes Visualisation Reprsenter le graphe Problme : Comment placer les sommets sur la feuille de manire avoir une reprsentation comprhensible et esthtique du graphe ? Approche standard : algorithmes de forces (FDP) (par exemple : [Fruchterman and Reingold, 1991]) forces attractives : similaires des ressorts sur les artes forces rpulsives : similaires des forces lectriques entre les paires de sommets algorithme itratif jusqu stabilisation de la position des sommets. Rseaux (Cafs de lIMT) Nathalie Villa-Vialaneix IMT, 19/01/2012 9 / 20 22. Quelques outils de fouille de graphes Visualisation Outils de visualisation package igraph1 [Csardi and Nepusz, 2006] (reprsentations statiques avec divers outils pour faire de la fouille de graphes) 1 http://igraph.sourceforge.net/ 2 http://gephi.org Rseaux (Cafs de lIMT) Nathalie Villa-Vialaneix IMT, 19/01/2012 10 / 20 23. Quelques outils de fouille de graphes Visualisation Outils de visualisation package igraph1 [Csardi and Nepusz, 2006] (reprsentations statiques avec divers outils pour faire de la fouille de graphes) logiciel libre Gephi2 (interactif, on peut zoomer, dplacer le graphe la souris...) 1 http://igraph.sourceforge.net/ 2 http://gephi.org Rseaux (Cafs de lIMT) Nathalie Villa-Vialaneix IMT, 19/01/2012 10 / 20 24. Quelques outils de fouille de graphes Charactristiques individuelles des sommets Plan 1 Quest-ce quun rseau/graphe ? 2 Quelques outils de fouille de graphes Visualisation Charactristiques individuelles des sommets Recherche de Communauts 3 Fouille sur un grand graphe mdival Rseaux (Cafs de lIMT) Nathalie Villa-Vialaneix IMT, 19/01/2012 11 / 20 25. Quelques outils de fouille de graphes Charactristiques individuelles des sommets Quels sont les sommets importants ? 1 Degr dun sommet : nombre dartes relies au sommet. Les sommets avec un fort degr sont appels des hubs (mesure de popularit). Rseaux (Cafs de lIMT) Nathalie Villa-Vialaneix IMT, 19/01/2012 12 / 20 26. Quelques outils de fouille de graphes Charactristiques individuelles des sommets Quels sont les sommets importants ? 1 Degr dun sommet : nombre dartes relies au sommet. Les sommets avec un fort degr sont appels des hubs (mesure de popularit). La distribution des degrs est souvent en loi de puissance dans les rseaux rels: 1 2 5 10 20 50 100 200 500 1550500 Names Transactions Rseaux (Cafs de lIMT) Nathalie Villa-Vialaneix IMT, 19/01/2012 12 / 20 27. Quelques outils de fouille de graphes Charactristiques individuelles des sommets Quels sont les sommets importants ? 1 Degr dun sommet : nombre dartes relies au sommet. Les sommets avec un fort degr sont appels des hubs (mesure de popularit). La distribution des degrs est souvent en loi de puissance dans les rseaux rels: 2 Centralit dun sommet : nombre de plus courts chemins entre toutes les paires de sommets qui passent par le sommet considr (sommets qui sont susceptibles de dconnecter le graphe si ils sont retirs). Rseaux (Cafs de lIMT) Nathalie Villa-Vialaneix IMT, 19/01/2012 12 / 20 28. Quelques outils de fouille de graphes Charactristiques individuelles des sommets Quels sont les sommets importants ? 1 Degr dun sommet : nombre dartes relies au sommet. Les sommets avec un fort degr sont appels des hubs (mesure de popularit). La distribution des degrs est souvent en loi de puissance dans les rseaux rels: 2 Centralit dun sommet : nombre de plus courts chemins entre toutes les paires de sommets qui passent par le sommet considr (sommets qui sont susceptibles de dconnecter le graphe si ils sont retirs). Rseaux (Cafs de lIMT) Nathalie Villa-Vialaneix IMT, 19/01/2012 12 / 20 29. Quelques outils de fouille de graphes Charactristiques individuelles des sommets Quels sont les sommets importants ? 1 Degr dun sommet : nombre dartes relies au sommet. Les sommets avec un fort degr sont appels des hubs (mesure de popularit). La distribution des degrs est souvent en loi de puissance dans les rseaux rels: 2 Centralit dun sommet : nombre de plus courts chemins entre toutes les paires de sommets qui passent par le sommet considr (sommets qui sont susceptibles de dconnecter le graphe si ils sont retirs). Rseaux (Cafs de lIMT) Nathalie Villa-Vialaneix IMT, 19/01/2012 12 / 20 30. Quelques outils de fouille de graphes Charactristiques individuelles des sommets Quels sont les sommets importants ? 1 Degr dun sommet : nombre dartes relies au sommet. Les sommets avec un fort degr sont appels des hubs (mesure de popularit). La distribution des degrs est souvent en loi de puissance dans les rseaux rels: 2 Centralit dun sommet : nombre de plus courts chemins entre toutes les paires de sommets qui passent par le sommet considr (sommets qui sont susceptibles de dconnecter le graphe si ils sont retirs). Rseaux (Cafs de lIMT) Nathalie Villa-Vialaneix IMT, 19/01/2012 12 / 20 31. Quelques outils de fouille de graphes Charactristiques individuelles des sommets Quels sont les sommets importants ? 1 Degr dun sommet : nombre dartes relies au sommet. Les sommets avec un fort degr sont appels des hubs (mesure de popularit). La distribution des degrs est souvent en loi de puissance dans les rseaux rels: 2 Centralit dun sommet : nombre de plus courts chemins entre toutes les paires de sommets qui passent par le sommet considr (sommets qui sont susceptibles de dconnecter le graphe si ils sont retirs). Rseaux (Cafs de lIMT) Nathalie Villa-Vialaneix IMT, 19/01/2012 12 / 20 32. Quelques outils de fouille de graphes Recherche de Communauts Plan 1 Quest-ce quun rseau/graphe ? 2 Quelques outils de fouille de graphes Visualisation Charactristiques individuelles des sommets Recherche de Communauts 3 Fouille sur un grand graphe mdival Rseaux (Cafs de lIMT) Nathalie Villa-Vialaneix IMT, 19/01/2012 13 / 20 33. Quelques outils de fouille de graphes Recherche de Communauts Classication des sommets But : Mettre en valeur des groupes de sommets denses et qui partagent peu de liens avec les autres groupes. Rseaux (Cafs de lIMT) Nathalie Villa-Vialaneix IMT, 19/01/2012 14 / 20 34. Quelques outils de fouille de graphes Recherche de Communauts Classication des sommets But : Mettre en valeur des groupes de sommets denses et qui partagent peu de liens avec les autres groupes. Reprsentation simplie du graphe : communaut reprsente par un symbole daire proportionnelle au nombre de sommets ; largeur du lien entre deux classes proportionnelle la somme des poids des artes. Rseaux (Cafs de lIMT) Nathalie Villa-Vialaneix IMT, 19/01/2012 14 / 20 35. Fouille sur un grand graphe mdival Plan 1 Quest-ce quun rseau/graphe ? 2 Quelques outils de fouille de graphes Visualisation Charactristiques individuelles des sommets Recherche de Communauts 3 Fouille sur un grand graphe mdival Rseaux (Cafs de lIMT) Nathalie Villa-Vialaneix IMT, 19/01/2012 15 / 20 36. Fouille sur un grand graphe mdival Retour au graphe darchives mdivales [Rossi et al., 2012] 10 542 sommets : transactions ou personnes ; artes modlisent limplication active dune personne dans une transaction. Graphe biparti Rseaux (Cafs de lIMT) Nathalie Villa-Vialaneix IMT, 19/01/2012 16 / 20 37. Fouille sur un grand graphe mdival Caractristiques macroscopiques Plus grande composante connexe : 10 025 sommets : petite compare un modle alatoire (graphe peu connect). Rseaux (Cafs de lIMT) Nathalie Villa-Vialaneix IMT, 19/01/2012 17 / 20 38. Fouille sur un grand graphe mdival Caractristiques macroscopiques Plus grande composante connexe : 10 025 sommets : petite compare un modle alatoire (graphe peu connect). Pourquoi ? Indivual Transaction 2 groupes denses... Rseaux (Cafs de lIMT) Nathalie Villa-Vialaneix IMT, 19/01/2012 17 / 20 39. Fouille sur un grand graphe mdival Caractristiques macroscopiques Plus grande composante connexe : 10 025 sommets : petite compare un modle alatoire (graphe peu connect). Pourquoi ? 2 groupes denses... ... correspondant deux pri- odes diffrentes Rseaux (Cafs de lIMT) Nathalie Villa-Vialaneix IMT, 19/01/2012 17 / 20 40. Fouille sur un grand graphe mdival Caractristiques macroscopiques Plus grande composante connexe : 10 025 sommets : petite compare un modle alatoire (graphe peu connect). Pourquoi ? Transaction dates Density 1250 1300 1350 1400 1450 1500 0e+003e05 all transactions Jean Roquefeuil Castelnaud Ratier (3rd) Ratier (first) 2 groupes denses... ... correspondant deux pri- odes diffrentes avant et aprs la guerre de Cent ans (et la grande peste) Rseaux (Cafs de lIMT) Nathalie Villa-Vialaneix IMT, 19/01/2012 17 / 20 41. Fouille sur un grand graphe mdival Recherche de communauts Rseaux (Cafs de lIMT) Nathalie Villa-Vialaneix IMT, 19/01/2012 18 / 20 42. Fouille sur un grand graphe mdival Recherche de communauts La visualisation aide reprer les personnes importantes (exemple : Hlne de Castel- nau) Rseaux (Cafs de lIMT) Nathalie Villa-Vialaneix IMT, 19/01/2012 18 / 20 43. Fouille sur un grand graphe mdival Recherche de communauts La visualisation aide identi- er des problmes : Trois classes Jean Laperarede Un lien direct suspicieux Jean Laperarede &amp; Ratier Rseaux (Cafs de lIM...</p>