{'fraction_non_alphanumeric': 0.025855805803666823, 'fraction_numerical': 0.014188640540194026, 'mean_word_length': 4.891238670694864, 'pattern_counts': {'":': 0, '<': 2, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Absence of epidemic thresholds in a growing adaptive network

The structure of social contact networks strongly influences the dynamics of epidemic diseases. In particular the scale-free structure of real-world social networks allows unlikely diseases with low infection rates to spread and become endemic. However, in particular for potentially fatal diseases, also the impact of the disease on the social structure cannot be neglected, leading to a complex interplay. Here, we consider the growth of a network by preferential attachment from which nodes are simultaneously removed due to an SIR epidemic. We show that increased infectiousness increases the prevalence of the disease and simultaneously causes a transition from scale-free to exponential topology. Although a transition to a degree distribution with finite variance takes place, the network still exhibits no epidemic threshold in the thermodynamic limit. We illustrate these results using agent-based simulations and analytically tractable approximation schemes.


I. INTRODUCTION
Throughout human history epidemic diseases have been a constant threat. The plague of Athens wiped out 25-35 percent of the city's population as early as 430 BC [1]. A bubonic plague epidemic killed between 75000 and 100000 inhabitants of London between April 1665 and January 1666, as its population was about 460000 [1]. Smallpox became a constant 15 threat to Europe throughout the eighteenth century, where growing cities like London were especially vulnerable to the disease on account of providing incessant susceptible immigrant hosts to the virus [1]. After a brief respite during the 20th century epidemics are on the rise again. For instance in 2010, around 655000 people died of malaria [2]. Combating such epidemic diseases efficiently in the mega-cities of the future is likely to require a heightened 20 understanding of the dynamics of the diseases and the social networks on which they spread.
The horrendous examples above illustrate that epidemic diseases can have devastating effects on populations. It is easily conceivable that this has a drastic effect on population structure and specifically on the structure of social contact networks in the population.
Simultaneously, the fate of epidemics strongly depends on properties of the contact networks, 25 leading to a complex interplay.
In the past two decades, epidemic spreading has been extensively studied on different complex networks to understand the influence of the social contact network structure on the disease prevalence [3][4][5]. In particular, it has been shown that a crucial determinant of epidemic spreading is the degree distribution of the contact network, i.e. the probability 30 distribution of finding an agent with a given number of contacts. If the variance of this distribution is finite then there is generally a threshold of infectiousness, which the disease has to exceed to persist in the network [6][7][8]. By contrast, if the variance of the degree distribution is infinite, such as in certain scale-free networks, then the epidemic threshold vanishes [7][8][9][10][11] and diseases can persist by hierarchical spreading from hub nodes of high 35 degree [12]. Thus scale-free networks allow unlikely diseases with low infectiousness to spread and become endemic.
A relatively recent addition is to consider also the feedback of the epidemic on the social network structure, which can be indirect, e.g. by triggering behavioural changes of agents 45 [5,30], or direct by removing agents due to hospitalization, quarantine or death.
Modelling the network response to an ongoing epidemic leads to an adaptive network, a system in which a dynamical interplay between the dynamics of the network and the dynamics on the network takes place [31,32]. Epidemics on adaptive networks can exhibit complex emergent dynamics [30,[33][34][35][36] (e.g. sustained oscillations, bistability, and hysteresis) and 50 emergent topological properties [30,33,37] (e.g. heterogeneous degree distributions and assortative degree correlations). Furthermore, the study of the social response to epidemics is interesting from an applied point of view because it could enable enhanced vaccine control [38] and effective quarantine strategies [39].
In comparison to social responses to the epidemics [30,[33][34][35][36][37], direct topological feedback 55 via the removal of nodes has received less attention. Previous works considered the case where network growth and death processes are balanced and thus the population stays in equilibrium and fluctuates around a fixed system size [40,41]. The case of continuous growth was studied in [45], where new nodes attach preferentially to high degree non-infected nodes. It was observed that a transition from a scale-free topology to an exponential one 60 takes place as the infectiousness decreases. In another study, network growth and node removals have been incorporated in a single model [42]. However, the authors focused on the epidemic oscillations and did not consider topological effects in detail. Another related work focused on the interplay between network growth and dynamical behaviour in the context of evolutionary game theory [43], where new players preferentially attach to those 65 receiving higher payoffs.
Here, we consider the growth of a network by preferential attachment from which nodes are simultaneously removed due to a susceptible-infected-removed (SIR) epidemic. The appeal of this model lies in its paradoxical nature, in absence of the disease preferential attachment will lead to the formation of scale-free topologies in which the epidemic threshold 70 vanishes, such that the disease can invade. However, an established SIR disease will quickly infect and remove nodes of high degree such that the variance of the degree distribution is decreased and epidemic thresholds reappear, potentially leading to the extinction of the disease.
One can attempt to guess the outcome by the following (slightly naive) line of reasoning: 75 Observing a scale-free topology implies that the epidemic is extinct. But an extinct epidemic implies scale-free structure and hence vanishing epidemic threshold precluding extinction.
Logically, the only possible solution is that the epidemic persists (unconditionally) in a network that is not scale free. In other words, one would expect that the coevolution of epidemic state and network structure should lead to a vanishing epidemic threshold in an 80 exponential network.
One could argue that the naive reasoning is wrong because the paradox above can be resolved temporally, such that the epidemic goes extinct while the network is exponential, whereas a disease-free scale-free network develops at later times. Subsequently the network cannot be re-invaded by the disease because all infected have been removed. However, this 85 temporal resolution is only feasible in finite networks. In the thermodynamic limit it can be easily shown that a finite number of infected survive even below the epidemic threshold, which precludes complete extinction and thus is sufficient to reignite the epidemic at a later stage.
In the remainder of this paper we present a detailed dynamical analysis of the epidemic 90 model showing that the naive reasoning presented above is actually correct in the thermodynamic limit. Here, high infectiousness elevates the prevalence of the disease but at the same time limits epidemic spreading by causing a transition from scale-free to exponential topologies. Thus a balance is reached where the finite variance of the degree distribution is matched to the finite infectiousness, such that the epidemic persists. We use a novel 95 analytical approximation scheme to understand this balance in detail, and also identify a small parameter region, where, after all, a temporal resolution of the paradox is observed.

II. MODEL
We study the spreading of a susceptible-infected-removed (SIR) disease [44] on an evolving network. In this network a given node is either susceptible (state S) or already infected with 100 the disease (state I). We start with a fully connected network of m 0 nodes and consider three dynamical processes: a) the arrival of nodes, b) disease transmission, and c) the removal of nodes.
In the following we measure all rates per capita, including the arrival rate. This implies that larger populations have a proportionally larger influx of agents. This assumption is 105 necessary to keep the model well-defined in the thermodynamic limit and appears plausible e.g. for growing cities, where the attractivity increases with size.
New nodes arrive in the population at a constant rate q and are already infected with the disease with probability w. Arriving nodes immediately establish links with m of the nodes selected according to the preferential attachment rule [46]: A new node establishes a link 110 with an existing node of degree k with probability kP k / k , where P k denotes the degree distribution (the probability that a randomly picked node has degree k) and k = kP k is the mean degree.
Disease transmission occurs at rate p on every link connecting a susceptible and an infected node. Therefore, nodes with higher degree are proportionally more likely to catch 115 and spread the disease.
Removal of infected nodes take place at rate r. Because we describe a fatal disease from which recovery is not possible, removed nodes and their links are entirely deleted from the simulation and do not re-enter at a later stage.
Unless mentioned otherwise, the following set of parameter values is used throughout the 120 paper: m 0 = 6, m = 5, q = 0.01. In agent-based simulations the network is simulated until N reaches 10 7 (the scale of present mega cities), or the network has stopped growing and the time reaches 10 4 .
We now formulate a dynamical system that captures the time evolution of the densities In the following we refer to equation (1) as the heterogeneous approximation. The main drawback of such heterogeneous approximations is the high dimensionality of the system of equations, which complicates the analytical solution and thus typically necessitates extensive numerical studies. Furthermore, since it is not possible to numerically integrate an infinite 155 dimensional system of differential equations, we need to introduce a degree cut-off k max by assuming ∞ k=kmax+1 P k ≪ kmax k=0 P k . The higher the degree cut-off, k max , the more precise the heterogeneous approximation becomes.
In the following, we develop a low dimensional approximation by summing over the degree classes. We consider the susceptible proportion of the population [S], the mean degree k , 160 and the mean degree of susceptibles k S which evolve according to Using equation (1) and equation (2), we obtain In the following, we refer to equation (3) as the coarse-grained heterogeneous approximation.
Because we have not derived an equation for the second moment of the susceptible degree 165 distribution k 2 S , equation (3) does not constitute a closed dynamical system. We address this problem by replacing k 2 S by k S 2 + k S in an additional approximation. We note that this approximation is valid exactly when the network has a Poissonian degree distribution.
It can therefore be thought of as a 'random-graph approximation'. This approximation will certainly fail in the case of scale-free degree distribution because of the degree distributions 170 with diverging variance, i.e. k 2 S → ∞. By contrast, as will become apparent below, the approximation still performs well for distributions with large finite variance.
Using the random-graph approximation we obtain where [I] and k I are given by the conservation laws, such that the system constitutes a closed model. In the following we refer to this model as the homogeneous approximation.

IV. BASIC ANALYSIS
In this section, we present a detailed analysis of the analytical model and confirm the results by comparison with agent-based simulations of the network.
Before we launch into a detailed discussion of the model, let us consider the limiting case of network evolution in the absence of the epidemic. In this case the model is identical 180 to the Barabási-Albert model of network growth [46], which is known to lead to scale-free topologies, where the degree distribution follows a power law P k ∝ k −γ with exponent γ = 3.
In the present model the emergence of scale-free topologies is thus expected in the limit where the disease goes extinct or remains limited to a finite number of infected nodes ≪ N. When the epidemic is present, high degree nodes are disproportionately likely to become infected 185 and subsequently removed, which can be expected to prevent the formation of scale-free topologies.
We confirm this intuition by plotting degree distributions for various parameter sets in is observed at higher rates of infected arrivals, 0 < w < 1.

195
When all arriving nodes are already infected (w = 1), the distribution has a bimodal form for p = 0 with high degree contribution coming from the initial susceptibles which never get infected. At positive infectiousness p, these individuals eventually die and the mode at high degrees disappears.
In order to quantify the topological transition from the scale-free to the exponential degree  Above we computed the variance σ 2 of the degree distribution of networks. One concern in any computation of this kind is finite-size effects. In the heterogeneous approximation these effects appear directly in form of the maximal degree that is considered in the approximation.
In agent-based simulation a similar cut-off exists as the maximal degree in a network of 210 finite size is bounded by the number of nodes. Hence all moments of the degree distribution, including the variance, must be finite regardless of the shape of the degree distribution.
However, if the finite networks are drawn from an ensemble that becomes scale-free in the Degree variance σ 2 as a function of the degree cut-off k c . A transition from a cut-off dependent (p = 0, scale-free) to an independent (p = 0.0004, p = 0.001, and p = 0.005, exponential) regime is observed as the infectiousness p is increased. In network simulations (circles), nodes were restricted to at most k c neighbours. In the heterogeneous approximation (solid lines) the cut-off k c is directly imposed as k max . Parameters: r = q = 0.01, m 0 = 6, m = 5, k c = 5 × 10 3 . thermodynamic limit the variance σ 2 is often found to increase logarithmically with the imposed cut-off [23]. The epidemic threshold is commonly defined as the minimal value of the infectiousness, 245 below which a randomly picked node is susceptible with probability 1. In any finite network this implies that below the epidemic threshold each individual node is susceptible. By contrast in the thermodynamic limit there can still be a finite number of infected nodes as long as the density of such nodes in the network is zero, i.e. [I] = 0. In the following we denote the state below the epidemic threshold as the disease-free state, but recognize that 250 there may be still a finite number of infected agents.
Because the density of infected vanishes in the disease-free state, it is apparent that the degree distribution must be independent of the parameters p and r. This can also be verified in the heterogeneous approximation. Furthermore, in the thermodynamic limit, i.e. N → ∞, the degree distribution converges to the power law P k ∼ k −3 for k ≥ m and thus also the the heterogeneous approximation implies Using In addition, the steady-state solution of the coarse-grained heterogeneous approximation provides that 1/σ 2 The argument above provides a substantiation for our intuition that, in the disease-free state, preferential attachment will eventually lead to the formation of scale-free topologies, where the degree variance of the susceptibles diverges. Considered on its own this argument 265 does not preclude the existence of an epidemic threshold, below which the network is diseasefree and scale-free. Although we know that the epidemic threshold vanishes in models of epidemic spreading on static scale-free networks, the same is not necessarily true in the adaptive network considered here. We therefore explicitly compute the epidemic threshold by checking the stability of the disease-free state against invasion of the epidemic.

270
In a dynamical system, a given steady state is stable if all eigenvalues of the corresponding Jacobian matrix have negative real parts. The Jacobian matrix is obtained by a local linearisation of the system around the steady state under consideration. For the diseasefree state, we can obtain the Jacobian J directly from the coarse-grained heterogeneous approximation (equation (3)), which yields where We can now compute the epidemic threshold p * as the critical threshold in p where the disease-free state loses its stability through a transcritical bifurcation. Since the Jacobian J depends only on the value of the susceptible degree variance σ 2 S but not on its partial derivatives, we can treat the susceptible degree variance σ 2 S as a parameter and obtain the 280 epidemic threshold as its function by numerical continuation of the bifurcation point. For sufficiently large degree variance σ 2 S , we find the scaling relation p * ∼ k /σ 2 S (figure 5), which recovers a famous result from epidemics on static networks. The epidemic threshold thus vanishes in the thermodynamic limit when σ 2 S → ∞. The two paragraphs above provide a clearer picture of the paradoxical situation sketched 285 already in the introduction. If the disease prevalence vanishes then the network becomes scale-free, however the scale-free network has a vanishing epidemic threshold and thus supports finite prevalence. In principle this paradox can be resolved in two ways, a) either the network does not become stationary but switches back and forth between scale-free and exponential phases, or b) the network approaches a state where the epidemic persists in an 290 exponential topology.
It is apparent that in finite networks the temporal dynamics can lead to a disease-free scale-free state. In this case the network goes through an initial exponential phase where an epidemic threshold exists that leads to the extinction of the epidemic. Subsequently, a scale-free topology is build up, in which the epidemic threshold vanishes. However the 295 epidemic cannot reappear as no infected are left which could reignite the epidemic.
We emphasize that the mechanism above is a finite-size effect. In the thermodynamic limit there would generally be some infected left even in the disease-free state. To see this consider that infected are removed exponentially, so that after any finite time there will still be infected left which can launch the network back into an endemic state, such Precluding the finite-size effect described above, simulation runs in the parameter range considered so far approach a finite prevalence for any positive value of infectiousness. The 305 paradox outlined above is thus resolved by alternative a) the model does not have an epidemic threshold although the evolving topologies remain exponential. As a final step in our exploration we now search for evidence of the temporal resolution of the paradox, the alternative b).
Up to now we have considered relatively small removal rates r. At sufficiently high 310 removal rate, the evolution of the disease and the topology exhibits dynamics different from the convergence to a stationary state. Figure 7 shows a representative evolution at non-zero When all arrivals are susceptible, i.e. w = 0, the epidemics in the finite population disappears entirely and the collapse-and-growth cycle cannot be completed. A disease-free 320 scale-free network then emerges. Based on the arguments above one can suspect that the same behaviour cannot occur in the thermodynamic limit. Instead it is likely that the observed dynamics forms part of a homoclinic cycle, where long phases of very low disease prevalence are disrupted by sharp outbreaks. Similar dynamics have for instance been studied in an adaptive-network model of cooperation among agents [54]. In the present 325 model, the moment closure approximation fails to capture this behaviour and predicts a stable steady-state solution for high values of r.
The observed dynamics at high removal rates would correspond to diseases with very high mortality where infected individuals die almost immediately. This is reminiscent of the massive pandemics in history, where humanity was exposed to new pathogens with very high

335
In the present paper we have investigated the dynamics of a fatal disease in a growing population. Our main finding is that no epidemic threshold exists in this model although the variance of the degree distribution remains finite. Thus even in evolving exponential network topologies "unlikely" diseases with very low infectiousness can persist indefinitely.
We presented a detailed analytical exploration for the case of low removal rate, where the 340 prevalence of the disease reaches a stationary level. In the growing population the ongoing epidemic dynamics eliminates the nodes of high degree and thus leads to the formation of exponential topologies for which the variance of the degree distribution is finite. However, this mechanism only reduces the width of the degree distribution so far that the epidemic can still persist. Thus for any finite value of the infectiousness the network adapts its topology 345 such that the variance of the degree distribution is lower to point where the epidemic can still be sustained, which explains the observed absence of the epidemic threshold.
When the removal rate is sufficiently high, we observed a much more dynamic picture, where degree variance acts as a supply of fuel that slowly builds up before being burned in large epidemic outbreaks. These dynamics are reminiscent of the massive deaths from 350 epidemic diseases in newly forming urban areas. A detailed analysis thus appears as a promising target for future work.
The dynamical feedback between the population structure and the epidemic disease has been so far studied in a number of articles in the past five years [30,[33][34][35][36][37]. However, models captured mostly social interactions in non-fatal diseases. A significant obstacle to progress 355 in this line of work is that the network evolution in most models is driven by behavioural changes of individuals (whom to meet, how often to wash hands). However, for behaviour often no records exist such that model predictions cannot easily be compared with real world data. By contrast, in the model proposed here, the social network evolves due to demographic processes such as migration and death on which data may be easier to obtain. 360 We believe that the proposed model is relevant for epidemics in rapidly growing cities, especially in the developing countries. We hope that in this context connecting the model to real world data will be feasible in the future. One can easily imagine extensions of the present model that incorporate policy measures such as vaccination, quarantine, or regulation of migration. We hope that this will in the future lead to the formulation of more 365 efficient policies for combating epidemic diseases.