Connectivity and Structure in Large Networks

Connectivity and Structure in Large Networks

Rupei Xu (University of Texas at Dallas, USA) and András Faragó (University of Texas at Dallas, USA)
Copyright: © 2016 |Pages: 16
DOI: 10.4018/978-1-4666-9964-9.ch007
OnDemand PDF Download:


Graph models play a central role in the description of real life complex networks. They aim at constructing graphs that describe the structure of real systems. The resulting graphs, in most cases, are random or random-like; so it is not surprising that there is a large literature on various classes of random graphs and networks. Our key motivating observation is that often it is unclear how the strength of the different models compare to each other, e.g., when will a certain model class contain another. We are particularly interested in random graph models that arise via (generalized) geometric constructions. This is motivated by the fact that these graphs can well capture wireless communication networks. We set up a general framework to compare the strength of random network models, and present some results about the equality, inequality and proper containment of certain model classes.
Chapter Preview

Classes Of Random Graph Models

General Random Graph Models

Let us first explain what we mean by random graphs and a random graph model in the most general sense. In full generality, by a random graph on n vertices we mean a random variable that takes its values in the set of all undirected graphs. on n vertices. (We use the words vertex and node interchangeably.) Let us denote a random graph on n nodes by Gn. At this point, it is still completely general, it can be generated by any mechanism, with arbitrary dependencies among its parts, it is just any graph-valued random variable, taking its values among undirected graphs on n nodes.

  • Definition 1. General Random Graph Model: A random graph model is given by a sequence of graph valued random variables, one for each possible value of n:

The family of all such models is denoted by GEN.

Complete Chapter List

Search this Book: