Document Open Access Logo

A Quest to Unravel the Metric Structure Behind Perturbed Networks

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

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2017.53.pdf
  • Filesize: 0.71 MB
  • 16 pages

Document Identifiers

Author Details

Srinivasan Parthasarathy
David Sivakoff
Minghao Tian
Yusu Wang

Cite As Get BibTex

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) https://doi.org/10.4230/LIPIcs.SoCG.2017.53

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.

Subject Classification

Keywords
  • metric structure
  • Erdös-Rényi perturbation
  • graphs
  • doubling measure

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Morteza Alamgir and Ulrike V. Luxburg. Shortest path distance in random k-nearest neighbor graphs. In 29th Intl. Conf. Machine Learning (ICML), pages 1031-1038, 2012. Google Scholar
  2. D. Asta and C. Shalizi. Geometric network comparisons. In 31st Annu. Conf. Uncertainty in AI (UAI), 2015. Google Scholar
  3. Xiaomeng Ban, Rik Sarkar, and Jie Gao. Local connectivity tests to identify wormholes in wireless networks. In 12th ACM International Symposium on Mobile Ad Hoc Networking and Computing, MobiHoc'11, pages 13:1-13:11. ACM, 2011. Google Scholar
  4. HS Bhadauria and ML Dewal. Efficient denoising technique for CT images to enhance brain hemorrhage segmentation. Journal of digital imaging, 25(6):782-791, 2012. Google Scholar
  5. Bela Bollobás and Fan R. K. Chung. The diameter of a cycle plus a random matching. SIAM Journal on discrete mathematics, 1(3):328-333, 1988. Google Scholar
  6. Béla Bollobás and Oliver M. Riordan. Mathematical results on scale-free random graphs. Handbook of graphs and networks: from the genome to the internet, pages 1-34, 2003. Google Scholar
  7. Martin R Bridson and André Haefliger. Metric spaces of non-positive curvature, volume 319. Springer Science &Business Media, 2011. Google Scholar
  8. Frédéric Chazal, Leonidas J Guibas, Steve Y. Oudot, and Primoz Skraba. Persistence-based clustering in riemannian manifolds. Journal of the ACM (JACM), 60(6):41, 2013. Google Scholar
  9. Rick Durrett. Random Graph Dynamics, volume 20. Cambridge University Press, 2006. Google Scholar
  10. Justin Eldridge, Mikhail Belkin, and Yusu Wang. Graphons, mergeons, and so on! In Advances in Neural Information Processing Systems, pages 2307-2315, 2016. Google Scholar
  11. Michalis Faloutsos, Petros Faloutsos, and Christos Faloutsos. On power-law relationships of the internet topology. ACM SIGCOMM Computer Comm. Review, 29(4):251-262, 1999. Google Scholar
  12. Debra S. Goldberg and Frederick P. Roth. Assessing experimentally derived interactions in a small world. Proceedings of the National Academy of Sciences, 100(8):4372-4376, 2003. Google Scholar
  13. Juha Heinonen. Lectures on analysis on metric spaces. Springer Science &Business Media, 2012. Google Scholar
  14. G. Joshi-Tope, Marc Gillespie, Imre Vastrik, Peter D'Eustachio, Esther Schmidt, Bernard de Bono, Bijay Jassal, G. R. Gopinath, G. R. Wu, Lisa Matthews, et al. Reactome: a knowledgebase of biological pathways. Nucleic acids research, 33(suppl 1):D428-D432, 2005. Google Scholar
  15. Jon Kleinberg. The small-world phenomenon: An algorithmic perspective. In Proc. 32nd. ACM Symp. Theory Computing, pages 163-170. ACM, 2000. Google Scholar
  16. Jon Kleinberg. Small-world phenomena and the dynamics of information. In Advances in Neural Information Processing Systems (NIPS), pages 431-438. 2002. Google Scholar
  17. Elizabeth A. Leicht, Petter Holme, and Mark E. J. Newman. Vertex similarity in networks. Physical Review E, 73(2):026120, 2006. Google Scholar
  18. Tiancheng Lou and Jie Tang. Mining structural hole spanners through information diffusion in social networks. In WWW'13, 2013. Google Scholar
  19. S. Parthasarathy, D. Sivakoff, M. Tian, and Y. Wang. A quest to unravel the metric structure behind perturbed networks. ArXiv e-prints, March 2017. URL: http://arxiv.org/abs/1703.05475.
  20. Mathew Penrose. Random geometric graphs. Oxford University Press, 2003. Google Scholar
  21. Venu Satuluri, Srinivasan Parthasarathy, and Yiye Ruan. Local graph sparsification for scalable clustering. In ACM SIGMOD Intl. Conf. Management Data, pages 721-732, 2011. Google Scholar
  22. A. Singer and H.-T. Wu. Two-dimensional tomography from noisy projections taken at unknown random directions. SIAM journal on imaging sciences, 6(1):136-175, 2013. Google Scholar
  23. H. F. Song and X.-J. Wang. Simple, distance-dependent formulation of the Watts-Strogatz model for directed and undirected small-world networks. Phys. Rev. E, 90:062801, 2014. Google Scholar
  24. Xiao Fan Wang and Guanrong Chen. Complex networks: small-world, scale-free and beyond. Circuits and Systems Magazine, IEEE, 3(1):6-20, 2003. Google Scholar
  25. Duncan J. Watts, Peter Sheridan Dodds, and M. E. J. Newman. Identity and search in social networks. Science, 296(5571):1302-1305, 2002. URL: http://dx.doi.org/10.1126/science.1070120.
  26. Duncan J. Watts and Steven H. Strogatz. Collective dynamics of ‘small-world’networks. nature, 393(6684):440-442, 1998. Google Scholar
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 About DROPS Imprint Privacy Contact