1 Search Results for "Sivakoff, David"

Document
DOI: 10.4230/LIPIcs.SoCG.2017.53
A Quest to Unravel the Metric Structure Behind Perturbed Networks

Authors: Srinivasan Parthasarathy, David Sivakoff, Minghao Tian, and Yusu Wang

Published in: LIPIcs, Volume 77, 33rd International Symposium on Computational Geometry (SoCG 2017)

Abstract
Graphs and network data are ubiquitous across a wide spectrum of scientific and application domains. Often in practice, an input graph can be considered as an observed snapshot of a (potentially continuous) hidden domain or process. Subsequent analysis, processing, and inferences are then performed on this observed graph. In this paper we advocate the perspective that an observed graph is often a noisy version of some discretized 1-skeleton of a hidden domain, and specifically we will consider the following natural network model: We assume that there is a true graph G^* which is a certain proximity graph for points sampled from a hidden domain X; while the observed graph G is an Erdos-Renyi type perturbed version of G^*. Our network model is related to, and slightly generalizes, the much-celebrated small-world network model originally proposed by Watts and Strogatz. However, the main question we aim to answer is orthogonal to the usual studies of network models (which often focuses on characterizing / predicting behaviors and properties of real-world networks). Specifically, we aim to recover the metric structure of G^* (which reflects that of the hidden space X as we will show) from the observed graph G. Our main result is that a simple filtering process based on the Jaccard index can recover this metric within a multiplicative factor of 2 under our network model. Our work makes one step towards the general question of inferring structure of a hidden space from its observed noisy graph representation. In addition, our results also provide a theoretical understanding for Jaccard-Index-based denoising approaches.
Cite as

Srinivasan Parthasarathy, David Sivakoff, Minghao Tian, and Yusu Wang. A Quest to Unravel the Metric Structure Behind Perturbed Networks. In 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, pp. 53:1-53:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{parthasarathy_et_al:LIPIcs.SoCG.2017.53,
  author =	{Parthasarathy, Srinivasan and Sivakoff, David and Tian, Minghao and Wang, Yusu},
  title =	{{A Quest to Unravel the Metric Structure Behind Perturbed Networks}},
  booktitle =	{33rd International Symposium on Computational Geometry (SoCG 2017)},
  pages =	{53:1--53:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-038-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{77},
  editor =	{Aronov, Boris and Katz, Matthew J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2017.53},
  URN =		{urn:nbn:de:0030-drops-72112},
  doi =		{10.4230/LIPIcs.SoCG.2017.53},
  annote =	{Keywords: metric structure, Erd\"{o}s-R\'{e}nyi perturbation, graphs, doubling measure}
}
  • Refine by Author
  • 1 Parthasarathy, Srinivasan
  • 1 Sivakoff, David
  • 1 Tian, Minghao
  • 1 Wang, Yusu

  • Refine by Classification

  • Refine by Keyword
  • 1 Erdös-Rényi perturbation
  • 1 doubling measure
  • 1 graphs
  • 1 metric structure

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2017

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact