Skip to main content

imm_algorithm

scirs2_graph::diffusion::ris

Function imm_algorithm 

Source 
pub fn imm_algorithm(
    adjacency: &AdjList,
    num_nodes: usize,
    config: &ImmConfig,
) -> Result<ImmResult>
Expand description

IMM (Influence Maximization via Martingales) algorithm.

Implements the IMM algorithm of Tang et al. (SIGMOD 2014/2015) which achieves a (1 – 1/e – ε)-approximation guarantee with probability 1 – δ while generating a near-optimal number of RR sets.

The number of RR sets θ is determined by the following formula:

θ = (8 + 2ε) · n · (ℓ · log(n) + log(C(n,k)) + log(2)) / (ε² · OPT_k)

where OPT_k is a lower bound on the optimal spread (estimated via binary search over the Martingale condition).

§Arguments

  • adjacency — directed adjacency list with propagation probabilities.
  • num_nodes — total number of nodes.
  • config — algorithm configuration.

§Errors

Returns an error when parameters are invalid or num_nodes == 0.