Colloque des sciences mathématiques du Québec

17 octobre 2008 de 16 h 00 à 18 h 00 (heure de Montréal/HNE) Sur place

Random Graphs: New models and the Internet

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

Adresse

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