On Compression Limits for Random Geometric Graphs

28 January 2020

It is known that many real-world networks exhibit geometric properties.  Brain networks, social networks, and wireless communication networks are a few examples.  Storage and transmission of the information contained in the topologies and structures of these networks are important tasks, which, given their scale, is often nontrivial.  Although some (but not much) work has been done to characterize and develop compression limits and algorithms for nonspatial graphs, little is known for the spatial case.  In this talk, we will discuss an information theoretic formalism for studying compression limits for a fairly broad class of random geometric graphs.  We will then discuss entropy bounds for these graphs and, time permitting, local (pairwise) connection rules that yield maximum entropy properties in the induced graph distribution.