Module ris 

Reverse Influence Sampling (RIS) and the IMM algorithm.

This module implements Reverse Influence Sampling (RIS) for influence maximisation, including:

• generate_rr_sets: Generate Reverse Reachable (RR) sets under the IC model.
• ris_estimate: Estimate influence spread using a collection of RR sets.
• imm_algorithm: IMM (Influence Maximization via Martingales, Tang 2014/2015).
• sandwich_approximation: Upper/lower bound for spread using two seed sets.

Algorithm Overview

An RR set for a node v is the set of nodes that can reach v in a random sample of the graph. A seed set S covers an RR set R_v iff S ∩ R_v ≠ ∅, which happens precisely when v would be activated starting from S.

IMM iteratively generates a growing pool of RR sets guided by a Martingale stopping condition, then finds the maximum-coverage seed set via greedy set-cover (approximation ratio (1 – 1/e – ε)).

References

• Borgs, C., Brautbar, M., Chayes, J., & Lucier, B. (2014). Maximizing Social Influence in Nearly Optimal Time. SODA 2014.
• Tang, Y., Xiao, X., & Shi, Y. (2014). Influence Maximization: Near-Optimal Time Complexity Meets Practical Efficiency. SIGMOD 2014.
• Tang, Y., Shi, Y., & Xiao, X. (2015). Influence Maximization in Near-Linear Time: A Martingale Approach. SIGMOD 2015.
• Borg, I., & Groenen, P. J. F. (2005). Sandwich approximation for submodular maximization.

Structs

ImmConfig

Configuration for the IMM algorithm.

ImmResult

Result returned by the IMM algorithm.

RISConfig

Configuration for RIS-based influence maximisation.

Functions

generate_rr_sets

Generate a collection of Reverse Reachable sets under the IC model.

imm_algorithm

IMM (Influence Maximization via Martingales) algorithm.

ris_estimate

Estimate the expected spread of a seed set using a pre-generated pool of RR sets.

sandwich_approximation

Sandwich approximation for submodular maximisation.

Type Aliases

RRSet

A Reverse Reachable (RR) set: the set of nodes that could activate a randomly chosen target node v in a sampled IC-model graph.