Supervision : Matthieu LATAPY

Co-supervision : MAGNIEN Clémence

Structure et dynamique des graphes de terrain bipartis : liens internes et prédiction de liens

Beaucoup de graphes de terrain comme les relations acteur-film ou fichier-fournisseur sont modélisables par des graphes bipartis, dont les noeuds sont divisés en deux ensembles avec des liens entre les noeuds de différents ensembles seulement. Cependant, des méthodes manquent actuellement pour analyser correctement ces graphes, la plupart des méthodes existantes étant conçues pour des graphes classiques. Une approche courante, mais limitée, consiste à transformer les graphes bipartis en graphes classiques, par un procédé appelé projection. Cependant ceci entraîne une perte importante d'informations. Nous introduisons dans cette thèse les liens internes, et les proposons comme une nouvelle notion importante pour analyser les graphes de terrain bipartis : elle permet de mesurer la redondance dans ces graphes, et de mesurer la perte d'information entre un graphe biparti et ses projections. Nous montrons en étudiant différents jeux de données que les liens internes sont très fréquents, et que les statistiques associées permettent de souligner leurs ressemblances et leurs différences avec les graphes bipartis aléatoires. Ensuite, nous montrons que nous pouvons tirer profit de cette notion pour modéliser les graphes de terrain bipartis et les stocker dans un format compact.
La plupart des graphes de terrain sont de plus dynamiques, c'est-à-dire que leur structure évolue au fil du temps par l'ajout et/ou le retrait de noeuds et/ou de liens. L'étude de la dynamique des graphes de terrain peut s'aborder par le problème de la prédiction de nouveaux liens dans ces graphes. Plusieurs travaux ont étudié le problème de la prédiction de liens dans les graphes classique (non-bipartis). Toutefois, leurs méthodes ne sont pas directement applicables aux graphes bipartis ou sont inappropriées. Nous proposons une approche basée sur les liens internes pour la prédiction dans les graphes bipartis. Nous montrons que notre méthode fonctionne très bien, beaucoup mieux que l'approche de recommandation classique.

2009-2013 Publications

• 2013
  • O. Allali, L. Tabourier, C. Magnien, M. Latapy : “Internal links and pairs as a new tool for the analysis of bipartite complex networks”, Social Network Analysis and Mining, vol. 3 (1), pp. 85-91, (Springer) (2013)
  • O. Allali, C. Magnien, M. Latapy : “Internal links prediction: a new approach for predicting links in bipartite graphs”, Intelligent Data Analysis, vol. 7 (1), pp. 5-25, (IOS Press) (2013)
• 2011
  • O. Allali : “Structure et dynamique des graphes de terrain bipartis : liens internes et prédiction de liens”, thesis, phd defence 06/24/2011, supervision Latapy, Matthieu, co-supervision : Magnien, Clémence (2011)
  • O. Allali, C. Magnien, M. Latapy : “Link prediction in bipartite graphs using internal links and weighted projection”, third International Workshop on Network Science for Communication Networks (Netscicom 2011), In Conjuction with IEEE Infocom 2011., Shanghai, China, pp. 936-941, (IEEE) (2011)
• 2009
  • O. Allali, M. Latapy, C. Magnien : “Measurement of eDonkey Activity with Distributed Honeypots”, Sixth International Workshop on Hot Topics in Peer-to-Peer Systems (Hot-P2P 2009),, Rome, Italy, pp. 1-8, (IEEE) (2009)