A distance-dependent random graph model and its analysis
Stochastic Models, 2026 (SCI-Expanded, Scopus)
- Publication Type: Article / Article
- Publication Date: 2026
- Doi Number: 10.1080/15326349.2026.2647764
- Journal Name: Stochastic Models
- Journal Indexes: Science Citation Index Expanded (SCI-EXPANDED), Scopus, Compendex, MathSciNet, zbMATH
- Keywords: Complex networks, dependent random graphs, integer partitions, random permutation graphs, unfair permutations
- Middle East Technical University Affiliated: No
Abstract
Let (Formula presented.) be non-negative random variables. We consider an undirected random graph model on the node set (Formula presented.), where two nodes (Formula presented.) are adjacent if (Formula presented.). In our setting, the (Formula presented.) ‘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 (Formula presented.) with node (Formula presented.) located at position (Formula presented.) —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.