Skip to main content

static_fitness_game

Function static_fitness_game 

Source
pub fn static_fitness_game(
    no_of_edges: u32,
    fitness_out: &[f64],
    fitness_in: Option<&[f64]>,
    loops: bool,
    multiple: bool,
    seed: u64,
) -> IgraphResult<Graph>
Expand description

Sample a random graph from the static-fitness model (Goh–Kahng–Kim 2001).

  • no_of_edges — exact number of edges to generate.
  • fitness_out — non-negative, finite per-vertex fitness. Length determines the resulting graph’s vertex count n. Higher values mean a vertex is more likely to be picked as the (out-)endpoint of each edge; the expected (out-)degree is proportional to the fitness, but unlike Chung–Lu the realised degrees fluctuate around that mean and the total edge count is fixed.
  • fitness_in — when Some, generates a directed graph with independent out- and in-fitness. Must have the same length as fitness_out. When None, generates an undirected graph.
  • loops — when true, self-loops are permitted (and may be sampled).
  • multiple — when true, parallel edges are permitted; when false, every accepted edge is unique.
  • seed — initialises an internal SplitMix64 PRNG so the output is reproducible given the inputs.

§Errors

Returns IgraphError::InvalidArgument if:

  • any fitness value is negative, NaN, or non-finite (±∞);
  • fitness_in length differs from fitness_out length;
  • the upper-bound max_no_of_edges is zero but no_of_edges > 0 (e.g. one-vertex graph without self-loops, or all-zero fitness);
  • !multiple && no_of_edges > max_no_of_edges (impossible to pack that many unique edges into the available slots);
  • the requested vertex count exceeds the u32::MAX bound on VertexId (or the more conservative 2^53 upper bound).

§Complexity

O(|V| + |E| log |V|) — the per-edge log |V| comes from the cumulative-fitness binary search; for multiple = false an extra O(log d_i) (here O(1) amortised via HashSet) per accepted edge is added for the duplicate check.

§Examples

use rust_igraph::static_fitness_game;

// Five vertices, decaying fitness, 8 undirected simple edges.
let fitness = [5.0, 4.0, 3.0, 2.0, 1.0];
let g = static_fitness_game(8, &fitness, None, false, false, 42).unwrap();
assert_eq!(g.vcount(), 5);
assert_eq!(g.ecount(), 8);
assert!(!g.is_directed());