Degree distributions in AB random geometric graphs

Clara Stegehuis, Lotte Weedage*

*Corresponding author for this work

Research output: Contribution to journalArticleAcademicpeer-review

2 Citations (Scopus)
18 Downloads (Pure)


In this paper, we provide degree distributions for AB random geometric graphs, in which points of type A connect to the closest k points of type B. The motivating example to derive such degree distributions is in 5G wireless networks with multi-connectivity, where users connect to their closest k base stations. In this setting, it is important to know how many users a particular base station serves, which gives the degree of that base station. To obtain these degree distributions, we investigate the distribution of area sizes of the kth order Voronoi cells of B-points. Assuming that the A-points are Poisson distributed, we investigate the amount of users connected to a certain B-point, which is equal to the degree of this point. In the simple case where the B-points are placed in an hexagonal grid, we show that all kth order Voronoi areas are equal and thus all degrees follow a Poisson distribution. However, this observation does not hold for Poisson distributed B-points, for which we show that the degree distribution follows a compound Poisson–Erlang distribution in the 1-dimensional case. We then approximate the degree distribution in the 2-dimensional case with a compound Poisson-Gamma degree distribution and show that this one-parameter fit performs well for different values of k. Moreover, we show that for increasing k, these degree distributions become more concentrated around the mean. This means that k-connected AB random graphs balance the loads of B-type nodes more evenly as k increases. Finally, we provide a case study on real data of base stations. We show that with little shadowing in the distances between users and base stations, the Poisson distribution does not capture the degree distribution of these data, especially for k>1. However, under strong shadowing, our degree approximations perform quite good even for these non-Poissonian location data.

Original languageEnglish
Article number126460
JournalPhysica A: Statistical Mechanics and its Applications
Early online date29 Sept 2021
Publication statusPublished - 15 Jan 2022


  • UT-Hybrid-D


Dive into the research topics of 'Degree distributions in AB random geometric graphs'. Together they form a unique fingerprint.

Cite this