H 2 Graphons and graphexes as limits of sparse graphs - lecture 1

Auteurs : Chayes, Jennifer Tour (Auteur de la Conférence)
CIRM (Editeur )

Loading the player...
dense graph limits left convergence right convergence graphon metric convergence equivalent notions of convergence for dense graphs sparse graphs of bounded degree sparse graphs of unbounded degree rescaled convergence stretched convergence non parametric graph modeling estimation and machine learning differentially private estimation recommendation algorithms

Résumé : Graphons and graphexes are limits of graphs which allow us to model and estimate properties of large-scale networks. In this pair of talks, we review the theory of dense graph limits, and give two alterative theories for limits of sparse graphs - one leading to unbounded graphons over probability spaces, and the other leading to bounded graphons (and graphexes) over sigma-finite measure spaces. Talk I, given by Jennifer, will review the general theory, highlight the unbounded graphons, and show how they can be used to consistently estimate properties of large sparse networks. This talk will also give an application of these sparse graphons to collaborative filtering on sparse bipartite networks. Talk II, given by Christian, will recast limits of dense graphs in terms of exchangeability and the Aldous Hoover Theorem, and generalize this to obtain sparse graphons and graphexes as limits of subgraph samples from sparse graph sequences. This will provide a dual view of sparse graph limits as processes and random measures, an approach which allows a generalization of many of the well-known results and techniques for dense graph sequences.

Keywords : sparse graphs; graphex; dense exchangeable graphs; graphon; network data; Aldous Hoover theorem

Codes MSC :
05C60 - Isomorphism problems (reconstruction conjecture, perfect graphs, etc.)
05C80 - Random graphs
60F10 - Large deviations
82B20 - Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs

    Informations sur la Vidéo

    Langue : Anglais
    Date de publication : 11/09/2018
    Date de captation : 28/08/2018
    Collection : Research talks ; Combinatorics
    Format : MP4 (.mp4) - HD
    Durée : 00:48:23
    Domaine : Combinatorics
    Audience : Chercheurs ; Doctorants , Post - Doctorants
    Download : https://videos.cirm-math.fr/2018-08-28_Chayes.mp4

Informations sur la rencontre

Nom de la rencontre : Advances in Statistical Mechanics / Avancées en mécanique statistique
Organisateurs de la rencontre : Arguin, Louis-Pierre ; Gayrard, Véronique ; Kistler, Nicola ; Kourkova, Irina
Dates : 27/08/2018 - 31/08/2018
Année de la rencontre : 2018
URL Congrès : https://conferences.cirm-math.fr/1855.html

Citation Data

DOI : 10.24350/CIRM.V.19442003
Cite this video as: Chayes, Jennifer Tour (2018). Graphons and graphexes as limits of sparse graphs - lecture 1. CIRM. Audiovisual resource. doi:10.24350/CIRM.V.19442003
URI : http://dx.doi.org/10.24350/CIRM.V.19442003

Voir aussi


Titres de périodiques et e-books électroniques (Depuis le CIRM)

Ressources Electroniques

Books & Print journals

Recherche avancée