Research
Research
Entropy of Soft Random Geometric Graphs
Entropy of Soft Random Geometric Graphs
A soft random geometric graph is a set of nodes embedded in a domain, which are connected in a probabilistic manner depending on their mutual distance. This creates a highly clustered network, which is very useful for modelling certain real-world scenarios, such as wireless sensor networks, social networks and biological networks.
This work finds application in wireless communication networks. As a general example, suppose that two nodes wish to communicate across the network. Establishing a route requires access to (at least partial) topological information about the network. Sending the entire network is expensive, since the number of bits of information that needs to be sent grows quadratically in the number of nodes. Therefore, it is desirable to send a compressed representation. Information-theoretic limits on the size of the compressed representation is governed by the entropy of the network.
To this end, I am currently working on the following projects, which are at various levels of completion.
1) Distributed Compression of Soft Random Geometric Graphs
In decentralised or peer-to-peer settings, no single entity typically has access to the full network state. If each node only knows its own neighbourhood and is not allowed to exchange side information with other nodes, can the network still be compressed in an information-theoretically optimal way?
Perhaps surprisingly, the answer is yes (in an asymptotic sense under the model assumptions). If each node is assigned a rate budget for encoding its local neighbourhood, we show that the minimum achievable rate is asymptotically equal to the entropy of that neighbourhood. This provides a theoretical benchmark for how much information must be communicated, even under severe decentralisation constraints.
2) Entropy of Soft Random Geometric Graphs Above the Connectivity Threshold
Much of our earlier work focuses on dense regimes. To move towards more realistic settings, we also study regimes in which the expected proportion of neighbours per node vanishes as the network size grows.
In this setting, boundary effects of the spatial domain become negligible in the large-network limit. In particular, we show that the entropy per edge converges to the same limit across a broad class of domains, provided the spatial dimension is fixed.
We also are working on compressing these (relatively) 'sparse' networks by estimating the positions of the nodes using graph distances.
3) Lossy Compression of Soft Random Geometric Graphs
Lossy compression is the study of compressing sources where we allow a small amount of error in exchange for reduced compression length. The tradeoff can be made precise using what is known as rate distortion theory. We proved some bounds on the mutual information between a soft random geometric graph and its node locations, which turns out to be useful in characterising the best achievable compression rate subject to a given amount of distortion.
4) Entropy of Soft Random Geometric Graphs with Mobile Nodes
In many real network applications, the nodes of the network are not stationary, but can move over time. In this work we plan to look at how much information is required to represent the network when the nodes are mobile. We aim to look into the random fluctuations of this quantity, and expect this to be useful in adaptively allocating compression rates for networks of moving entities.