Title

Techniques for analyzing dynamic random graph models of web-like networks: An overview

Authors

Authors

A. Cami;N. Deo

Comments

Authors: contact us about adding a copy of your work at STARS@ucf.edu

Abbreviated Journal Title

Networks

Keywords

scale-free networks; web graphs; dynamic random graphs; SMALL-WORLD NETWORKS; SCALE-FREE NETWORKS; COMPLEX NETWORKS; DEGREE; SEQUENCE; GROWING NETWORKS; EVOLVING NETWORKS; WIDE-WEB; INTERNET; TOPOLOGY; EVOLUTION; Computer Science, Hardware & Architecture; Operations Research &; Management Science

Abstract

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, degree-correlation 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. (C) 2007 Wiley Periodicals, Inc.

Journal Title

Networks

Volume

51

Issue/Number

4

Publication Date

1-1-2008

Document Type

Review

Language

English

First Page

211

Last Page

255

WOS Identifier

WOS:000257048800001

ISSN

0028-3045

Share

COinS