I Introduction
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 [1], viral marketing campaigns [2]), in epidemiology (disease spreading, vaccination and immunization problems), in computer science (computer viruses, information flow), in social sciences (social behavior [3]) and medicine (obesity diffusion [4], smoking cessation [5], alcohol consumption [6]) are just some instances. A large number of social behaviors can be modeled as states propagating over networks [7, 3, 4, 5].
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 (e.g. [8]), 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 Largest Reduction in Infectious Edges (LRIE) [9] results to be the optimal greedy algorithm for resource allocation under limitations in the resource budget, in the intertwined SusceptibleInfectedSusceptible (SIS) epidemic model. This model is a twostate continuoustime 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 realworld 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 (e.g. as in the SIIS model [1]) and, in the second, mutual exclusivity only one infection is allowed for each individual at a given time (e.g. SIS model [10]). Other attempts tried to change the dynamical equations (like in the SISa [7, 3]).
In this study, we propose the Generalized Largest Reduction in Infectious Edges (gLRIE) strategy, which is adapted for the diffusion competition of recurrent epidemics, as well as nonlinearity and saturation of the functions of node transition rates. This strategy includes the LRIE strategy [9] and, as such, provides an optimal greedy approach for this more sophisticated network diffusion setting. gLRIE computes a node score using only local information about the state of closeby nodes. Although in the present formulation the method can be applied to any twostate 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 keyindividuals so as to minimize the negative effects. Apart from the mentioned habits affecting one’s personal health (e.g. unhealthy diet, smoking, etc.), the recent COVID19 pandemic highlighted yet another interesting ‘unhealthy’ misbehavior: the disrespect of confinement under a city lockdown, or of social distantiation guidelines in general. Indeed, this kind of misbehavior is a determinant factor for the reproduction rate (the infamous ) 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.
Ii Background
Iia Setup and model formulation
A graph is a set of nodes , let , endowed with a set of edges . It can be intuitively represented by its adjacency matrix , where each element is if , and otherwise. Without loss of generality, we refer to undirected graphs without selfloops, i.e. and . The neighborhood of node is the set of all nodes connected to it with a direct edge, and is denoted by . The size of equals to the node degree, i.e. . We also denote the indicator function by .
The standard continuoustime homogeneous SIS model describes the spread of a disease over a graph, where each node represents an individual that can be in either the susceptible or the infected state: or , respectively). The system at time
is hence globally represented by the node state vector
. The state of a specific node evolves according to the following stochastic transition rates:(II.1) 
where the parameters , are the transition rates encoding respectively the infection aggressiveness and selfrecovery capability of nodes. The epidemic control is realized by the resource allocation vector , whose coordinate iff we heal node at time , and otherwise. Finally, is the increase in recovery rate when a node receives a resource unit (thought as treatment).
A generic twostate recurrent model. In this paper we study the dynamic epidemic suppression problem by first introducing the following generic twostates Markovian process:
(II.2) 
and are two nodespecific memoryless functions; respectively the infection rate function and recovery rate function for node . The rate functions depend on the current overall network state and implicitly on the network structure (we omit this dependency in our notation).
Remark 1.
A Markovian Poisson process can be recovered using the rate functions of Eq. II.2 as follows:
IiB Greedy dynamic resource allocation
In the Dynamic Resource Allocation (DRA) problem [9, 11], the objective is to administer a budget of treatment resources, each of them of strength , in order to suppress an undesired states diffusion. The treatments can not be stored and their efficiency is limited to a certain value.
In [9], a greedy dynamic scorebased strategy is developed, called 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. (II.1). Other scorebased solutions have been proposed, e.g. based on fixed priority planning [11], or static ones based on spectral analysis [8] (see details in Sec. IV).
Iii Generalized Largest Reduction in Infectious Edges: analysis and algorithm
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 [9] as it to a wider range of models. Let be the number of infected nodes at time . In a Markovian setting, given the state of the population at time , the best intervention with respect to the resource allocation vector would minimize the following cost function:
(III.1) 
where can be chosen so as to give emphasis on shortterm effects [12, 13]. Expanding in series with respect to , yields:
where .
The detailed evaluation of the three terms can be found in the Supplementary Material^{1}^{1}1Available at: http://kalogeratos.com/MyPapers/gLRIEshortSM.pdf . Here, though, we present the final results. To simplify our notation, we denote the updated transition rate of node if node is considered healthy, respectively: for the positive diffusion by , and for the negative diffusion by . We define accordingly the differences in these rates: and . Then, the final forms of the derivatives are:
(III.2)  
(III.3)  
(III.4) 
In the third equation, and since our purpose is to minimize Eq. III.1 with respect to , we let the terms that are independent to any to get absorbed in the function .
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. III.4 we derive the following score for each infected node :
(III.5) 
The score has the following interpretation. We can identify two main parts: the quantification of the transition rate of the node, and the effect of its recovery on the neighbors . On the one hand, if a node could get easily reinfected (high value) or is going to be healed rapidly by either the selfrecovery or the positive diffusion (high 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 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 value), then the node gets also higher score.
Algorithm. At time , the gLRIE strategy would take as input the network state and the budget of resources . It would independently compute the criticality score of Eq. (III.5) for each node, rank them and finally note with 1’s in the resource allocation vector which nodes to target while respecting the budget, i.e. . The computational cost of the algorithm is .
Iv Simulations
In this section we select competitors from the literature, define specific diffusion functions for the comparison, and present simulations on random and real networks.
Iva Experimental setup
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) [8], which is based on spectral graph analysis generalized to arbitrary healing effects (
). LRSR selects nodes that maximize the eigendrop of the largest eigenvalue of the adjacency matrix, known as
spectral radius. The next competitor is the Maxcut Minimization (MCM) [11], which introduces the priority planning approach. The strategy proceeds according to a precomputed node priorityorder, that is a linear arrangement of the network with minimal maxcut, i.e. 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 [9] that we generalize in this work. 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 nonlinearity and saturation in the node transition rates [7]
. We employ sigmoid functions to model these model properties:
(IV.1) 
where and are the number of infected and healthy neighbors. Also, (resp. ) parameter controls the saturation level and (resp. ) the slope at the origin.
IvB Random Networks
Next, we present comparative experiments in ErdösRényi (ER), Preferential Attachment (PR), and SmallWorld (SW) random networks of size 300 nodes each. First we gradually introduce nonlinearity in the diffusion, and then we show the effects of introducing also competition diffusion.
From linear to nonlinear spreading. We first consider only the negative diffusion (i.e. ) and we gradually increase in an ER random graph, moving gradually from linear (as in the standard SIS model) to nonlinear functions. Fig. 1
shows the average over 1, 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 nonlinearity our strategy becomes much more efficient than the competitors.
Introducing competition. Next, in Fig. 2 we present the effects of the positive diffusion, embedded in the function , 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 gLRIE, the methods of the literature lack modeling power to deal with this complex setting involving nonlinearity and competition, and suppress the infection.
for the positive diffusion (when present). At any moment in time, up to
nodes are targeted with resource units of healing strength.IvC Real Networks
We performed simulations on the Gnutella^{2}^{2}2Available at SNAP datasets: http://snap.stanford.edu/data peertopeer network containing nodes and
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, e.g. 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 gLRIE and competitors such as LRIE and MCM is summarized in Fig. 3 using heatmaps showing the ratio of respective AUC values: . 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 gLRIE (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 of the positive diffusion and only play with the parameters of the function of the negative diffusion: its saturation level increases along the xaxis and its slope increases along the yaxis. On the topleft side of a heatmap, the epidemic parameters define a weak infection and any strategy would perform well, while on the bottomright 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 to already saturate with just one neighbor of the opposing state. In the regime where is almost linear and , gLRIE and LRIE are equivalent and perform almost the same. The general remark on the results is that gLRIE appears to be the most versatile and best performing strategy in this setting of competitive spreading.


V Conclusion
In this paper we discussed a general form of recurrent twostates continuoustime Markov process that allows both nonlinear node transition functions and competition among the two states. We then proposed the Generalized LRIE (gLRIE) strategy to suppress the diffusion of the undesired state. Experiments showed that gLRIE is welladapted 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.
References
 [1] B.A. Prakash, A. Beutel, R. Rosenfeld, and C. Faloutsos. Winner takes all: competing viruses or ideas on fairplay networks. In Proc. ACM Intern. Conf. on World Wide Web, pages 1037–1046, 2012.
 [2] J. Leskovec, L.A. Adamic, and B.A. Huberman. The dynamics of viral marketing. ACM Trans. on the Web, 1(1):5, 2007.
 [3] A.L. Hill, D.G. Rand, M.A. Nowak, and N.A. Christakis. Emotions as infectious diseases in a large social network: the SISa model. Proc. Royal Society of London B: Biol. Sc., 277(1701):3827–3835, 2010.
 [4] N.A. Christakis and J.H. Fowler. The spread of obesity in a large social network over 32 years. N. E. J. of Medicine, 357(4):370–379, 2007.
 [5] N.A. Christakis and J.H. Fowler. The collective dynamics of smoking in a large social network. N. E. J. of Medicine, 358(21):2249–2258, 2008.
 [6] J.N. Rosenquist, J. Murabito, J.H. Fowler, and N.A. Christakis. The spread of alcohol consumption behavior in a large social network. Annals of Internal Medicine, 152(7):426–433, 2010.
 [7] A.L. Hill, D.G. Rand, M.A. Nowak, and N.A. Christakis. Infectious disease modeling of social contagion in networks. PLoS Computational Biology, 6(11):e1000968, 2010.
 [8] H. Tong, B. A. Prakash, C. Tsourakakis, T. EliassiRad, C. Faloutsos, and D.H. Chau. On the vulnerability of large graphs. In Proc. IEEE Intern. Conf. on Data Mining, pages 1091–1096, 2010.

[9]
K. Scaman, A. Kalogeratos, and N. Vayatis.
A greedy approach for dynamic control of diffusion processes in
networks.
In
Proc. IEEE Intern. Conf. on Tools with Artificial Intelligence
, pages 652–659, 2015.  [10] A. Beutel, B.A. Prakash, R. Rosenfeld, and C. Faloutsos. Interacting viruses in networks: can both survive? In Proc. ACM SIGKDD Intern. Conf. on Knowledge Discovery and Data Mining, pages 426–434, 2012.
 [11] K. Scaman, A. Kalogeratos, and N. Vayatis. Suppressing epidemics in networks using priority planning. IEEE Trans. on Network Science and Engineering, 3(4):271–285, 2016.
 [12] R.E. Rowthorn, R. Laxminarayan, and C.A. Gilligan. Optimal control of epidemics in metapopulations. J. R. S. Interface, 6(41):1135–1144, 2009.
 [13] G.A. Forster and C.A. Gilligan. Optimizing the control of disease infestations at the landscape scale. Proc. National Academy of Sciences, 104(12):4984–4989, 2007.
Comments
There are no comments yet.