Models of large-scale real-life networks

Duration: 1 hour 1 min 57 secs

About this item

Description:	http://www.talks.cam.ac.uk/talk/index/22080


Created:	2010-06-09 11:30
Collection:	Computer Laboratory Wednesday Seminars
Publisher:	University of Cambridge
Copyright:	Computer Laboratory
Language:	eng (English)


Abstract:	In the last fifty years or so, much research has been done on various models of random graphs in mathematics, computer science and physics. Among the families of models that mathematicians have worked on over the years, two stand out: the mean-field models, whose study was started by Erd˝os and R´enyi in the late 1950s, and the percolation models, based on lattices and lattice-like infinite graphs, introduced by Broadbent and Hammersley at about the same time. By now, we have elaborate and deep theories of random subgraphs of complete graphs and of percolation on lattices. It was realized only fairly recently that random graph models may be very important in the study of massive graphs that occur in real life, like the graph of the World Wide Web, or various biological networks. These graphs are too big to describe precisely, and even if we could get all the information about them, this information could not be handled efficiently. It seems that the best we can do is model them as well as we can, and study the model. At the first sight it is surprising that the best models seem to be random graphs, although this is much less surprising if we realize that many of these graphs arise by a mixture of deterministic constructions and random decisions. In the talk we shall review a number of these models, and present several results about them, including some I have obtained jointly with Oliver Riordan and Svante Janson.

Abstract:

In the last fifty years or so, much research has been done on various models of random graphs in mathematics, computer science and physics. Among the families of models that mathematicians have worked on over the years, two stand out: the mean-field models, whose study was started by Erd˝os and R´enyi in the late 1950s, and the percolation models, based on lattices and lattice-like infinite graphs, introduced by Broadbent and Hammersley at about the same time. By now, we have elaborate and deep theories of random subgraphs of complete graphs and of percolation on lattices.

It was realized only fairly recently that random graph models may be very important in the study of massive graphs that occur in real life, like the graph of the World Wide Web, or various biological networks. These graphs are too big to describe precisely, and even if we could get all the information about them, this information could not be handled efficiently. It seems that the best we can do is model them as well as we can, and study the model. At the first sight it is surprising that the best models seem to be random graphs, although this is much less surprising if we realize that many of these graphs arise by a mixture of deterministic constructions and random decisions.

In the talk we shall review a number of these models, and present several results about them, including some I have obtained jointly with Oliver Riordan and Svante Janson.

Available Formats

Format	Quality	Bitrate	Size
MPEG-4 Video	480x360	1.84 Mbits/sec	856.81 MB	View	Download
WebM	480x360	337.5 kbits/sec	150.79 MB	View	Download
Flash Video	480x360	803.74 kbits/sec	365.18 MB	View	Download
Flash Video	320x240	437.27 kbits/sec	198.67 MB	View	Download
iPod Video	480x360	505.24 kbits/sec	229.55 MB	View	Download
MP3	44100 Hz	125.02 kbits/sec	56.59 MB	Listen	Download
Auto *	(Allows browser to choose a format it supports)