key: cord-0650009-p05a8zjy
authors: Backhausz, 'Agnes; Bogn'ar, Edit
title: Virus spread and voter model on random graphs with multiple type nodes
date: 2020-02-17
journal: nan
DOI: nan
sha: b60c1c89edc91d6d585b9e3e9035369ffd8fddb1
doc_id: 650009
cord_uid: p05a8zjy

When modelling epidemics or spread of information on online social networks, it is crucial to include not just the density of the connections through which infections can be transmitted, but also the variability of susceptibility. Different people have different chance to be infected by a disease (due to age or general health conditions), or, in case of opinions, ones are easier to be convinced by others, or stronger at sharing their opinions. The goal of this work is to examine the effect of multiple types of nodes on various random graphs such as ErdH{o}s--R'enyi random graphs, preferential attachment random graphs and geometric random graphs. We used two models for the dynamics: SEIR model with vaccination and a version of voter model for exchanging opinions. In the first case, among others, various vaccination strategies are compared to each other, while in the second case we studied sevaral initial configurations to find the key positions where the most effective nodes should be placed to disseminate opinions.

freedom in choosing the position of these vertices.

One of our main interests is epidemic spread. The accurate modelling, regulating or preventing of a possible epidemic is still a difficult problem of the 21st century. (As of the time of writing, a novel strain of coronavirus has spread to at least 16 other countries from China, although authorities have been taking serious actions to prevent a worldwide outbreak.) As for mathematical modelling, there are several approaches to model these processes, for example, using differential equations, the theory of random graphs or other probabilistic tools [10, 12, 15] . As it is widely studied, the structure of the underlying graph can have an important impact on the course of the epidemic. In particular, structural properties such as degree distribution and clustering are essential to understand the dynamics and to find the optimal vaccination strategies [7, 11] . From the point of view of random graphs, in case of preferential attachment graphs, it is also known the initial set of infected vertices can have a huge impact on the outcome of the process [3] : A small proportion infected vertices is enough for a large outbreak if the positions are chosen appropriately. On the other hand, varying susceptibility of vertices also has an impact for example on the minimal proportion of vaccinated people to prevent the outbreak [6, 4] . In the current work, by computer simulations, we study various cases when these effects are combined in a SEIR model with vaccination: We have a multitype random graph, and the vaccination strategies may depend on the structure of the graph and types of the vertices as well.

The other family of models which we studied is a variant of the voter model. The voter model is also a common model of interacting particle systems and population dynamics, see e.g. the book of Liggett [16] . This model is related to epidemics as well: Durett and Neuhauser [9] applied the voter model to study virus spread. The two processes can be connected by the following idea: We can see virus spread as a special case of the voter model with two different opinions (healthy and infected), but only one of the opinions (infected) can be transmitted, while any individuals with infected opinion switch to healthy opinion after a period of time. Also the virus can spread only through direct contacts of individuals (edges of the graphs), while in the voter model it is possible for the particles to influence one another without being neighbors in the graph. Similarly to the case of epidemics, the structure of the underlying graph has an important impact on the dynamics of the process [2, 8] . Here we study a version of this model with various underlying random graphs and multiple types of nodes.

We examined the virus spread with vaccination and the voter model on random graphs of different structures, where in some cases the nodes of the graph corresponding to the individuals of the network are divided into groups representing significantly distinct properties for the process. We studied the possible differences of the processes on different graphs, regarding the nature and magnitude of distinct result and both tried to find the reasons for them, to understand how can the structure of an underlying network affect outcomes.

The outline of the paper is as follows. In the second section we give a description of the virus spread in continuous time, and the discretized model. Parameters are chosen such that they match the realworld data from [14] . We confront outcomes on different random graphs and the numerical solutions of the differential equations originating from the continuous time counterpart of the process. We also study different possible choices of reproduction number R 0 corresponding to the seriousness of the disease. We examine different vaccination strategies (beginning at the start of the disease of a few days before), and a model with weight on edges is also mentioned.

In the third section we study the discretized voter model on Erdős-Rényi and Barabási-Albert graphs firstly without, then with multiple type nodes. Later we run the process on random graphs with a geometric structure on the plane.

The dynamics of virus spread can be described by differential equations, therefore they are usually studied from this approach. However, differential equations use only transmission rates calculated by the number of contacts in the underlying network, while the structure of the whole graph and other properties are not taken into account. Motivated by the paper "Modelling the strategies for age specific vaccination scheduling during influenza pandemic outbreaks" of Diána H. Knipl and Gergely

Röst [14] , we modelled the process on random graphs of different kinds. In this section we use the same notions and sets for most of the parameters. Ideas for vaccination strategies are also derived from there.

We examined a model in which individuals experience an incubation period, delaying the process. Dynamics are also effected by a vaccination campaign started at the outbreak of the virus, or vaccination campaign coming a few days before the outbreak.

In the classical SEIR model, each individual in the model is in exactly one of the following compartment during the virus spread:

• Susceptible: Individuals are healthy, but can be infected.

• Exposed: Individuals are infected but not yet infectious.

• Infectious: Individuals are infected and infectious.

• Recovered: Individuals are not infectious anymore, and immune (cannot be infected again). Individuals can move through compartments only in the defined way above (it is not possible to miss out one in the line). The rate at which individuals leave compartments are described by probabilities (transmission rates) and the parameters of the model (incubation rate, recovery rate). Individuals in R are immune, so R is a terminal point.

SEIR with vaccination: We mix the model with a vaccination campaign. The campaign lasts for 90 days, and we vaccinate individuals according to some strategy (described later) so that at the end of the campaign 60% of the population is vaccinated (if it is possible). We vaccinate individuals only in S, but the vaccination ensures immunity only with probability q, and only after 14 days. We vaccinate individuals at most once irrespectively of the success of vaccination. However, vaccinated individuals can be infected within the first 14 days. In this case, nothing differs from the process without vaccination. 

To describe the underlying network, we use real-life data. We distinguish individuals according to their age. In particular, we consider 5 age groups since they have different social contact profile. The To describe the social relationships of the different age groups, we used the contact matrix obtained in [1] : 

where the elements c i,j represent the average number of contacts an individual in age group i has with individuals in age group j.

In the sequel, the number of individuals in a given group is denoted by the label of the group according to Figure 1 . The model is specified by the following family of parameters.

• R 0 = 1.4: basic reproduction number. It characterizes the intensity of the epidemic. Its value is the average number of infections an infectious individual causes during its infectious period in a population of only susceptible individuals (without vaccination). Later we also study less severe cases with R 0 = 1.0 − 1.4.

• β i,j : transmission rates. They control the rate of the infection between a susceptible individual in age group i and an infectious individual in age group j. They can be derived from R 0 and the C contact matrix. According to [1] we used β i,j = β · c i,j N j , where β = 0.0334 for R 0 = 1.4.

.25: latent period. ν E is the rate of exposed individuals becoming infectious.

Each individual spends an average of 1 ν I in I.

• 1 ν W = 14: time to develop antibodies after vaccination.

• q i = 0.8 for i = 1, . . . , 4 and q 5 = 0.6: vaccine efficacy. The probability that a vaccinated individual develops antibodies and becomes immune.

• δ = 0.75: reduction in infectiousness. The rate by which infectiousness of unsuccessfully vaccinated individuals is reduced.

• λ i = 5 j=1 β j,i · (I j + δ · I j V ) is the total rate at which individuals of group i get infected and become exposed.

• V i : vaccination rate functions determined by a strategy. This describes the rate of vaccination in group i.

The dynamics of the virus spread and the vaccination campaign can be described by 50 differential equations (10 for each age group), according to [14] :

We would like to create an underlying network and examine the outcome of virus spread on this given graph.

We generated random graphs of different structures with N = 10000 nodes, such that each node has a type corresponding to the age of the individual. The age distributions and number of contacts in the graph between age groups comply with statistic properties detailed above. Since the contact matrix C describes only the average number of contacts, the variances can be different.

• Erdős-Rényi graphs: We create 10000 nodes and their types are defined immediately, such that the number of types comply exactly to the age distribution numbers. The relationships within each age group and the connections between different age groups are both modelled with an Erdős-Rényi graph in the following sense: We create an edge between every node in age group i and node in age group j independently with probability p i,j , where

• Preferential attachment graphs: Initially we start from an Erdős-Rényi graph of size 100, then we keep adding nodes to the graph sequentially. Every new node chooses its type randomly, with probabilities given by the observed age distribution. After that we create edges between the new node and the old ones with preferential attachment. If the new node is of type i, then we connect it with an edge independently to an old node v of type j with probability

where d(v) denotes the actual degree of v, and D is the sum of degrees belonging to nodes with type j. Thus the new node is more likely to attach to nodes with a high degree, resulting a few enormous degrees in each age group. On the other hand, the connection matrix C is used to ensure that the density of edges between different age groups is different.

• Preferential attachment mixed with Erdős-Rényi graphs: We create the 10000 nodes again with their types exactly according to age distribution numbers. First we create five preferential attachment graphs, the ith of size N i so that every node has an average of c i,i neighbours.

In particular, the endpoints of the new edges are chosen independently, and the attachment probabilities are proportional to the degrees of the old vertices. Then we attach nodes in different age groups independently with the corresponding p i,j probabilities defined above.

• Random graphs of minimal degree variances with configuration model: We prescribe not only a degree sequence of the nodes, but the degree of a node broken down into 5 parts regarding the age groups in a way the expectations comply with the contact matrix C, but the degrees also have a small variance. The distribution is chosen such that the variance is minimal among distribution supported on the integers, given the expectation. For example in case of c 1,4 = 2, 4847 every node in age group 1 has exactly 2 or 3 neighbours in age group 4, and the average number is 2, 4847. Our configuration model creates a random graph with the given degree sequence. According to [5] , the expected value of the number of loops and multiple edges divided by the number of nodes tends to zero, thus for N = 10000 it is suitable to neglect them and to represent a network of social contacts with this model.

In this section we detail how we implemented the discretization of the process on the generated random graphs. Most of the parameters remained the same as in the differential equations, however to add more reality we toned them with a little variance. For the matter of the transmission rates, we needed to find different numbers to describe the probability of infections, since β was derived from C matrix and R 0 basic reproduction number. Since C is built in the structure of our graphs, using different parameters β i,j would result in adding the same effect of contacts twice to the process. Therefore instead of β i,j , we determined a universalβ according to the definition of R 0 . We set the disease transmissions toβ = R 0 3·12.8113 , under the assumption, that the contact profile of age groups are totally implemented in the graph structure. Only the average density of the graph (without age groups), severity of the disease and average time spent in infectious period can affect the parameters.

Parameters ν W , δ, q i remained exactly the same, while 1 ν E = 1.25 and 1 ν I = 3 holds only in expected value. The exact distributions are given as follows:

We built in reduction in infectiousness δ in the process in such way that an unsuccessfully vaccinated individual spends 3 · 0.75 = 2.25 days in average in I, instead of modifyingβ.

In the discretized process, we start with 10 infectious nodes chosen randomly and independently from the age groups. We observe a 90 day period with vaccination plus 10 days without it. (In the basic scenarios we start vaccination at day 1, however we later examine the process with vaccination starting a few days before the outbreak). At a time step firstly the infectious nodes can transmit the disease to their neighbours. Only nodes in S can be infected, and they cannot be infected ever again. When a node becomes infected, its position is set immediately to E, and also the number of days it spends in E is generated. Secondly we check if a node reached the end of its latent/infectious period, and we set its position to I or R. (As soon as a node becomes infectious, the days it spends in I is also calculated.) Then at the end of each iteration we vaccinate 0.67% of the whole population according to some strategy (if it is possible). Only nodes in S get vaccination (at most once), it is generated immediately whether the vaccination is successful (with probability q i , according to its type). In case of success, the day it could become immune without any infection is also noted. If it reaches the 14th day, and still in S, its position is set to immune.

The first question is whether the structure of the underlying graph can affect the process, in the case when the edge densities are described by the same contact matrix C. We can ask how it can affect the overall outcome and other properties, and how we can explain and interpret these differences regarding the structure of the graph. We compare results on different graphs with each other, and also with the numerical solution of the differential equations describing the process. In this section we study the basic scenario: Our vaccination starts at day 1, we vaccinate by uniform strategy. This strategy does not distinguish age groups, every day we vaccinate 0.67% of each age group randomly (if it is still possible). We set R 0 = 1.4.

Using the differential equation system from [14] Giving structure to the underlying social network boosted these numbers in every case, however differences are still significant between the random graphs of different properties.

To study the result on the discretized model, we generated 5 random graphs with N = 10000 nodes for each graph structure, and run the process 20 times on a random graph with independent In case of most of the structures we can derive rather different outcomes on the same graph with different initial values concerning the peak of the virus. Therefore using the same graphs more is acceptable.)

As we can see on Figure 3 (compared to Figure 2 ), random graphs from the configuration model were the closest to the numerical solution of differential equations. However, the difference in outcomes can be clearly seen from every perspective: Almost 20% of the population (5.7% more) was infected by the virus at the end of the time period, the infection peaked almost 10 days sooner (at day 41) and the number of infectious cases at the peak is almost twice as large. We got similar, but more severe result on Erdős-Rényi graphs. however still only a maximum 0.021% of the population was infected at the same time.

The outcome in case of graphs with a (partial) preferential attachment structure shows that distribution of degrees do matter in this process. (This notice gave the idea initially to model a graph with minimal degree deviation with the help of the configuration model. We were curious if we can get closer results to the differential equations on such a graph.) On preferential attachment graphs 47.66% of the individuals came through the disease. What is more, 1% of the population was infected at the same time at the peak of the virus, only at day 21. However, after day 40 the infection was substantially over. With preferential attachment structure it is very likely that a node with huge degree gets infected in the early days of the process, irrespectively of initial infectious individual choices, resulting in an epidemic really fast. However, after the dense part of the graph passed through the virus around day 40, even 40% of the population is still in S, magnitude of infectious cases is really low.

The process on Preferential attachment mixed with Erdős-Rényi graphs reflects something in be-

tween, yet preferential properties dominate. It was possible to reach 60% vaccination rate during the process, except in case of Preferential attachment graphs. At the end of the 100th day, 0.4 − 0.45

proportion of individuals could acquire immunity after vaccination. 

Basic reproduction number is a representative measure for the seriousness of disease. Generally, diseases with a reproduction number greater than 1 should be taken seriously, however the number is a measure of potential transmissibility. It does not actually tell, how fast a disease will spread. Seasonal flu has an R 0 about 1.3, HIV and SARS around 2 − 5, while according to [18] 

In this section we investigate how different strategies in vaccination can affect the attack rates. We study three very different strategies based on age groups or other properties of the graph. In each strategy 0.67% of the population is vaccinated at each time step (sometimes exactly, sometimes only in expected value). After a 90 days vaccination campaign 60% of the population should be vaccinated from each age group (if it is possible). We still start our vaccination campaign at day 1, and we vaccinate individuals at most once irrespectively of the success of the vaccination.

• Uniform strategy: This strategy does not distinguish age groups, every day we vaccinate randomly 0.67% individuals of each age group.

• Contacts strategy: We prioritize age groups with bigger contact number, corresponding to denser parts of the graph (concerning the 5 groups). We vaccinate the second age group for 11 days, then the third age group for 26, first age group for 10 days, forth group for 29 days, and at last age group 5 with the smallest number of contacts for 15 days. This strategy turned out to be the best in the case without any graph structure [14] . However, in conventional vaccination strategies, in the first days of the campaign, amongst others health care personnel is vaccinated which certainly makes sense, but can be also interpreted as nodes of the graph not only with high degree, but also with high probability to get infected.

The effect of vaccination by degrees can be also noticed on the shape of infected individuals in age groups developing in time (see Figure 6 ). Not only the magnitude decreased, but the vaccination also increased the skewness, especially for age group 2. Vaccination by contacts totally distorted the curve of age group 2, while the others did not changed much.

We examine if vaccination before the outbreak of a virus (only a few, 5-10 days before) could influence the epidemic spread significantly. Delay in development of immunity after vaccination is one of the key factors of the model, thus pre-vaccination could counterweight this effect. 

Edges of the graph so far represented only the existence of a social contact, however relationships between the individuals could be of different quality. It is also a natural idea to make a connection between the type of the nodes (age groups of individuals) and the feature of the edge between them.

For example, generally we can assume that children of age 0-9 (age group one) are more likely to catch or transmit a disease to any other individual regardless of age, since the nature of contacts with children are usually more intimate. So on the one hand, creating weights on the edges of the graph can strongly be in connection with the type of the given nodes. On the other hand regardless of age groups, individuals tend to have a few relationships considered more significant in the aspect of a virus spread (individuals sharing a household), while many social contacts are less relevant.

For the reasons above, we upgrade our random graphs with a weighting on the edges, taking into account the age groups of the individuals. Regardless of age, relationships divided into two types:

close and distant. Only 20% of the contacts of an individual can be close, transmission rates on these edges are much higher, while on distant edges they are reduced.

We examine a model in which age groups do not affect weights of the edges. We double the probabilities of transmitting the disease on edges representing close contacts, and decrease probabilities on other edges at a 0.75 rate. In expected value the total R 0 of the disease has not changed. However, results on graphs can be different from the unweighted cases. With the basic scenario and in case of We experience the biggest difference on Erdős-Rényi-graphs, however models with edge weights give bigger attack rates of only 0.01. We get a less severe virus spread with edges only on the configuration model.

In this section we study the discretized voter model in which particles exchange opinions from time to time, in connection with relationships between them. We create a simplified process to be able to examine the outcome on larger graphs. Firstly, we examine this simplified process on Erdős-Rényi and

Barabási-Albert graphs, then multiple type of nodes is introduced. With a possible interpretation of different types of nodes in the graphs, we generalize the voter model. Later we examine the "influencer" model, in which our aim is, in opposition to the SEIR model, to spread one of the opinions. The process in continuous time can be modelled with a family of independent Poisson process.

For each pair of vertices (x, y) we have a Poisson process of rate q(x, y), which describes the moments

x convincing y. The rate q(x, y) increases as the distance d(x, y) decreases. In this case, every time a vertex is influenced by another one, it changes its opinion immediately.

In our discretized voter process, there are two phases at each time step. First, nodes try to share their opinions and influence each other, which is successful with probabilities depending on the distance of the two vertices. More precisely, vertices that are closer to each other have higher chance that their opinion "reaches" the other one. Still, every vertex can "hear" different opinions from many other vertices. In the second phase, if a node v receives the message of m 0 nodes with opinion 0, and m 1 nodes with opinion 1, then v will represent opinion 0 with probability m 0 m 0 +m 1 during the next step, and 0 otherwise. If a node v does not receive any opinions from others at a time step, then its opinion remains the same. This way, the order of influencing message in the first phase can be arbitrary, and it is also possible that two nodes exchange opinions. Now we specify the probability that a vertex x manages to share its opinion to vertex y in the first phase. We transform graph distances d(x, y) into a matrix of transmission probabilities with choice q(x, y) = e −c·d(x,y) , where c is a constant. This is not a direct analogue of the continuous case, but it is still a natural choice of a decreasing function of d. (Usually we use c = 2, however later we also investigate cases c ∈ {0.5, 1, 2, 3}. Decreasing c escalates the process.)

In the model above, on a graph on n nodes, at every time step our algorithm consists of O(n 2 ) steps, which can be problematic for bigger graphs if our aim is to make sample with viter = 100 or 200 iteration of the voter model (in the sequel, viter denotes the number of steps of the voter model). However, with c = 2 a node x convinces vertices y with d(x, y) = 3 only with a probability of e −6 = 0, 0025. Thus we used the following simplified model: When we created a graph, we stored the list of edges and also calculated for each node the neighbours of distance 2. The simplified voter model spread opinions only on these reduced number of edges with the proper probabilities. We were able to run the original discretized model only on graphs with n = 100, while the simplified version can deal with n = 1000 nodes. We made the assumption that neglecting those tiny probabilities cannot significantly change the outcome of the process. From now on we only model the simplified version of the process.

Firstly we study the voter model on Erdős-Rényi(n, p) and Barabási-Albert(n, m) random graphs.

• ER(n, p): We create n nodes, and connect every possible pair x, y ∈ V independently with probability p.

• BA(n, m): Initially we start with a graph G 0 . At every time step we add a new node v to the graph and attach it exactly with m edges to the old nodes with preferential attachment probabilities. Let D denote the sum of degrees in the graph before adding the new node, then we attach an edge independently to u with probability d(u) D . We generated graphs starting from G 0 = ER 50, m (50−1) graph of complying density. Multiple edges can be created by the algorithm, however loops cannot occur. Attachment probabilities are not updated during a time step. Multiple edges do matter in the voter model, since they somehow represent a stronger relationship between individuals: opinion on a k-multiple edge transmits with a k-times bigger probability.

Firstly, we examine the voter model on graphs without any nodes of multiple types to understand the pure differences of the process resulting from the structure. We compare graphs with the same density, BA(1000, m) graphs with m = {4, 5, . . . , 10} and ER(1000, p), where p ∈ [0.004, 0.01]. Initial probability of opinion 1 is set to 0.05 in both graphs. We compare the probability of disappearing the opinion with viter = 50 iteration of the voter model. We generated 10 different graphs from each structure and ran voter model on each 20 times with independent initial opinions. Altogether the results of 200 trials were averaged. Figure 8 shows the results.

Before the phase transition of Erdős-Rényi graphs, that is, with p < ln n n ≈ 0.007 with n = 1000 nodes (BA graphs of the same density are belonging to m ≤ 7) the graph consists of several 

As mentioned before, in this sequel we investigate extreme outcomes of the process caused by one of the most important properties of Barabási-Albert graphs. Since nodes do not play a symmetrical role in Barabási-Albert graphs, fixing the proportion of nodes representing opinion 1 (we usually use v = 0.05, so 50 nodes represent opinion 1 in expected value), but changing the position of these nodes in the graph can lead to different results. We examined the following three ways of initial opinion setting:

• randomly: Each individual chooses opinion 1 with probability v.

• "oldest nodes": We deterministically set the first 50 nodes of the graph to represent opinion 1.

These nodes have usually the largest number of degrees, thus they play a crucial part in the process. Not only have they large degrees, but they are also very likely to be connected to each other (this is the densest part of the graph).

• "newest nodes": We deterministically set the last 50 nodes of the graph to represent opinion 1.

These nodes usually have only m edges, and they are not connected to each other with a high probability. The histogram on Figure 9 shows the distribution of nodes with opinion 1 with the three different choice of L 0 vectors after viter = 50 iterations of the voter model on BA(1000, 5) graphs. We experience differences in terms of probabilities of disappearing opinion 1: with random opinion distribution 11%, with L new almost one third of the cases resulted in extinction of opinion 1, while for L old this probability was negligible (0.005%). Actually, for L old after only one iteration of the voter model it is impossible to see any structure in the distribution of individuals with opinion 1. Vector of opinions became totally random, but with a probability of 0.12. Indeed only with one step of the voter model individuals with opinion 1 could double in number, however opinion 1 cannot take advantage of any special positions in the graph anymore. All in all, giving a certain opinion to individuals who are more likely to be connected in the graph, reduces the probability of disappearing, since they can keep their opinion with a high probability, while with opinion 1 scattered across the graph (in case of L new as well as L rand ) with a dynamic parameter setting of c number of individuals with opinion 1 can reduce drastically even in a few time steps.

It is a natural idea to divide the nodes of a network into separate groups according to some aspect, where the properties of different groups can affect processes on the graph. There are various ways to classify nodes into different types. We examined a simple and an other widely used method. In the following section we only have nodes with two types, however definitions still hold for multiple type cases. From now on, for purposes of discussion we only refer to the types as red and blue.

We consider two different ways to assign types to the nodes:

• Each node independently of each other chooses to be red with probability p r , and blue with 1 − p r . (Here index r corresponds to random.)

• Since preferential attachment graphs are dynamic models, this enables another very natural and logical way of choosing types: After a new node has connected to the graph with some edges, informally the node chooses its type with probabilities corresponding to the proportions among its neighbours' type (see also [1, 13, 17] ). This way nodes with the same type tend to connect to each other with a higher probability, forming a "cluster" in the graph. We only examined linear models. According to [2] , a few properties in the initial graph G 0 and initial types of nodes can determine the asymptotic behaviour of the proportion of types.

Let G n denote the graph when n nodes have been added to the initial graph G 0 . Let A n and B n denote the number of red and blue nodes in G n . Then the following theorem holds for the asymptotic proportion of red (a n ) and blue (b n )nodes, a n = An An+Bn , b n = Bn An+Bn . Let X n and respectively Y n denote the sum of the degrees of red and blue nodes in G n .

and that X 0 , Y 0 ≥ 0. Then a n converges almost surely as n → ∞. Furthermore, the limiting distribution of a := lim n→∞ a n has full support on the interval [0, 1], has no atoms, and depends only on X 0 , Y 0 , and m.

This property has great significance, since we would like to compare graphs with the same proportion of red and blue nodes. The theorem ensures us about the existence of such a limiting proportion.

What is more, with the generation of Barabási-Albert graphs with multiple edges we can examine the speed of convergence. We set types of nodes in the initial graph G 0 in such a way that not necessarily half of the nodes will be blue, but approximately the sum degree of nodes with type blue will be the half of the whole sum of degrees. (Of course, in case of an initial Erdős-Rényi graph these will be the same in expected value. However we can get more stable proportion of types with the second method. In this case by stable we mean proportions can be closer to 1 2 .)

In the voter model we can see nodes with multiple types, defined in the last section, with the following interpretation. Each node (individual) has two types according to two different aspects: So each node chooses a type from both of the aspects, and the choice of types according to different aspects are independent. (Since four combination of these is possible, we could say that each node chooses one type from the 4 possible pairs.) During the voter model, interaction of nodes with different types influence the process in the following way: Complying with the names of the types, we expect that good reasoner nodes could convince any nodes with a higher probability than bad reasoner nodes. Also any node should convince a node of unstable type with a higher probability than a node of a stable type. In a step of the voter model, when node x influences a node y, the probability of success should only depend on node x's ability to convince (good/ bad reasoner type) and node y's We investigated the model with symmetric parameter set: The probability of a good reasoner node convincing a stable one is equal to the probability of a bad reasoner node convincing an unstable one.

We also made the assumption that a bad reasoner node can convince a stable node with probability 0. Voter model was examined with different c(1) ≥ c(2) set of parameters, and different possible choices of types in the graph.

In this sequel we examine a special case of voter model with multiple type nodes, in which the aim is to spread an initially underrepresented opinion. This problem might be related to finding good marketing strategies on online social networks, when "opinion" might be about a commercial product or a certain political convinction.

We investigate the following "influencer" model: Types of a node according to the different aspects is not independent, nor is the L 0 vector of initial opinions. The nodes of the graph are divided into two groups, influencers and non-influencers. Influencers usually form a smaller population; they represent opinion 1, which we want to spread across the graph. They are good reasoners, and also stable, while non-influencers have bad reasoner type according to the ability to convince, while they can be stable as well as unstable. According to definitions of c values, it is impossible for a bad reasoner node to convince a stable one, resulting influencers representing opinion 1 for the whole process.

Firstly, we study a case in which nodes of a BA graph get a type randomly or deterministically, not according to preferential attachment. We study the equivalent of the case in subsection 3.2.1 with multiple type nodes. In each graph 10% of individuals (100 nodes) are influencers. In BA graphs influencers are situated randomly, on the "oldest nodes" or on the "newest nodes" of the graph. In ER graphs influencers are situated randomly (however, since the role of nodes is symmetric, they can be situated anywhere, with no difference in the outcome). We would like to examine the differences in opinion spread. We are also interested whether it is possible to convince all the nodes of the graph to opinion 1, and in case it is, we calculate the average time needed to do so.

We observed differences in the outcome for 100 runs (on 5 different random graphs), with c = [2, 1] and m = 8 parameter set (see Figure 10 ) (We wanted to exclude cases in which the proportion of one of the types is negligibly small.) For these reasons, we created ER and BA graphs with multiple nodes, where the proportion of good reasoners is 1 2 and according to preferential attachment (in BA graphs), we set these nodes to be the influencers (they are stable, while non-influencer individuals can be stable and unstable with probability 1 2 ). So in expected value half of the nodes are influencers, but in case of BA graphs we can experience greater deviance (in expected value half of the nodes have good reasoner type according to the ability to convince, and 3 4 of the nodes have stable type). For ER graphs the only meaningful possibility to create types is the random choice, but the same proportions also hold. proportions in BA graphs are still a bit greater). However, in terms of disappearing opinions results are rather different. On ER graphs in none of the cases could opinion 0 disappear, while on BA graphs it strongly depended on the exact initial proportion of influencers in the graph: On the same graph (and hence with the same proportion of influencers) opinion 0 disappears either within the first 50 iterations of the voter model, or holds a high proportion of opinion 1, yet it will never be able to reach the limit. This main difference resulted from the fact that we can not exactly set the proportion of types in BA graphs, thus the co-existence of opinions is rather sensitive to changes in the number of influencers in BA graphs. (In ER graphs only 20% of the examined runs resulted in disappearance of opinion 0, even with 600 influencers.)

In this section we examine the voter model on a random graph which has a geometric structure on the plane. Since the graph model is not dynamic, nodes can only choose their type randomly (or according to some deterministic strategy related to the position of nodes in the plane). However firstly we study the model without multiple types, with constant c = 0.5, 0.1. Since the voter model is rather time-consuming, and even in case of parameter c = 0.5 the probability of conviction q(x, y) = e −c·d(x,y) for d(x, y) = 10 is ≈ 0.0067. Thus we create a reduced graph from RP (n) by erasing edges in case of d(x, y) > 10. We can assume that results on the reduced graph can approximate the outcome on the original one, since transmission of opinions on those edges are negligible. The average degree in the reduced graph is still 27.85. Modifying the voter model to spread opinions only on these edges makes the algorithm less robust and manageable to run the process on graphs with many (n = 1000) nodes.

Firstly, we would like to understand the behaviour of the process without multiple types of the graph.

In this section we make an advantage of the geometric structure of the graph, and examine different deterministic and random choices for initial opinions of L 0 . We study how these alternative options can influence the outcome (the probability of the disappearance of an opinion, expected time needed for extinction). Another interesting question is whether after a given number of iterations t of the voter model we can still observe any nice shape of the situation of opinions. In both of the following four choices for initial opinions in expected value 10% of the individuals are given opinion 1, the rest of them represent opinion 0. The discretized voter model with different initial opinion vectors L 0 was performed on 400 different graphs for viter = 100 steps. With n = 1000 number of nodes, c = 0.5 and only 10% of population representing opinion 1, opinion 1 disappeared only in a few (negligible) cases for any examined L 0 .

We can say, without any doubt according to picture 11, that after 100 time steps the deterministic position of initial opinions is still recognizable (even after viter = 200 steps). We can generally state that with clustering individuals with the same opinion in a group, makes proportion of opinions more stable in the process: From the different runs we observed that proportion of opinions (from initial 0.1) stayed between [0.8, 1.2] with a probability of more than 0.4 in case of opinion 1 situated in a corner of the graph, while in any other cases this was significantly lower (less than 0.3). With this placement of opinion 1, average distances within individuals with opinion 1 was the smallest, however average distances between different groups of opinions was the largest among the examined cases, resulting in moderate change of opinions.

Number of individuals representing 1 decreased below 50 only with probability of 0.08, while with placing opinion 1 in the center this probability is 0.1325. Opinion 1 is the most likely to disappear (with probability 0.195), or reduce to an insignificant amount with random placement of opinion 1.

However, inverse extreme cases are also more likely to occur, since proportions of opinion 1 exceeding 0.2 is outstandingly high with this scenario. Moreover, despite the high probability of extinction, in expected value we get the highest proportion of opinion 1 after viter = 100 iteration of the voter model with random initial configuration.

We also examined random graphs on a plane with a random or deterministic type choice of the nodes corresponding to two different aspect as before. We set the type pairs to form an influencer model defined before. Due to the fact that average distances in this random graph model are significantly larger than in ER and BA graphs of small-world property, small proportion of influencers in most In most of the cases neither can help the problem the setting of all non-influencer individual to unstable type. Even with random influencer position the calculation of average time needed to convince all nodes of the graphs is challenging due to its time cost. With the increase of influencers in number to 300, in half of the runs was able to reach opinion 1 all nodes of the graph within 400 time steps.

However, sometimes only in a relatively small number of iterations, suggesting that exact position on the plane of randomly chosen individuals do effect the process significantly.

Coexistence in preferential attachment networks

Evolving voter model on dense random graphs

On the spread of viruses on the internet

A trust model for spreading gossip in social networks

Random Graphs. Second Edition

On critical vaccination coverage in multitype epidemics

Graphs with specified degree distributions, simple epidemics, and local vaccination strategies

The noisy voter model on complex networks

Coexistence results for some competition models

Random graph dynamics

SIR epidemics and vaccination on random graphs with clustering

Random graphs and complex networks

Preferential attachment graphs with co-existing types of different fitnesses

Gergely Röst Modelling the strategies for age specific vaccination scheduling during influenza pandemic outbreaks

Interacting Particle Systems

Daihai He, Preliminary estimation of the basic reproduction number of novel coronavirus (2019-nCoV) in China, from 2019 to 2020: A data-driven analysis in the early phase of the outbreak