text:
\begin{document}

\maketitle

\begin{abstract}
In this paper we consider the epidemic competition between two generic diffusion processes, where each competing side is represented by a different state of a stochastic process. For this setting, we present the \emph{\methodname} (\methodinitials) dynamic resource allocation strategy to advantage the preferred state against the other.

Motivated by social epidemics, we apply this method to a generic continuous-time SIS-like diffusion model where we allow for: i)~arbitrary node transition rate functions that describe the dynamics of propagation depending on the network state, and ii)~competition between the \emph{healthy} (positive) and \emph{infected} (negative) states, which are both diffusive at the same time, yet mutually exclusive on each node.

Finally we use simulations to compare empirically the proposed \methodinitials against competitive approaches from literature.
\end{abstract}

\section{Introduction}\label{sec:intro}

In recent years, the growing amount of available data on networks led to a revolution in the application of diffusion processes. The enrichment of analysis by means of detailed information regarding specific populations yielded to a plethora of realistic and accurate models.
Through diffusion models, it is possible to study disparate branches of knowledge: in economy (competition among products \cite{winner_takes_all}, viral marketing campaigns \cite{viral-marketing-DP}), in epidemiology (disease spreading, vaccination and immunization problems), in computer science (computer viruses, information flow), in social sciences (social behavior \cite{SISa_emotions}) and medicine (obesity diffusion \cite{obesity-DP}, smoking cessation \cite{smoking-ces-DP}, alcohol consumption \cite{alcohol-ass-DP}) are just some instances. A large number of social behaviors can be modeled as states propagating over networks \cite{SISa_obesity, SISa_emotions, obesity-DP, smoking-ces-DP}.

Consequently to the availability of diffusion models, many intervention strategies were developed aiming to answer questions like: What are the most dangerous computers in a network? How to maximize the customer awareness for a product? On which individuals is better to focus to win a poll?

Few studies proposed strategies to advantage a state compare to another (like in marketing campaigns) or to mitigate the diffusion of an undesirable state (like in epidemiology). Most of them are static strategies based on the network structure (\eg \cite{LRSR}), while others are dynamic strategies that use the whole information about the current state of the system to suggest the best elements to treat.
Among them, the \emph{Largest Reduction in Infectious Edges} (LRIE) \cite{LRIE} results to be the optimal greedy algorithm for resource allocation under limitations in the resource budget, in the $N$-intertwined Susceptible-Infected-Susceptible (SIS) epidemic model. This  model is a two-state continuous-time Markov process over a network, in which a node can change state according to a transition rate that is linear in its neighbors' states.

However SIS models have been deemed too simple to describe the complexity of real-world phenomena such as the contemporary presence of two distinct viruses which spread on the same network. In particular, there can be considered two possible cases; in the first an individual can be infected simultaneously by both diseases (\eg as in the SI$_1$I$_2$S model \cite{winner_takes_all}) and, in the second, mutual exclusivity only one infection is allowed for each individual at a given time (\eg SI$_{1|2}$S model \cite{SI1I2S}). Other attempts tried to change the dynamical equations (like in the SISa \cite{SISa_obesity, SISa_emotions}).

In this study, we propose the \emph{\methodname} (\methodinitials) strategy, which is adapted for the diffusion competition of recurrent epidemics, as well as non-linearity and saturation of the functions of node transition rates. This strategy includes the LRIE strategy \cite{LRIE} and, as such, provides an optimal greedy approach for this more sophisticated network diffusion setting. \methodinitials computes a node score using only local information about the state of close-by nodes. Although in the present formulation the method can be applied to any two-state recurrent Markov process and is easily generalizable to more states, in this work we focus on social behaviors that can be `healthy' or `unhealthy' with negative effects in the social environment. Given a limited amount of resources we would like to target the few key-individuals so as to minimize the negative effects. Apart from the mentioned habits affecting one's personal health (\eg unhealthy diet, smoking, etc.), the recent COVID-19 pandemic highlighted yet another interesting `unhealthy' misbehavior: the disrespect of confinement under a city lock-down, or of social distantiation guidelines in general. Indeed, this kind of misbehavior is a determinant factor for the reproduction rate (the infamous $R_t$) of an epidemic over time, and can be readily enforced by making more controls in key areas, or using mobility and contact information at individual level.

\section{Background}\label{sec:background}

\subsection{Setup and model formulation}\label{sec:setup}

A \emph{graph} $\mathcal{G} \op{=} (\mathcal{V},\mathcal{E})$ is a set of nodes $\mathcal{V}$, let $N \op{=} |\mathcal{V}|$, endowed with a set of edges $\mathcal{E}\subset \mathcal{V} \op{\times} \mathcal{V}$. It can be intuitively represented by its \emph{adjacency matrix} $A \op{=} \{0,1\}^N$, where each $A_{ij}$ element is $1$ if $(i,j) \op{\in} \mathcal{E}$, and $0$ otherwise.
Without loss of generality, we refer to undirected graphs without self-loops, \ie $A=A^\top$ and $A_{ii}\op{=}0, \forall i\op{=}1,...,N$. The \emph{neighborhood} of node $i$ is the set of all nodes connected to it with a direct edge, and is denoted by $\mathcal{N}_i \op{=} \{i_k, \forall k \op{\in} \{1,...,d_i\}\!:(i_k,i)\op{\in}\mathcal{E}  \}$. The size of $\mathcal{N}_i$ equals to the node degree, \ie $|\mathcal{N}_i| \op{=} d_i \op{=} \sum_{j} A_{ji}$. We also denote the indicator function by $\ind{\{\cdot\}}$.

The standard \emph{continuous-time homogeneous SIS} model describes the spread of a disease over a graph, where each node $i$ represents an individual that can be in either the \emph{susceptible} or the \emph{infected} state: $X_i(t)\op{=}0$ or $1$, respectively). The system at time $t$ is hence globally represented by the node state vector $X(t) \op{\in} \{0,1\}^N$. The state of a specific node $i$ evolves according to the following stochastic transition rates:
\begin{align}\label{eq:SIS}
	X_i(t):\begin{cases}
		0 \rightarrow 1 \quad$ with rate $\quad \beta \sum_jA_{ji}X_j(t);\\
		1 \rightarrow 0 \quad$ with rate $\quad \delta + \rho R_i(t),
	\end{cases}
\end{align}
where the parameters $\beta$, $\delta$ are the transition rates encoding respectively the infection aggressiveness and self-recovery capability of nodes. The epidemic control is realized by the resource allocation vector $R(t) \op{\in} \{0,1\}^N$, whose coordinate $R_i(t) = 1$ iff we heal node $i$ at time $t$, and $0$ otherwise. Finally, $\rho$ is the increase in recovery rate when a node receives a resource unit (thought as treatment).

\inlinetitle{A generic two-state recurrent model}{.} In this paper we study the dynamic epidemic suppression problem by first introducing the following generic two-states Markovian process:
\begin{align}\label{eq:genericSIS}
	X_i(t):\begin{cases}
		0 \rightarrow 1 \quad $ with rate$\quad \InfFun_i(X(t));\\
		1 \rightarrow 0 \quad $ with rate$\quad \HealFun_i(X(t))  + \rho R_i(t).
	\end{cases}
\end{align}
$\InfFun_i$ and $\HealFun_i$ are two \emph{node-specific memoryless functions}; respectively the \emph{infection rate function} and \emph{recovery rate function} for node $i$. The rate functions depend on the current overall network state $X(t)$ and implicitly on the network structure (we omit this dependency in our notation).

\begin{remark}
	A Markovian Poisson process can be recovered using the rate functions of \Eq{eq:genericSIS} as follows:
	\begin{equation*}
		\lambda_i(t)\doteq \ind{\{X_i(t)=0\}}\InfFun_i(X(t)) + \ind{\{X_i(t)=1\}}\HealFun_i(X(t)).
	\end{equation*}
\end{remark}

\subsection{Greedy dynamic resource allocation}\label{sec:greedyDRA}

In the \emph{Dynamic Resource Allocation} (DRA) problem \cite{LRIE, MCM}, the objective is to administer a budget of $\budget$ treatment resources, each of them of strength $\rho$, in order to suppress an undesired states diffusion. The treatments can not be stored and their efficiency is limited to a certain value.

In \cite{LRIE}, a greedy dynamic score-based strategy is developed, called \emph{Largest Reduction of Infectious Edges} (LRIE), in order to address the DRA problem. Specifically, each node is associated with a score quantifying how critical it is for further spreading the infection of the standard SIS model, Eq.~\eqref{eq:SIS}.
Other score-based solutions have been proposed, \eg based on fixed priority planning \cite{MCM}, or static ones based on spectral analysis \cite{LRSR} (see details in \Sec{sec:results}).

\section{\methodname: analysis and algorithm}\label{sec:model}

The proposed Generalized Largest Reduction in Infectious Edges (gLRIE) strategy, each time identifies and targets the most critical nodes in order reduce the disease in as quickly as possible. The idea generalizes the one introduced in \cite{LRIE} as it to a wider range of models.
Let $N_I(t) \op{\doteq} \sum_i X_i(t)$ be the number of infected nodes at time $t$. In a Markovian setting, given the state of the population $X$ at time $t$, the best intervention with respect to the resource allocation vector $R$ would minimize the following cost function:
\begin{equation}\label{eq:minfunc}
	\int_0^{\infty} e^{-\gamma u} \Exp[N_I(t\op{+}u)\,|\,X(t)\op{=}X]du,
\end{equation}
where $\gamma$ can be chosen so as to give emphasis on short-term effects \cite{OC_in_metapopulations, Forster_2007}. Expanding in series with respect to $u$, yields:
\begin{equation*}
	\begin{split}
		(\text{\ref{eq:minfunc}}) = \frac{1}{\gamma}\Phi_{t,X}(0) + \frac{1}{\gamma^2}\Phi_{t,X}^{'}(0) + \frac{1}{\gamma^3}\Phi_{t,X}^{''}(0) + O\Big(\frac{1}{\gamma^4}\Big),
	\end{split}
\end{equation*}

where $\Phi_{t,X} \propto \, \Exp[N_I(t\op{+}u)\,|\,X(t)\op{=}X]$.

The detailed evaluation of the three terms can be found in the Supplementary Material\footnote{Available at: \url{http://kalogeratos.com/MyPapers/gLRIE-short-SM.pdf} }. Here, though, we present the final results. To simplify our notation, we denote the updated transition rate of node $j$ if node $i$ is considered healthy, respectively: for the positive diffusion by $\HealFun_j^{-i} \op{\doteq} \HealFun_j(X_1,...,X_i\op{=}0,...,X_N)$, and for the negative diffusion by $\InfFun_j^{-i} \doteq \InfFun_j(X_1,...,X_i\op{=}0,...,X_N)$. We define accordingly the differences in these rates: $\DeltaH{j}{i} \op{\doteq} (\HealFun_{j} \op{-} \HealFun^{-i}_j) \op{\leq} 0$ and $\DeltaI{j}{i} \op{\doteq} (\InfFun_{j} \op{-} \InfFun_j^{-i}) \op{\geq} 0$. Then, the final forms of the derivatives are:
\begin{align}
	 \Phi_{t,X}(0) & = \sum_i X_i, \\
	 \Phi_{t,X}^{'}(0) & = -\sum_i \HealFun_i X_i -\rho \sum_i R_i X_i + \sum_i \InfFun_i \,\notX[i],\\
	 \begin{split}
	 \Phi_{t,X}^{''}(0)& =\Xi (t) + \rho \sum_i  X_i R_i\Bigg\{(\HealFun_i+\InfFun_i)+
	 \\
	 &\quad\quad+\sum_{j\not=i} \bigg[X_j(\DeltaH{j}{i})-\notX[j](\DeltaI{j}{i})\bigg] \Bigg\}.
	 \end{split}
	 \label{eq:3rd term}
\end{align}
In the third equation, and since our purpose is to minimize \Eq{eq:minfunc} with respect to $R_i$, we let the terms that are independent to any $R_i$ to get absorbed in the function $\Xi(t)$.

The terms of the expansion provide information about the way in which healing a node affects the cost function: the first order does not provide any new information, the second order suggests something as trivial as to heal only infected nodes, while the third order quantifies the contribution of healing a specific node in reducing the cost function.

Based on \Eq{eq:3rd term} we derive the following score for each infected node $i$:
\begin{equation}\label{eq:genericScore}
	S_i \doteq -\Bigg[ (\HealFun_i+\InfFun_i)+\sum_{j\not=i}\bigg[X_j(\DeltaH{j}{i})-\notX[j](\DeltaI{j}{i})\bigg]\Bigg].
\end{equation}
The score has the following interpretation. We can identify two main parts: the quantification of the transition rate $\HealFun_i \op{+} \InfFun_i$ of the node, and the effect of its recovery on the neighbors $\sum_{j\not=i}\big[X_j(\DeltaH{j}{i}) \op{-} \notX[j](\DeltaI{j}{i})\big]$.
On the one hand, if a node could get easily reinfected
(high $\InfFun_i$ value) or is going to be healed rapidly by either the self-recovery or the positive diffusion (high $\HealFun_i$ value), then it is not a good candidate to invest resources on. On the other hand, if a possible node recovery would largely increase the healing rate of its infected neighbors (low $\DeltaH{j}{i}$ value), then the node is attributed with a higher score. Finally, if a possible node recovery would largely decrease the infectious rate of its infected neighbors (low $\DeltaI{j}{i}$ value), then the node gets also higher score.

\inlinetitle{Algorithm}{.}

At time $t$, the \methodinitials strategy would take as input the network state $X(t)$and the budget of resources $\budget$. It would independently compute the criticality score of Eq.~\eqref{eq:genericScore} for each node, rank them and finally note with 1's in the resource allocation vector $R(t)$ which nodes to target while respecting the budget, \ie $\sum_i R(t) = \min(\budget,\sum_iX_i(t)))$. The computational cost of the algorithm is $O(N^2 \op{+} N\log N)$.

\section{Simulations}\label{sec:results}

In this section we select competitors from the literature, define specific diffusion functions for the comparison, and present simulations on random and real networks.

\subsection{Experimental setup}\label{sec:exp_setup}

\inlinetitle{Other strategies}{.}

As a naive baseline, we use the Random Allocation (RAND) that targets infected nodes at random. The second competitor is the Largest Reduction in Spectral Radius (LRSR) \cite{LRSR}, which is based on spectral graph analysis generalized to arbitrary healing effects ($\rho \op{\not=} \infty$). LRSR selects nodes that maximize the eigen-drop of the largest eigenvalue of the adjacency matrix, known as \emph{spectral radius}. The next competitor is the Maxcut Minimization (MCM) \cite{MCM}, which introduces the \emph{priority planning} approach. The strategy proceeds according to a precomputed node \emph{priority-order}, that is a linear arrangement of the network with minimal \emph{maxcut}, \ie maximum number of edges need to be cut in order to split the ordering in two parts. The last but most direct competitor is the greedy dynamic LRIE \cite{LRIE} that we generalize in this work.

\inlinetitle{Diffusion function}{.}

Generally, the state transition rate for a node can be assumed to be a function either of the absolute number of neighbors in the opposing state (standard for SIS), or of the fraction of those nodes our of all neighbors.
Here we take as an example the former option, as the strategies presented in the literature consider that type and it is therefore a fair comparison. Future work could include additional experiments with the latter type.

Social behaviors have complex properties that are not covered by the standard SIS models, such as \emph{non-linearity} and \emph{saturation} in the node transition rates \cite{SISa_obesity}. We employ sigmoid functions to model these model properties:
\begin{equation}\label{eq:spreading_absolute}
	\begin{cases}
		\ \InfFun(n,d)  = s_{_\InfFun} \big[1-\frac{2}{1+\exp\left({4\slopeSymbol_{_\InfFun} n}\right)}\big];\\
		\HealFun(n,d) = s_{_\HealFun} \big[1-\frac{2}{1+\exp\left({4\slopeSymbol_{_\HealFun} (d-n)}\right)}\big]+\delta,\
	\end{cases}
\end{equation}

where $n$ and $d\op{-}n$ are the number of infected and healthy neighbors.
Also, $\saturationSymbol_{_\InfFun}$ (resp. $\saturationSymbol_{_\HealFun}$) parameter controls the saturation level and $\slopeSymbol_{_\InfFun}$ (resp. $\slopeSymbol_{_\HealFun}$) the slope at the origin.

\subsection{Random Networks}

Next, we present comparative experiments in \Erdos\ (ER), Preferential Attachment (PR), and Small-World (SW) random networks of size 300 nodes each.
First we gradually introduce non-linearity in the diffusion, and then we show the effects of introducing also competition diffusion.

\inlinetitle{From linear to non-linear spreading}{.}

We first consider only the negative diffusion (\ie $\HealFun=0$) and we gradually increase $\slopeSymbol_{_\InfFun}$ in an ER random graph, moving gradually from linear (as in the standard SIS model) to non-linear functions.
\Fig{fig:seq} shows the average over 1\np{,}000 simulations of the percentage of infected nodes over time and the 95\% confidence interval under the hypothesis of Gaussian distribution.
The results show that in the presence of non-linearity our strategy becomes much more efficient than the competitors.

\begin{figure}[t] \footnotesize
	\centering
	\emph{\scriptsize\myfont Scenario without diffusion competition} ($\InfFun\neq 0, \HealFun=0$)
	\makebox[\linewidth][c]{
	\subfigure[$\slopeSymbol_{_\InfFun} \op{=} 0.01$, $\rho\op{=}1.6$]{

		\includegraphics[viewport=1 -1 530 410, clip=true,width=0.34\linewidth]{seq_1_v1-eps-converted-to.pdf}
	}
	\subfigure[$\slopeSymbol_{_\InfFun}\op{=}1$, $\rho\op{=}63$]{
		\includegraphics[viewport=47 2 530 410, clip=true,width=0.33\linewidth]{seq_3_v1-eps-converted-to.pdf}
	}
	\subfigure[$\slopeSymbol_{_\InfFun}\op{=}3$, $\rho\op{=}120$]{

		\includegraphics[viewport=47 2 530 410, clip=true,width=0.33\linewidth]{seq_4_v1-eps-converted-to.pdf}
	}
    }
	\beforecaptvskip
	\caption{\footnotesize The percentage of infection in time in \Erdos\ graphs of 300 nodes with average degree $8$, when different strategies are employed.
\emph{Only the negative diffusion is considered}. From (a) to (c) the diffusion moves from being effectively linear to non-linear. The saturation level is fixed to $s_{_\InfFun}\op{=}13$ and the budget of resources to allocate is $\budget\op{=}10$. The plots show averages over 1\np{,}000 simulations of the generalized SIS model using \Eq{eq:spreading_absolute}.}
	\label{fig:seq}
\end{figure}

\inlinetitle{Introducing competition}{.}

Next, in \Fig{fig:competition-lines} we present the effects of the positive diffusion, embedded in the function $\HealFun$, on ER, PR, and SW random networks.

The last plot each row shows the shape of the diffusion functions used in the simulations. The simulations show that, unlike \methodinitials, the methods of the literature lack modeling power to deal with this complex setting involving non-linearity and competition, and suppress the infection.

\begin{figure}[t] \footnotesize

	\centering
	\emph{\scriptsize\myfont Scenario without diffusion competition} ($\InfFun\neq 0, \HealFun=0$)
	\vspace{-1mm}
	\makebox[\linewidth][c]{
	\subfigure[]{

		\includegraphics[viewport=8 1 385 285, clip=true, width=0.337\linewidth]{ER_noHD_1000-eps-converted-to.pdf}
	}

	\subfigure[]{

		\includegraphics[viewport=38 1 385 285, clip=true, width=0.31\linewidth]{prefAtt_noHD_1000-eps-converted-to.pdf}
		\label{fig:prefAtt_noHD}
	}
	\subfigure[]{
		\includegraphics[viewport=38 1 385 285, clip=true, width=0.31\linewidth]{smallW_noHD_1000-eps-converted-to.pdf}
	\label{fig:smallW_noHD}
	}
	}
    \\
    \emph{\scriptsize\myfont Scenario with diffusion competition} ($\InfFun\neq 0, \HealFun\neq0$)
	\vspace{-1mm}
	\makebox[\linewidth][c]{
	\subfigure[]{

		\includegraphics[viewport=8 1 385 285, clip=true, width=0.337\linewidth]{ER_HD_1000-eps-converted-to.pdf}
  \label{fig:ER_HD}
	}
	\subfigure[]{

		\includegraphics[viewport=38 1 385 285, clip=true, width=0.31\linewidth]{prefAtt_HD_1000-eps-converted-to.pdf}
		\label{fig:prefAtt_HD}
	}
	\subfigure[]{
		\includegraphics[viewport=38 1 385 285, clip=true, width=0.31\linewidth]{smallW_HD_1000-eps-converted-to.pdf}
	\label{fig:smallW_HD}
	}
	}
	\beforecaptvskip
	\caption{\footnotesize Percentage of infected nodes under a generalized SIS model using \Eq{eq:spreading_absolute} using several control strategies. Results for ER (a,\,d), PA (b,\,e), and SW (c,\,f) networks, 300 nodes in each case.
	The model's parameters are: $s_{_\InfFun}\op{=}13$, $\slopeSymbol_{_\InfFun}\op{=}5$ for the negative diffusion and $s_{_\HealFun}\op{=}2$, $\slopeSymbol_{_\HealFun}\op{=}0.5$ for the positive diffusion (when present). At any moment in time, up to $\budget\op{=}10$ nodes are targeted with resource units of $\rho\op{=}155$ healing strength.
	}
\label{fig:competition-lines}
\vspace{-2mm}
\end{figure}

\subsection{Real Networks}

We performed simulations on the Gnutella\footnote{Available at SNAP datasets: \url{http://snap.stanford.edu/data}}
peer-to-peer network containing $8\np{,}846$ nodes and $31\np{,}839$ edges. Two scenarios were used for the simulations, with and without positive diffusion, using a wide range of parameters. Out of the many possible evaluation metrics for the quality of a strategy, \eg expected extinction time (EET), final percentage of infection (FIS), area under the curve (AUC), we choose the AUC. This has many advantages: it provides useful measurements even if the strategy did not removed the infection, which is a limitation of the EET metric; it accounts for the total amount of infected nodes in the process, which in a socioeconomic context is more interesting than the FIS metric.

The empirical comparison between \methodinitials and competitors such as LRIE and MCM is summarized in \Fig{fig:heat-maps Gnutella} using heatmaps showing the ratio of respective AUC values:
$\frac{\text{AUC}(\text{\methodinitials}(s_{_\InfFun},\slopeSymbol_{_\InfFun},s_{_\HealFun},\slopeSymbol_{_\HealFun}))}{\text{AUC}(\text{Competitor}(s_{_\InfFun},\slopeSymbol_{_\InfFun},s_{_\HealFun},\slopeSymbol_{_\HealFun}))}$. The first row corresponds to the scenario where the positive diffusion is absent, but becomes present in the second row.
In each row, the rightmost heatmap shows the final infection size when applying \methodinitials (in the black regions the infection is completely removed, while in the white it persists at the end of the simulation).

In each heatmap, we fix the shape of the transition function $\HealFun$ of the positive diffusion and only play with the parameters of the function $\InfFun$ of the negative diffusion: its saturation level increases along the x-axis and its slope increases along the y-axis. On the top-left side of a heatmap, the epidemic parameters define a weak infection and any strategy would perform well, while on the bottom-right side the infection becomes hard to completely remove for all strategies (given the amount of resources). Moreover, in the left border, the low saturation level causes $\InfFun$ to already saturate with just one neighbor of the opposing state. In the regime where $\InfFun$ is almost linear and $\HealFun=0$, \methodinitials and LRIE are equivalent and perform almost the same. The general remark on the results is that \methodinitials appears to be the most versatile and best performing strategy in this setting of competitive spreading.

\begin{figure}[t]
\footnotesize
	\centering
	\emph{\scriptsize\myfont Scenario without diffusion competition} ($\InfFun\neq 0, \HealFun=0$)
	\vspace{-1mm}
	\makebox[\linewidth][c]{
		\hspace{1mm}
		\begin{picture}(0,40)
			\put(2,15){\rotatebox{90}{\scalebox{.8}{\tiny {\myfont slope at the origin} ($\slopeSymbol$}\scalebox{.5}{$_{_\InfFun}$}\scalebox{.8}{\tiny)}}}
		\end{picture}
		\hspace{-0.4mm}
	\subfigure[\methodinitials vs LRIE]{

		\includegraphics[viewport=9 1 335 295, clip=true, width=0.30\linewidth]{Gnutella_gLRIE_LRIE-eps-converted-to.pdf}
		\begin{picture}(0,0)
			\put(-48,0){\scalebox{.8}{\tiny {\myfont saturation} ($s$}\scalebox{.5}{$_{_\InfFun}$}\scalebox{.8}{\tiny)}}
		\end{picture}
  \label{fig:heatmap LRIE Gnutella noHD}
	}
	\hspace{-1.7mm}
	\subfigure[\methodinitials vs MCM]{

		\includegraphics[viewport=40 1 335 295, clip=true, width=0.272\linewidth]{Gnutella_gLRIE_MCM-eps-converted-to.pdf}
		\includegraphics[viewport=340 1 380 295, clip=true, width=0.037\linewidth]{Gnutella_gLRIE_MCM-eps-converted-to.pdf}
		\begin{picture}(0,0)
			\put(-60,0){\scalebox{.8}{\tiny {\myfont saturation} ($s$}\scalebox{.5}{$_{_\InfFun}$}\scalebox{.8}{\tiny)}}
		\end{picture}
		\label{fig:heatmap MCM Gnutella noHD}
	}
	\subfigure[\methodinitials: final inf. size]{

		\!\!\!\raisebox{1mm}{\includegraphics[viewport=15 15 335 295, clip=true, width=0.295\linewidth]{Gnutella_gLRIE_conv-eps-converted-to.pdf}}
		\includegraphics[viewport=340 1 383 295, clip=true, width=0.0393\linewidth]{Gnutella_gLRIE_conv-eps-converted-to.pdf}
		\begin{picture}(0,0)
\myfont 			\put(-60,0){\scalebox{.8}{\tiny {\myfont saturation} ($s$}\scalebox{.5}{$_{_\InfFun}$}\scalebox{.8}{\tiny)}}
		\end{picture}
		\label{fig:heatmap Gnutella conv noHD}	}}
	\\
	\emph{\scriptsize\myfont Scenario with diffusion competition} ($\InfFun\neq 0, \HealFun\neq 0$)
	\vspace{-1mm}
	\makebox[\linewidth][c]{
	  \hspace{1mm}
		\begin{picture}(0,40)
			\put(2,15){\rotatebox{90}{\scalebox{.8}{\tiny {\myfont slope at the origin} ($\slopeSymbol$}\scalebox{.5}{$_{_\InfFun}$}\scalebox{.8}{\tiny)}}}
		\end{picture}
		\hspace{-0.4mm}
	\subfigure[\methodinitials vs LRIE]{

		\includegraphics[viewport=9 1 335 295, clip=true, width=0.30\linewidth]{Gnutella_HD_gLRIE_LRIE-eps-converted-to.pdf}
		\begin{picture}(0,0)
			\put(-48,0){\scalebox{.8}{\tiny {\myfont saturation} ($s$}\scalebox{.5}{$_{_\InfFun}$}\scalebox{.8}{\tiny)}}
		\end{picture}
  \label{fig:heatmap LRIE Gnutella HD}
	}
	\hspace{-1.5mm}
	\subfigure[\methodinitials vs MCM]{

		\includegraphics[viewport=45 1 335 295, clip=true, width=0.268\linewidth]{Gnutella_HD_gLRIE_MCM-eps-converted-to.pdf}
		\includegraphics[viewport=340 1 380 295, clip=true, width=0.037\linewidth]{Gnutella_HD_gLRIE_MCM-eps-converted-to.pdf}
		\begin{picture}(0,0)
			\put(-60,0){\scalebox{.8}{\tiny {\myfont saturation} ($s$}\scalebox{.5}{$_{_\InfFun}$}\scalebox{.8}{\tiny)}}
		\end{picture}
		\label{fig:heatmap MCM Gnutella HD}
	}
	\subfigure[\methodinitials: final inf. size]{

		\!\!\!\raisebox{1mm}{\includegraphics[viewport=15 15 335 295, clip=true, width=0.295\linewidth]{Gnutella_HD_gLRIE_conv-eps-converted-to.pdf}}
		\includegraphics[viewport=340 1 383 295, clip=true, width=0.0393\linewidth]{Gnutella_HD_gLRIE_conv-eps-converted-to.pdf}
		\begin{picture}(0,0)
			\put(-60,0){\scalebox{.8}{\tiny {\myfont saturation} ($s$}\scalebox{.5}{$_{_\InfFun}$}\scalebox{.8}{\tiny)}}
		\end{picture}
		\label{fig:heatmap Gnutella conv HD}
	}}
	\beforecaptvskip
	\caption{\footnotesize Heatmaps of the AUC ratio between \methodinitials and competitors in the Gnutella network, using a wide range of model parameterization.
The color map ranges from yellow (ratio\op{=}$1$), where the strategies perform the same, to blue (ratio\op{=}$0$), where only \methodinitials manages to remove the infection. As expected, the positive diffusion reduces the difficulty of the control problem.
	}
	\label{fig:heat-maps Gnutella}
	\vspace{-2mm}
\end{figure}

\section{Conclusion}\label{sec:conclusion}

In this paper we discussed a general form of recurrent two-states continuous-time Markov process that allows both non-linear node transition functions and competition among the two states. We then proposed the \emph{Generalized LRIE} (\methodinitials) strategy to suppress the diffusion of the undesired state.

Experiments showed that \methodinitials is well-adapted to the considered setting of competitive spreading, and makes better use of the resources available by targeting the most critical infected nodes compared to competitors from literature. Future work could generalize to more competing epidemic states
and the incorporation of factors related to the network structure in the node scores.

\bibliographystyle{unsrt}
\bibliography{gLRIE_short_arxiv}

\end{document}


TITLE: Continuous functions/ Extreme value theorem
QUESTION [1 upvotes]: $g:[0,1]\rightarrow \mathbb{R}$ is continuous, $g(0)>0$, $g(1) = 0$. I want to show there is a $a\in (0,1]$ s.t. $g(a)=0$ and $g(x)>0$ for $0\le x<a$.
A student brought this to the tutoring center where I work, and the problem is in a section that comes right before the intermediate value theorem, it is in the section for extreme value theorem. So they basically have the definition of continuity and the $E.V.T$. I would love some help to find a not to intense solution. It is from a advanced calculus class.

REPLY [0 votes]: Let be $x_1$ the point where $g(x_1)=\min_{[0,1]}g$. If $x_1=1$ then the exercise is solved. If $x_1\neq 1$ consider the interval $[0,\overline{x_1}]$ where $\overline{x_1}<x_1$ and $g(\overline{x_1})=0$. Let be $x_2\in [0,\overline{x_1}]$ such that $g(x_2)=\min_{[0,\overline{x_1}]}g$. Continue the construction in this way and you obtain a decreasing sequence of point $\overline{x_n}$ in $[0,1]$. Since $[0,1]$ is compact there exists $\overline x \in [0,1]$ such that $\overline{x_n}\rightarrow \overline x$. Now $\overline{x}$ is the point you were looking for because $f(\overline x)=0$ by the continuity of $f$ and $f$ is poisitive before $\overline x$ by the construction of the sequence $\overline{x_n}$.


TITLE: Using Substitution to Solve a 1st Order Differential Equation
QUESTION [2 upvotes]: Solve $\frac{dy}{dx} = \frac{x^2 + y^2}{xy}$ for $y(1) = 2$
I began by simplifying such that: $\frac{dy}{dx} = \frac{x}{y} - \frac {y}{x}$
Then, I set $v = \frac {y}{x}$
Therefore: $y = xv$ and $y'$ = $v$ + $xv'$
Substituting back: $v + xv' = \frac{x}{xv} - \frac{xv}{x}$
or $v + xv' = \frac{1}{v} - v$
To continue, should $x$ be divided from both sides to allow for use of an integrating factor?

REPLY [2 votes]: To continue with your method then
( You have a sign mistake )
$$v + xv' = 1/v \color{red}{+} v$$
$$v'vx=1$$
It's separable
$$\int vdv=\int \frac {dx}x$$
$$v^2=2 \ln  |x|+C$$
Substitute back $v=\frac y x$

Another approach
$$y'xy=x^2+y^2$$
Note that
$$(y^2)'=2yy'$$
$$\frac x2(y^2)'=x^2+y^2$$
Substitute $y^2=z$
$$\frac x2z'=x^2+z$$
It's a first order differential equation
$$z'-\frac 2xz=2x$$
Multiply by $x^2$
$$z'x^2-2xz=2x^3$$
Divide by $x^4$
$$\left(\frac z {x^2}\right )'=\frac 2x$$
Integrate
$$\left(\frac z {x^2}\right )=2 \ln |x|+K$$
$$z=2 x^2\ln |x|+Kx^2$$
$$z(1)=y^2(1)=4 \implies K=z=4$$
$$\boxed {y(x)=\pm |x|\sqrt {2\ln |x|+4}}$$


TITLE: Maximizing magnitude given a complex valued function
QUESTION [1 upvotes]: I am presented with a problem, which asks you to maximize $|z|$ with the constraint of $$\left|z+\frac 2z \right| = 2.$$
I tried to approach this with components, however this degraded into a messy cubic, letting $z=a+bi$ only to receive $$\frac{a^3+a^2b+ab^2+b^3+2a-2b}{a^2+b^2},$$ trying to maximize $\sqrt{a^2+b^2}.$
How does one go through solving this, without calculus?

REPLY [1 votes]: Your approach works (It seems that you have an error in your approach).
Letting $z=a+bi$ where $a,b$ are real numbers, we have
$$\begin{align}&\bigg|a+bi+\frac 2{a+bi}\bigg|=2
\\\\&\iff \bigg|a+bi+\frac{2(a-bi)}{a^2+b^2}\bigg|=2
\\\\&\iff \bigg|\bigg(a+\frac{2a}{a^2+b^2}\bigg)+\bigg(b-\frac{2b}{a^2+b^2}\bigg)i\bigg|=2
\\\\&\iff \sqrt{\bigg(a+\frac{2a}{a^2+b^2}\bigg)^2+\bigg(b-\frac{2b}{a^2+b^2}\bigg)^2}=2
\\\\&\iff \frac{(a(a^2+b^2)+2a)^2+(b(a^2+b^2)-2b)^2}{(a^2+b^2)^2}=4
\\\\&\iff \frac{(a^2 + b^2) (a^4 + 2 a^2 b^2 + 4 a^2 + b^4 - 4 b^2 + 4)}{(a^2+b^2)^2}=4
\\\\&\iff \frac{a^4 + 2 a^2 b^2 + 4 a^2 + b^4 - 4 b^2 + 4}{a^2 + b^2}=4
\\\\&\iff a^4 + 2 a^2 b^2 + 4 a^2 + b^4 - 4 b^2 + 4-4(a^2+b^2)=0
\\\\&\iff b^4 +(2 a^2 - 8) b^2 +a^4  + 4=0
\\\\&\iff b^2=4-a^2\pm\sqrt{12-8a^2}\end{align}$$
So, we can write
$$|z|=\sqrt{a^2+b^2}=\sqrt{4\pm\sqrt{12-8a^2}}$$
So, the maximum value of $|z|$ is $$\sqrt{4+\sqrt{12-8\times 0^2}}=\sqrt{4+2\sqrt 3}=\sqrt{(1+\sqrt 3)^2}=\color{red}{1+\sqrt 3}$$ which is attained when $z=\pm(1+\sqrt 3)i$.

Another approach (there was an answer using this approach, but the answer was deleted) :
For any two complex numbers $z_1$ and $z_2$,
$$|z_1+z_2|\le |z_1|+|z_2|$$
(see here for a proof)
Using this inequality, we have
$$|z|=\bigg|z+\frac 2z-\frac 2z\bigg|\le \bigg|z+\frac 2z\bigg|+\bigg|-\frac 2z\bigg|=2+\frac{2}{|z|}$$
$$\implies |z|\le 2+\frac{2}{|z|}\implies |z|^2-2|z|-2\le 0\implies |z|\le 1+\sqrt{3}$$
If $z=(1+\sqrt 3)i$, then $|z|=1+\sqrt 3$ and $\bigg|z+\dfrac 2z\bigg|=2$ hold.
Therefore, the maximum value of $|z|$ is $\color{red}{1+\sqrt 3}$.


TITLE: How do I write this matrix as a product of elementary matrices?
QUESTION [1 upvotes]: Given the matrix $\mathbf A = \begin{pmatrix}3&5\\2&4\end{pmatrix}$, how would I go about writing this as a product of elementary matrices? I understand the concept of elementary matrices I'm just a little unsure algorithmically what the steps should be. Any help would be appreciated.

REPLY [2 votes]: Perform the Gauss algorithm to bring $A$ into the reduced echelon form.
Because every step of the Gauss algorithm is basically a multiplication with an elementary matrix you get the equation (You can also get the $T_i$ on the left side of $A$ it depends if you do row or column operations)
$$A \cdot T_1 \cdot T_2 \cdot \ldots \cdot T_k = \mathcal{E}$$
Where $\mathcal{E}$ is the unit matrix. Therefore you have that
$$A = T_k^{-1} \cdot \ldots \cdot T_2^{-1} \cdot T_1^{-1}$$
And because the inverse of elementary matrices are elementary matrices you have written $A$ as the product of elementary matrices. This is a constructive algorithm you just have to keep track of the elementary matrices you use.