Invasion Dynamics in the Biased Voter Process

1 Introduction

Invasion processes are a standard framework for modeling the spread of novel traits in populations. The population structure is represented as a graph, with nodes occupied by agents, while the edge relation captures some sort of agent connection, such as spatial proximity, friendship, direct communication, or particle interaction. The invasion dynamics define the rules of trait diffusion from an agent to its neighbors. These dynamics raise a natural optimization problem that calls to choose a set of at most k initial trait-holders that maximizes a goal involving the eventual spread of the trait in the population. This type of problem has been studied extensively with a focus on influence spread on social network dynamics [Domingos and Richardson, 2001; Kempe et al., 2003; Mossel and Roch, 2007]; see [Li et al., 2018] for a survey.

The voter process is a fundamental and natural probabilistic diffusion model that arises in evolutionary population dynamics, where the diffused trait is a mutation and the initial trait-holders are mutants. Also known as imitation updating in evolutionary game theory [Ohtsuki et al., 2006], it was initially introduced to study particle interactions [Liggett, 1985] and territorial conflict [Clifford and Sudbury, 1973]; since then, it has found numerous applications in the spread of genetic mutations (the death-birth Moran process) [Hindersin and Traulsen, 2015; Tkadlec et al., 2020], social dynamics [Castellano et al., 2009], robot coordination and swarm intelligence [Talamali et al., 2021]. In the long run, the process leads to a consensus state [Even-Dar and Shapira, 2007], in which the mutant trait is either fixated (i.e., adopted by all agents), or gone extinct. The calibre of the invasion is quantified in terms of its fixation probability [Kaveh et al., 2015; Brendborg et al., 2022]; thus, the goal of optimization in this context is to maximize the probability that the mutant trait spreads in the whole population. Unlike other models of spread, the voter process accounts for active resistance to the invasion: an agent carrying the mutant trait may not only forward it to its neighbors, but also lose it due to exposure to the resident trait from its neighbors. This model exemplifies settings such as individuals that may switch opinions, magnetic spins that may undergo transient states, and sub-species that compete in a gene pool.

In this paper, we study the problem of fixation probability maximization in the context of the biased voter process: find a set of k agents initially having a mutant trait A that maximizes the fixation probability of A in a population with a preexisting resident trait B. The invasion bias r ∈ (0,∞) quantifies the stochastic preference of each agent towards (r > 1) or against (r < 1) adopting A over B. Despite extensive interest in this type of optimization problem and the appeal and generality of the voter process, to our knowledge, this problem in the context of the voter process has only been studied in the restricted case r = 1, which admits a simple polynomial-time algorithm [Even-Dar and Shapira, 2007]. Yet biased invasions naturally occur in most settings: for genetic mutations, r captures the fitness (dis)advantage conferred by the new mutation [Allen et al., 2020]; for magnetic spins, r reveals the presence of a magnetic field [Antal et al., 2006]; for social traits, r accounts for the societal predisposition towards a new idea [Bhat and Redner, 2019].

Our contributions can be summarized as follows:

1. We show that computing the fixation probability on undirected graphs admits a fully polynomial-time approximation scheme (FPRAS).
2. We show that, notwithstanding the neutral case where r = 1, fixation maximization is NP-hard both for r > 1 and for r < 1, while the latter case is also inapproximable within any multiplicative factor.
3. On the positive side, we show that, when r > 1, the optimization function is submodular and thus can be greedily approximated within a factor 1 - 1/e.

2 Preliminaries

Structured populations. Following the literature standard, we represent a population structure by a (generally, directed and weighted) graph G = (V, E, w) of n = |V | nodes. Each node stands for a location in some space, while a population of n agents is spread on G with one agent per node. Given a node u, we denote by N(u) = {v ∈ V : (v, u) ∈ E} the neighbors of u, and by deg(u) = |N(u)| its degree. The weight function w: E → R≥0 maps every edge to a nonnegative number. As a convention, we write w(v, u) = 0 if (v, u) ̸∈ E. We consider graphs for which the sub-graph induced by the support of w is strongly connected - which is necessary for the voter process to be well-defined. We say that G is undirected if E is symmetric and irreflexive, and w(v, u) = 1 for all (v, u) ∈ E. For simplicity, when G is undirected we denote it by G = (V, E).

The voter invasion process. The classic voter process models the invasion of a mutant trait A into a homogeneous population [Clifford and Sudbury, 1973; Liggett, 1985]. The process distinguishes between two types of agents, residents, who carry a resident trait B, and mutants, who carry the mutant trait A. A seed set S ⊆ V defines the agents that are initially mutants. The invasion bias r > 0 is a real-valued parameter that defines the relative competitive advantage of mutants in this invasion. When r > 1 (resp., r < 1), the mutants have a competitive advantage (resp., competitive disadvantage), and the process is biased towards (resp., against) invasion, while r = 1 yields the neutral case. A configuration X ⊆ V defines the set of mutants at a given time. The fitness of the agent occupying a node u ∈ V is defined as

The discrete-time voter invasion process [Antal et al., 2006; Even-Dar and Shapira, 2007], a.k.a. Moran death-birth process [Tkadlec et al., 2020; Allen et al., 2020], with seed set S is a stochastic process (Xi)i≥0, where Xi ⊆ V is a random configuration. Initially, X0 = S, and, given the current configuration X, we obtain Xi+1 in two stochastic steps.

1. (Death event): a focal agent on some node u is chosen with uniform probability 1/n.
2. (Birth event): the agent on u adopts the trait of one of its

neighbors, on v, with probability:

Note that the focal agent may assume its pre-existing trait, and generally, the mutant set may grow or shrink in each step. We often identify agents with the nodes they occupy and use expressions such as "node v reproduces onto u" to indicate that the agent occupying node u adopts the trait of the agent at node v. See Fig. 1 for an illustration.

Fixation probability. As G is strongly connected, one type will spread to all nodes in finitely many steps with probability 1. The mutant invasion succeeds if the mutant trait spreads, an event called fixation. Given a graph G, a bias r, and an initial seed set S, the fixation probability, denoted as fpGr (S), is the probability that the mutants starting from S eventually fixate on G. See Fig. 2 for an illustration.

Whereas the computational complexity of determining fpGr (S) is unknown, the function is approximately computable by a simulation of the invasion process. In the next section we will show that when G is undirected, such a simulation yields an efficient approximation scheme.

Fixation maximization. We formulate and study the optimization problem of selecting a seed set that leads to a most successful invasion, i.e., maximizes the fixation probability, subject to cardinality constraints. Formally, given a graph G, a bias r and a budget k, the task is to compute the set

The corresponding decision question is: Given a budget k and a threshold α ∈ [0, 1] determine whether there exists a seed set S with |S| = k such that fpGr (S) ≥ α. As Fig. 2 illustrates, different seed sets yield considerably different fixation probabilities, while the optimal choice varies depending on r, hence the intricacy of the problem.

3 Computing the Fixation Probability

For r = 1, the fixation probability is additive [Broom et al., 2010]. Thus, given a graph G = (V,E,w) and a budget k, the set S∗ that maximizes fpGr=1 (S) is obtained by selecting the k largest values from the vector ⟨fpGr=1 ({v}) | v ∈ V ⟩, determined by solving a system of n linear equations [Allen et al., 2015]; thus the problem can be solved in polynomial time. When G is undirected, that system admits a closed-form solution [Broom et al., 2010]: fpGr=1 ({v}) = deg(v)/2|E|.

For r ̸= 1, the complexity of determining fpGr (S) is open. Here we show that, for undirected graphs, it can be efficiently approximated by a fully-polynomial randomized approximation scheme (FPRAS). The key component of our result is a polynomial upper bound on the expected number of steps TGr (S) until one of the types fixates; an analogous approach has been used for the so-called Moran Birth-death process [D´ıaz et al., 2014].

Theorem 1. Let G = (V,E) be an undirected graph with |V | = n nodes, |E| = m edges, and maximum degree ∆. Let S ⊆ V be the initial seed set and r ̸= 1. Then TGr (S) = O(∆nm) = O(n4 ).

Proof. Without loss of generality, suppose r > 1 (otherwise we swap the role of mutants and residents). Given a current configuration X, we define a potential ϕ(X): 2V → R as ϕ(X) = ∑v∈X deg(v). We show that, as we run the process, ϕ(X) increases in a controlled manner. To that end, we distinguish two types of configurations: we say that a configuration is bad if every edge uv ∈ E connects nodes of different types, and good otherwise. Note that bad configurations exist iff G is bipartite, in which case there are exactly two of them. In [Durocher et al., 2022], we show that:

1. When at a bad configuration, the next configuration is good and the potential does not change in expectation.
2. When at a good configuration, in one step the potential increases by at least s = (r - 1)/(r∆n) in expectation.

All in all, this implies that, in expectation, the potential increases by at least s over any two consecutive steps (until fixation occurs). Since at all times the potential is non-negative and upper-bounded by U = ∑v∈V deg(v) = 2m, by a standard drift theorem for submartingales [He and Yao, 2001;

Lengler, 2020] the expected number of steps is at most:

Theorem 1 yields the following corollary based on the Monte Carlo method.

Corollary 1. When G = (V,E) is undirected, S ⊆ V , the function fpGr (S) admits a FPRAS for any r.

4 Invasion with Favorable Bias

In this section we study the voter process for r > 1. We show that the problem is NP-hard (Section 4.1) but the fixation probability is monotone and submodular and can thus be efficiently approximated (Section 4.2).

4.1 Hardness of Optimization

Here we consider the weakly biased process, i.e., the case r = 1 + ε for small ε > 0. Since fpGr (S) is a continuous and smooth function of r, its Taylor expansion around r = 1 is:

Lemma 1. For any undirected regular graph G, there exists a small constant ε > 0 such that:

In light of Lemma 1, we establish the hardness of fixation maximization by computing c(G, S) analytically on regular graphs, and showing that maximizing it is NP-hard. McAvoy and Allen [2021] recently showed that, given G and S, the constant c(G, S) can be defined through a system of n2 linear equations. Here we determine c(G, S) explicitly for regular graphs. For each node v ∈ V , let xv = 1 iff v ∈ S. First, we restate [McAvoy and Allen, 2021, Proposition 2] in the special case of d-regular graphs and adapt it to our notation.

Lemma 2. Fix an undirected d-regular graph G = (V,E) on n nodes and an initial configuration S ⊆ V . Then

where ηuv comprise the unique solution to the linear system

Intuitively, each ηuv expresses the expected number of steps in which nodes u and v are occupied by a mutant and resident, respectively. We say that an edge e ∈ E is active if its endpoints are occupied by heterotypic agents. The following lemma establishes that, on regular graphs, c(G, S) is decreasing in the number of active edges induced by S.

Lemma 3. Let G = (V,E) be a d-regular graph on n nodes and S ⊆ V an initial configuration of size |S| = k. Let a(S) be the number of active edges induced by S. Then

Proof. Let |uv| be the shortest-path distance between u and v in G. We proceed in two steps. First, we claim that summing all the n2 equations in the system of Eq. (4), we obtain

Indeed:

1. We have ∑u,v∈V |xu - xv| = 2k(n - k), since each ordered pair of heterotypic agents is counted once.
2. For a fixed pair (u, v) with |uv| ≥ 2, term 1 2d ηuv appears on the right-hand side of 2d equations, namely d equations with ηwv on the left-hand side and u∈N(w) and d equations with ηuw on the left-hand side and v∈N(w).
3. For a fixed pair (u, v) with |uv| = 1, term 1 2d ηuv appears on the right-hand side of 2d - 2 equations, namely the above 2d equations, except for 2 cases where w ∈ {u, v}.

Rearranging Eq. (5), we obtain

Second, we claim that summing the 2|E| equations in the system of Eq. (4) where |uv| = 1, we obtain

ergo, using Eq. (6)

Indeed,

1. We have ∑|uv|=1 |xu - xv| = 2a(S), since each active edge is counted exactly twice, once in each direction.
2. For a fixed pair (u, v) with |uv| = 1, let N(u, v) = N(u) ∩N(v) be the set of common neighbors of u and v. The term 1 2d ηuv then appears on the right-hand side of precisely 2|N(u, v)| equations, namely |N(u, v)| equations with ηwv on the left-hand side and |N(u, v)| equations with ηuw on the left-hand side, where w ∈ N(u, v).

From Lemma 2 and Eq. (7), we obtain the desired

Thus, given a budget k, we maximize the fixation probability at the limit r → 1, by minimizing the number of active edges. We are now ready to establish the main result in this section.

Theorem 2. Fixation maximization in the biased voter process with r > 1 is NP-hard, even on regular undirected graphs.

Proof. Lemma 1 and Lemma 3 imply that, for any regular undirected graph G, there exists a small ε > 0 for which

i.e., the fixation probability is maximized by a seed set that minimizes the number of active edges. For k = n/2, this is known as the minimum bisection problem, which is NP-hard even on 3-regular graphs [Bui et al., 1987].

4.2 Monotonicity and Submodularity

A real-valued set function f is called monotone if for any two sets A and B with A ⊆ B, we have f(A) ≤ f(B). Further, f is called submodular if for all sets A and B we have

Monotone submodular functions, even if hard to maximize, admit efficient approximations. Here we complement the hardness of Theorem 2 by showing that fpGr≥1 (S) is monotone and submodular. Although submodularity is well-known for some progressive invasion processes [Kempe et al., 2003], recall that our setting is non-progressive, i.e., the mutant set may grow or shrink in any step. This non-progressiveness renders submodularity a non-trivial property.

Node duplication. Towards establishing monotonicity and submodularity, it is convenient to view the process in a slightly different but equivalent way, via node duplication. Consider the voter process M on a graph G with bias r > 1. The node duplication view of M is another stochastic process M′ = (X ′ i )i on G, defined as follows. Let X ⊆ V be the current configuration.

1. A node u is chosen for death uniformly at random (i.e., this step is identical toM).
2. We modify G = (V,E,w) to G′ = (V ′ ,E′ ,w′ ) as follows. For every node v ∈ N(u) ∩ X, we create a duplicate v′ of v, and insert an edge (v′ , u) in G′ with weight w′ (v′ , u) = w(v, u). We associate v′ with fitness f ′X (v′ ) = r - 1, while every other node v ∈ V gets fitness f ′X (v) = 1. Finally, we execute a stochastic birth step as in the standard voter process, i.e., we choose a node v to propagate to u with probability

The new configuration X ′ i+1 contains u if either some mutant node v or its duplicate v′ was chosen for reproduction. It is straightforward to see that this modified birth step preserves the probability distribution of random configurations, and thusMandM′ are equivalent.

Monotonicity. Using the equivalence between the voter process and its variant with node duplication, we now establish the monotonicity of the fixation probability.

Lemma 4. For any graph G and bias r, for any two seed sets S1 and S2 with S1 ⊆ S2, we have fpGr (S1) ≤ fpGr (S2).

Proof. First assume r > 1. Consider two processes M1 = (X 1 i )i and M2 = (X 2 i )i starting from X 1 0 = S1 and X 2 0 = S2, respectively. We establish a coupling between M1 and M2 that satisfies X 1 i ⊆ X 2 i for all i ≥ 0, from which the lemma follows.

In each step, we first choose the same node u for death in M2 and M1 with uniform probability. Then, we execute a birth step inM2. If the reproducing node v is present inM1, we perform the same update inM1. Otherwise, if v is a mutant duplicate absent fromM1, we perform an independent birth step inM1. This coupling maintains the invariant X 1 i ⊆ X 2 i , as whenever M1 takes an independent step, a mutant has reproduced inM2. Moreover, the coupling is indeed transparent to M1 and M2, as every birth event occurs with probability proportional to its agent's fitness.

The monotonicity for all r follows by symmetry, as when r < 1 we can exchange the roles of mutants and residents. Using the above argument, it follows that the fixation probability of the residents grows monotonically in V \ S and, in reverse, decreases monotonically as V \ S shrinks, hence the fixation probability of the mutants grows monotonically in S.

Submodularity. We now show submodularity, i.e., we have

To this end, it is convenient to consider the following more refined view of the invasion process. Given an initial seed set S = A ∪ B, we keep track not only of the mutant set, but also the subset of mutants that are copies of those agents initially in A, and those initially in B. Consider this refined view, and execute the invasion beyond the point where mutants fixate. With probability 1, every execution that results in the fixation of S eventually leads to the fixation of A or B (possibly both, assuming that A ∩ B ̸= ∅). We can thus compute the fixation probability of S by summing over each execution that ends in the fixation of at least one of A, B. This "extended" process is instrumental in proving submodularity.

Lemma 5. For any graph G and bias r ≥ 1, the fixation probability fpGr (S) is submodular.

Proof. Consider any two sets A,B ⊆ V . Let M1, M2, M3 and M4 be the four (extended) invasion processes, under node duplication, that correspond to initial seeds A, B, A∪B and A∩B, respectively. For j ∈ [4], let X j i be the ith random configuration ofMj. Moreover, let Yi (resp., Zi) be the set of nodes of M3 in step i that are occupied by mutant agents who are descendants of some agent initially in A (resp., B). We establish a four-way coupling between all Mj that preserves the following invariants:

Given our extended invasion process, any execution that leads to the fixation of A ∪ B in M3 will eventually witness the fixation of at least one of A or B. Invariants (i) and (ii), then, guarantee that any fixating execution inM3 is also fixating in at least one ofM1 andM2. Invariant (iii) guarantees that any fixating run execution inM4 is fixating in bothM1 andM2. Hence, the three invariants imply Eq. (9), i.e., submodularity.

We now establish the coupling. In each step i, we choose the same node u in all Mj to die uniformly at random. Then, as long as Yi, Zi ̸= ∅ we perform the following steps.

1. Choose a node v to reproduce inM3 using node duplication (hence v is either an original or a duplicate node). For each process Mj in which v is a node (either original or duplicate), propagate the agent from v to u. Note that this step updates M3 and at least one of M1 and M2, while if it updatesM4, it also updates bothM1 andM2.
2. If v is not a node in one of M1 or M2, then perform an independent birth step in that process, choosing some node x (either original or duplicate). If x is present inM4, apply the birth event in M4 as well, otherwise apply an independent birth step inM4.

If Yi = ∅ or Zi = ∅, we perform step 2 only in the process not yet terminated. As in Lemma 4, the coupling is indeed transparent to eachMj and maintains invariants (i)-(iii).

Conclusively, monotonicity and submodularity lead to the following approximation guarantee [Nemhauser et al., 1978].

Theorem 3. Given a graph G and integer k, let S∗ be the seed set that maximizes fpGr (S), and S′ the seed set constructed by a greedy algorithm opting for maximal returns in each step. Then fpGr (S′ ) ≥ (1 - 1/e) fpGr (S∗ ).

5 Invasion with Infavorable Bias

We now turn our attention to disadvantageous invasions, i.e., r < 1, and show that the problem is intractable. To establish our result we focus on the limit r → 0, i.e., the process is "infinitely" biased against invasion, and write fpG0 (S) = limr→0 fpGr (S). Our key insight is the following lemma.

Lemma 6. Let G = (V,E) be an undirected graph on n nodes and S ⊆ V a seed set. If S is a vertex cover on G then fpG0 (S) > 1/nn , otherwise fpG0 (S) = 0.

Proof. First, suppose S is a vertex cover. Denote the nodes in V \ S by u1, . . . , ui. With probability 1/ni ≥ 1/nn , in the next i steps the agents at nodes u1, . . . , ui are selected for death (in this order). Since S is a vertex cover, each of them adopts the mutant trait, and mutants fixate.

Second, suppose S is not a vertex cover, thus we have an edge (u, v) ∈ E with u, v ̸∈ S. The idea is that, in the limit r → 0, the agents on u and v are overwhelmingly more likely to spread to the rest of the graph than to ever become mutants.

Consider a node with a mutant and b ≥ 1 resident agents among its neighbors. Note that if an agent at such a node dies, the node gets occupied by a resident agent with probability b b+ar ≥ 1n =: pres and by a mutant agent with probability ar b+ar ≤ nr =: pmut. Since G is connected, there exists an ordering (u1, . . . , uk) of the nodes in S such that node ui has a neighbor among {u1, . . . , ui-1} ∪ (V \ S), for each i = 1, . . . , k. Consider the first k steps. With probability pext ≥ ( 1n · pres )k = 1/n2k , agents at nodes u1, . . . , uk die (in this order) and all become residents, thus mutant extinction occurs. On the other hand, by Union Bound, within this time-frame, one of u, v becomes mutant with probability puv ≤ 2n pmut ≤ 2r. If neither event occurs, in the next k steps the situation repeats. Thus, mutants fixate with probability at most puv puv+pext ≤ 2r 2r+1/n2k →r→0 0.

Since vertex cover is known to be hard even on regular graphs, Lemma 6 implies the following theorem.

Theorem 4. Fixation maximization in the biased voter process with r < 1 is NP-hard, even on regular undirected graphs.

Submodularity considerations. Lemma 6 implies that maxS⊆V,|S|=k fpG0 (S) cannot be approximated within any multiplicative factor in polynomial time, unless P = NP, since such an algorithm would decide whether S is a vertex cover on G. That is so even though Lemma 5 implies, by symmetrically exchanging mutant and resident roles, that the extinction probability 1-fpGr (S) for r < 1 is submodular. Fixation maximization with r < 1 is thus equivalent to minimizing a submodular function subject to the constraint |S| = k. Although the minimization of submodular functions without constraints is polynomially solvable, simple cardinality constraints render it intractable [Svitkina and Fleischer, 2011].

6 Experiments

Here we present some selective case studies on the performance of various heuristics solving the fixation maximization problem for the biased voter process. Our studies do not aim to be exhaustive, but rather offer some insights that may drive future work. We consider six heuristics for the choice of the seed set, namely (i) high degree, (ii) high temperature, defined as T (u) = ∑v w(v, u), (iii) high pagerank, (iv) high eigenvalue centrality, (v) high betweeness centrality, (vi) high closeness centrality, and the Greedy algorithm (Theorem 3)

that provides an approximation guarantee for r ≥ 1. We evaluate all methods on four networks from the Netzschleuder database [Peixoto, 2020], chosen arbitrarily. In each case, we choose a budget k equal to 5% of the nodes of the graph.

Fig. 3 shows the performance for various biases r ≥ 1. The networks Wiki and Polblogs are well-optimizable by almost all heuristics, possibly except high closeness centrality in the second case that performs visibly worse (though not by much). The Twitter graph is more challenging, while the Elegans graph is the most difficult to optimize, with high variability on heuristic performance. Unsurprisingly, the Greedy algorithm dominates the performance on this benchmark, which is expected given its theoretical guarantees (Theorem 3). Among the heuristics, high pagerank appears to be the most consistently performant, and the first one to match the performance of Greedy on the Elegans network.

7 Conclusion

We have studied the optimization problem of selecting a cardinality-constrained seed set of mutants that maximizes the fixation probability in the classic biased voter process. We have shown that the problem exhibits intricate complexity properties in the presence of biases r ̸= 1. In particular, the problem is NP-hard in both regimes r > 1 and r < 1, while the latter case is also hard to approximate. On the positive side, we have shown that the optimization function is monotone and submodular, and can thus be approximated efficiently within a factor (1 - 1/e). Interestingly, our results on optimization hardness imply that even just computing the fixation probability over randomly chosen seed sets is also NP-hard. Random seed sets arise in genetic/biological settings [Kaveh et al., 2015; Allen et al., 2020; Tkadlec et al., 2020], due to the random nature of novel mutations. Interesting future work includes investigating better approximation factors for r > 1, and an in-depth search for good heuristics.