Independent Cascades

The Independent Cascades (IC) model [1] describes information diffusion or contagion processes on a static graph \(G=(V,E)\), where each node can be either active (infected and recovered) or inactive (susceptible). Once a node becomes active, it gets one chance to activate each of its inactive neighbors with a given probability (infected); whether or not it succeeds, it has no more chance to activate others (recovered).

Implementation

Independent Cascades is the special case of the SIR Model, where :math: gamma=1.

Node transitions follow two rules: 1) if a \(S\) state node has \(I\) state neighbors, each \(I\) state neighbor transmits the infection to the \(S\) state node with probability \(\beta\); 2) the \(I\) state node is recovered to the \(R\) state with probability \(1\).

Node states are represented by two Boolean indicator vectors \(h, r \in \{0,1\}^N\):

• \(h_i=1\) denotes infected (Active)

• \(r_i=1\) denotes recovered (Active)

• \((h_i,r_i)=(0,0)\) denotes susceptible (Inactive)

The update of the system at step \(k\) is decomposed into three stages:

1. Each infected neighbor \(j\) of node \(i\) transmits a log-probability contribution

\[m_{ji}^{(k)} = h_j^{(k-1)} \cdot \log(1-\beta)\]

2. Node \(i\) collects contributions from all neighbors \(N(i)\) to compute its infection probability

\[m_i^{(k)} = 1 - \exp\!\left( \sum_{j \in N(i)} m_{ji}^{(k)} \right)\]

3. The indicator variables are updated with independent uniform random variables \(U_i^{\mathrm{inf}}, U_i^{\mathrm{rec}} \sim \mathrm{Uniform}(0,1)\)

\[\begin{split}\begin{aligned} h_i^{(k)} &= \begin{cases} 1, & \text{if } (h_i^{(k-1)}=0 \land r_i^{(k-1)}=0) \land (U_i^{\mathrm{inf}} < m_i^{(k)}), \\[4pt] 0, & \text{if } h_i^{(k-1)}=1, \\[4pt] h_i^{(k-1)}, & \text{otherwise}, \end{cases} \\[6pt] r_i^{(k)} &= \begin{cases} 1, & \text{if } h_i^{(k-1)}=1, \\[4pt] r_i^{(k-1)}, & \text{otherwise}. \end{cases} \end{aligned}\end{split}\]

Status

During the simulation, a node can be in one of the following states:

Status	Code
Susceptible	0
Infected	1

IndependentCascadesModel

class fs_gplib.Epidemics.IndependentCascadesModel(data, seeds, threshold: float, device='cpu', rand_seed=None)

Bases: DiffusionModel

Independent Cascades (IC) diffusion model on static graphs.

Each node starts as inactive (susceptible) or active (seed). At every step each newly active node gets exactly one chance to activate each of its inactive out-neighbors independently. After that attempt the node can not activate any other nodes, but it remains active in the final cascade outcome.

Returned node states are encoded as: 0 = susceptible/inactive, 1 = active/infected.

Parameters:

• data (torch_geometric.data.Data) -- PyTorch Geometric Data object representing graph \(G=(V,E)\). Must contain edge_index (the edge set \(E\)) and num_nodes (\(|V|\)).

• seeds (list[int] | float) -- Nodes whose initial state is active. Pass a list of node IDs, or a float in (0, 1) to activate that fraction of nodes chosen uniformly at random.

• threshold (float) -- Per-edge activation probability. When threshold > 0, every edge uses the same probability \(p=\text{threshold}\). When threshold == 0, the model assigns edge-specific probabilities \(p_{ji}=1/\deg_{in}(i)\).

• device (str | int) -- (optional) 'cpu' or a CUDA device index. Defaults to 'cpu'.

• rand_seed (int | None) -- (optional) Random seed used when seeds is a float. Defaults to None.

run_iteration()

Execute a single simulation step.

The internal node_status is updated so that subsequent calls continue from the latest state.

Returns:

Node states after one step, shape (1, N).

Return type:

torch.Tensor

run_iterations(times)

Execute times simulation steps sequentially.

The internal node_status is updated in-place so that subsequent calls continue from the latest state.

Parameters:

times (int) -- Number of maximum simulation steps to run, each step runs until no node remains newly active.

Returns:

Node states at final step, shape (1, N).

Return type:

torch.Tensor

run_epoch(iterations_times=0)

Run a single Monte-Carlo epoch (one independent realisation).

Node states are re-initialised before the epoch starts.

Parameters:

iterations_times (int) -- Number of maximum simulation steps per epoch, each epoch runs until no node remains newly active.

Returns:

Node states at final step of the epoch, shape (1, N).

Return type:

torch.Tensor

run_epochs(epochs, iterations_times, batch_size=1)

Run multiple independent Monte-Carlo epochs in batches.

Node states are re-initialised before the run.

Parameters:

• epochs (int) -- Total number of independent realisations.

• iterations_times (int) -- Number of maximum simulation steps per epoch, each epoch runs until no node remains newly active.

• batch_size (int) -- (optional) Number of epochs processed in parallel per batch. Defaults to 1.

Returns:

Node states at final step of all epochs, shape (epochs, N).

Return type:

torch.Tensor

References

[1]

Kempe D, Kleinberg J, Tardos É. Maximizing the spread of influence through a social network[C]//Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining. 2003: 137-146.