key: cord-0010899-nc5xnozv
authors: Iotti, Bryan; Antonioni, Alberto; Bullock, Seth; Darabos, Christian; Tomassini, Marco; Giacobini, Mario
title: Infection dynamics on spatial small-world network models
date: 2017-11-30
journal: Phys Rev E
DOI: 10.1103/physreve.96.052316
sha: 4ba44e8b11efcaa96ef3f04364e6dd623e839768
doc_id: 10899
cord_uid: nc5xnozv

The study of complex networks, and in particular of social networks, has mostly concentrated on relational networks, abstracting the distance between nodes. Spatial networks are, however, extremely relevant in our daily lives, and a large body of research exists to show that the distances between nodes greatly influence the cost and probability of establishing and maintaining a link. A random geometric graph (RGG) is the main type of synthetic network model used to mimic the statistical properties and behavior of many social networks. We propose a model, called REDS, that extends energy-constrained RGGs to account for the synergic effect of sharing the cost of a link with our neighbors, as is observed in real relational networks. We apply both the standard Watts-Strogatz rewiring procedure and another method that conserves the degree distribution of the network. The second technique was developed to eliminate unwanted forms of spatial correlation between the degree of nodes that are affected by rewiring, limiting the effect on other properties such as clustering and assortativity. We analyze both the statistical properties of these two network types and their epidemiological behavior when used as a substrate for a standard susceptible-infected-susceptible compartmental model. We consider and discuss the differences in properties and behavior between RGGs and REDS as rewiring increases and as infection parameters are changed. We report considerable differences both between the network types and, in the case of REDS, between the two rewiring schemes. We conclude that REDS represent, with the application of these rewiring mechanisms, extremely useful and interesting tools in the study of social and epidemiological phenomena in synthetic complex networks.

Complex networks, and in particular social networks, have received a great deal of attention in the last two decades (see, e.g., [1, 2] and references therein). Despite the important relationship between space and structure, most social network models and empirical analyses of actual social networks are limited to their relational aspects, while the physical distance between network nodes is abstracted. However, in almost all aspects of our life we interact with and through spatial networks of all kinds, from contact networks of friendships and sexual partners to utility distribution networks of transports, power, water, and gas, among others. In the last decade, thanks to the availability of network data in many disciplines, spatial complex networks have also received their share of attention (for an excellent recent review see [3] ), although significantly less than relational complex networks.

Ignoring spatial aspects in social networks is often a reasonable simplifying assumption. In the case of face-to-face networks such as those found in social interactions, distance does not play an important role as the interactions can be assumed to occur in a single place. At the other extreme, today's large internet-mediated social networks, such as Facebook, can be considered purely relational for most practical purposes thanks to the fact that modern computer and communication systems have mostly freed us from space constraints, allowing geographically distant people to communicate in an almost instant manner.

If we look closer, however, we realize that geography enters the picture in many daily situations [4] . For example, studies show that the number of social contacts or friends of an individual in such online social networks tends to decrease with physical distance [3] [4] [5] [6] . In a similar manner, communities of individuals in social networks are characterized by the fact that their members, in addition to being densely connected, mostly belong to a given geographical area, at least in the case of groups of a limited size [6] . A related effect is the observed negative correlation between phone calls and distance: people that are closer call each other more often [7, 8] .

The spatial influence on social networks is due to the fact that network memberships and connections often occur after people have had a direct face-to-face meeting, or through a common acquaintance, which are both more likely if the actors are in physical proximity. Once they are connected, people residing in a limited geographical area may interact more easily and more often for the same reasons. These considerations suggest that the introduction of high-speed, location-independent communication technologies does not completely suppress the role of physical space in social networks. While there is an increasing awareness of the role of physical space in modern social networks, especially in the mobile communication field, there has been comparatively less work on complex network models that take these factors into account [3] . The present paper is a step in this direction.

Previous work is contained in [9] [10] [11] . In [9] social network formation is based on the concept of social distance. In the other models [10, 11] nodes are located in a given metric space and connections between nodes are influenced by the distance separating them. Our proposed model, called REDS, falls within this category and, like several other spatial network models, is an extension of random geometric graphs (RGGs), the canonical spatial network model [3, 12] . The main REDS features were briefly introduced in [13] . The REDS acronym relates to the four aspects of a social system that influence network topology: the social reach, energy, and synergy parameters of the network, and the distance between pairs of nodes. The resulting REDS networks resemble real-life social networks from a statistical point of view. However, standard REDS networks are not small worlds. While they are highly clustered, they have relatively long characteristic path lengths, like lattices. In order to model social processes such as the flow of information or disease in a structured population, it is desirable to rely on a random network model that exhibits tunable analogs of all the major properties of real social networks. Consequently, in this paper we explore how readily "small-world REDS" can be constructed through a Watts-Strogatz-style rewiring process [14] , extending and generalizing our first attempts [15] .

Understanding the propagation of infectious diseases and other diffusion phenomena on more realistic network structures is important from a practical point of view. Therefore, in the second part of the paper we describe the behavior of the classical susceptible-infected-susceptible (SIS) epidemiological model, comparing its behavior on REDS and rewired REDS networks.

The paper is structured as follows. We first introduce the network models we use in this paper. Next, we explore how these spatial network models are affected by the introduction of random rewiring, demonstrating that rewired REDS networks can be small worlds. Finally, we study a SIS epidemic process on RGGs, REDS, and rewired RGGs and REDS. The paper closes with a discussion of the main results.

The canonical spatial network model is the RGG. A RGG is obtained by connecting nodes on a plane according to a geometric rule, e.g., linking together all pairs of nodes closer than a threshold distance, R. There is an extensive mathematical literature on RGGs, particularly in the context of continuum percolation [3, 12, 16, 17] . In this paper, we generate an N -node RGG with distance threshold, R, distributing the N nodes uniformly at random in the unit space [0,1] 2 and creating an edge between every pair of nodes separated by a distance smaller than R. The average degree is estimated as k = πNR 2 , while the degree distribution for a sufficiently large number of nodes is approximated by the Poisson distribution with parameter λ =k [16] . The average clustering and the assortativity coefficient values tend to 1 − 3 √ 3 4π ∼ 0.5865 [16, 17] . Many more properties of RGGs are derived in [12] .

Energy-constrained RGGs [18] (EC-RGGs) are an extension to the standard RGG model where each of a node's connections costs a predefined amount of energy, equivalent to its Euclidean length. In addition to the standard constraint that each edge cannot cost more than R, the total cost of an individual node's edges may not exceed some finite threshold value, E. Networks are constructed by assigning legal edges at random until no more edges can be afforded. For large E, EC-RGGs tend to become equivalent to RGGs, saturating such that all edges of length less than R are present in the graph.

Where both E and R are large, complete graphs are obtained. However, where both E and R are limiting factors, EC-RGG graphs exhibit a range of clustering and positive assortativity values, unlike RGGs. Neither RGGs nor EC-RGGs exhibit the skewed degree distributions and community structure that are typical features of actual social networks.

The REDS network construction builds on the RGG and EC-RGG models by including and parametrizing the positive influence of shared network neighbors on the cost of maintaining relationships. The intuitions here are that (i) there is a limit to the distance over which a relationship can be maintained, (ii) relationships between nodes vary in terms of cost, (iii) longer distance relationships cost proportionately more than shorter distance relationships, and (iv) relationships with individuals that are themselves connected together are cheaper to maintain.

The REDS model thus comprises four components.

(1) Reach: An undirected edge, ij , between a pair of nodes, i and j , only exists if the distance between them, D ij , is less than their "social reach," R.

(2) Energy: Each node, i, has a finite quantity of "social energy," E, spent on maintaining its edges.

(3) Distance: The cost, c ij , of edge ij is proportionate to the "social distance," D ij , between i and j .

(4) Synergy: The cost, c ij , of edge ij varies inversely with the number of shared neighbors of i and j .

More explicitly, the cost of each edge is calculated as

where k ij is the number of neighbors shared by i and j . We refer the reader to [13] for a detailed analysis of the above cost function using other cost values. The construction process to build an N -node REDS network with social reach R and social energy E can be summarized as follows.

(1) A population of N nodes is distributed uniformly at random in the unit square [0,1] 2 . Each node, i, is allocated the same initial energy, E i = E.

(2) A node i is picked uniformly at random and a second node j is chosen uniformly at random from the set of nodes for which the distance D ij < R.

(3) An undirected edge between i and j is created only if both nodes have sufficient energy to afford the new set of neighbors that would result.

denotes the cost of an edge in the updated graph including the new edge ij , and x are the neighbors of i in this updated graph. The same condition must hold for j , mutatis mutandis.

(4) Steps 2 and 3 are repeated until no more edges can be created according to the linking rule.

In Fig. 1 we show an example of a RGG and of a REDS network with the same number of nodes and average degree for comparison. For more network properties on RGGs and REDS networks, we refer the reader to [3, 12, 13, 16, 17] . 

In order to characterize a small-world regime for RGGs and REDS networks, it is customary to subject obtained networks to a random process of link rewiring. More generally, we will employ two different rewiring protocols. Both erode network structure, but while the standard scheme tends to encourage a Poisson degree distribution the conservative scheme preserves the network's original degree distribution, and does so without introducing spurious spatial correlations between rewired edges. What we term "standard" rewiring is the familiar approach to random rewiring employed by Watts and Strogatz [14] . This protocol implies that for each edge ij of the network the following rewiring scheme is performed with probability p.

(1) Pick a random node, k, where k = i and k = j , and no edge ik exists.

(2) Remove edge ij from the network and add edge ik.

Note that new rewired edges may not have been affordable under the network construction process. Moreover, while this rewiring protocol does not change the average degree of a network, it may change its degree distribution. For instance, high degree nodes will tend to lose neighbors more often than average degree nodes as they are involved in more edges. In general, the rewiring process will tend to move the degree distribution towards a Poisson distribution. While RGGs already have a Poisson degree distribution, REDS networks may initially have a more skewed degree distribution, and standard rewiring will tend to pull in the high degree tail.

In order to separate the influence of random rewiring on degree from its more general influence on network structure, we introduce a second "conservative" scheme which preserves a network's degree distribution. This protocol implies that for each edge ij the following rewiring scheme is performed with probability p.

(1) Remove edge ij from the network. Add i and j to the rewire list. A node may be added to this list more than once if more than one of its edges is to be rewired. This step is performed for all edges of the initial network, creating the entire rewire list, before proceeding to step 2.

(2) Until the rewire list is empty, remove a randomly chosen pair of values, i and k, from the rewire list, where i = k and edge ik does not already exist in the network. Add edge ik to the network.

The conservative rewiring scheme may also allow the creation of edges that would have been unaffordable during network construction. This scheme, however, is designed to avoid a specific bias that would arise in spatial networks subjected to a more straightforward degree-distributionpreserving rewiring protocol that simply "crosses over" pairs of edges that have been chosen to be randomly rewired. Consider, if ij and xy are two edges that have been chosen to be randomly rewired, removing these edges and replacing them with, e.g., edges iy and xj will preserve the degree of each of the nodes involved, but will tend to create two new edges that are correlated in space. In a spatial network, ij and xy will tend to be short edges because they each link together nodes that are near to each other. Hence, new edges iy and xj (or ix and jy) will tend to link two nodes from one spatial region (i and j ) to two nodes in another arbitrary spatial region (x and y), thus introducing additional unwanted correlation structure into the network.

Note also that, although a network's degree distribution is preserved by conservative rewiring, other aspects of network structure are not, e.g., clustering, path length, assortativity, and community structure. By comparing the results of the standard and conservative rewiring schemes we can distinguish the influence of degree distribution from that of network structure more generally.

In Fig. 2 we show the small-world index [19] for the two rewiring schemes and the two considered network models, i.e., RGG and REDS. The small-world effect can be seen for p values around 0.05 for both types of network and both rewiring schemes. This effect is somewhat smaller for REDS networks under standard rewiring due to the smaller clustering coefficients typical of REDS networks, and is even less pronounced for REDS networks subjected to conservative rewiring. 

In the previous section we have seen that, for some parameter combinations, REDS and rewired REDS have statistical properties that resemble those of empirically measured social networks possessing a spatial component. Understanding diffusion and contagion processes in the real world is of the utmost importance. For instance, ideas, rumors, or viruses all can spread, in different ways, through the same network substrates. It is thus of interest to simulate contagion processes on the family of networks presented here. For this reason, we ran a simple SIS compartmental model on both unmodified and rewired REDS and RGG networks, varying the parameter β (probability that a susceptible node at time t may become infected at time t + 1) while keeping μ (probability that an infected node may recover and become susceptible again at time t) constant at 1.0. This implies that recovery is automatic after one simulator time step. All simulations were started by selecting uniformly at random 50 nodes out of 1000 for each network and declaring them infected. The simulation is allowed to run for a minimum of 300 time steps. There are three possible outcomes: (i) the outbreak can die out when there are no infected nodes left, (ii) the infection can still be developing and not have reached a stable prevalence, or (iii) the infection can stabilize at a given prevalence level. We started with a group of 100 REDS networks with N = 10 3 , R = 0.08, and E = 0.124 and 100 RGGs with N = 10 3 and R ≈ 0.05. Model parameter values have been chosen in order to obtain, on average, the same mean degree, i.e.,k = 8, for both network constructions. For each of these networks, we prepared randomly rewired variants, using both standard and conservative rewiring, for rewiring probabilities ranging from p = 1 to 10 −4 . For each rewiring scheme and value of the rewiring parameter we built 100 networks. In total we counted 8600 networks, and the SIS model was run 100 times on each one.

In Fig. 3 we see the effect of the two rewiring schemes applied to REDS and RGGs on the numerical critical beta (β c ) estimation, following the method of Gómez et al. [20] . This is the critical value of the parameter β above which an outbreak will be successful and becomes an epidemic. For values of β < β c , instead, an outbreak will die out. In our case, this shows that REDS networks are consistently more vulnerable to contagion than RGGs. The effect of the two rewiring schemes on β c is initially very small, but, as the FIG. 4 . Median outbreak size for REDS (left) and RGG networks (right), using either the standard (top) or conservative (bottom) rewiring method. Each point in the graph is subject to a probability, p, of rewiring for a range of transmission probabilities, β: Each cell in these heat maps represents the average size of successful outbreaks, i.e., the median size of the final stable population of infected nodes for 100 outbreaks (one outbreak on each of 100 different networks), ignoring outbreaks that fail. Cells shaded gray represent conditions under which all 100 simulated outbreaks failed. rewiring probability p increases and exceeds levels associated with the small-world effect (p ≈ 0.05), we see an increase in β c that is more pronounced in the case of standard rewiring. In other words, the network becomes less vulnerable to contagion when edges are randomized to a significant extent, but the smaller increase in case of conservative rewiring indicates that the influence of random rewiring is only partly accounted for by distortion of the degree distribution. An important part is also played by the erosion of other aspects of network structure, which can occur in both types of rewiring.

Comparing the quadrants of Fig. 4 , we see that REDS networks are indeed in general more vulnerable to contagion than RGGs, with the boundary separating outbreaks that die out from successful ones showing substantial agreement with the theoretical values of β c , only increasing when p passes through the regime associated with the small-world effect. For low values of p and supercritical values of β, the contours are widely spaced, indicating that the outbreak size grows slowly with increasing values of β. For high values of p and supercritical values of β, instead, the tightly packed contour lines indicate that the outbreak grows rapidly, spreading widely across the network even for marginally supercritical values of β. Intermediate values of p in the small-world regime show a "sweet spot" that combines a low critical β threshold with a large outbreak size. In the case of conservative rewiring, the effect is less pronounced, but the behavior is substantially identical. RGGs seem insensitive to the differences between the rewiring schemes.

We define successful outbreaks as those cases where there were more than 50 infected nodes at the end of the 300th time step, and we examine what percentage of all runs are successful for a given value of the parameter β. Results are presented in Fig. 5 . While rewiring makes disease spreading easier in both networks, REDS and RGGs remain well separated, with the former requiring lower values of β for outbreaks to become successful. The standard rewiring scheme increases FIG. 5 . Curves showing the ratio of successful outcomes vs the total number of runs, for each value of the parameter β, divided by network type (REDS or RGG) and rewiring type (conservative or standard) the vulnerability of REDS networks at first, but for high values of p, as structure is lost, the percentage of successful outbreaks returns to the initial point, which is in agreement with what can be seen in the bottom left quadrant of Fig. 4 . An interesting behavior can be seen in the case of REDS with conservative rewiring in Fig. 5 , where the outbreaks do not simply become easier, as in all other cases. In this particular case, for p > 0.01 conservative rewiring makes REDS networks harder to infect. Further work is necessary to understand why this occurs.

We consider the average number of infected nodes for each value of β. We find that infections in REDS networks seem to transition from the disease-absorbent state where no outbreak is successful to the epidemic state less sharply, whereas RGGs seem to require a higher infection pressure before this transition can take place. The differences between the two rewiring schemes seem less pronounced in this case than for the network analysis coefficients, with the conservative approach showing only a marginal decrease in the value of β. This behavior is useful for the purposes of simulating disease spread, since the rewiring parameter can be used to represent, for example, the shift from a local market to a global one.

In this paper we have considered several aspects of the proposed REDS model, and discussed two methods that allow the introduction of shortcuts within these networks to better mimic the topological properties observed in real social networks. Through the use of a common epidemiological model, we showed that the different network properties derived from the application of the two rewiring schemes yields behaviors that are distinct and interesting, identifying the REDS model as a valid addition to the available types of synthetic networks at our disposal when studying complex social phenomena. The ability to "tune" the properties of the network model to such an extent makes REDS appealing for applications in epidemiology where changes in network topology are considered. This flexibility would be instrumental in evaluating how the introduction of long distance links affects disease spread in animal trade networks. An example of this would be the case of the livestock trade network of a developing country, where increased urbanization has introduced, through improved transportation infrastructure, feasible long distance links. In this case, what was essentially a "mostly local" market has now become a global one, with interesting epidemiological implications. Using empirical data to tune the parameters of our model could also be useful when approximating other real world scenarios and for comparing its accuracy with existing models present in the literature, but further work is necessary to determine which network measures should be considered. A lot of work has gone into the study of real world network characteristics [21] [22] [23] , but the possibility of creating an ensemble of networks that gradually shift from purely localized to global movements would undoubtedly allow for a better understanding of the influence and effect of this factor, or at least provide an effective null model for comparison. The visible differences between the behavior and properties of REDS and RGG networks clearly show that the former is not simply an extension of the latter, but a completely different and valuable tool altogether.

Networks: An Introduction

Dynamical Processes on Complex Networks

IEEE Second International Conference on Social Computing

Random Geometric Graphs

The Fourteenth International Conference on the Synthesis and Simulation of Living Systems

Proceedings of the European Conference on Artificial Life

Advances in Artificial Life, ECAL 2013 (MIT