Site de Vincent Gripon

Blog sur mes recherches et mon enseignement

Reconstructing a Graph from Path Traces

V. Gripon et M. Rabbat, "Reconstructing a Graph from Path Traces," dans Proceedings of International Symposium on Information Theory, pp. 2488-2492, juillet 2013.

Ce document s'intéresse au problème d'inférer la structure d'un réseau à partir d'observations indirectes. Chaque observation (une "trace") est un ensemble non ordonné de noeuds qui s'activent le long d'un chemin du réseau. Puisqu'une trace ne contient aucune information à propos de l'ordre des noeuds dans le chemin, il y a beaucoup d'ordres possibles pour chaque trace, et donc le problème d'inférence d'un réseau à partir de traces est, en général, mal posé. Nous proposons et analysons un algorithme qui insère des arêtes en ordonnant chaque trace afin d'en faire un chemin en fonction des paires de noeuds dans le chemin qui apparaissent le plus fréquemment dans l'ensemble des observations. Lorsque toutes les traces impliquent exactement trois noeuds, nous analysons les conditions nécessaires et suffisantes pour que l'algorithme de reconstruction retrouve exactement le graphe initial. Enfin, pour une famille de graphes aléatoires, nous introduisons les probabilités d'erreur de reconstruction (arêtes faussement ajoutées et manquées).

Télécharger le manuscrit.

Bibtex
@inproceedings{GriRab20137,
  author = {Vincent Gripon and Michael Rabbat},
  title = {Reconstructing a Graph from Path Traces},
  booktitle = {Proceedings of International Symposium
on Information Theory},
  year = {2013},
  pages = {2488-2492},
  month = {July},
}




Vous êtes le 842971ème visiteur

Site de Vincent Gripon