Multilateration of Random Networks with Community Structure

arXiv1911.01521MaRDI QIDQ6328515

Richard D. Tillquist, Manuel E. Lladser

Publication date: 4 November 2019

Abstract: The minimal number of nodes required to multilaterate a network endowed with geodesic distance (i.e., to uniquely identify all nodes based on shortest path distances to the selected nodes) is called its metric dimension. This quantity is related to a useful technique for embedding graphs in low-dimensional Euclidean spaces and representing the nodes of a graph numerically for downstream analyses such as vertex classification via machine learning. While metric dimension has been studied for many kinds of graphs, its behavior on the Stochastic Block Model (SBM) ensemble has not. The simple community structure of graphs in this ensemble make them interesting in a variety of contexts. Here we derive probabilistic bounds for the metric dimension of random graphs generated according to the SBM, and describe algorithms of varying complexity to find---with high probability---subsets of nodes for multilateration. Our methods are tested on SBM ensembles with parameters extracted from real-world networks. We show that our methods scale well with increasing network size as compared to the state-of-the-art Information Content Heuristic algorithm for metric dimension approximation.

Has companion code repository: https://github.com/riti4538/SBM-Metric-Dimension

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph theory (including graph drawing) in computer science (68R10) Stochastic network models in operations research (90B15) Approximation algorithms (68W25)

This page was built for publication: Multilateration of Random Networks with Community Structure

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6328515)