Accueil/ expose #carousel1 li{ width:150px; height:180px; } #carousel2 li{ width:150px; height:180px; } Clustering of networks : From phase transitions to optimal algorithms
jeudi 26 mars 2015
Loading the player... Descriptif

Conférence de Lenka Zdeborova organisée par le Département de Physique.

A central problem in analyzing networks or graphs is partitioning them into modules or communities, i.e. groups with a statistically homogeneous pattern of connections to each other or to the rest of the network. A principled approach to address this problem is to fit the network on a stochastic block model. This task, however, belongs to the class of very hard algorithmic problems. Still it can be reformulated as the equilibrium statistical mechanics of a particular mean field spin glass model. We apply the cavity method that is standard in studies of spin glasses and structural glasses and compute the associated phase diagram of the problem. We describe consequences of this result for algorithmic resolvability of the clustering problem. Further, we take advantage of the insight gained by the analysis to introduce a new class of spectral algorithms based on a non-backtracking walk on the directed edges of the graph. We show that the algorithm is optimal for graphs generated by the stochastic block model, detecting communities all the way down to the theoretical limit.

Thèmes : Physique
Catégories: Colloquium / Séminaire général du département de physique
Mot-clés : informatique, physique théorique, algorithme, groupe, réseau

Voir aussi

Auteur(s) Lenka Zdeborova
CEA Saclay
Chercheuse

Plus sur cet auteur
Voir la fiche de l'auteur

Cursus :

Lenka Zdeborova est chercheur CNRS à l'Institut de physique théorique (IPhT) du CEA à Saclay. Elle a obtenu son doctorat en physique statistique en 2008 à l'Université Paris-XI. En 2014, elle a reçu la médaille de bronze du CNRS.

Ses champs de recherche : applications de méthodes de la mécanique statistique et de la physique théorique aux problèmes en informatique, théorie de l'information, traitement du signal et de l'apprentissage de la machine.

Cliquer ICI pour fermer Annexes Téléchargements :
   - Télécharger la vidéo
   - Télécharger l'audio (mp3)

Dernière mise à jour : 08/04/2015

Liens utiles

Contact
Partenaires
Conditions d'utilisation
Mentions légales
Podcasts

CYCLES

> Colloquium DEC
> Les Ernest
> Les jeudis de l’archéologie
> Actualité critique
> Les jeudis de l’HPS
> Séminaire Médecine
   Humanités
> Journée Georges Bram
> Les lundis de la philo


> Les Nuits de l’ENS
> Semaine du cerveau
> Séminaire général du
   département d'informatique
> Séminaire général
   de physique
> Séminaire Transferts culturels
> La Voix d’un texte

PARTENARIATS

Louvre

France cuture

Institut Français

RESEAUX SOCIAUX

Retrouvez-nous sur Facebook

Twitter

Savoirs ENS
Tous droits réservés
@ 2011 ENS