key: cord-0046120-uas8hsl5
authors: nan
title: Contact Adaption During Epidemics: A Multilayer Network Formulation Approach
date: 2017-11-02
journal: IEEE Trans Netw Sci Eng
DOI: 10.1109/tnse.2017.2770091
sha: 054dffc2efc75a0a6227386c34ad8943c03bf187
doc_id: 46120
cord_uid: uas8hsl5

People change their physical contacts as a preventive response to infectious disease propagations. Yet, only a few mathematical models consider the coupled dynamics of the disease propagation and the contact adaptation process. This paper presents a model where each agent has a default contact neighborhood set, and switches to a different contact set once she becomes alert about infection among her default contacts. Since each agent can adopt either of two possible neighborhood sets, the overall contact network switches among [Formula: see text] possible configurations. Notably, a two-layer network representation can fully model the underlying adaptive, state-dependent contact network. Contact adaptation influences the size of the disease prevalence and the epidemic threshold—a characteristic measure of a contact network robustness against epidemics—in a nonlinear fashion. Particularly, the epidemic threshold for the presented adaptive contact network belongs to the solution of a nonlinear Perron-Frobenius (NPF) problem, which does not depend on the contact adaptation rate monotonically. Furthermore, the network adaptation model predicts a counter-intuitive scenario where adaptively changing contacts may adversely lead to lower network robustness against epidemic spreading if the contact adaptation is not fast enough. An original result for a class of NPF problems facilitate the analytical developments in this paper.

M ATHEMATICAL models of infectious diseases transmission are one of the primary tools for understanding the propagation of infectious diseases among plant, animal, or human populations [1] , [2] , [3] . Understanding how spreading dynamics are affected by individual-level transmission characteristics and large-scale properties of interactions aids endeavors to control and mitigate epidemics, making it critical for the public health and security.

In addition to their critical role in public health decision making [4] , infectious disease models are appealing from complex systems perspective. Take for instance the Susceptible-Infected-Susceptible (SIS) model [3] , where each individual in the population is either 'Susceptible' or 'Infected'. The SIS model simply states that susceptible individuals may become infected when interacting with infected individuals, and infected individuals will become susceptible immediately after recovery. Rich dynamics of the SIS model, such as the phase transition observed between fast die-out of infections and long-term epidemic persistence [5] , exemplify the ability of simple individual-level interactions to give rise to emergent phenomena.

Understanding disease transmission dynamics in human social networks is particularly challenging [6] , partly because humans take preventive measures and alter their interactions in response to disease spreading [7] , which subsequently change the course of the spreading [8] . As such, coupled modeling of behavioral change and infection transmission dynamics has seen significant attention recently [8] , [9] , [10] , [11] . Medical treatments, quarantines, illness management practices, and individual preventive behaviors are a few examples of ways society works to reduce disease spreading.

Common preventive behaviors of individuals to the emergence of an epidemic are (1) adopting hygiene/pharmaceutical actions such as wearing a mask, using condoms, improving bodily/environmental cleanliness, and receiving vaccinations, and (2) altering contacts to avoid infection. In the first case, individuals are intending to reduce the probability of infection by cleansing themselves and their environment-or at least placing barriers between the two [12] , [13] , [14] , [15] , [16] , [17] . In the second case, when individuals change who they come in contact with, the fundamental topology of the network itself is changing. As individuals remove certain contacts with people, while possibly creating new ones, the structural paths available to dynamic processes are being altered, resulting in rich dynamic interplay between network topology and the spreading process on top of it [18] , [19] , [20] , [21] , [22] , [23] , [24] , [25] , [26] .

Existing approaches to incorporate preventive behaviors in mathematical models of infectious diseases fall into two general categories. First approach incorporates the effect of preventive behaviors directly into disease model parameters [27] , [28] , [29] , [30] , [31] , [32] , [33] . The second approach introduces additional dynamic states into a disease model to explicitly distinguish those who have adopted a preventive behavior from those who have not [13] , [17] , [34] , [35] , [36] , [37] , [38] . One example of individual-based models taking the second approach is the susceptible-alert-infectedsusceptible (SAIS) framework, first introduced in [17] .

The SAIS framework adds an 'Alert' state to the networked SIS model of [39] . The alert state represents individuals who (similar to susceptible individuals) can potentially become infected, but has adopted a preventive behavior. In the original SAIS model [17] , alert individuals have a lower infection rate compared to the susceptible individuals, and susceptible individuals could become alert in presence of infection among their local contacts. The lower infection rate of alert individuals would correspond to their type-1 preventive behaviors (such as wearing masks or using condoms). This model predicts possibility of total eradication of an epidemics through preventive behaviors [34] . In a subsequent study [40] , authors considered an informationdissemination network as an alternative alerting mechanism, and proposed the optimal design solution for an information-dissemination network based on eigenvector centralities [41] in the contact network graph. The SAIS model has been further explored in [42] , [43] , [44] .

In this paper, we introduce the AC-SAIS model, where AC stands for 'Adaptive Contact', to model a scenario in which individuals change their contact neighborhood upon becoming alert. More specifically, each susceptible individual i is in contact with a given set of individuals ðN S i Þ, and when she becomes alert, she switches to another set of individuals ðN A i Þ. We will use the terms default neighborhood and adapted neighborhood to distinguish the two. In our model, we assume both of these neighborhoods are known a priori. Yet, we do no make any restrictive assumptions on these neighborhood sets and deliver our results in the most generic setup. In practice, the default and adapted neighborhood sets might be closely related. For example, in a social distancing scenario [45] , the adapted neighborhood would be a subset of the default neighborhood. Social distancing is not the only possible scenario of contact adaptation. In the context of sexually transmitted infections, for example, when a person is notified that one of his sexual partners is infected, in response, he may abandon all or some of his set of partners and seek partnership from a new venue.

When nodes adapt their contacts to a neighborhood constituting a more robust network, one might intuitively expect that the robustness of the network against epidemic spreading increases monotonically with the contact adaptation rate. This is true in the case of social distancing (where the alert neighborhood is a subset of the default ones) as it always help mitigating epidemic spreading, and the faster the social distancing is implemented, the better. However, when the set of adapted contacts of an individual is not restricted to be a subset of their default contacts, the network robustness against epidemic spreading can be a nonmonotone function of the contact adaptation rate. Indeed, our model detects a counter-intuitive scenario where adaptively changing contacts may adversely lead to lower network robustness against epidemic spreading if the adaptation is not fast enough.

From dynamical systems perspective, this study contains several contributions. First, we propose a novel state-dependent switching network framework and show that a multilayer-network [46] formulation can be successfully employed. Second, we develop an original result of nonlinear Perron-Frobenius theory, where we find necessary and sufficient conditions for existence and uniqueness of a strictly positive eigenvector for the class of nonnegative, concave maps. We apply this tool to find the epidemic threshold for our AC-SAIS model. Furthermore, we introduce a novel notion of connectivity for multilayer networks, which is novel for the new research field of multilayer networks.

The rest of the paper is organized as follows: After the literature review in Section 2, Section 3 introduces a novel notion of multilayer connectivity and an original result for nonlinear Perron-Frobenius theory, which are pivotal for the subsequent modeling and analysis. Section 4 develops the AC-SAIS model, showing that the proposed adaptive contact can be equivalently modeled by multilayer networks. Analyses in Section 5 are followed by numerical experiments in Section 6. Several proofs to theorems and lemmas are omitted for the sake of brevity, and can be found in the Supplemental Materials of this article, which can be found on the Computer Society Digital Library at http://doi.ieeecomputersociety.org/ 10.1109/TNSE.2017.2770091.

Typical approaches to modeling spreading processes on networks consider network topologies as independent of individual node states, such is the case when nodes retain the same set of contacts regardless of whether or not they, or their neighbors, are infected. This assumption is made for simplicity's sake and is not representative of real world networks; especially in regards to social networks where a person's contacts are in constant fluctuation. The notion of state-dependent topologies is especially poignant in the context of disease dynamics where a person will adjust who they come in contact with when in the presence of an infection. The extent to which this occurs can vary greatly-from removing a single contact to completely changing all of them-depending on the perceived severity of an infection.

Several formulations of adaptive contact exist in the literature of infectious disease modeling, including: 1) social distancing [47] , where healthy individuals lower their contact with the rest of the population, 2) delete-and-reactivate [48] , where healthy break their contact with infected population and reactivate after some time, 3) rewiring [49] , [50] , where healthy break their contact with infected population and create new links with healthy members [21] or any other randomly chosen individual [23] .

Altering the local contacts can have a strong effect on disease dynamics, which in turn influences the contact adaptation process; a complicated mutual interaction between a time varying network topology and the dynamics of the nodes emerges. For example, Gross et al. [21] presented a model where susceptible individuals rewire their links from other infected individuals toward susceptible ones in an SIS model, resulting in the formation of two loosely connected clusters. Several researches have built on this model: Marceau et al. [22] additionally include the infection state of its neighbors in the node information. Risau et al. [23] rewire susceptible individuals from infected neighbors to random nodes, which in some cases completely suppresses epidemic spreading.

Most of contact adaptation schemes have been implemented for well-mixed populations or random network models of physical interactions. Studies that work with generic graphs as their contact network are scarce in the literature. Among a few existing research endeavors is the Adaptive-SIS (ASIS) model developed by Guo et al. [48] , who studied an SIS epidemic model where contacts between susceptible and infected nodes are removed at some rate and reactivated later. They showed the epidemic threshold increases as a function of the link removal rate, while the network topology exhibits binomial-like degree distribution, assortative mixing, and modularity. This approach was rigorously extended by Ogura and Preciado [51] , who additionally considered heterogeneous node and edge parameters, as well as a method for optimizing adaptation rates to mitigate epidemic outbreaks. This approach of adaptation for generic graphs considers a dynamic equation for the edge weights which is coupled with the epidemic model. Another approach would be through the notion of switching networks in dynamical systems.

A switching contact network is defined as a set of distinct networks where the "active" network at any given time is determined by some switching signal. More precisely, we denote a switching network GðtÞ ¼ ðV; E sðtÞ Þ, where sðtÞ : R ! f1; 2; . . . ; qg is a signal that determines which of the q networks are active at time t. Usually this signal is external and independent of the system states. For example, a common approach is to consider sðtÞ as a Markov process independent from the disease states [52] , [53] . The collection of possible edge sets E ¼ fE 1 ; E 2 ; . . . ; E q g may be given a priori as in [52] , or they might be generated from local processes as in [53] . In the latter, Ogura and Preciado considered a base graph with jEj edges where each edge can become active or inactive according to an externally defined Markov process, leading to an overall 2 jEj possible configurations for the switching contact network. We can also think of a more complex situation where the switching signal is dependent on the system states. In this way, the topology of the active network determines the evolution of the dynamic process and in turn, the state of the process itself signals network switching. Here lies our proposed contact adaptation scheme.

We consider a class of switching networks where the neighborhood set of each node depends on the state it occupies. Specifically, each node i has one of two contact sets N S i and N A i , depending on whether is is 'susceptible' or 'alert'. Therefore, for a network of size N, the entirety of the switching network is composed of 2 N separate topologies. In this case, not only the network state-space size exponentially increases by N, but also the switching signal depends on the collective system state.

Before diving into the modeling and analysis, we first start with a novel notion of connectivity for multilayer networks and an original results for a class of nonlinear Perron-Frobenius problems that will facilitate the subsequent developments in this paper.

The classical Perron-Frobenius theorem [54] concerns the eigenvalue problem Ax ¼ x for a nonnegative and irreducible matrix A. Let R n þ be the non-negative cone in the nÀdimensional Euclidean space

Assuming x; y 2 R n þ , here x " y (x 0 y) means x i y i (x i < y i ) for 1 i n and x n y denotes x " y but x 6 ¼ y. A matrix A ¼ ½a ij is called non-negative if all of its entries are either positive or zero. We can construct a graph GðAÞ associated with A such that the edge ði; jÞ exists if a ij > 0. The matrix A is irreducible if and only if its associated graph GðAÞ is strongly connected. The classical Perron-Frobenius theorem may be stated as the following:

Theorem 1 (Perron-Frobenius Theorem [54] ). Let A be a nonnegative, irreducible matrix. Then A has a positive eigenvalue 1 > 0 which has multiplicity one and any eigenvalue of A has a magnitude smaller than or equal to 1 . Furthermore the eigenvector v v 1 corresponding to 1 is strictly positive (i.e., v v 1 1 0) and is the only eigenvector of A in the nonnegative cone.

From mappings perspective, the classical Perron-Frobenius theory concerns solutions to the eigenvalue problem F ðxÞ ¼ x where F ðxÞ ¼ Ax is a linear self-map of the non-negative cone. By "self-map of the non-negative cone," we mean that F : R n þ ! R n þ maps the non-negative cone to itself. But what if the map F ðxÞ is not linear? Can we still get powerful results for nonlinear maps analogous to the Perron-Frobenius theorem? The whole area of the nonlinear Perron-Frobenius theory [55] , [56] , [57] , [58] , [59] seeks answer to these questions. A thorough review of nonlinear Perron-Frobenius theory is out of the scope of this paper. In short, results are usually more limited in that existence, uniqueness, or strictly positivity of an eigenvector is seldom guaranteed unless under restrictive assumptions on the nonlinear map.

The following properties are among the possibilities to relax the linearity assumption for the non-negative map F . Note that the linear map F ðxÞ ¼ Ax with non-negative matrix A has all of these properties.

þ is a self-map of nonnegative cone. We say F is 1) homogeneous, if for any x # 0 and c ! 0, F ðcxÞ ¼ cF ðxÞ, 2) concave, if F ðux þ ð1 À uÞyÞ # uF ðxÞ þ ð1 À uÞF ðyÞ for all x; y # 0 and 0 u 1, 3) super-additive, if F ðx þ yÞ # F ðxÞ þ F ðyÞ for all

x; y # 0, 4) monotone, 1 if F ðyÞ # F ðxÞ for all y # x # 0.

The homogeneity property indicates that if x à # 0 is an eigenvector of F , so is cx à for any c ! 0. Furthermore, the following lemma indicates that the class of homogeneous, concave self-maps of the non-negative cone is a special case of homogeneous, monotone maps.

þ is a homogeneous, concave map of the non-negative cone, then F is also monotone and superadditive.

Several results in the literature concern the more general class of homogeneous, monotone maps [56] , [57] . While existence and strict positivity of an eigenvector can be proved for this class of maps, uniqueness cannot be guaranteed without quite restrictive assumptions [56] . For example, 2 for the homogeneous, monotone function F ðxÞ ¼ ½maxfx 1 ; x 2 2 g; maxf x 1 2 ; x 2 g T , any vector ½x 1 ;

x 2 2x 1 is an eigenvector of F with eigenvalue ¼ 1. On the contrary, existence and strict positivity of a unique eigenvector can be proved for the special class of homogeneous, concave maps.

The nonlinear map of interest in this paper falls in the special class of homogeneous and concave maps. Therefore, we focus on this class of nonlinear maps and develop a new result.

So far, we relaxed the linearity restriction by assuming that our nonlinear map is homogeneous and concave. The next question is what would be the counter part to irreducibility of A in the linear map F ðxÞ ¼ Ax for a homogeneous, concave map. For homogeneous, concave maps, Krause [58] proposes the following condition:

Definition 2 (Krause [58] , Section 3). We say the homogeneous, concave self-map F : R n þ ! R n þ satisfies condition 3 C1 in R n þ if for any non-empty subset ; 6 ¼ J z f1; . . . ; ng, there exists j 2 J and i = 2 J such that F i ðe j Þ > 0, where e j is the jth unit vector in R n and F i denotes the ith component of F .

Furthermore, Krause proves that condition C1 is a sufficient condition for existence and uniqueness of a positive eigenvector:

Theorem 2 (Krause [58] , Theorem 13) . For the self-map F : R n þ ! R n þ , which is concave, homogeneous, and satisfies condition C1, the equation F ðxÞ ¼ x has a strictly positive solution x ¼ x à 1 0, ¼ à > 0, and x à is the only eigenvector in the non-negative cone (up to scaling).

We argue that the condition C1 for the notion of irreducibility in [58] may be restrictive, and same strong results would be still valid under a more relaxed condition. Indeed, the nonlinear map of our interest in this paper may not satisfy the condition C1 in Definition 2.

To illustrate, suppose n ¼ 3 and the nonlinear map is

This map is both homogeneous and concave. However, it does not satisfy condition C1 of [58] stated in Definition 2. To test this, let J ¼ f2; 3g; no j 2 J leads to F 1 ðe j Þ > 0 because F ðe 2 Þ ¼ e 3 and F ðe 3 Þ ¼ e 2 . However, this map has a unique, strictly positive eigenvector

Again, F ðe 2 Þ ¼ e 3 and F ðe 3 Þ ¼ e 2 , so it does not satisfy condition C1. However, this map has a unique, strictly positive eigenvector

We say the homogeneous, concave self-map

The following lemma proves that C2 is indeed less restrictive than C1. Lemma 2. A homogeneous, concave self-map F of the nonnegative cone that satisfies condition C1 also satisfies condition C2.

We would like to emphasize that there is nothing special about usage of e J in Definition 3. The following lemma shows that any vector that has positive values on elements corresponding to J and is zero on other elements would be equivalently applicable. In the linear domain, we know that if a non-negative matrix A is irreducible, the matrix A þ cI is primitive for any c > 0 [60, Theorem 9], and vice versa. How would be the extension of this idea to the nonlinear domain? First, let us precisely define a primitive map. The following theorem states that F satisfying C2 and F ðxÞ þ cx being primitive are equivalent.

Theorem 3. The map F c ðxÞ , cx þ F ðxÞ with c > 0 is primitive if and only if the homogeneous, concave self-map F : R n þ ! R n þ of the non-negative cone satisfies condition C2. The duality between F satisfying C2 and F ðxÞ þ cx being primitive leads to the main theorem in this paper:

Compared with Theorem 1, it is evident that results for the nonlinear Perron-Frobenius problem in case of homogeneous, concave maps are very strong; existence and uniqueness of a strictly positive eigenvector can be guaranteed. Our contribution to the theory of nonlinear Perron-Frobenius theory for homogeneous, concave maps is that we relaxed the 2. This example is from [56] . 3. In Krause [58] , authors refer to this condition as being irreducible. We choose to avoid this term to avoid any confusion with other notions that tend to extend irreducibility of linear maps to nonlinear domain. sufficient condition of [58] (through replacing C1 by C2) and proved that this new 4 condition is also the necessary condition for uniqueness of the eigenvector in the non-negative cone.

Graph theory is the mathematics of networks. In graph theory, a directed graph is formally defined as an ordered pair G ¼ ðV; EÞ, where V is the set of nodes and E & V Â V is the set of ordered pairs of nodes representing their directed relation. We say node j is a neighbor of node i, if ði; jÞ 2 E. The set N i ¼ fjjði; jÞ 2 Eg denotes the neighbors of node i. A path ðv 0 ¼ i; v 1 ; . . . ; v lÀ1 ; v l ¼ jÞ of length l is an ordered tuple of edges than connects i to j, i.e., ðv kÀ1 ; v k Þ 2 E. A directed graph is strongly connected if there exists a path between all ordered pair of nodes in the network [54] . Several natural and technological systems show complex patterns of interactions among their heterogeneous entities. To capture the complexities of such systems, the network science community has recently shown substantial interest in the notion of multilayer networks [46] , [61] and developing proper mathematics for them beyond the classical graph theory [62] .

In this paper, we denote a multilayer network 5 as an ordered tuple G ¼ ðV; E A ; E B Þ where nodes in V are connected through two link types E A and E B . Corresponding to the multilayer network G, we define G A ¼ ðV; E A Þ and G B ¼ ðV; E B Þ as the layers of G. Motivated by the notion of strong connectivity for directed graphs, we propose a novel notion of connectivity for multilayer networks in the following.

Our proposed notion of multilayer connectivity, which from now on we will refer to it as M-connectivity, has an algorithmic definition. To motivate and acquaint our definition to the reader, we first point out a straight-forward property of simple strongly connected graphs. Suppose for the graph G ¼ ðV; EÞ we have an arbitrary partition P of the node set V , i.e., members of P are non-empty disjoint subsets of V that cover V , more precisely

[

We can build a graph G G ¼ ðP; LÞ, where the partition set P is the node set of G G. Note that each node I 2 P of G G is a partitioning subset of V . As such, to avoid possible confusion, we will refer to nodes of G G as hypernodes from now on. We assign a directed link from one hypernode I 2 P to another hypernode J 2 P, if there is a node i 2 I of G that is connected to a node j 2 J, i.e., ði; jÞ 2 E. Trivially, yet importantly, strong connectivity of G implies strong connectivity of G G. For a multilayer network G, we use a related notion to define connectivity. 6 The main difference is that connection among subsets must be through both layers. Following provides a formal definition. For a multilayer network G ¼ ðV;

. . . ; fNgg is the trivial partition of V singletons. From the graph G G kÀ1 , we build G G k ¼ ðP k ; L k Þ in the following way:

Step 1. Define the hypernode set P k of cardinality equal to the number of strongly connected components of G G kÀ1 where each element I 2 P k groups one and only one strongly connected component of G G kÀ1 (i.e., I is the union of all the hypernodes in that strongly connected component). Note that, doing so, the hypernode set P k always denotes a partitioning of the node set V .

Step2. We assign the directed link ðI; JÞ 2 L k if at least one single node in I is connected to J through both layers simultaneously, 7 i.e.,

ði; j 2 Þ 2 E B for some j 1 ; j 2 2 J : Fig. 1 illustrates the iterative procedure explained above.

. . . ; fNgg is the trivial partition of V singletonsand inductively building G G 1 ; G G 2 ; . . . following Step 1 and Step 2 described above, there exists an iteration step k à such that G G kà is strongly connected.

Intuitively, M-connectivity of G implies that if we split the node set V into any two subsets V a and V b , there is always a node in V a (resp. V b ) that is connected to V b (resp. V a ) through both edge types. A necessary condition for Mconnectivity of G is that both individual layers G A and G B are strongly connected. Moreover, a sufficient condition for M-connectivity of G is that the intersection graph G c , ðV; E A \ E B Þ is strongly connected (because, G G 1 which is similar to G c , will be already strongly connected).

M-Connectivity and Condition C2. Consider a multilayer network G ¼ ðV; E A ; E B Þ, where the node set are labeled from 1 to N, i.e., V ¼ f1; 2; . . . ; Ng. By defining a real valued vector x : V ! R N þ on node set V , we show the relation between M-connectivity and condition C2 for functions F ðxÞ. 4 . We got the inspiration for our definition of condition C2 for homogeneous, concave maps from a notion in [56] for homogeneous, monotone maps. Gaubert and Gunawardena [56] refer to the homogeneous, monotone map F as indecomposable if for any choice of ; 6 ¼ J z f1; . . . ; ng, there exists i = 2 J such that lim a!1 F i ðr J ðaÞÞ ¼ 1, where r J ðaÞ is defined as ðr J ðaÞÞ j ¼ a if j 2 J; and ðr J ðaÞÞ j ¼ 1 otherwise. While this may look very similar (or perhaps equivalent) to condition C2, we would like to point out a subtle difference which can be very consequential. Consider the function F ðxÞ ¼ ½

This function is homogeneous, concave, and monotone. It does not satisfy condition C2 because for J ¼ f2g we get F 1 ðe J Þ ¼ F 1 ðe 2 Þ ¼ 0. However, it falls in the category of indecomposable maps of [56] because lim a!1 F 1 ðr 2 ðaÞÞ ¼ lim a!1 4a 3 2 1þa ¼ 1 and lim a!1 F 2 ðr 1 ðaÞÞ ¼ lim a!1 1 þ a ¼ 1. The nonlinear eigenvalue problem for this function gives two eigenvectors in R 2 þ , namely,

5. In some literature, this may be referred to as a multiplex network. 6 . We have been inspired by the notions of indecomposability for nonlinear maps and the method of aggregated graphs from Gaubert and Gunawardena [56,

7. Note that this is different from, 9i 1 ; i 2 2 I s:t: ði 1 ; j 1 Þ 2 E A ; ði 2 ; j 2 Þ 2 E B for some j 1 ; j 2 2 J, which basically indicates that both individual layers G A and G B are strongly connected.

Theorem 5. Associated with the multilayer network

. . . ; Ng, suppose a homogeneous, concave map F of the non-negative cone is such that for any nontrivial subset J of V and i = 2 J, F i ðe J Þ > 0 if and only if there exists j 1 ; j 2 2 J for which ði; j 1 Þ 2 E A and ði; j 2 Þ 2 E B . Then, F satisfies condition C2 if and only if the multilayer network G is M-connected.

Before introducing our model, we first review a background on the networked SIS epidemic process.

Susceptible-infected-susceptible model is a paradigmatic epidemic spreading model. In the SIS model, each individual is either susceptible or infected, and individuals are assumed to immediately become susceptible to the disease after recovery. SIS model is thus suitable for modeling sexually transmitted infections such as Gonorrhea and Syphilis [2] .

Classical compartmental epidemic models assume homogeneous (fully mixed) interactions among individuals. In networked epidemic models, interactions among individuals are explicitly modeled using a contact network, represented by the graph G ¼ ðV; EÞ, where individuals are represented by nodes V of a graph and possible interactions are the edges E of a graph. Node j is a neighbor of node i, denoted as ði; jÞ 2 E, if she can infect node i directly. We can also use weighted graphs to represent contact networks. Doing so, the weight value of a link would serve as a proxy for heterogeneity of contact levels among pairs of individuals. For example, if both nodes j and k are infected and w ij ¼ 2w ik , the likelihood that a susceptible node i contracts the disease from node j is double the likelihood of contracting it from node k. In this paper, we allow the contact graph be directed and weighted.

In the networked SIS model [63] , the state of node i at time t is denoted by X i ðtÞ 2 fS; Ig, where X i ðtÞ ¼ S if the node is susceptible or X i ðtÞ ¼ I if it is infected. In this model, a susceptible nodes becomes infected if it is exposed to an infected individual. Moreover, an infected individual recovers and becomes susceptible again after a recovery period. The infection and curing times are commonly assumed to have a memoryless property, leading to exponentially distributed time intervals in continuous time descriptions. More general time distributions are also possible and addressed in the literature to some extent [53] , [64] , [65] , [66] , [67] .

The overall evolution of the nodes states are due to their interactions with each other. Hence, mathematical description of the SIS model requires utilization of the collective state X X ¼ ½X 1 ; . . . ; X N , which is the joint state of all N nodes in the network. The network state is a continuoustime Markov process that undergoes transition over a space consisting of 2 N possible network states. In this description, we say an event has occurred if the state of a single node changes. Furthermore, the time interval for the event occurrence is exponentially distributed. This time interval can equivalently be described as the minimum of transition times of a set of statistically independent processes on node states, denoted by X i , and pair states, denoted by ðX i ; X j Þ, as the following:

T $ expðdÞ; ðX i ; X j Þ : ðS; IÞ ! ðI; IÞ; ifði; jÞ 2 E;

T $ expðbw ij Þ;

where d and b are called curing and infection rates, respectively, and T represents the corresponding exponentially distributed transition duration.

Describing the network Markov process as competition among statistically independent nodal and edge-based transitions, similar to the above formulation of the SIS process, allows for a much more general framework for modeling networked epidemic processes (see, [68] ). We will use this approach to describe our adaptive contact epidemic model.

Finally, the Kolmogorov equation, which governs probability distribution of the SIS Markov process, is a system of 2 N coupled differential equations which is neither computationally nor analytically tractable for large number of nodes. . (b) The first graph G G 1 has the hypernodes set P 1 ¼ ff1g; f2g; . . . ; f12gg, and its links are the intersection of E A and E B edges. Hypernodes are depicted by black squares, and links between them are shown by black arrows. The graph G G 1 is not strongly connected. (c) The second aggregate graph G G 2 has the strongly connected components of G G 1 as its hypernodes set P 2 ¼ ff1; 2; 3g; f4; 5; 6g; f7; 8; 9g; f10; 11; 12gg. The links among the hypernodes is according to Step 2 in Section 3.2. For example, the directed link ðf4; 5; 6g; f7; 8; 9gÞ 2 L 2 is due to node 6, a member of f4; 5; 6g, being connected to the hypernode f7; 8; 9g through both layers (because, ð6; 8Þ 2 E A and ð6; 7Þ 2 E B :). The graph G G 2 is not strongly connected either. (d) The third aggregated graph G G 3 groups strongly connected components of G G 2 as its hypernodes set P 3 ¼ ff1; 2; 3; 4; 5; 6g; f7; 8; 9g; f10; 11; 12gg. The graph G G 3 is strongly connected. Therefore, the two-layer network in (a) is M-connected according to Definition 1.

Moment closure approximations [39] , [68] , [69] , [70] or Monte Carlo simulations are thus necessary to study the networked SIS process. The SIS process shows a phase transition behavior where initial infections die out quickly for small values of b=d, while infections can persist in the network for long time (coined as metastable state) for large values of b=d [71] . The critical value separating these regions is called the epidemic threshold. As such, epidemic threshold suggests a measure of networks robustness against epidemic spreading. In this paper, whenever we say network a is more robust against epidemic spreading than network b, we mean network a has a larger value of epidemic threshold that network b.

Consider a population of N individuals, where each individual is either susceptible, alert, or infected. For each individual i 2 f1; . . . ; Ng, let the random variable X i ðtÞ ¼ S if the individual i is susceptible at time t, X i ðtÞ ¼ A if alert, and X i ðtÞ ¼ I if infected. In the AC-SAIS model of this paper, contacts of a node depends on her state. Specifically, we define N S i as the neighbors of node i when she is susceptible, and N A i as her neighbors when she is alert. Associated with these neighborhood sets, we consider weight values w S ij > 0 if j 2 N S i and w A ij > 0 if j 2 N A i as a proxy for heterogeneity of the contact levels.

Four competing stochastic transitions describe the AC-SAIS model, as Fig. 2 A Few Remarks on the AC-SAIS Model. The disease dynamics component of the AC-SAIS model is according to the networked SIS model, elaborated in Section 4.1. Therefore, a representative example would be the spread of Syphilis or Gonorrhea for which the sexual contact network is welldefined and disease dynamics are SIS-type. In this scenario, the alerting process can be the result of a partner notification effort.

In the AC-SAIS model, we assume that if an alert individual never gets infected, she will remain in the alert state indefinitely. In other words, we do not consider an awareness decay process where alert individuals can transition to the susceptible state directly. In practice, we are assuming that the awareness decay process is so much slower than the disease dynamics that it becomes irrelevant for the disease spreading. Interested readers can refer to [44] for analysis of an SAIS model with awareness decay.

The current setup of the AC-SAIS model only considers a type-2 preventive behavior of altering contacts, whereas the original SAIS model considered a type-1 preventive behavior by assuming a lower infection rate for alert individuals. It would be possible to also incorporate type-1 behaviors in the AC-SAIS model by lowering the infection rate for the alert individuals to b a < b. In order to isolate the role of network adaptation, we do not change the infection rate in this study.

The contact alteration scheme in the AC-SAIS model assumes the contacts set of an individual only depends on her own state; it is the default set when susceptible, and the adapted set when alert. Particularly, the contact set of an alert individual is fixed and is independent of the health state of those contacts. Such contact adaptation scheme is most sensible when the identity of infected contacts are not known to the individual. For example, in the context of sexually transmitted diseases and partner notification, the identity of the infectious patient is not revealed to their partners. So, a subsequent contact adaptation may not necessarily lead to definite avoidance of infectious partners.

From a networked dynamical system perspective, the network topology in the AC-SAIS model is time-varying and switches among 2 N different possibilities because each node i may adopt one of the two neighborhood sets N S i and N A i . However, the AC-SAIS model can be equivalently interpreted as a spreading process on a two-layer network. The AC-SAIS Markov process described in Section 4.2 falls in the broad class of generalized epidemic modeling framework (GEMF) introduced in [68] for spreading processes on multilayer networks. In essence, the switching contact network of the AC-SAIS model can be equivalently described as a spreading process on multilayer network G ¼ ðV; E S ; E A Þ, where each layer determines the interaction neighborhood that induces state change in a node, depending on its current state. Note that we only need to include layers for susceptible and alert nodes, because the transition of an infected node towards the susceptible state is spontaneous and does not depend on other nodes states. Significantly, a multilayer network formulation of adaptive contact reduces the problem from defining a process between 2 N separate topologies to defining a process on top of a static two-layer network, effectively modeling complex switching dynamics with a conceptually straightforward framework. The network layers G S ¼ ðV; E S Þ and G A ¼ ðV; E A Þ represent the two extreme cases among all possible 2 N configurations. The network layer G S would be physical contact network if none of the nodes were alert, and the network layer G A would be the physical contact network if none of the nodes were susceptible. Associated with network layers G S and G A , we define the weighted adjacency matrices W S ¼ ½w S ij and W A ¼ ½w A ij , respectively. The realized topology at a given time will be a mixture of the two network layers according to the collective node states at that time. Interestingly though, we show it is possible to characterize the behavior of the AC-SAIS model in terms of the spectral properties of W S and W A and their interrelation.

Remark. The actual, physical/social contact between the network agents is fundamentally different from those represented by the multilayer network G. For example, a directed edge ði; jÞ 2 E S is physically relevant only if node i is susceptible and node j is infected. Otherwise, node i and j might have a different interaction if, for instance, both are susceptible. However, the later is not relevant for disease spreading and thus no need to be incorporated in our epidemic model. Take for instance the contact between node i, who is a nurse, and node j, who is a student. These two might not have any social contact in normal situation, however, when node j (the student) is sick, she can possibly pass infection to node i (the nurse); and this is the contact important for epidemic modeling purpose. Also, realize that this contact is directional because when the nurse is sick, she may not have a physical contact with the student. This is why in our state-dependent contact network formulation we do not make "undirectedness" assumption on the underlying graph.

Similar to the networked SIS model described in Section 4.1, the collective state X XðtÞ in the AC-SAIS model is a Markov process. However, this Markov process is both analytically and numerically intractable due to its exponential state space size of 3 N (each node can be in one of three states). We can leverage the observation that the AC-SAIS model falls in the GEMF class of stochastic spreading processes on multilayer networks-for which Sahneh et al. [68] have derived a system of nonlinear differential equations describing the evolution of state-occupancy probabilities after adopting a first-order, mean-field-type approximation.

Following procedures explained in [68] , we find the first order mean-field-type approximate model for the AC-SAIS model as

for i 2 f1; . . . ; Ng, where p i corresponds to the probability that individual i is infected, and q i corresponds to the probability that she is alert. It is worthwhile to acknowledge the limitations of meanfield models. Statistical physics tells us that MF approximations function suitably for infinite-dimensional networks. While, they can perform very poorly for sparse or highly structured networks, such as rings or low-dimensional lattices, particularly close to critical model parameters. Despite, the approximation allows for investigating extremely complex dynamics, and discovering intriguing phenomena and key network characteristics influencing them.

In this section, we compute and study the epidemic threshold of the mean-field AC-SAIS model in Eqs. ( (2) and (3)) through analyzing its equilibrium points. Our motivation for this approach stems from the mean-field SIS model which exhibits a threshold phenomena in its equilibrium where a stable (see, [72] , [73] , [74] ) endemic equilibrium emerges [39] .

To facilitate the subsequent analysis, we make the following assumption on the structure of the default and adapted neighborhoods throughout this article. Assumption 1. The edge sets E S and E A are such that the twolayer network G ¼ ðV; E S ; E A Þ is M-connected according to Definition 5.

Our approach to finding the critical value t c for AC-SAIS model (Eqs. (2) and (3)) is through examining the equilibrium points; as used by Van Mieghem for the SIS model in [39] . The idea is to show that for t > t c an endemic equilibrium (p à i > 0; 8iÞ exists aside from the disease-free equilibrium. 8 In this approach, strong connectivity of the underlying contact network is pivotal. In case of the SIS model, Van Mieghem [39] showed that if the contact graph is strongly connected, equilibriums of the mean-field model must either be all zero-the disease-free equilibrium-or they must be strictly positive-the endemic equilibrium. Following lemma shows that similar argument holds for the AC-SAIS model (Eqs. (2) and (3)) under the M-connectivity assumption of the multilayer network G as in Definition 5. 

with effective infection rate t and relative alerting rate k respectively defined as 9 t , b=d; k , k b :

Therefore, according to Eq. (2), the equilibrium infection probabilities p à i satisfy

Replacing q à i from Eq. (5) in Eq. (6) yields the formula in Eq. (4) .

The rest of the proof concerns choosing i deliberately, so that p à j > 0 guarantees p à i > 0, and repeating the process until concluding positive equilibrium probabilities for all nodes. We employ the definition of graphs G G k ¼ ðP k ; L k Þ associated with the multilayer network G ¼ ðV; E S ; E A Þ as explained in Section 3.2. According to Definition 5, if G is M-connected, there exists k à such that G G kà is a strongly connected graph. Eq. (4) indicates that in order to get p à i > 0, both P w A ij p à j and P w S ij p à j must be positive. Therefore, choosing i such that ði; jÞ 2 L 1 (for which w S ij > 0 and w A ij > 0) necessitates p à i > 0. Repeating this process yields the equilibrium probability of all the nodes in the strongly connected component of G 1 that contains j are all positive. This strongly connected component of G 1 becomes a single hypernode, which we call J 2 P 2 , for graph G G 2 . So far, we have proved that 8j 2 J; p à j > 0. According to the definition of G G k , for graph G G 2 , there is a directed link from component J to component I, i.e., ðI; JÞ 2 L 2 , if and only if 9i 2 I such that w A ij 1 ; w S ij 2 > 0 for some j 1 ; j 2 2 J: (7) Since 8j 2 J; p à j > 0, we get p à i > 0 for the above choice of i, which further indicates all the nodes of I have positive equilibrium values. As a result, all the nodes belonging to the strongly connected component of G G 2 that contains J have positive equilibrium values. This procedure can be repeated for G G 3 ; . . . ; G G k à . Since, G G k à is strongly connected, all the nodes of the network must have positive equilibrium values. t u

We can find the epidemic threshold by examining the equilibrium points in Eq. (4). For t < t c , the disease-free state is the only equilibrium. However, for t > t c , another equilibrium point p p à , ½p à 1 ; . . . ; p à N T 1 0, also exists in the positive orthant. Therefore, we find the threshold value of t c if we can find a critical value t ¼ t c such that p à i j t¼tc ¼ 0 while dp à i dt j t¼tc > 0 for all i 2 f1; . . . ; Ng. We have the following theorem regarding the value of the epidemic threshold. We would like to emphasize that such a threshold corresponds to the mean-field approximate model (Eqs. (2) and (3) ) and should not be confused as the actual threshold value in the exact AC-SAIS Markov model. Theorem 6. The threshold value t c for AC-SAIS model ( (2) and (3)) is such that the equation

has a nontrivial solution z z , ½z 1 ; . . . ; z N T 1 0.

Proof. Eq. (4) can be rewritten as

: Now, we take the limit of both sides as t # t c , for which p à i # 0 for 8i according to the definition of an epidemic threshold. Since the limit of numerator and denominator of fraction terms of both sides goes to zero, we apply the L'Hôpital's rule for limits [76] 

Defining z i , d dt p à i j t¼t c , the above equation will lead to (8) . The value of t c that solves (8) is the critical value for which p à i ¼ 0, however, dp à i =dt > 0, denoting a secondorder phase transition at t ¼ t c . Therefore, t c is the epidemic threshold for AC-SAIS model ( (2) and (3)). t u

Letting k ¼ 0 in Eq. (9) yields F ðz zÞ ¼ W S z z, which reduces Eq. (8) to the Perron Frobenius problem z z ¼ t c W S z z, suggesting t c ¼ 1= 1 ðW S Þ; the SIS mean-field threshold. For the AC-SAIS model, the epidemic threshold condition pertains to the nonlinear Perron-Frobenius problem (8) . Though an analytical solution is not expected, we can employ the tools of Section 3.1.

In order to employ Theorem 6, we should prove our nonlinear map F in Eq. (9) is homogeneous and concave, and it satisfies condition C2 defined in Definition 3. The map F in Eq. (9) is defined for interior of the nonnegative cone. We extend the definition to the boundary of the nonnegative cone by letting F ðz zÞ i ¼ 0 whenever P w S ij z j ¼ 0 and P w A ij z j ¼ 0. In this way, F ðz zÞ is well defined for all z z # 0. It is obvious that F in Eq. (9) is a homogeneous map. Concavity of F can be also deduced from the concavity of the function g : R 2 þ ! R þ defined as gðu; vÞ ¼ uv uþv (which is half of the harmonic average) because the arguments of u and v are linear transformation of z i 's. Next lemma proves that it also satisfies condition C2. 9 . According to Poisson processes theory, the effective infection rate t ¼ b=d is equal to the expected number of attempts per link that an infected node makes to infect her neighbor during her infectious period [75] . The relative alerting rate k ¼ k=b indicates the ratio of the chance that an infected neighbor cause her neighbor to become alert versus the causing her to become infected. For instance, k ¼ 1 2 means the chance that a node becomes infected from her infected neighbor is twice the chance of becoming alert as the result of interacting with the same neighbor. Proof. We just argued that F , as defined in Eq. (9), is homogeneous and concave. Also, for any set J, F i ðe J Þ > 0 if and only if there exists i = 2 J and j 1 ; j 2 2 J for which w S i;j 1 > 0 and w A i;j 2 > 0, i.e., ði; j 1 Þ 2 E S and ði; j 2 Þ 2 E A . Therefore, Theorem 5 is applicable and proves the lemma.

t u

Since we showed F in Eq. (9) is homogeneous and concave, and satisfies condition C2, we can apply Theorem 4 to prove existence and uniqueness of a strictly positive solution for z z to the nonlinear Perron-Frobenius problem (8).

Corollary 1. If the multilayer graph G ¼ ðV; E S ; E A Þ is M-connected, the nonlinear Perron-Frobenius problem (8) has a unique solution z z ¼ z z à 1 0 with jjz z à jj 2 ¼ 1. Furthermore, the following numerical update law will converge asymptotically to z z à z z kþ1 ,

with c > 0, and the initial state z z 0 1 0 and jjz z 0 jj 2 ¼ 1. Moreover, the threshold value is t c ¼

Corollary 1 proves the existence and uniqueness of a solution for the AC-SAIS threshold formula in Eq. (8) . Furthermore, the update law of Eq. (10) suggests a numerical algorithm for finding the threshold value. Interestingly, a numerical experiment in the next section (see, Fig. 3) shows that the epidemic threshold value is a non-monotone function of contact adaptation rate (quantified by k); indicating faster contact adaptation is not necessarily always better in suppressing epidemics. Here, we aim to predict such scenarios without numerically solving the nonlinear Perron-Frobenius problem for the epidemic threshold.

The idea is perturbing the threshold Eq. (8) around two extreme cases of k ¼ 0 and k ! 1, for which we know the exact solutions. Specifically, 1) for k ¼ 0, the epidemic threshold is t c j k¼0 ¼ 1 1 ðW S Þ and z zj k¼0 ¼ v v S is a solution, where v v S is the dominant eigenvector of matrix W S ; and 2) for k ! 1, the epidemic threshold is t c j k!1 ¼ 1 1 

and v v A ¼ ½v 1 ; . . . ; v N T and u u A ¼ ½u 1 ; . . . ; u N T are the right and left dominant eigenvectors of A corresponding to 1 ðAÞ with v v T A u u A ¼ 1. Fortunately, spectral perturbation of the nonlinear Perron-Frobenius problem (Eq. (8)) leads to analytically tractable formulas expressed in terms of spectral properties of individual layers G S and G A , and their interrelation (as manifested by C terms in Eqs. (11) and (12)). Using Eq. (11) for small values of k and Eq. (12) for large values of k, we can categorize several solution possibilities for the full range of k values.

To reflect more realistic scenarios, we impose the constraint 1 ðW S Þ > 1 ðW A Þ, that is, we assume that if all healthy individuals adopted their alert neighborhood simultaneously, they would collectively raise the epidemic threshold value, making their network more robust against epidemics than the default contact graph G S .

The three scenarios for the dependency of the threshold value on contact adaptation rate-as shown in Fig. 3 -can be characterize as the following: 1) Monotone scenario (the faster, the better): This is the simplest case where the value of the epidemic threshold increases monotonically with k, as simulated in Section 6 and shown in Fig. 3 , showing three dependency scenarios. All three alert layers have the same spectral radius with respect to G S i.e., 1 ðW S Þ= 1 ðW Ai Þ ¼ 1:5. Therefore, in all of them the threshold value t c ð kÞ starts from t c ð0Þ ¼ 1= 1 ðW S Þ and converges to t c ð1Þ ¼ 1:5t c ð0Þ. Graph G A1 is synthesized such that CðW S ; W A1 Þ < 1. From the red curve we can observe that t c ð kÞ decreases for small k values after which it increases. Graph G A2 is synthesized such that CðW A2 ; W S Þ > 1. In this case the blue curve t c ð kÞ is maximal around k % 2. The topology of graph G A3 is G S with reduced weights and is represented by the black epidemic threshold curve which increases monotonically by k. neighbors upon becoming alert, the higher the rate they do so, the better; because the epidemic threshold increases with the alerting rate in this scenario. 2) Overshooting scenario (moderate even better than fast): It is possible that an optimal alerting rate k exists for which the adaptive network is most robust with respect to spreading infection. In other words, having a moderate contact adaptation rate is even better than than the case where the alerting rate is so large that alerting processes is almost instantaneous. The blue curve in Fig. 3 Fig. 3 depicts such scenario. The following lemma shows that asymmetry of contacts is critical for observing the latter scenario. Lemma 6. If W S and W A are both symmetric, CðW S ; W A Þ is lower-bounded as

Given 1 ðW S Þ > 1 ðW A Þ (the alert layer is more robust than the susceptible layer), the right hand side of Eq. (14) will be always greater than 1. Hence, for undirected network layers, it is impossible for the critical threshold of the adaptive contact network to go below the critical threshold of the default contacts layer, G S . We can conclude that asymmetry of contacts is in part responsible for this unexpected behavior.

In this section, we perform a numerical study to evaluate our findings. For E S edges, we consider the well-known "Football" network from [77] with N ¼ 115 nodes and jE S j ¼ 615 edges, and spectral radius 1 ðW S Þ ¼ 10:8. Given G S , we synthesize three adapted contact layers G A1 , G A2 , and G A3 as described bellow, and compute their corresponding threshold values as a function of the relative alerting rate as shown in Fig. 3 .

The spectral radii of G Ai graphs are all equal to 2 3 of the spectral radius of G S , i.e., 1 ðW Ai Þ ¼ 2 3 1 ðW S Þ. In this way, we ensure that the adapted contacts layers are more robust to epidemic spreading compared to the default contacts layer. This can be verified in Fig. 3 where t c ð1Þ ¼ 3 2 t c ð0Þ. Note that t c ð0Þ is the threshold value when k ¼ 0, i.e., no adaptation occurs, and t c ð1Þ corresponds to k ¼ 1 where the contact adaptation occurs instantaneously. For G A1 , CðW S ; W A1 Þ < 1. From Eq. (11), we can predict that for small values of k, the epidemic threshold decreases below t c ð0Þ, the threshold if no contact adaptation was in place at all . Therefore, we expect an undershoot in t c ð kÞ as a function of k. This is the configuration where contact adaptation can "go wrong"; despite the fact that the alert contact network is more robust, switching to it can adversely aid in the spread of infection. The red curve in Fig. 3 corresponds to this scenario. For G A2 , CðW A2 ; W S Þ > 1. From Eq. (12), we can predict it is possible to get t c ð kÞ > t c ð1Þ, an thus there is a value for k for which t c ð kÞ is maximum. This is in contrast to G A1 in that the epidemic threshold for the multilayer network is greater than its constituent layers. In this configuration, the characteristics are such that an enhanced robustness is created synergistically. The blue curve in Fig. 3 corresponds to this scenario. Graph G A3 is made by decreasing the link weights from G S , representing a social-avoidance scenario. As discussed in Section 5.2, we expect to see a monotonic increase in the epidemic threshold as the contact adaptation rate increases. The black curve in Fig. 3 corresponds to this scenario. In order to synthesize G A1 and G A2 , we performed a greedy search to obtain desired values of C functions. For each alert contact graph, G Ai , and subsequent multilayer network representation, G i ¼ ðV; E S ; E Ai Þ, we examine spreading behavior at three effective infection rates t 1 ¼ 0:9t c ð0Þ, t 2 ¼ 1:3t c ð0Þ, and t 3 ¼ 1:7t c ð0Þ, as seen in Fig. 3 (dotted lines). In our numerical simulations, we have set d ¼ 1, which without loss of generality, chooses the unit of time equal to the expected curing period. Steady-state solutions to the mean-field AC-SAIS Eqs. (2) and (3) are calculated for 10 À2 k 10 2 and fraction of population infected p ¼ 1 N P N i¼1 p i -as the indicator of severity of the spreading-is plotted as a function of the alerting rate in Figs. 4, 5, and 6.

For the multilayer network with G A1 as the adaptive contact layer, we expect to observe increased epidemic sizes-due to a decreased threshold (red curve of Fig. 3 )-for a range of low alerting rates.

In Case 1, the infection rate is chosen so that t < t c ð0Þ < t c ð1Þ. In the top plot of Fig. 4 , we can see that for most k values there is no outbreak, as one would expect since the effective infection rate is below the either extreme values. However, for 0:1 k 1:2 an epidemic is sustained due entirely to inter-layer dynamics creating conditions where an epidemic is more effectively carried throughout the population. In the context of persons altering who they come into contact with, although in an effort to avoid becoming infected, may in fact unintentionally contribute to the opposite outcome.

For Case 2, with t c ð0Þ < t < t c ð1Þ, we observe two regimes of behavior as depicted in the middle plot of Fig. 4 : for lower alerting rates, where the effective infection rate is above the epidemic threshold t c ð kÞ, an infection is sustained. For higher alerting rates the reverse is true since the critical threshold goes above t.

In Case 3, effective infection rate is set above the critical threshold (red curve of Fig. 3) for all values of k, i.e., t c ð kÞ < t. Therefore, persistent infections are observed regardless of contact adaptation rate in bottom plot of Fig. 4 .

We perform the same computations on when the adapted contact layer is G A 2 . Case 1 yields trivially zero infection size. For case 2, shown in the top plot of Fig. 5 , we observe that increasing alerting rate beyond a certain value successfully suppresses the infection spreading. Case 3, shown in the bottom plot of Fig. 5 , provides an interesting observation in that the critical threshold raises even larger than the alert contacts layer, indicating that a moderate rate of contact adaptation is indeed better than fast rates in enhancing the robustness of the network. Therefore, for 0:8 < k < 5, the critical threshold increases such that no infection is sustained. While for larger values an outbreak occurs, and the infection size increases as contact adaptation rate increases.

In the third scenario, the adapted contact layer is constructed by lowering the edge weights of G S . This would correspond to a social distancing scenario, where individuals limit or abandon their contacts when they become alert. As can be seen by the black curve in Fig. 3 , the threshold value increases monotonically by the alerting rate. Fig. 6 depicts the second case where t c ð0Þ < t < t c ð1Þ. As expected, there is a certain value of kà so that the epidemic infection is controlled for alerting rates k ! kÃ. Case 1 and 3 are omitted for trivial behavior.

The state-dependent switching (adaptive) contact network in the AC-SAIS model leads to rich dynamics for the epidemic spreading process and behavior not yet identified in literature (to the best of the authors' knowledge). Intuitively, when nodes can "switch" to a neighborhood constituting a more robust network, the expected effect on the overall robustness of the network would be to increase monotonically with the alerting rate. As shown in Sections 6.2 and 6.1, this is not always the case. Indeed, we observed non-monotone dependency of the epidemic threshold in most of our experiment trials. We show how the adaptive switching topology of the contact network is different from fixed static graphs and can lead to regimes of extreme or unexpected behavior. In particular, it is possible that adaptive behavior towards a supposedly more resilient network can in fact worsen the severity of an outbreak, or enable the Fig. 4 . The effect of alerting rate on infection size for the undershooting scenario, for which the epidemic threshold dependence on k is depicted by the red curve in Fig. 3 . Case 1 (top) Despite setting the effective infection rate below that of the extreme cases, i.e., t < t c ð0Þ < t c ð1Þ, an epidemic outbreak is still observed for small alerting rates because t is larger than the minimum of t c ð kÞ. case 2 (middle) Effective infection rate lies in between the two extreme values, i.e., t c ð0Þ < t < t c ð1Þ. There is a slight increase in infected individuals after which the infection size drops to 0 due to the increase in the critical threshold. Case 3 (bottom) Persistent infections are observed regardless of contact adaptation rate because t c ð kÞ < t for all k. 5 . The effect of alerting rate on infection size for the overshooting scenario, for which the epidemic threshold dependence on k is depicted by the blue curve in Fig. 3 . Case 1 This case is omitted since the infection size would be 0 regardless of the alerting rate. Case 2 (top) The behavior is similar to case 2 with G A1 (middle graph in Fig. 4 ) though the transition to zero infection size occurs at a smaller alerting rate. Case 3 (bottom) This is a scenario when the effective infection rate is larger than the extreme values ðt c ð0Þ < t c ð1Þ < tÞ, yet it is less than the maximum of the threshold curve t c ð kÞ as seen by the blue curve in Fig. 3 . A non-zero infection size is observed for small alerting rates, eventually t c ð kÞ raises above t so that an epidemic cannot be sustained. As the threshold converges towards t c ð1Þ, an epidemic can once again persist, and the infection size even increases by the contact adaptation rate. Fig. 6 . The effect of alerting rate on infection size for the monotone scenario, for which the epidemic threshold dependence on k is depicted by the black curve in Fig. 3 . Case 2 Similar to Sections 6.1 and 6.2, case 2 shows a transition between low and high alerting rates where epidemic outbreaks occur for the former and not the latter. Cases 1 and 3 are omitted for trivial behavior. possibility where it did not exist before. On the other hand, it is possible to configure network layers such that the multilayer network is more robust than either individual layer.

It is noteworthy to mention that some results in the literature point to the observation that contact adaptation do not always aid suppressing the infection. For example, Meloni et al. [26] considered a self-initiated behavior where individuals change their mobility patterns. When travelers decide to avoid locations with high levels of infection and travel through locations with low levels of infections, this behavioral change may facilitate disease spreading because individuals effectively act as vectors of the disease transmission. It is very important to highlight the difference of the underlying mechanism between these formerly reported results and the "adaptation-gone-wrong" behavior in this paper. In our model, individuals who adapt their contacts (alerts) do not act as vectors for propagating the infection because they do not carry infection. This comes purely as a result of the adaptive behavior, signifying the importance of further analysis of state-dependent networks.

Finally, we would like to highlight several aspects of this study that go beyond the specific epidemic model considered in this paper. We developed a necessary and sufficient condition for existence and uniqueness of a positive eigenvector for homogeneous, concave maps. Furthermore, our utilization of multilayer networks to formulate dynamics on state-dependent switching networks is novel and can facilitate analysis of many networked dynamical systems. In our analysis, we come up with concepts that are genuine and novel to multilayer networks. Specifically, our analysis leads to 1) critical phenomena characterized by a nonlinear Perron Frobenius equation, and 2) the definition of Mconnectivity. Our proposed concept of M-connectivity can easily scale to more than two layers. Furthermore, the joint descriptor C in Eq. (13) emphasizes the importance of joint descriptors when characterizing dynamics over multilayer networks. While network science has flourished in understanding intra-layer network topologies, intrinsic descriptors of inter-layer connectivity of multilayer networks are yet to be investigated.

Faryad Darabi Sahneh received the doctoral degree in electrical engineering from the Kansas State University, in 2014. In August 2014, he joined the ECE Department as a research assistant professor. Since July 2016, he has also been a visiting faculty in the School of Computing, Georgia Institute of Technology. His primary research is on the intersection of complex systems, network science, and control theory.

Aram Vajdi is working toward the PhD degree at Electrical and Computer Engineering Department, Kansas State University. His research is mainly focused on network inference and spreading processes. " For more information on this or any other computing topic, please visit our Digital Library at www.computer.org/publications/dlib.

The mathematics of infectious diseases

Modeling Infectious Diseases in Humans and Animals

Bridging the gap between evidence and policy for infectious diseases: How models can aid public health decision-making

Epidemic processes in complex networks

Epidemic forecasting is messier than weather forecasting: The role of human behavior and internet data streams in epidemic forecast

Demographic and attitudinal determinants of protective behaviours during a pandemic: A review

Modeling the Interplay Between Human Behavior and the Spread of Infectious Diseases

Modelling the influence of human behaviour on the spread of infectious diseases: A review

Behavioural change models for infectious disease transmission: A systematic review

Coupled disease-behavior dynamics on complex networks: A review

A susceptible-infected epidemic model with voluntary vaccinations

Endemic disease, awareness, and local behavioural response

The spread of awareness and its impact on epidemic outbreaks

Towards a characterization of behavior-disease models

Spontaneous behavioural changes in response to epidemics

Epidemic spread in human networks

Game theory of social distancing in response to an epidemic

An individual-based approach to SIR epidemics in contact networks

Adaptive coevolutionary networks: A review

Epidemic dynamics on an adaptive network

Adaptive networks: Coevolution of disease and topology

Contact switching as a control strategy for epidemic outbreaks

Dynamics of epidemic diseases on a growing adaptive network

Adaptive contact networks change effective disease infectiousness and dynamics

Modeling human mobility responses to the largescale spreading of infectious diseases

Adaptive human behavior in epidemiological models

Endemic bubbles generated by delayed behavioral response: Global stability and bifurcation switches in an SIS model

A simple model for behaviour change in epidemics

Bifurcation of an SIS model with nonlinear contact rate

Disease risk mitigation: The equivalence of two selective mixing strategies on aggregate contact patterns and resulting epidemic spread

Sliding mode control of outbreaks of emerging infectious diseases

Epidemic spread over networks with agent awareness and social distancing

On the existence of a threshold for preventive behavioral responses to suppress epidemic spreading

Effect of awareness programs in controlling the prevalence of an epidemic with time delay

Effect of awareness programs by media on the epidemic outbreaks: A mathematical model

Stability analysis and optimal control of an epidemic model with awareness programs by media

Interaction of media and disease dynamics and its impact on emerging infection management

Virus spread in networks

Optimal information dissemination in epidemic networks

Some unique properties of eigenvector centrality

A convex framework for optimal investment on disease awareness in social networks

Optimal information dissemination strategy to promote preventive behaviours in multilayer epidemic networks

Analysis of an epidemic model with awareness decay on regular random networks

Controlling epidemic spread by social distancing: Do it well or not at all

Multilayer networks

Intermittent social distancing strategy for epidemic control

Epidemic threshold and topological structure of susceptible-infectious-susceptible epidemics in adaptive networks

Outbreak analysis of an SIS epidemic model with rewiring

Can rewiring strategy control the epidemic spreading?

Epidemic processes over adaptive state-dependent networks

Disease spread over randomly switched large-scale networks

Stability of spreading processes over time-varying large-scale networks

Graph Spectra for Complex Networks

Positive Solutions of Operator Equations

The Perron-Frobenius theorem for homogeneous, monotone functions

Nonlinear Perron-Frobenius Theory

Concave perron-frobenius theory and applications

Generalizations of the Perron-Frobenius Theorem for Nonlinear Maps

An always convergent method for finding the spectral radius of an irreducible non-negative matrix

The structure and dynamics of multilayer networks

Mathematical formulation of multilayer networks

The effect of network topology on the spread of epidemics

How viruses spread among computers and people

Endemic behaviour of SIS epidemics with general infectious period distributions

Non-Markovian infection spread dramatically alters the susceptible-infectedsusceptible epidemic threshold in networks

Susceptible-infected-susceptible epidemics on networks with general infection and cure times

Generalized epidemic mean-field model for spreading processes over multilayer complex networks

Accuracy of mean-field theory for dynamics on real-world networks

From Markovian to pairwise epidemic models and the performance of moment closure approximations

Epidemic processes in complex networks

Stability properties of infected networks with low curing rates

Stability properties of infection diffusion dynamics over directed networks

Epidemic outbreaks in networks with equitable or almostequitable partitions

Performance Analysis of Communications Networks and Systems

Community structure in social and biological networks

Dynamical systems

We are grateful to anonymous reviewers for their constructive feedback to improve this manuscript. We would like to thank Victor Preciado for inspiring conversations regarding use of the SAIS model in a contact adaptation context. Also, we would like to thank Heman Shakeri and Rad Niazadeh for their helpful discussions on the nonlinear Perron-Frobenius theory. This material is based on work supported by the US National Science Foundation under Grant No. CIF-1423411.