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

Random hyperbolic graphs Kiwi, Marcos | CIRM H

Multi angle

y

Research talks

Random hyperbolic graphs (RHG) were proposed rather recently (2010) as a model of real-world networks. Informally speaking, they are like random geometric graphs where the underlying metric space has negative curvature (i.e., is hyperbolic). In contrast to other models of complex networks, RHG simultaneously and naturally exhibit characteristics such as sparseness, small diameter, non-negligible clustering coefficient and power law degree distribution. We will give a slow pace introduction to RHG, explain why they have attracted a fair amount of attention and then survey most of what is known about this promising infant model of real-world networks. Random hyperbolic graphs (RHG) were proposed rather recently (2010) as a model of real-world networks. Informally speaking, they are like random geometric graphs where the underlying metric space has negative curvature (i.e., is hyperbolic). In contrast to other models of complex networks, RHG simultaneously and naturally exhibit characteristics such as sparseness, small diameter, non-negligible clustering coefficient and power law degree ...

05C80 ; 68Q87 ; 74E35

... Lire [+]

Filtrer

Type
Domaine
Codes MSC

Ressources Electroniques

Books & Print journals

Recherche avancée


0
Z
cord=19274756124910929389&idlist=1" data-alt="0">1

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

Connected chord diagrams, bridgeless maps, and perturbative quantum field theory Yeats, Karen | CIRM H

Multi angle

y

Research talks

Rooted connected chord diagrams can be used to index certain expansions in quantum field theory. There is also a nice bijection between rooted connected chord diagrams and bridgeless maps. I will discuss each of these things as well as how the second sheds light on the first. (Based on work with Nicolas Marie, Markus Hihn, Julien Courtiel, and Noam Zeilberger.)

81T15 ; 81T18 ; 05C80

... Lire [+]

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

Random walk on random digraph Salez, Justin | CIRM H

Multi angle

y

Research talks

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 ...

05C80 ; 05C81 ; 60G50 ; 60J10

... Lire [+]

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

Random cubic planar graphs revisited Rué, Juanjo | CIRM H

Multi angle

y

Research School

We analyze random labelled cubic planar graphs according to the uniform distribution. This model was analyzed first by Bodirsky et al. in a paper from 2007. Here we revisit and extend their work. The motivation for this revision is twofold. First, some proofs where incomplete with respect to the singularity analysis and we provide full proofs. Secondly, we obtain new results that considerably strengthen those known before. For instance, we show that the number of triangles in random cubic planar graphs is asymptotically normal with linear expectation and variance, while formerly it was only known that it is linear with high probability.
This is based on a joint work with Marc Noy (UPC) and Clément Requilé (FU Berlin - BMS).
We analyze random labelled cubic planar graphs according to the uniform distribution. This model was analyzed first by Bodirsky et al. in a paper from 2007. Here we revisit and extend their work. The motivation for this revision is twofold. First, some proofs where incomplete with respect to the singularity analysis and we provide full proofs. Secondly, we obtain new results that considerably strengthen those known before. For instance, we show ...

05C80 ; 05C10 ; 05A16

... Lire [+]

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

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

Multi angle

y

Research talks

05C80

... Lire [+]

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

y

Research talks

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 ...

05C80 ; 60D05 ; 60G55

... Lire [+]

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

Weighted distances in scale free random graphs Komjathy, Julia | CIRM H

Multi angle

y

Research talks

In this talk I will review the recent developments on weighted distances in scale free random graphs as well as highlight key techniques used in the proofs. We consider graph models where the degree distribution follows a power-law such that the empirical variance of the degrees is infinite, such as the configuration model, geometric inhomogeneous random graphs, or scale free percolation. Once the graph is created according to the model definition, we assign i.i.d. positive edge weights to existing edges, and we are interested in the proper scaling and asymptotic distribution of weighted distances.
In the infinite variance degree regime, a dichotomy can be observed in all these graph models: the edge weight distributions form two classes, explosive vs conservative weight distributions. When a distribution falls into the explosive class, typical distances converge in distribution to proper random variables. While, when a distribution falls into the conservative class, distances tend to infinity with the model size, according to a formula that captures the doubly-logarithmic graph distances as well as the precise behaviour of the distribution of edge-weights around the origin. An integrability condition decides into which class a given distribution falls.
This is joint work with Adriaans, Baroni, van der Hofstad, and Lodewijks.
In this talk I will review the recent developments on weighted distances in scale free random graphs as well as highlight key techniques used in the proofs. We consider graph models where the degree distribution follows a power-law such that the empirical variance of the degrees is infinite, such as the configuration model, geometric inhomogeneous random graphs, or scale free percolation. Once the graph is created according to the model ...

05C80 ; 90B15 ; 60C05 ; 60D05

... Lire [+]