m

Documents  Critères de recherche : "Random graphs" | enregistrements trouvés : 21

O

-A +A

P Q

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

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

05C50 ; 05C80 ; 68T05 ; 91D30

... Lire [+]

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

- vii; 354 p.
ISBN 978-0-444-70265-4

North-Holland mathematics studies , 0144

Localisation : Colloque 1er étage (POZN)

00Bxx ; 05-06 ; 05C80

... Lire [+]

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

- viii; 363 p.
ISBN 978-0-444-87821-2

North-Holland mathematics studies , 0118

Localisation : Colloque 1er étage (POZN)

graphe aléatoire

00Bxx ; 05-06

... Lire [+]

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

- xv; 519 p.
ISBN 978-1-316-60440-3

London mathematical society lecture note series , 0436

Localisation : Collection 1er étage

marche aléatoire # combinatoire # théorie des groupes # représentation des graphes

05-06 ; 20-06 ; 05C81 ; 05C62 ; 00B25

... Lire [+]

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

Research talks;Combinatorics;Probability and Statistics

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 [+]

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

Research talks;Algebra;Combinatorics;Geometry

Erdös and Rényi introduced a model for studying random graphs of a given "density" and proved that there is a sharp threshold at which lower density random graphs are disconnected and higher density ones are connected. Motivated by ideas in geometric group theory we will explain some new threshold theorems we have discovered for random graphs. We will then explain applications of these results to the geometry of Coxeter groups. Some of this talk will be on joint work with Hagen and Sisto; other parts are joint work with Hagen, Susse, and Falgas-Ravry. Erdös and Rényi introduced a model for studying random graphs of a given "density" and proved that there is a sharp threshold at which lower density random graphs are disconnected and higher density ones are connected. Motivated by ideas in geometric group theory we will explain some new threshold theorems we have discovered for random graphs. We will then explain applications of these results to the geometry of Coxeter groups. Some of this talk ...

05C80 ; 20F65

... Lire [+]

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

Research talks;Combinatorics

05C80

... Lire [+]

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

Research School;Combinatorics

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.

Research talks;Combinatorics;Computer Science;Probability and Statistics

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 [+]

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

Research talks;Combinatorics;Number Theory

The notion of quasi-random graphs was introduced in 1987 by F. R. K. Chung, R. L. Graham and R. M. Wilson, resp. A. Thomason. It has been shown that there is a strong connection between this notion and the pseudorandomness of (finite) binary sequences. This connection can be utilized for constructing large families of quasi-random graphs by considering graphs defined by a circular adjacency matrix whose first column is a binary sequence with strong pseudo-random properties. Starting out from this construction principle one may extend, generalize and sharpen some definitions and results on quasi-randomness of graphs. The notion of quasi-random graphs was introduced in 1987 by F. R. K. Chung, R. L. Graham and R. M. Wilson, resp. A. Thomason. It has been shown that there is a strong connection between this notion and the pseudorandomness of (finite) binary sequences. This connection can be utilized for constructing large families of quasi-random graphs by considering graphs defined by a circular adjacency matrix whose first column is a binary sequence with ...

11K45 ; 11K36 ; 11K31 ; 05C80 ; 05Cxx

... Lire [+]

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

- 158 p.
ISBN 978-0-12-111755-9

Localisation : Ouvrage RdC (BOLL)

05C55 ; 05C80 ; 60Gxx ; 60Hxx

... Lire [+]

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

- 252 p.
ISBN 978-0-521-44081-3

Encyclopedia of mathematics and its applications , 0053

Localisation : Collection 1er étage

graphe aléatoire # mathématiques discrètes # permutation # théorie de probabilité # théorie des graphes

05C80 ; 20B30 ; 60C55

... Lire [+]

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

- 334 p.
ISBN 978-0-521-55292-9

Cambridge tracts in mathematics , 0138

Localisation : Collection 1er étage

probabilité # marche aléatoire # chaîne de Markov # probabilité de transition # problème aux limites # graphe infini # arbre transitoire # fonction de Green # théorie asymptotique

60B15 ; 60G50 ; 60J10

... Lire [+]

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

- 333 p.
ISBN 978-0-471-17541-4

Wiley-interscience series in discrete mathematics and optimization

Localisation : Ouvrage RdC (JANS)

graphe aléatoire # combinatoire # transition de phase # nombre chromatique # probabilité combinatoire # mécanique statistique # distribution asymptotique # propriété de Ramsey

05C80 ; 60C05 ; 82B41

... Lire [+]

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

- 168 p.
ISBN 978-3-540-41654-8

Algorithms and combinatorics , 0022

Localisation : Ouvrage RdC (SPEN)

graphe # logique # graphe aléatoire # logique de premier ordre # structure finie # théorie des modèles # structure dénombrable # loi du zéro-un # structure discrète

05C80 ; 03-02 ; 03B10 ; 03C13 ; 03C15

... Lire [+]

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

- 66 p.
ISBN 978-0-8218-3825-9

Memoirs of the american mathematical society , 0845

Localisation : Collection 1er étage

coloriage de graphe # théorie de Ramsey # graphe aléatoire # phénomène de seuil # lemme de régularité de Szemoridi

05C15 ; 05C55 ; 05C80

... Lire [+]

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

- xi; 247 p.
ISBN 978-0-521-19798-4

Institute of mathematical statistics textbooks

Localisation : Ouvrage RdC (GRIM)

probabilité discrète # percolation # graphe aléatoire

60-02 ; 60G50 ; 60K35 ; 60K40 ; 05C80 ; 82B43

... Lire [+]

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

- xvii; 464 p.
ISBN 978-1-107-11850-8

Localisation : Ouvrage RdC (FRIE)

formation de réseaux # graphe aléatoire # mathématiques discrètes # informatique # probabilités

05-01 ; 05C80 ; 60B20

... Lire [+]

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

- vi; 122 p.
ISBN 978-1-316-50191-7

London mathematical society student texts , 0084

Localisation : Collection 1er étage

graphe aléatoire # géométrie algébrique # topologie

05-02 ; 05-06 ; 05C80 ; 60B20 ; 00B15

... Lire [+]

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

- xi; 226 p.
ISBN 978-1-107-67442-4

London mathematical society lecture note series , 0438

Localisation : Collection 1er étage

isométrie # critère de Foster # propriété de Louville # graphe pondéré # analyse de réseau électrique # inégalité elliptique de Harnack

05-02 ; 05C81 ; 05C22 ; 05C70 ; 35K05 ; 60J10

... Lire [+]

Z