Title

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

Keywords

Dynamic random graphs; Scale-free networks; Web graphs

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, 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.

Publication Date

7-1-2008

Publication Title

Networks

Volume

51

Issue

4

Number of Pages

211-255

Document Type

Article

Personal Identifier

scopus

DOI Link

https://doi.org/10.1002/net.20215

Socpus ID

51449104504 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/51449104504

This document is currently not available here.

Share

COinS