Module correlated 

Correlated Erdős–Rényi graph generators (ALGO-GN-023).

Counterparts of igraph_correlated_game() and igraph_correlated_pair_game() from references/igraph/src/games/correlated.c (lines 90-338).

Given a simple old_graph on n vertices with target marginal density p, correlated_game returns a new graph whose adjacency vector has Pearson correlation corr ∈ [0, 1] with that of the original. The construction preserves the marginal density p by solving the elementary 2 × 2 contingency table:

  q     = p + corr · (1 − p)
  p_del = 1 − q                        // P(drop | original edge)
  p_add = (1 − q) · p / (1 − p)        // P(create | original non-edge)

The per-position Bernoullis are sampled via the same Batagelj–Brandes geometric-skip trick used in crate::erdos_renyi_gnp (ALGO-GN-001): two RNG_GEOM streams skip directly over kept-or-skipped edge slots without visiting each O(n²) position. The deletion stream walks the m existing edges (in canonical-code order); the addition stream walks the n(n−1)/2 undirected (or n(n−1) directed) candidate non-edges. A 3-way merge interleaves the kept edges, the deletes, and the additions in sorted code order.

correlated_pair_game is the convenience wrapper that samples an ER(n, p) graph and a correlated counterpart from a single seed.

References

• Pedarsani, P. & Grossglauser, M. (2011). On the privacy of anonymized networks. Proc. SIGKDD.
• Barak, B. et al. (2018). (Nearly) Efficient algorithms for the graph matching problem on correlated random graphs. NeurIPS.

Functions

correlated_game

Generate a random graph whose adjacency vector is Pearson-correlated to that of old_graph at level corr.

correlated_pair_game

Sample two random graphs with target adjacency-vector correlation corr. Builds graph1 via ER(n, p) and graph2 via correlated_game against graph1.