Loading...

ITA 2010 - Random Graphs and Large Networks, Dimitris Achlioptas

3,110 views

Loading...

Loading...

Transcript

The interactive transcript could not be loaded.

Loading...

Loading...

Rating is available when the video has been rented.
This feature is not available right now. Please try again later.
Uploaded on May 16, 2011

2010 Information Theory and Applications Workshop
Random Graphs and Large Networks
Dimitris Achlioptas, UC Santa Cruz & RACTI

Abstract: The best-known model of random graphs was introduced 50 years ago, by Erdos and Renyi (ER): take n vertices and connect each pair of them, independently, with probability p(n). By now, and thousands of research papers later, we know that ER random graphs have a number of amazing properties, many of which we understand very well. A bit more slowly we have also come to understand that ER random graphs can be poor models of "network realities": it is impossible to place the vertices of a (typical) ER random graph in a low-dimensional space, so that for each pair of vertices, their geometric distance is a good approximation of their graphical (shortest-path) distance. In other words, ER random graphs are inherently high-dimensional objects, in contrast to many real networks. In this tutorial talk we will survey some of the fundamental results for ER random graphs and use them as springboards to introduce (and compare with) alternative random graph models.

Loading...

When autoplay is enabled, a suggested video will automatically play next.

Up next


to add this to Watch Later

Add to

Loading playlists...