A Distance-Dependent Random Graph Model and Its Analysis

Abstract

Let W-1,..., Wn be non-negative random variables. We consider an undirected random graph model on the node set {1,. ..,n}, where two nodes i < j are adjacent if W-i < W-j. In our setting, the Wi's are independent but not necessarily identically distributed, resulting in a model that generalizes the classical random permutation graphs. The model exhibits a certain dependence among the edges. Moreover, when nodes have physical interpretations- such as points on the real line R with node i located at position x = i-the model gains spatial structure and becomes, in particular, distance-dependent. We derive theoretical results on degree distributions, the number of isolated vertices, and the number of close neighbors. Simulation-based observations are also provided for the average clustering and the global efficiency.