Canal-U

Mon compte
CEREMADE - UMR 7534

Massoulié - Planting trees in graphs, and finding them back


Copier le code pour partager la vidéo :
<div style="position:relative;padding-bottom:56.25%;padding-top:10px;height:0;overflow:hidden;"><iframe src="https://www.canal-u.tv/video/ceremade/embed.1/massoulie_planting_trees_in_graphs_and_finding_them_back.53797?width=100%&amp;height=100%" style="position:absolute;top:0;left:0;width:100%;height: 100%;" width="550" height="306" frameborder="0" allowfullscreen scrolling="no"></iframe></div> Si vous souhaitez partager une séquence, indiquez le début de celle-ci , et copiez le code : h m s
Auteur(s) :
Massoulié Laurent

Producteur Canal-U :
CEREMADE - UMR 7534
Contacter le contributeur
J’aime
Imprimer
partager facebook twitter Google +

Massoulié - Planting trees in graphs, and finding them back

In this talk we  consider detection and reconstruction of planted structures in Erdős-Rényi random graphs. For planted line graphs, we establish the following phase diagram. In a low density region where the average degree λ of the initial graph is below some critical value λc, detection and reconstruction go from impossible to easy as the line length K crosses some critical value f(λ)ln(n), where n is the number of nodes in the graph. In the high density region λ>λc, detection goes from impossible to easy as K goes from o(\sqrt{n}) to ω(\sqrt{n}), and reconstruction remains impossible so long as K=o(n). We show similar properties for planted D-ary trees. These results are in contrast with the corresponding picture for detection and reconstruction of low rank planted structures, such as dense subgraphs and block communities: We observe a discrepancy between detection and reconstruction, the latter being impossible for a wide range of parameters where detection is easy. This property does not hold for previously studied low rank planted structures.

  •  
  •  
    Date de réalisation : 2 Juillet 2019
    Lieu de réalisation : École Normale Supérieure, Paris.
    Durée du programme : 42 min
    Classification Dewey : Probabilités et mathématiques appliquées
  •  
    Catégorie : Conférences, Cours magistraux, Séminaires
    Niveau : niveau Doctorat (LMD), Recherche
    Disciplines : Mathématiques et informatique, Probabilités
    Collections : PSL Summer School on High Dimensional Probability and Algorithms - HDPA 2019
    ficheLom : Voir la fiche LOM
  •  
    Auteur(s) : Massoulié Laurent
    producteur : Boyer Claire, Chafaï Djalil, Lehec Joseph
  •  
    Langue : Anglais
    Mots-clés : random graph
 

commentaires


Ajouter un commentaire Lire les commentaires
*Les champs suivis d’un astérisque sont obligatoires.
Aucun commentaire sur cette vidéo pour le moment (les commentaires font l’objet d’une modération)
 

Dans la même collection

 Tropp 9/9 - Random matrix theory and computational linear algebra
 Tropp 8/9 - Random matrix theory and computational linear algebra
 Carpentier - Introduction to some problems of composite and minimax hypothesis testing
 Tropp 7/9 - Random matrix theory and computational linear algebra
 Tropp 6/9 - Random matrix theory and computational linear algebra
 Bubeck 9/9 - Some geometric aspects of randomized online decision making
 Bubeck 8/9 - Some geometric aspects of randomized online decision making
 Zdeborová - Loss landscape and behaviour of algorithms in the spiked matrix-tensor model
 Tropp 5/9 - Random matrix theory and computational linear algebra
 Bubeck 7/9 - Some geometric aspects of randomized online decision making
 Bubeck 6/9 - Some geometric aspects of randomized online decision making
 Bubeck 5/9 - Some geometric aspects of randomized online decision making
 Verzelen - Clustering with the relaxed K-means
 Tropp 4/9 - Random matrix theory and computational linear algebra
 Tropp 3/9 - Random matrix theory and computational linear algebra
 Bubeck 3/9 - Some geometric aspects of randomized online decision making
 Klopp - Sparse Network Estimation
 De Castro - Spectral convergence of random graphs and a focus on random geometric graphs
 Tropp 2/9 - Random matrix theory and computational linear algebra
 Tropp 1/9 - Random matrix theory and computational linear algebra
 Bubeck 4/9 - Some geometric aspects of randomized online decision making
 Bubeck 2/9 - Some geometric aspects of randomized online decision making
 Bubeck 1/9 - Some geometric aspects of randomized online decision making
FMSH
 
Facebook Twitter Google+
Mon Compte