Quebec Mathematical Sciences Colloquium

October 17, 2008 from 16:00 to 18:00 (Montreal/Miami time) On location

Random Graphs: New models and the Internet

Colloquium presented by Svante Janson (Uppsala University)

Random graphs have been more or less successfully applied to many real-life problems. One important example is the Internet, which can be regarded as a very large graph. This graph can in practise not be described exactly, and to study various properties, such as vulnerability to intentional or accidental disruptions, it is natural to study random models However, the classical random graph models are often too homogeneous to be good approximations. In particular, in the Internet and many other real-life examples, it is observed that the vertex degrees (number of adjacent edges) vary a lot, often with a power-law distribution of the high degrees. This has served as a source of inspiration for random graph theorists, and during the last 10 years, a number of new random graph models have been introduced and studied in order to mimic the Internet or other similar graphs. This illustrates that not only can mathematics be useful for applications; conversely, applications can stimulate new theoretical developments. I will give some examples from the Internet and describe some different random graph models that have been proposed.


Pavillon André-Aisenstadt, Université de Montréal, 2920, ch. de la Tour, Salle / Room 1360