Skip to main content

Module dotproduct

rust_igraph::algorithms::games

Module dotproduct 

Source
Expand description

Random dot-product graph generator (ALGO-GN-022).

Counterpart of igraph_dot_product_game() from references/igraph/src/games/dotproduct.c:59-102.

§Model — Random Dot-Product Graph (RDPG)

Every vertex i ∈ [0, n) carries a latent position vector v_i ∈ R^d. For every unordered pair (i, j) with i < j (undirected) or ordered pair (i, j) with i ≠ j (directed), the edge probability is

    p_{i,j} = v_i · v_j   (Euclidean inner product, length d)

and the edge is realised by a single Bernoulli(p_{i,j}) draw. The latent positions are caller-supplied — this generator only consumes them and never tries to fit them. See Nickel (2006) and Young–Scheinerman (2007) for the construction’s properties (degree distribution as a function of position-vector marginals, etc.).

§Clamp semantics (mirroring the C reference exactly)

Latent inner products are not guaranteed to live in [0, 1]. The C reference resolves the three regimes deterministically:

  • prob < 0 → no edge added. Sets the negative_warning flag on the first occurrence so callers can audit (caller-side warning, no eprintln! here).
  • prob > 1 → edge always added, no RNG draw consumed (the C reference deliberately short-circuits past RNG_UNIF01). Sets the over_one_warning flag on the first occurrence.
  • 0 ≤ prob ≤ 1 → a single RNG_UNIF01() < prob draw decides.

The PRNG-draw count therefore depends on how many pairs fall in the [0, 1] band — exactly mirroring the C kernel. Conformance is structural (vcount, directed flag, simple-by-construction, no self-loops, edge-count bound) rather than bit-exact because SplitMix64 is not bit-portable to upstream’s glibc-style stream.

§Construction guarantees

  • Never produces a self-loop. The i == j slot is short- circuited explicitly in the directed loop; the undirected loop starts j at i + 1 so it cannot reach i.
  • Always simple. Each (un)ordered pair is inspected exactly once, so multi-edges are impossible by construction.
  • Bounded edge count: at most n · (n − 1) / 2 undirected, at most n · (n − 1) directed.

§Determinism

Reproducible given (vecs, directed, seed) against the shared SplitMix64 PRNG.

Structs§

DotProductWarnings
Outcome of dot_product_game_with_warnings.

Functions§

dot_product_game
Sample a random dot-product graph (Nickel 2006) — silent variant.
dot_product_game_with_warnings
Sample a random dot-product graph from caller-supplied latent position vectors and report whether clamp regimes were hit.