Nonuniform random graphs on the plane: A scaling study.

Area of Science:

• Graph Theory
• Computational Geometry
• Statistical Physics

Background:

• Random geometric graphs are crucial for modeling complex networks.
• Existing models often assume uniform vertex distribution, limiting applicability.
• Nonuniform vertex distributions are common in real-world systems.

Purpose of the Study:

• To introduce and analyze a novel random geometric graph model with nonuniform vertex density.
• To characterize the topological and spectral properties of this model.
• To investigate the scaling behavior of graph measures with respect to model parameters.

Main Methods:

• Utilized polar coordinates (l, θ) for vertex distribution within a unit disk.
• Defined vertex connection based on Euclidean distance and a connection radius ℓ.
• Employed average degree (〈k〉), nonisolated vertices (V×), eigenvalue spacing ratio (r), and Shannon entropy (S) for characterization.
• Derived heuristic expressions and analyzed scaling properties of normalized measures.

Main Results:

• Proposed a heuristic expression for the average degree 〈k(n,σ,ℓ)〉.
• Demonstrated that average degree 〈k〉 scales the normalized number of nonisolated vertices 〈V×〉/n, with 〈V×〉/n ≈ 1 - exp(-〈k〉).
• Showed that spectral measures 〈r〉 and 〈S〉 scale with n⁻γ〈k〉, where γ ≈ 0.16.

Conclusions:

• The proposed random geometric graph model captures essential features of nonuniformly distributed networks.
• Average degree is a key parameter governing both topological and spectral properties.
• The findings offer a framework for analyzing complex networks with heterogeneous vertex distributions.