Title: Scale-free Random Graphs Models of Real-Life Networks

Speaker: Bela Bollobas, University of Cambridge

Date: Tuesday April 15, 2003, 4:30-5:30

Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ

Abstract:

Watts and Strogatz observed in 1998 that many large-scale real-world networks, including neural networks, power grids, collaboration graphs, and the internet, have numerous common features that resemble properties of random graphs. It was also realized that the standard mean-field and lattice-based random graphs are not appropriate models of these large-scale networks, so we should look for other classes of random graphs. One of the main features demanded of these new random graphs is that they should be scale-free. The first such model, introduced by Barab\'asi and Albert in 1999, has been extensively studied from heuristic and experimental points of view. By now, numerous models of scale-free random graphs have been proposed and studied, mostly by computer simulations and heuristic analysis.

In the talk we shall review a number of these models, and present several recent rigorous results obtained jointly with Oliver Riordan. Two of the important characteristics of graphs that we shall consider are robustness, i.e., resistance to random damage, and vulnerability, i.e., vulnerability to malicious attack. We also hope to mention some results proved with Noam Berger, Christian Borgs and Jennifer Chayes.