Erdos-Renyi G(n,p)

Formula: each of the C(n,2) possible edges is present independently with probability p. Realised on a DETERMINISTIC low-discrepancy stream – edge slot k is compared against p using van der Corput base PRIMES[k mod 12], so successive dyads are not correlated the way one shared stream would make them, and both language arms build the identical graph.

Usage

Erdosg(n, p)

Arguments

n

Number of vertices (>= 1).

p

Edge probability in [0, 1].

Value

List with estimate, edges, density, expected_edges, mean_degree, expected_degree, n_components, largest_component, giant_threshold, connectivity_threshold, n, method.

Details

PROVENANCE: the binomial model G(n,p) is Gilbert (1959). Erdos & Renyi (1959) defined G(n,M), the uniform model on graphs with exactly M edges; the two are asymptotically equivalent but not the same construction, and the usual name for G(n,p) is a misattribution.

Alongside the realised graph the exact analytic quantities are returned: E[edges] = C(n,2) p, E[degree] = (n-1) p, the connectivity threshold log(n)/n and the giant-component threshold 1/n.

References

Gilbert (1959), Ann. Math. Statist. 30(4):1141-1144, doi:10.1214/aoms/1177706098; Erdos & Renyi (1959), Publ. Math. Debrecen 6:290-297 (the G(n,M) model).

Examples

Erdosg(n = 5L, p = 0.5)
#> $estimate
#> [1] 0.9
#> 
#> $edges
#> [1] 9
#> 
#> $density
#> [1] 0.9
#> 
#> $expected_edges
#> [1] 5
#> 
#> $mean_degree
#> [1] 3.6
#> 
#> $expected_degree
#> [1] 2
#> 
#> $n_components
#> [1] 1
#> 
#> $largest_component
#> [1] 5
#> 
#> $giant_threshold
#> [1] 0.2
#> 
#> $connectivity_threshold
#> [1] 0.3218876
#> 
#> $n
#> [1] 5
#> 
#> $method
#> [1] "Erdos-Renyi G(n,p)"
#> 
#> attr(,"class")
#> [1] "morie_rich_result" "list"