Connectivity of Random Annulus Graphs and the Geometric Block Model
Document Open Access Logo

Connectivity of Random Annulus Graphs and the Geometric Block Model

Authors Sainyam Galhotra, Arya Mazumdar, Soumyabrata Pal, Barna Saha

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2019.53.pdf
  • Filesize: 0.58 MB
  • 23 pages

Document Identifiers

Author Details

Sainyam Galhotra
  • University of Massachusetts Amherst, USA
Arya Mazumdar
  • University of Massachusetts Amherst, USA
Soumyabrata Pal
  • University of Massachusetts Amherst, USA
Barna Saha
  • University of California, Berkeley, USA

Funding

S. Galhotra and B. Saha are supported in part by NSF 1652303, a Google award and a Sloan fellowship. A. Mazumdar and S. Pal are supported in part by NSF 1642658 and 1642550.

Cite As Get BibTex

Sainyam Galhotra, Arya Mazumdar, Soumyabrata Pal, and Barna Saha. Connectivity of Random Annulus Graphs and the Geometric Block Model. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 53:1-53:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2019.53

Abstract

Random geometric graph (Gilbert, 1961) is a basic model of random graphs for spatial networks proposed shortly after the introduction of the Erdős-Rényi random graphs. The geometric block model (GBM) is a probabilistic model for community detection defined over random geometric graphs (RGG) similar in spirit to the popular stochastic block model which is defined over Erdős-Rényi random graphs. The GBM naturally inherits many desirable properties of RGGs such as transitivity ("friends having common friends') and has been shown to model many real-world networks better than the stochastic block model. Analyzing the properties of a GBM requires new tools and perspectives to handle correlation in edge formation. In this paper, we study the necessary and sufficient conditions for community recovery over GBM in the connectivity regime. We provide efficient algorithms that recover the communities exactly with high probability and match the lower bound within a small constant factor. This requires us to prove new connectivity results for vertex-random graphs or random annulus graphs which are natural generalizations of random geometric graphs. 
A vertex-random graph is a model of random graphs where the randomness lies in the vertices as opposed to an Erdős-Rényi random graph where the randomness lies in the edges. A vertex-random graph G(n, [r_1, r_2]), 0 <=r_1 <r_2 <=1 with n vertices is defined by assigning a real number in [0,1] randomly and uniformly to each vertices and adding an edge between two vertices if the "distance" between the corresponding two random numbers is between r_1 and r_2. For the special case of r_1=0, this corresponds to random geometric graph in one dimension. We can extend this model naturally to higher dimensions; these higher dimensional counterparts are referred to as random annulus graphs. Random annulus graphs appear naturally whenever the well-known Goldilocks principle ("not too close, not too far') holds in a network. In this paper, we study the connectivity properties of such graphs, providing both necessary and sufficient conditions. We show a surprising long edge phenomena for vertex-random graphs: the minimum gap for connectivity between r_1 and r_2 is significantly less when r_1 >0 vs when r_1=0 (RGG). We then extend the connectivity results to high dimensions. These results play a crucial role in analyzing the GBM.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Random graphs
Keywords
  • random graphs
  • geometric graphs
  • community detection
  • block model

Metrics

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

Related Versions

References

  1. Emmanuel Abbe, Afonso S. Bandeira, and Georgina Hall. Exact Recovery in the Stochastic Block Model. IEEE Trans. Information Theory, 62(1):471-487, 2016. Google Scholar
  2. Emmanuel Abbe and Colin Sandon. Community detection in general stochastic block models: Fundamental limits and efficient algorithms for recovery. In 56th Annual Symposium on Foundations of Computer Science (FOCS), pages 670-688, 2015. Google Scholar
  3. Austin R Benson, David F Gleich, and Jure Leskovec. Higher-order organization of complex networks. Science, 353(6295):163-166, 2016. Google Scholar
  4. Béla Bollobás. Random Graphs. Cambridge Press, 2001. Google Scholar
  5. Béla Bollobás. Percolation. Cambridge Press, 2006. Google Scholar
  6. Sébastien Bubeck, Jian Ding, Ronen Eldan, and Miklós Z Rácz. Testing for high-dimensional geometry in random graphs. Random Structures & Algorithms, pages 503-532, 2016. Google Scholar
  7. Peter Chin, Anup Rao, and Van Vu. Stochastic block model and community detection in sparse graphs: A spectral algorithm with optimal rate of recovery. In Conference on Learning Theory (COLT), pages 391-423, 2015. Google Scholar
  8. Aurelien Decelle, Florent Krzakala, Cristopher Moore, and Lenka Zdeborová. Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications. Physical Review E, 84(6):066106, 2011. Google Scholar
  9. Carl P Dettmann and Orestis Georgiou. Random geometric graphs with general connection functions. Physical Review E, 93(3):032313, 2016. Google Scholar
  10. Martin E. Dyer and Alan M. Frieze. The solution of some random NP-hard problems in polynomial expected time. Journal of Algorithms, 10(4):451-489, 1989. Google Scholar
  11. David Easley and Jon Kleinberg. Networks, crowds, and markets. Cambridge Books, 2012. Google Scholar
  12. Paul Erdös and Alfréd Rényi. On random graphs, I. Publicationes Mathematicae (Debrecen), 6:290-297, 1959. Google Scholar
  13. Stephen Eubank, Hasan Guclu, VS Anil Kumar, Madhav V Marathe, Aravind Srinivasan, Zoltan Toroczkai, and Nan Wang. Modelling disease outbreaks in realistic urban social networks. Nature, 429(6988):180, 2004. Google Scholar
  14. Ehud Friedgut and Gil Kalai. Every monotone graph property has a sharp threshold. Proceedings of the American mathematical Society, 124(10):2993-3002, 1996. Google Scholar
  15. Sainyam Galhotra, Arya Mazumdar, Soumyabrata Pal, and Barna Saha. The Geometric Block Model. In The Thirty-Second AAAI Conference on Artificial Intelligence (AAAI-18), 2018. Google Scholar
  16. Sainyam Galhotra, Arya Mazumdar, Soumyabrata Pal, and Barna Saha. Connectivity in random annulus graphs and the geometric block model. arXiv preprint, 2019. URL: http://arxiv.org/abs/1804.05013.
  17. Edgar N Gilbert. Random graphs. The Annals of Mathematical Statistics, 30(4):1141-1144, 1959. Google Scholar
  18. Edward N Gilbert. Random plane networks. Journal of the Society for Industrial and Applied Mathematics, 9(4):533-543, 1961. Google Scholar
  19. Martin Haenggi, Jeffrey G Andrews, François Baccelli, Olivier Dousse, and Massimo Franceschetti. Stochastic geometry and random graphs for the analysis and design of wireless networks. IEEE Journal on Selected Areas in Communications, 27(7):1029-1046, 2009. Google Scholar
  20. Bruce E. Hajek, Yihong Wu, and Jiaming Xu. Computational Lower Bounds for Community Detection on Random Graphs. In Proceedings of The 28th Conference on Learning Theory (COLT), pages 899-928, 2015. URL: http://proceedings.mlr.press/v40/Hajek15.html.
  21. David Haussler and Emo Welzl. epsilon-nets and simplex range queries. Discrete & Computational Geometry, 2(2):127-151, 1987. Google Scholar
  22. Paul W Holland, Kathryn Blackmond Laskey, and Samuel Leinhardt. Stochastic blockmodels: First steps. Social networks, 5(2):109-137, 1983. Google Scholar
  23. Jure Leskovec, Kevin J Lang, Anirban Dasgupta, and Michael W Mahoney. Statistical properties of community structure in large social and information networks. In 17th international conference on World Wide Web, pages 695-704, 2008. Google Scholar
  24. Elchanan Mossel, Joe Neeman, and Allan Sly. Consistency thresholds for the planted bisection model. In 47th Annual ACM Symposium on Theory of Computing (STOC), pages 69-75, 2015. Google Scholar
  25. S Muthukrishnan and Gopal Pandurangan. The bin-covering technique for thresholding random geometric graph properties. In Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms (SODA), pages 989-998, 2005. Google Scholar
  26. Mathew Penrose. Random geometric graphs. Oxford University Press, 2003. Google Scholar
  27. Mathew D Penrose. Connectivity of soft random geometric graphs. The Annals of Applied Probability, 26(2):986-1028, 2016. Google Scholar
  28. Abishek Sankararaman and François Baccelli. Community Detection on Euclidean Random Graphs. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2181-2200, 2018. Google Scholar
  29. Charalampos E Tsourakakis, Jakub Pachocki, and Michael Mitzenmacher. Scalable motif-aware graph clustering. In Proceedings of the 26th International Conference on World Wide Web (WWW), pages 1451-1460, 2017. Google Scholar
  30. Stephen J Young and Edward R Scheinerman. Random dot product graph models for social networks. In International Workshop on Algorithms and Models for the Web-Graph, pages 138-149, 2007. Google Scholar
  31. Weituo Zhang, Chjan C Lim, Gyorgy Korniss, and Boleslaw K Szymanski. Opinion dynamics and influencing on random geometric graphs. Scientific reports, Nature Publishing Group, 4:5568, 2014. 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