Monday, September 21st, 2015 | 4pm-5pm | Burnside 1205 |

McGill University

Random Models Of 21st Century Networks And Their Connectivity Structure

The traditional Erdos-‐Renyi model of a random network is of little use in modeling the type of complex networks which modern researchers study. It postulates that each node has the same likelihood of being attached to every other node. However, in, e.g. the web, certain authoritative pages will have many more links entering them. A 1995 paper of Molloy and Reed, cited over 1500 times, sets out some conditions guaranteeing the existence of a giant component in a uniformly random network with a specified degree sequence. This work has attracted such a great deal of attention because it can be applied to random models of a wide range of complicated 21st century networks such as the web or biological networks operating at a sub-‐molecular level. A heuristic argument suggests that a giant component will exist provided the sum of the squares of the degrees of the nodes of the network is at least twice the sum of the degrees. Molloy and Reed proved that this is indeed true subject to certain technical conditions. Many authors, have obtained related results by specifying different technical conditions, or by tying down the size of the giant component. Since the interest in this result is its wide applicability, it is natural to try and prove it under as few assumptions as possible. Recently, Joos, Perarnau-‐Llobet, Rautenbach, and Reed characterized for which degree sequences giant components will exist, except for those in a very small exceptional set. I will present, in an accessible way, a variety of complex networks and their random models to which the Molloy-‐Reed result has been applied. I will then sketch the proof of our result and how it differs from the proof of the Molloy-‐Reed result.