Emergence of the Web-Like Networks
by
Narsingh Deo
Professor and Charles E. Millican Eminent-Scholar Chair of Computer Science, University of Central Florida, Orlando, FL 32816

With the dramatic growth of the World Wide Web (Web) and the Internet, the study of large, random networks has acquired new prominence. Recent empirical studies have shown statistical similarities between these and other complex, real-life networks such as the network of phone calls, power-distribution networks, citation network, science-collaboration network, movie-actor collaboration network, neural networks, and various infrastructure networks. The ubiquity and the increasing importance of such networks have spawned a truly cross-disciplinary research aimed at understanding their fundamental properties and functions.

Viewed as large, random graphs in which birth and death of nodes and edges are taking place continuously, these graphs differ from the classical Erdös-Rényi random graphs in significant ways. Some of these differences have recently been discovered through empirical studies of the real-life networks; a great deal more remains to be discovered. In this talk we will present an overview of recently-proposed (by us and others) dynamic random graph models of these complex, large, real-life networks in a unified manner; explain salient techniques (graph-theoretic, statistical, and computational) used in analyzing these models; and discuss the main results derived through these techniques. For instance, how the structural properties of social networks facilitate or impede the spread of diseases, or how the properties of the Internet can be exploited to devise efficient strategies for containing the spread of viruses and worms.

PDF

Date received: June 25, 2007