Théorie des réseaux : le problème de prédiction de liens manquants

Résumé

Le but de ce mémoire est la description du problème des liens manquants dans la théorie des réseaux ainsi que le développement et le test de cinq méthodes de prédiction de liens manquants, à savoir la méthode aléatoire, la méthode du produit des degrés, la méthode des triangles, la méthode des communautés et la méthode hiérarchique. Nous nous concentrerons surtout sur une méthode basée sur le principe de la hiérarchie dans un réseau et dont le développement est particulièrement intéressant à cause de ses fondements mathématiques : nous commencerons par la construction d'une fonction de vraisemblance à deux paramètres que nous maximiserons afin de trouver les valeurs optimales d'un de ces paramètres. L'optimisation du deuxième paramètre sera effectuée en considérant une chaîne de Markov que nous modéliserons par un algorithme de la classe Markov Chain Monte Carlo. Nous ajouterons à cet algorithme la règle de Metropolis-Hastings pour optimaliser les pas considérés par l'algorithme.
Nous appliquerons ces méthodes à des réseaux réels et nous comparerons l'efficacité de ces méthodes en utilisant la mesure Area Under Curve (AUC). Grâce à un exemple nous montrerons comment la prédiction de liens manquants peut être appliquée dans la vie réelle, et plus particulièrement dans les stratégies de marketing d'une entreprise.

la date de réponse	17 janv. 2013
langue originale	Français
L'institution diplômante	Universite de Namur
Superviseur	Renaud Lambiotte (Promoteur), Timoteo Carletti (Jury), Jean-Charles DELVENNE (Jury) & Andre Fuzfa (Jury)