Random rectangular graphs

Ernesto Estrada, Matthew James Sheerin

Research output: Book/ReportOther report

Abstract

A generalization of the random geometric graph (RGG) model is proposed by considering a set of points uniformly and independently distributed on a rectangle of unit area instead of on a unit square [0; 1]2 : The topological properties, such as connectivity, average degree, average path length and clustering, of the random rectangular graphs (RRGs) generated by this model are then studied as a function of the rectangle sides lengths a and b = 1=a, and
the radius r used to connect the nodes. When a = 1 we recover the RGG, and when a ! 1 the very elongated rectangle generated resembles a one-dimensional RGG. We provided computational and analytical evidence that the topological properties of the RRG differ significantly from those of the RGG. The connectivity of the RRG depends not only on the number of nodes as in the case of the RGG, but also on the side length of the rectangle. As the rectangle is more elongated the critical radius for connectivity increases following first a power-law and then a linear trend. Also, as the rectangle becomes more elongated the average distance between the nodes of the graphs increases, but the local cliquishness of the graphs also increases thus producing graphs which are relatively long and highly locally connected. Finally, we found the analytic expression for the average degree in the RRG as a function of the rectangle side lengths and the radius. For different values of the side length, the expected and the observed values of the average degree display excellent correlation,
with correlation coefficients larger than 0.9999.
LanguageEnglish
PublisherUniversity of Strathclyde
Number of pages21
Publication statusUnpublished - 9 Feb 2015

Fingerprint

Random Geometric Graph
Rectangle
Graph in graph theory
Connectivity
Radius
Topological Properties
Vertex of a graph
Unit of area
Linear Trend
Locally Connected
Average Distance
Geometric Model
Graph Model
Path Length
Correlation coefficient
Set of points
Power Law
Clustering
Unit

Keywords

  • random rectangular graphs
  • random geometric graph
  • clustering
  • rectangle unit area

Cite this

Estrada, E., & Sheerin, M. J. (2015). Random rectangular graphs. University of Strathclyde.
Estrada, Ernesto ; Sheerin, Matthew James. / Random rectangular graphs. University of Strathclyde, 2015. 21 p.
@book{49e154b0c48d4d8fb8278b8fbef63aeb,
title = "Random rectangular graphs",
abstract = "A generalization of the random geometric graph (RGG) model is proposed by considering a set of points uniformly and independently distributed on a rectangle of unit area instead of on a unit square [0; 1]2 : The topological properties, such as connectivity, average degree, average path length and clustering, of the random rectangular graphs (RRGs) generated by this model are then studied as a function of the rectangle sides lengths a and b = 1=a, andthe radius r used to connect the nodes. When a = 1 we recover the RGG, and when a ! 1 the very elongated rectangle generated resembles a one-dimensional RGG. We provided computational and analytical evidence that the topological properties of the RRG differ significantly from those of the RGG. The connectivity of the RRG depends not only on the number of nodes as in the case of the RGG, but also on the side length of the rectangle. As the rectangle is more elongated the critical radius for connectivity increases following first a power-law and then a linear trend. Also, as the rectangle becomes more elongated the average distance between the nodes of the graphs increases, but the local cliquishness of the graphs also increases thus producing graphs which are relatively long and highly locally connected. Finally, we found the analytic expression for the average degree in the RRG as a function of the rectangle side lengths and the radius. For different values of the side length, the expected and the observed values of the average degree display excellent correlation,with correlation coefficients larger than 0.9999.",
keywords = "random rectangular graphs, random geometric graph, clustering, rectangle unit area",
author = "Ernesto Estrada and Sheerin, {Matthew James}",
year = "2015",
month = "2",
day = "9",
language = "English",
publisher = "University of Strathclyde",

}

Estrada, E & Sheerin, MJ 2015, Random rectangular graphs. University of Strathclyde.

Random rectangular graphs. / Estrada, Ernesto; Sheerin, Matthew James.

University of Strathclyde, 2015. 21 p.

Research output: Book/ReportOther report

TY - BOOK

T1 - Random rectangular graphs

AU - Estrada, Ernesto

AU - Sheerin, Matthew James

PY - 2015/2/9

Y1 - 2015/2/9

N2 - A generalization of the random geometric graph (RGG) model is proposed by considering a set of points uniformly and independently distributed on a rectangle of unit area instead of on a unit square [0; 1]2 : The topological properties, such as connectivity, average degree, average path length and clustering, of the random rectangular graphs (RRGs) generated by this model are then studied as a function of the rectangle sides lengths a and b = 1=a, andthe radius r used to connect the nodes. When a = 1 we recover the RGG, and when a ! 1 the very elongated rectangle generated resembles a one-dimensional RGG. We provided computational and analytical evidence that the topological properties of the RRG differ significantly from those of the RGG. The connectivity of the RRG depends not only on the number of nodes as in the case of the RGG, but also on the side length of the rectangle. As the rectangle is more elongated the critical radius for connectivity increases following first a power-law and then a linear trend. Also, as the rectangle becomes more elongated the average distance between the nodes of the graphs increases, but the local cliquishness of the graphs also increases thus producing graphs which are relatively long and highly locally connected. Finally, we found the analytic expression for the average degree in the RRG as a function of the rectangle side lengths and the radius. For different values of the side length, the expected and the observed values of the average degree display excellent correlation,with correlation coefficients larger than 0.9999.

AB - A generalization of the random geometric graph (RGG) model is proposed by considering a set of points uniformly and independently distributed on a rectangle of unit area instead of on a unit square [0; 1]2 : The topological properties, such as connectivity, average degree, average path length and clustering, of the random rectangular graphs (RRGs) generated by this model are then studied as a function of the rectangle sides lengths a and b = 1=a, andthe radius r used to connect the nodes. When a = 1 we recover the RGG, and when a ! 1 the very elongated rectangle generated resembles a one-dimensional RGG. We provided computational and analytical evidence that the topological properties of the RRG differ significantly from those of the RGG. The connectivity of the RRG depends not only on the number of nodes as in the case of the RGG, but also on the side length of the rectangle. As the rectangle is more elongated the critical radius for connectivity increases following first a power-law and then a linear trend. Also, as the rectangle becomes more elongated the average distance between the nodes of the graphs increases, but the local cliquishness of the graphs also increases thus producing graphs which are relatively long and highly locally connected. Finally, we found the analytic expression for the average degree in the RRG as a function of the rectangle side lengths and the radius. For different values of the side length, the expected and the observed values of the average degree display excellent correlation,with correlation coefficients larger than 0.9999.

KW - random rectangular graphs

KW - random geometric graph

KW - clustering

KW - rectangle unit area

M3 - Other report

BT - Random rectangular graphs

PB - University of Strathclyde

ER -

Estrada E, Sheerin MJ. Random rectangular graphs. University of Strathclyde, 2015. 21 p.