Techniques For Analyzing Dynamic Random Graph Models Of Web-Like Networks: An Overview

Various random graph models have recently been proposed to replicate and explain the topology of large, complex, real-life networks such as the World Wide Web and the Internet. These models are surveyed in this article. Our focus has primarily been on dynamic random graph models that attempt to account for the observed statistical properties of web-like networks through certain dynamic processes guided by simple stochastic rules. Particular attention is paid to the equivalence between mathematical definitions of dynamic random graphs in terms of inductively defined probability spaces and algorithmic definitions of such models in terms of recursive procedures. Several techniques that have been employed for studying dynamic random graphs-both heuristic and analytic-are expounded. Each technique is illustrated through its application in analyzing various graph parameters, such as degree distribution, degreecorrelation between adjacent nodes, clustering coefficient, distribution of node-pair distances, and connected-component size. A discussion of the most recent salient work and a comprehensive list of references in this rapidly-expanding area are included. © 2007 Wiley Periodicals, Inc