The dynamics of complex networks

by Fan Chung

Date

Saturday, May 6, 2006

Time

1:00 p.m.

Place

Lindley Hall, Room 102

Abstract

We discuss some recent results and methods for analyzing large and evolving information networks. Both on-line and off-line random graph models will be considered. The analysis has made use of two tools -- a general framework for comparing different random graph models and a general martingale inequality that requires only a weak Lipschitz condition. By coupling the on-line model with the off-line model for random power law graphs, we examine an addition-deletion model and derive sharp bounds for a number of graph properties including diameter, average distances, connected components and spectral bounds. We will also discuss algorithmic implications of these structural properties and mention a number of related problems on complex networks.

Biography

Fan Chung Graham received a B.S. degree in mathematics from National Taiwan University in 1970 and a Ph.D. in mathematics from the University of Pennsylvania in 1974, after which she joined the technical staff of AT&T Bell Laboratories. From 1983 to 1991, she headed the Mathematics, Information Sciences and Operations Research Division at Bellcore. In 1991 she became a Bellcore Fellow. In 1993, she was the Class of 1965 Professor of Mathematics at the the University of Pennsylvania. Since 1998, she has been a Professor of Mathematics and Professor of Computer Science and Enginering at the University of California, San Diego. She is also the Akamai Professor in Internet Mathematics. Her research interests are primarily in graph theory, combinatorics, and algorithmic design, in particular in spectral graph theory, extremal graphs, graph labeling, graph decompositions, random graphs, graph algorithms, parallel structures and various applications of graph theory in Internet computing, communication networks, software reliability, chemistry, engineering, and various areas of mathematics. She was awarded the Allendoerfer Award by Mathematical Association of America in 1990. Since 1998, she has been a member of the American Academy of Arts and Sciences.

Colloquium provided by:

Distinguished Invited Lecture,
52nd Midwest Theory Day