Séminaire des équipes de recherche

Some implications of local weak convergence for sparse random graphs

Séminaires organisés par l'équipe-projet RAP, entrée libre à 10h30.

  • Date : 17/06/2011
  • Lieu : Rocquencourt, bâtiment 9
  • Intervenants : Justin Salez, TREC, Inria Paris-Rocquencourt
  • Organisateurs : RAP

We investigate the asymptotic behavior of certain graph invariants in the so-called sparse regime, where the numbers of edges and vertices tend to infinity in a comparable way. In many situations, it is believed that those asymptotics should depend only upon local statistics. This idea originates from the thermodynamic study of certain disordered systems in statistical physics, where the microscopic contribution of each particle is insensitive to any perturbation occurring far away from that particle. Mathematically, the lack of long-range interactions can be formalized as continuity with respect to the topology of local weak convergence. Any graph invariant that can be proven to be continuous in that sense is
automatically guaranteed to admit a deterministic limit along most of the classical sequences of sparse random graphs, and to be efficiently approximable via local distributed algorithms, regardless of the size of the global structure. We illustrate this modern approach by focusing on two graph invariants that play an important role in theory and applications : the empirical spectral distribution and the matching number. Each one is shown to admit a unique locally self-consistent extension to infinite graphs, and this extension is continuous with respect to local weak convergence. This leads to new asymptotic formulae for certain popular random graph models and to the simplification, unification and generalization of various results that were previously relying on model-specific arguments.

Mots-clés : Paris - Rocquencourt Séminaire RAP

Haut de page

Siège et centres de recherche Inria

Accès direct

Social