Graph density ρ(G) = 2|E|/(n(n-1)) = |E|/C(n,2). Measures 'fullness': ρ=1 for K_n, ρ=0 for empty. Average degree d̄ = 2|E|/n = ρ(n-1). Erdős-Rényi random graphs: properties emerge at density thresholds.
How to Use
Enter graph:
- ρ: Edge density
- d̄: Average degree
- Class: Sparse/dense
Random Graph Thresholds
In G(n,p): connected at p~ln(n)/n. Giant component at p~1/n. Hamiltonian at p~ln(n)/n. These phase transitions are central to random graph theory (Erdős-Rényi, 1959).
Density Classes
Sparse: |E|=O(n), ρ→0. Examples: trees, planar. Dense: |E|=Θ(n²), ρ→constant. Examples: random G(n,1/2). Between: |E|=Θ(n^α), 1<α<2. Real networks are often sparse but clustered.
Step-by-Step Instructions
- 1Enter n and |E|.
- 2Compute density.
- 3Find average degree.
- 4Classify sparse/dense.
- 5Compare to thresholds.