m
• E

F Nous contacter

0

# Documents  Virág, Bálint | enregistrements trouvés : 6

O

P Q

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

## Non-backtracking spectrum of random graphs: community detection and non-regular Ramanujan graphs Massoulié, Laurent | CIRM H

Post-edited

Research talks;Combinatorics;Computer Science;Probability and Statistics

A non-backtracking walk on a graph is a directed path such that no edge is the inverse of its preceding edge. The non-backtracking matrix of a graph is indexed by its directed edges and can be used to count non-backtracking walks of a given length. It has been used recently in the context of community detection and has appeared previously in connection with the Ihara zeta function and in some generalizations of Ramanujan graphs. In this work, we study the largest eigenvalues of the non-backtracking matrix of the Erdos-Renyi random graph and of the Stochastic Block Model in the regime where the number of edges is proportional to the number of vertices. Our results confirm the "spectral redemption" conjecture that community detection can be made on the basis of the leading eigenvectors above the feasibility threshold. A non-backtracking walk on a graph is a directed path such that no edge is the inverse of its preceding edge. The non-backtracking matrix of a graph is indexed by its directed edges and can be used to count non-backtracking walks of a given length. It has been used recently in the context of community detection and has appeared previously in connection with the Ihara zeta function and in some generalizations of Ramanujan graphs. In this work, we ...

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

## Spectral measures of factor of i.i.d. processes on the regular tree Backhausz, Ágnes | CIRM H

Multi angle

Research talks;Combinatorics;Probability and Statistics

We prove that a measure on $[-d,d]$ is the spectral measure of a factor of i.i.d. process on a vertex-transitive infinite graph if and only if it is absolutely continuous with respect to the spectral measure of the graph. Moreover, we show that the set of spectral measures of factor of i.i.d. processes and that of $\bar{d}_2$-limits of factor of i.i.d. processes are the same.

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

## Random walk on random digraph Salez, Justin | CIRM H

Multi angle

Research talks;Combinatorics;Probability and Statistics

A finite ergodic Markov chain exhibits cutoff if its distance to equilibrium remains close to its initial value over a certain number of iterations and then abruptly drops to near 0 on a much shorter time scale. Originally discovered in the context of card shuffling (Aldous-Diaconis, 1986), this remarkable phenomenon is now rigorously established for many reversible chains. Here we consider the non-reversible case of random walks on sparse directed graphs, for which even the equilibrium measure is far from being understood. We work under the configuration model, allowing both the in-degrees and the out-degrees to be freely specified. We establish the cutoff phenomenon, determine its precise window and prove that the cutoff profile approaches a universal shape. We also provide a detailed description of the equilibrium measure. A finite ergodic Markov chain exhibits cutoff if its distance to equilibrium remains close to its initial value over a certain number of iterations and then abruptly drops to near 0 on a much shorter time scale. Originally discovered in the context of card shuffling (Aldous-Diaconis, 1986), this remarkable phenomenon is now rigorously established for many reversible chains. Here we consider the non-reversible case of random walks on sparse ...

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

## Random irregular graphs are nearly Ramanujan Puder, Doron | CIRM H

Multi angle

Research talks;Combinatorics

05C80

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

## Anchored expansion in the hyperbolic Poisson Voronoi tessellation Paquette, Elliot | CIRM H

Multi angle

Research talks;Combinatorics;Probability and Statistics

We show that random walk on a stationary random graph with positive anchored expansion and exponential volume growth has positive speed. We also show that two families of random triangulations of the hyperbolic plane, the hyperbolic Poisson Voronoi tessellation and the hyperbolic Poisson Delaunay triangulation, have 1-skeletons with positive anchored expansion. As a consequence, we show that the simple random walks on these graphs have positive speed. We include a section of open problems and conjectures on the topics of stationary geometric random graphs and the hyperbolic Poisson Voronoi tessellation. We show that random walk on a stationary random graph with positive anchored expansion and exponential volume growth has positive speed. We also show that two families of random triangulations of the hyperbolic plane, the hyperbolic Poisson Voronoi tessellation and the hyperbolic Poisson Delaunay triangulation, have 1-skeletons with positive anchored expansion. As a consequence, we show that the simple random walks on these graphs have positive ...

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

## Zeros of Gaussian analytic functions and determinantal point processes Hough, J. Ben ; Krishnapur, Manjunath ; Peres, Yuval ; Virág, Bálint | American Mathematical Society 2009

Ouvrage

- ix; 154 p.
ISBN 978-0-8218-4373-4

University lecture series , 0051

Localisation : Collection 1er étage

processus gaussiens # fonctions analytiques # polynômes

#### Filtrer

##### Codes MSC

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

Ressources Electroniques

Books & Print journals

Recherche avancée

0
Z