Size of the giant component in a random geometric graph

DOI10.1214/12-AIHP498MaRDI QIDQ376695zbMATH OpenFDO

Authors Ghurumuruhan Ganesan

Publication date 19 November 2013

Published in Annales de l'Institut Henri Poincaré. Probabilités et Statistiques (Search for Journal in Brave)

Full work available at URL https://projecteuclid.org/euclid.aihp/1380718740

zbMATH Keywords

graph diameternumber of componentsrandom geometric graphsize of giant component

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05) Geometric probability and stochastic geometry (60D05)

Review text

A random geometric graph \(G\) is defined with \(n\) nodes that are independently selected according to a common probability distribution with density \(f\) in the unit square. Two nodes are joined by an edge if their distance is less than a specified positive value \(r=r(n)\). The density \(f\) is assumed to have its infimum and its supremum strictly between 0 and infinity. By dividing the unit square into subsquares, so that nodes in adjacent subsquares can be joined by an edge, a technique is developed to investigate the structure of the giant component for a certain range of values of \(r\). Size and diameter are estimated as \(n\) tends to infinity and \(r\) is proportional to the square root of \(1/n\) or of \((\log n)/n\). Both uniform and non-uniform \(f\) are considered.

Recommendations

• Giant component of the soft random geometric graph
• The Asymptotic Size of the Largest Component in Random Geometric Graphs with Some Applications
• Random Geometric Graphs
• On the first and second largest components in the percolated random geometric graph
• Stretch and diameter in random geometric graphs

Cites work

• Closing the Gap in the Capacity of Wireless Networks Via Percolation Theory
• scientific article; zbMATH DE number 1254188 (Why is no real title available?)
• Percolation
• Random Geometric Graphs
• The bin-covering technique for thresholding random geometric graph properties

Cited in

(18)

• Some properties for the largest component of random geometric graphs with applications in sensor networks
• The expected size of some graphs in computational geometry
• The size of the largest hole in a random graph
• Topology of random geometric complexes: a survey
• Threshold for the outbreak of cascading failures in degree-degree uncorrelated networks
• Stretch and diameter in random geometric graphs
• Giant component of the soft random geometric graph
• Giant components in random graphs
• Some introductory notes on random graphs
• Random Geometric Graphs
• Rumors spread slowly in a small-world spatial network
• The Asymptotic Size of the Largest Component in Random Geometric Graphs with Some Applications
• Infection spread in random geometric graphs
• Giant Component and Connectivity in Geographical Threshold Graphs
• scientific article; zbMATH DE number 7651057 (Why is no real title available?)
• Dynamic geometric graph processes: Adjacency operator approach
• On the first and second largest components in the percolated random geometric graph
• Bridged Hamiltonian cycles in sub-critical random geometric graphs

This page was built for publication: Size of the giant component in a random geometric graph

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