Premium
Techniques for analyzing dynamic random graph models of web‐like networks: An overview
Author(s) -
Cami Aurel,
Deo Narsingh
Publication year - 2008
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.20215
Subject(s) - degree distribution , computer science , random graph , clustering coefficient , theoretical computer science , salient , random geometric graph , graph , giant component , cluster analysis , dynamic network analysis , exponential random graph models , complex network , artificial intelligence , line graph , voltage graph , world wide web , computer network
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. © 2007 Wiley Periodicals, Inc. NETWORKS, 2008