EECS Joint Colloquium Distinguished Lecture Series

Wednesday, January 22, 2003
Hewlett Packard Auditorium, 306 Soda Hall
4:00-5:00 p.m.

Professor Bela Bollobas

Hardin Chair of Excellence in Combinatorics,
Dept. of Mathematical Sciences,
University of Memphis


Models of Large-Scale Real-World Networks




In 1998, Watts and Strogatz observed 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 was introduced by Barabasi and Albert in 1999; 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, and shall mention some even more recent results proved jointly with Christian Borgs, Jennifer Chayes and Oliver Riordan.


Bela Bollobas is the holder of the Jabie Hardin Chair of Excellence in Combinatorics at the University of Memphis, and for well over thirty years has been a Fellow of Trinity College, Cambridge, England. He has worked extensively in functional analysis, discrete geometry, combinatorics and probability theory; for the past ten years or so he has been working almost exclusively in extremal and probabilistic combinatorics, and various applications of these fields.

He has published about 300 papers and eight books, including Extremal Graph Theory, Random Graphs, Linear Analysis, and Modern Graph Theory. He has had close to forty Ph.D. students, including a Fields Medalist; four of his former students teach at Cambridge. He has given main talks at a host of international conferences. In addition to trying to spend time in Memphis and Cambridge, he is a frequent visitor to the Institute for Advanced Study in Princeton, the Mathematical Institute in Budapest, and the Theory Group at Microsoft Research in Redmond, near Seattle.