# Spreading processes on networks Networked Dynamical Systems involve dynamical systems hosted by each node, with interactions defined by links. The collective behaviour of the network is typically more complex than isolated nodes and is influenced by the topological structure of the network. ## Contagion and epidemics The spread of infectious diseases, as well as the adoption of products and opinions, can be modeled using **probabilistic cellular automata** in networked system characterized by: - **Finite State Set**: Each node $i$ is in state $s^i$ at time $t$, belonging to a set $\Sigma$ (example *Susceptible, Infected, Recovered* in the SIS model we will see). - **Local Rules**: The state of a node at the next time step depends probabilistically on its current state and the states of its neighbour (the contagion mechanism in the SIS model). ### SIS Process in networks The SIS (Susceptible-Infected-Susceptible) model describes the dynamics of disease spread in networks. The process includes two main transitions: - **Susceptible to Infected (S → I)**: Occurs with probability $\beta I_i\Delta$, where $\beta$ is the infection rate, $I_i$ is the number of infected neighbours and $\Delta$ the time step. - **Infected to Susceptible (I → S)**: Occurs with probability $\gamma\Delta$, representing the recovery rate. In summary: - $\beta$ measures how easily the disease spreads (higher $\beta$ means more contagious disease) - $\gamma$ measures how quickly individuals recover from the disease (higher $\gamma$ means faster recovery). The dynamics of epidemics are influenced by the network topology. #### Homogeneous networks Using as first approximation that the degree of each node can be approximated to the average $k$. The equations of the rate of change of the fraction of infected individuals in the population is: $\frac{dy(t)}{dt} = -\gamma y(t) + \beta \langle k \rangle y(t) [1 - y(t)]$ where $\gamma$ is the recovery rate, $\beta$ is the transmission rate, and $\langle k \rangle$ is the average number of neighbours. In case of **homogeneous networks**, the epidemy outcome depends on a $\beta$ respect to the threshold $\beta_c$ : $\beta_c = \frac{\gamma}{\langle k \rangle}$ Below this threshold, the disease dies out, while above it, the disease can persist in the population. If $\beta > \beta_c$ , the epidemy reaches a non-trivial (gt;0$) asymptotically stable equilibrium given by: $y = 1 - \frac{\gamma }{\beta \langle k \rangle}$ #### Heterogeneous networks In **Heterogeneous networks** (like scale-free networks) the epidemic threshold is $\beta_c=\frac{\gamma \langle k \rangle }{\langle k^2 \rangle}$ then it may tend to $0$ for large networks $(N\to\infty)$ ! This means that for large networks $y(t)$ never vanishes, whatever the value of the transmission rate $\beta$ and that the epidemy is able to survive with arbitrarily small transmission rate. ### Immunization With the immunization we are able to eradicating the epidemic $y \rightarrow 0$ and also we can define the threshold of fraction of individuals ($g_c$) we need to vaccinate to eradicate the population. Homogeneous networks (random vaccination) $\beta$ is now $\beta(1-g)$ which makes the epidemic threshold equation $\beta(1-g)<\frac{\gamma}{<k>}$ which is satisfied by: $g>g_{c}=1-\frac{\gamma}{\beta<k>}$ If $g>g_c$ nodes are vaccinated at random, the epidemic is eradicated $(y\to0)$. Heterogeneous networks (random vaccination) In heterogeneous networks, same reasoning but with different threshold: $\beta(1-g)<\frac{\gamma<k>}{<k^{2}>}$ which is satisfied by: $g>g_{c}=1-\frac{\gamma<k>}{\beta<k^{2}>}$ If the network is too large, lt;k^2>\to\infty$ (scale-free nets with large $N)$ then $g_c\to1$ which means that the entire population needs to be vaccinated. ### Models of influence propagation (“social contagion”) These models describe the diffusion of information or behaviour in a network-structured population. This can include: - Information (news, rumor, opinion, etc.) - Behavior (adoption of a product/service, food/smoking habits, etc.) The simple models are based on two states $\Sigma = \{\text{Inactive, Active}\}$. The **progressive** nature of the contagion makes that once an individual turns to active, it remains such forever. Two problems can be formulated from this: 1. Analysis: Determine the final active set $S_{\infty}$ based on a given initial set $S_0$ 2. Optimization: Find the best initial active set $S_0$ that maximizes the size of final set size $|S_{\infty}|$ while staying within a specified budget $|S_0| = m \ll N$ We saw two simple models: - **Linear Threshold** (LT) Model: - Each node $i$ has a threshold $\theta_i > 0$ and is influenced by the incoming neighbors $N_i = \{j | a_{ji} = 1\}$ with a weight $w_{ji} > 0$. - If $A_t$ is the set of Active nodes at time $t$, then node $i$ becomes active at time $t + 1$ if $\sum_{j\in N_i\cap A_t}w_{ji} \geq \theta_i$ - The model is deterministic. - **Independent Cascade** (IC) Model - Each node $i$ becoming active at time $t$ is given a single chance to activate each of its currently inactive outgoing neighbors $N_i = \{j | a_{ij} = 1\}$. - The activation attempt succeeds with probability $p_{ij}$, and $j$ will become Active at time $t + 1$. - The model is stochastic. # Consensus in Networked Multi-Agent Systems The concept of "consensus" refers to the process where all agents in the network eventually reach the same state over time. Both continuous and discrete models to specify how each single agent's state changes over time can exists. The simplest local dynamic for an agent is represented by a network of $N$ **integrator** agents, each hosting a linear system $\dot{x}_{i}(t)=u_{i}(t)$ (integrator because actually they continue to compute the integral of the input). The interaction between elements in a system is proportional to the difference in their states due to its "diffusive" nature: $\dot{x}_i(t) = u_i(t) = \sum_{j \in V_i} (x_j(t) - x_i(t))$ The **Laplacian** matrix plays a crucial role in consensus dynamics because its properties determine how quickly and effectively a consensus can be reached in the network. $L=diag(k_1,k_2,...,k_N)-A$ represents the $N\times N$ Laplacian matrix of the network, influencing the collective dynamics of the system. The eigenvalues and eigenvectors of the Laplacian, in particular, provide insights into the network's connectivity and the speed of convergence to consensus. In principle, infinite consensus states but only one is possible which **depends** on the **graph topology**. ### Undirected networks **Conservation of the Sum of States**: The equation $\Sigma_i\dot{x}_i=0$ suggests that the sum of the rate of change of states over all nodes in the network is zero. This implies conservation in the system – the total "quantity" represented by the states $x_i$​ of the nodes doesn't increase or decrease over time; it's merely redistributed among the nodes. The only feasible equilibrium state $\overline{x}$ for all nodes, where equilibrium means no node's state is changing anymore (consensus is reached), is the average of all the initial states: $ \bar{x}_{1}=\bar{x}_{2}=\cdots=\bar{x}_{N}=\frac{1}{N}\sum_{i}x_{i}(0) $ ### Directed networks In **directed networks**, consensus is still achievable, but it depends on the network's connectivity. In directed networks the Laplacian matrix is built using $k_i^{out}$ : $L_{ii}=k_{i}^{out},L_{ij}=-a_{ij},i\neq j$ We found out that only if the **network is strongly connected**, there is a consensus value which is **weighted average** network. In a directed network, a consensus value is a weighted average of the initial states. This is mathematically represented as: $\alpha=\sum_iw_ix_i(0)$ where $\sum_iw_i=1$.Here, $w_i$ are weights that depend on the network topology, and $\alpha$ is the weighted average. These weights $[w_1,w_2,...,w_N]$ are actually the components of a left eigenvector of the Laplacian matrix $L$ corresponding to the eigenvalue $\lambda_1=0.$ **Iff** each node's in-degree $k_i^{in}$ is equal to its out-degree $k_i^{out}$, $\alpha$ becomes the average of the initial states, expressed as: $\alpha=\frac1N\sum_ix_i(0)$ Finally, the speed at which a network reaches consensus is dominated by the first sub-dominant eigenvalue of $L_S=(L+L^T)/2$,where $L^\mathrm{T}$ is the transpose of the Laplacian matrix. This eigenvalue gives an indication of how quickly the consensus state will be achieved in the network.