Entropy of Spatial Network Ensembles

Justin P Coon, Carl Dettmann, Orestis Georgiou

Research output: Contribution to journalArticle (Academic Journal)peer-review

5 Citations (Scopus)
235 Downloads (Pure)

Abstract

We analyze complexity in spatial network ensembles through the lens of graph entropy. Mathematically, we model a spatial network as a soft random geometric graph, i.e., a graph with two sources of randomness, namely nodes located randomly in space and links formed independently between pairs of nodes with probability given by a specified function (the "pair connection function") of their mutual distance. We consider the general case where randomness arises in node positions as well as pairwise connections (i.e., for a given pair distance, the corresponding edge state is a random variable). Classical random geometric graph and exponential graph models can be recovered in certain limits. We derive a simple bound for the entropy of a spatial network ensemble and calculate the conditional entropy of an ensemble given the node location distribution for hard and soft (probabilistic) pair connection functions. Under this formalism, we derive the connection function that yields maximum entropy under general constraints. Finally, we apply our analytical framework to study two practical examples: ad hoc wireless networks and the US flight network. Through the study of these examples, we illustrate that both exhibit properties that are indicative of nearly maximally entropic ensembles.
Original languageEnglish
Article number042319
Number of pages7
JournalPhysical Review E
Volume97
Issue number4
Early online date25 Apr 2018
DOIs
Publication statusPublished - Apr 2018

Fingerprint Dive into the research topics of 'Entropy of Spatial Network Ensembles'. Together they form a unique fingerprint.

Cite this