---
title: "Seed Selection in the Heterogeneous Moran Process"
authors:
  - "Petros Petsinis"
  - "Andreas Pavlogiannis"
  - "Josef Tkadlec"
  - "Panagiotis Karras"
doi: "10.24963/ijcai.2024/254"
url: "https://ijcai.org/proceedings/2024/254"
pdf: "https://ijcai.org/proceedings/2024/0254.pdf"
venue: "Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence"
year: 2024
pages: "2297-2305"
track: "Main Track"
keywords:
  - "Data Mining: DM: Networks"
  - "Agent-based and Multi-agent Systems: MAS: Resource allocation"
  - "Constraint Satisfaction and Optimization: CSO: Constraint optimization problems"
  - "Search: S: Evolutionary computation"
---

# Seed Selection in the Heterogeneous Moran Process

Petros Petsinis, Andreas Pavlogiannis, Josef Tkadlec, Panagiotis Karras

*Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence*, pages 2297-2305. DOI: [10.24963/ijcai.2024/254](https://doi.org/10.24963/ijcai.2024/254)

## Abstract

The Moran process is a classic stochastic process that models the rise and takeover of novel traits in network-structured populations. In biological terms, a set of mutants, each with fitness m ∈ (0, ∞) invade a population of residents with fitness 1. Each agent reproduces at a rate proportional to its fitness and each offspring replaces a random network neighbor. The process ends when the mutants either fixate (take over the whole population) or go extinct. The fixation probability measures the success of the invasion. To account for environmental heterogeneity, we study a generalization of the Standard process, called the Heterogeneous Moran process. Here, the fitness of each agent is determined both by its type (resident/mutant) and the node it occupies. We study the natural optimization problem of seed selection: given a budget k, which k agents should initiate the mutant invasion to maximize the fixation probability? We show that the problem is strongly inapproximable: it is NP-hard to distinguish between maximum fixation probability 0 and 1. We then focus on mutant-biased networks, where each node exhibits at least as large mutant fitness as resident fitness. We show that the problem remains NP-hard, but the fixation probability becomes submodular, and thus the optimization problem admits a greedy (1 − 1/e)-approximation. An experimental evaluation of the greedy algorithm along with various heuristics on real-world data sets corroborates our results.

## Full text

## 1 Introduction

Modeling and analyzing the spread of a novel trait (e.g., a trend, meme, opinion, genetic mutation) in a population is vital to our understanding of many real-world phenomena. Typically, this modeling involves a network invasion process: nodes represent agents/spatial locations, edges represent communication/interaction between agents, and local stochastic rules define the dynamics of trait spread from an agent to its neighbors.

Network diffusion processes raise several optimization challenges, whereby we control elements of the process to achieve a desirable emergent effect. A well-studied problem is that of influence maximization, which calls to find a seed set of agents initiating a peer-to-peer influence dissemination that maximizes the expected spread thereof; the problem arises in various diffusion models, such as Independent Cascade and Linear Threshold [Kempe et al., 2003; Domingos and Richardson, 2001; Mossel and Roch, 2007; Li et al., 2011; Logins et al., 2020], the Voter model [EvenDar and Shapira, 2007; Durocher et al., 2022], content-aware models [Ivanov et al., 2017], models of multifaceted influence [Li et al., 2019], and geodemographic models of agent mobility [Zhang et al., 2020].

Diffusion processes also play a key role in evolutionary dynamics, which model the rules underpinning the sweep of novel genetic mutations in populations and the emergence of new phenotypes in ecological environments [Nowak, 2006]. A classic evolutionary process is the Moran process [Moran, 1958]. In high level, a set of mutants, each with fitness m ∈ (0,∞), invade a preexisting population of residents, each with fitness normalized to 1. Over time, each agent reproduces with rate proportional to its fitness, while the produced offspring replaces a random neighbor. In the long run, the new mutation either fixates in the population (i.e., all agents become mutants) or goes extinct (i.e., all agents remain residents). The probability of fixation is the main quantity of interest, especially under advantageous mutations (m > 1).

Network structure affects the fixation probability [Lieberman et al., 2005; Allen et al., 2017], and may both amplify it [Adlam et al., 2015] and suppress it [Giakkoupis, 2016; Mertzios and Spirakis, 2018], while certain structures nearly guarantee mutant fixation [Giakkoupis, 2016; Goldberg et al., 2019; Pavlogiannis et al., 2018; Tkadlec et al., 2021]. The Moran process thus provides a simple stochastic model by which a community of communicating agents reaches consensus; one option has an advantage over another, yet its prevalence (i.e., fixation) depends on the positioning of its initial adherents (i.e., mutants) and on the network structure.

Recent work aims to make the Moran process more realistic by incorporating some form of environmental heterogeneity [Maciejewski and Puleo, 2014; Brendborg et al., 2022; Melissourgos et al., 2022; Svoboda et al., 2023]. Here, the fitness of an agent is not only a function of its type (resident/mutant), but also of its location in space, i.e., the node that it occupies. For example, in a biological setting, the ability to metabolise a certain sugar boosts growth more in environments where such sugar is abundant. Similarly, in a social setting, the spread a trait is more, or less viral depending on the local context (e.g., ads, societal predispositions). Analogous extensions have been recently considered for the Voter evolutionary model [Anagnostopoulos et al., 2020; Becchetti et al., 2023; Petsinis et al., 2023].

Figure 1: Moran processes (with and without environmental heterogeneity) and the complexity of seed selection.

![Image](https://ijcai.org/proceedings/2024/fulltext/254/image_000000_948deb31da1e617ac2043f44d756d88218b519f6d847d8f17784a792d546c2e1.png)

In this work we generalize the classic Moran process to account for complete environmental heterogeneity, obtaining the Heterogeneous Moran process: for every network node u, a mutant (resp., resident) occupying u exhibits fitness m(u) (resp., r(u)) specific to that node. We then study the natural optimization problem of seed selection: given a budget k, which k nodes should initiate the mutant invasion so as to maximize the fixation probability? Although the seed selection problem has been studied extensively in other diffusion models, this is the first paper to consider it in Moran models. We obtain upper and lower bounds for the complexity of this problem in our Heterogeneous model, which also imply analogous results to other relevant Moran models.

Contributions. Our main theoretical results are as follows (see Fig. 1 for a summary in the context of Moran models).

- (1) We prove that computing the fixation probability admits a FPRAS on undirected and unweighted networks that are mutant-biased, where m(u) ≥ r(u) for every node u.
- (2) We show that the optimization problem is strongly inapproximable: for any 0 < ε < 1/2, it is NP-hard to distinguish between maximum fixation probability ≤ ε and > 1 - ε.
- (3) We then focus on mutant-biased networks. We show that the optimization problem remains NP-hard to solve exactly, but the fixation probability becomes submodular, yielding a greedy (1 - 1/e)-approximation.

Further, through experimentation with real-world data, we establish that the greedy algorithm outperforms standard heuristics for seed selection and uncovers high-quality seed sets with diverse data sets and problem parameters. Due to space constraints, we relegate some proofs to the paper's full version [Petsinis et al., 2024].

Technical Challenges. Seed selection was studied recently under the Voter model, which bares some resemblance to the Moran model [Durocher et al., 2022]. However, the two models are distinct, and results in one do not transfer to the other. Some novel technical challenges we address are as follows.

- (1) Our NP-hardness and inapproximability proofs are fundamentally different from the NP-hardness of [Durocher et al., 2022], and are not limited to weak selection (mutant advantage ϵ → 0).
- (2) Our submodularity proof is based on introducing a novel variant of the Moran process that we call the Loopy process. This also allows us to show that the Heterogeneous Moran process is a special case of the Two-Graph Moran process [Melissourgos et al., 2022], thereby extending our hardness results to the latter.
- (3) Our model accounts for environmental heterogeneity, while the Voter model in [Durocher et al., 2022] does not. This complicates our proof for FPRAS.

## 2 Preliminaries

In this section we introduce the Heterogeneous Moran process and the problem of seed selection.

Population structure. We consider a population of agents structured as a weighted directed graph G = (V,E,w), where each node u ∈ V stands for a single agent, each edge (u, v) ∈ E signifies that u influences v, and w(u, ·) is a probability distribution expressing the frequency at which u influences v. G is strongly connected, i.e., any two nodes are connected by a sequence of edges of non-zero weight. We call G undirected if E is symmetric and w(u, ·) is uniform.

Fitness graphs. Trait diffusion in the Heterogeneous Moran process occurs by associating each node with a type: at each moment in time, each node u is either resident or mutant. Moreover, u is associated with a type-dependent fitness that represents the rate at which u influences its neighbors while being resident or mutant. We denote the respective fitness values by r(u) and m(u), as functions r,m: V → (0,∞). We call the triplet G = (G, (m, r)) a fitness graph, and denote the minimum and maximum resident and mutant fitnesses in G as rmin = minu∈V r(u), and mmax = maxu∈V m(u). We call G mutant-biased if for all u ∈ V , we have m(u) ≥ r(u).

The Heterogeneous Moran process. A configuration is a subset of nodes X ⊆ V , representing the mutant nodes in G at some time point. The fitness of node u in X is defined as

<!-- formula-not-decoded -->

i.e., it is m(u) if u is mutant and r(u) if u is a resident. At time t = 0 a seed set S ⊆ V specifies the nodes where mutant invasion begins. The Heterogeneous Moran process is a discrete-time stochastic process X0,X1, . . . , of stochastic configurations Xt ⊆ V , where X0 = S and for each t &gt; 0, Xt+1 is obtained from Xt by two successive random steps:

- (1) Birth Event: Pick a node u for reproduction with probability proportional to its fitness, fX (u) ∑v∈V fX(v) .

Figure 2: Two steps in the Heterogeneous Moran process; mutants/residents are marked in red/blue; the numbers indicate typedependent mutant/resident fitness (top/bottom).

![Image](https://ijcai.org/proceedings/2024/fulltext/254/image_000001_03c878c40334759cbcd488222fc8dd7f4d2885ece045c839ee06cba61482411c.png)

(2) Death Event: Pick a neighbor v of u with probability w(u, v) and make v have the same type as u.

Note that the mutant set can both grow and shrink over time. Fig. 2 illustrates the process on a small example.

Relation to other Moran processes. We recover the Standard Moran process [Moran, 1958] as a special case of the Heterogeneous process with r(u) = 1 and m(u) constant for all u ∈ V . The Neutral Moran process is a further special case of the Standard process, in which residents and mutants have equal fitness. The Positional Moran process [Brendborg et al., 2022] parametrizes the Standard process with an active set of nodes A, which define the node fitness as fX(u) = 1+δ if u ∈ X ∩ A and fX(u) = 1 otherwise. This is also a special case of the Heterogeneous process, with r(u) = 1 and m(u) = 1 + δ if u ∈ A and m(u) = 1 otherwise. The Two-Graphs Moran process [Melissourgos et al., 2022] lets mutants and residents propagate via different, type-specific graphs GM and GR, respectively, over the same set of nodes but with different edge sets. The Two-Graphs process generalizes the Heterogeneous process, a connection formally implied by an intermediate result we derive in Section 5.

Fixation probability. In the long run, mutants either fixate with Xt = V or go extinct with Xt = ∅. The fixation probability fpG(S) is the probability that mutants fixate on a fitness graph G = (G, (m, r)) with seed set S. The complexity of computing fpG(S) is an open question, even for the Standard Moran process, in contrast to cascade spread models, for which the spread function is efficiently approximable [Svitkina and Fleischer, 2011]; as we prove in the next section, on mutant-biased, undirected fitness graphs, fpG(S) is approximable efficiently via Monte Carlo simulations.

The seed-selection problem. The standard optimization question in invasion processes is optimal seed placement: given a budget k, which k nodes S∗ should initiate the mutant invasion so as to maximize the fixation probability?

<!-- formula-not-decoded -->

The optimal seed depends on the graph structure, budget k, and node fitnesses. Fig. 3 showcases this intricate relationship, even with all residents having fitness 1. The optimal seed S∗ may comprise (i) only nodes of the largest mutant fitness (k = 3, left), (ii) nodes of both large and small mutant fitness (k = 3, middle), or (iii) only nodes of the smallest mutant fitness (k = 3, right). Moreover, increasing k may yield an optimal seed set that is not a superset of, or even disjoint to, the previous one; (left, k = 1 vs k = 3).

Figure 3: Optimal seed set S∗ (in red) while varying the mutant fitness and seed size k; all residents have fitness 1.

![Image](https://ijcai.org/proceedings/2024/fulltext/254/image_000002_51673df1da523fbd0696d09033082e678058908853ad591bfb3e0224ce86f83c.png)

## 3 Computing the Fixation Probability

In the neutral setting (m(u) = r(u), ∀u), the fixation probability is linear, fpG(S) = ∑u∈S fpG({u}). When the graph is also undirected, fpG(S) = ∑u∈S 1/d(u) ∑v∈V 1/d(v) , where d(x) is the degree of x [Broom et al., 2010]. No closed-form solution is known for the non-neutral setting. Yet on undirected graphs the expected time until convergence is polynomial, yielding a fully polynomial-time randomized approximation scheme (FPRAS) via Monte Carlo simulations [D´ıaz et al., 2014; Brendborg et al., 2022]. The next lemma generalizes this result to the Heterogeneous process on mutant-biased graphs, in sharp contrast to non-biased graphs, on which the expected time is exponential in general [Svoboda et al., 2023].

Lemma 1. Given an undirected and mutant-biased fitness graph G and a seed set S ⊆ V , the expected time to convergence T(G, S) satisfies T(G, S) ≤ (n2 · mmax rmin )3 .

Proof. For a configuration X, we define the potential function Φ(X) = ∑u∈X m(u) d(u) , where d(u) ≥ 1 is the degree of u. Note that Φ(X) ≤ n · mmax. We let ∆t = Φ(Xt+1) - Φ(Xt) be the potential difference in step t. In addition, let Xt = X, and R = {(u, v) ∈ E: u ∈ X and v ̸∈ X} be the set of edges in X with one endpoint being mutant and the other being resident. Moreover, denote F = ∑u∈V fX(u) as the total population fitness in X. Given a pair (u, v) ∈ R, let pu→v be the probability that u reproduces and replaces v. First we show that E(∆t) ≥ 0, i.e., in expectation, the potential function increases in each step:

<!-- formula-not-decoded -->

as m(v) ≥ r(v) ≥ rmin since G is mutant-biased. Second, we give a lower bound on the variance of ∆t when ∅ ⊂ X ⊂ V , and thus there exists an edge (u, v) ∈ R. First, we have

<!-- formula-not-decoded -->

n · mmax n2 · mmax while the potential function changes by ∆t ≤ - m(u) d(u) . Therefore, P [∆t ≤ -m(u)/d(u)] ≥ rmin n2 ·mmax , and

<!-- formula-not-decoded -->

The potential Φ gives rise to a submartingale with upper bound B = n · mmax. The re-scaled function Φ(Φ - 2B) + B2 satisfies the conditions of the upper additive drift theorem [K¨otzing and Krejca, 2019] with initial value at most B2 and step-wise drift at least Var(∆t). We thus arrive at

<!-- formula-not-decoded -->

Lemma 1 yields an FPRAS for the fixation probability when mutant and resident fitnesses are polynomially (in n) related.

Corollary 1. Given a mutant-biased undirected fitness graph G with mmax/rmin = nO(1) and a seed set S ⊆ V , the fixation probability fpG(S) admits an FPRAS.

## 4 Hardness of Optimization

Here we turn our attention to the seed selection problem, and prove two hardness results. First, we show that on arbitrary graphs, for any 0 &lt; ε &lt; 1/2, it is NP-hard to distinguish between graphs that achieve maximum fixation probability at most ε and at least 1 - ε. This is in sharp contrast to standard cascade models of influence spread, for which the optimal spread can be efficiently approximated [Kempe et al., 2003]. Then we focus on mutant-biased graphs, and show that achieving the maximum fixation probability remains NP-hard even in this restricted setting.

Our reduction is from the NP-hard problem Set Cover [Karp, 1972]. Given an instance (U, S, k), where U is a universe, S a set of subsets of U, and k a size constraint, the task is to decide whether there exist k subsets in S that cover U. Wlog, U = ⋃A∈S A. We construct a fitness graph G = (G, (m, r)) where G = (V, E, w) is a bipartite graph with two parts V = V1∪V2 with V1 = S and V2 = U, and define the edge relation as E = {(u, v) ∈ V1×V2 : v ∈ u}∪(V2×V1) i.e., there is an edge (u, v) for each element v of U that appears in the set u of S, as well as all possible edges from V2 to V1. The weight function is uniform: w(u, v) = 1/d(u) for each (u, v) ∈ E. The resident fitness is r(u) = 1 for all u ∈ V . The mutant fitness is parametric on two values x ≥ 1 and y ≤ 1 to be fixed later, with m(u) = x if u ∈ V1 and m(u) = y if u ∈ V2. See Fig. 4 for an illustration.

Our construction guarantees upper and lower bounds on the fixation probability depending on whether the seed set forms a set cover of (U, S), as stated in the following lemma.

Figure 4: (Left): Graph G for a Set Cover instance with U = {1, 2, 3, 4, 5} and S = {{1, 4}, {1, 2, 4}, {3, 5}}. (Right): For k = 2, the optimal seed set forms a Set Cover.

![Image](https://ijcai.org/proceedings/2024/fulltext/254/image_000003_0b32f818afd62614b2314a4663cdb819bdc540c932e1f820d9fb04cd1724b224.png)

Lemma 2. The following assertions hold.

<!-- formula-not-decoded -->

<!-- formula-not-decoded -->

Before we prove Lemma 2, we show how Lemma 2 leads to the two hardness results of this section.

Theorem 1. For any 0 &lt; ε &lt; 1/2, it is NP-hard to distinguish between instances with maxS fpG(S) ≤ ε and those with maxS fpG(S) &gt; 1 - ε.

Proof sketch. We solve the inequalities of Lemma 2, and obtain that there exist y = 1/O(n3 ) and x = O(n10 ) satisfying them. As both values are polynomial in n, this completes a polynomial reduction from Set Cover to seed selection.

Theorem2. For mutant-biased fitness graphs, it isNP-hard to distinguish between instances with maxS fpG(S) ≤ 1 - 1/(n2n ) and those with maxS fpG(S) &gt; 1 - 1/(n2n ).

Proof sketch. We set y = 1 and solve the second inequality of Lemma 2. We obtain that it is satisfied by some x = 2O(n logn) . The fitness graph is mutant-biased as r(u) = 1 and m(u) ≥ 1 for all nodes u. The description of x is polynomially long in n, thus we have a polynomial reduction from Set Cover to seed selection on mutant-biased graphs.

We remark that the class of graphs behind Theorem 2 form a special case of the Positional Moran process [Brendborg et al., 2022], by setting as active nodes A = V1 and fitness advantage δ = 2O(n logn) . Thus, the NP-hardness of Theorem 2 extends to the Positional Moran process.

We now turn our attention to the proof of Lemma 2. By a small abuse of terminology, we say that a configuration X covers V2 to denote that the sets in X ∩V1 cover V2. Item (1) relies on the following intermediate lemma, which intuitively states that, starting from a configuration X1 that contains a resident node v ∈ V2 not covered by X, the process loses all mutants in V1 with large enough probability.

Lemma 3. From any configuration X1 with V2 \ (X1 ∪{u ∈ X1 : (u, v) ∈ E}) ̸= ∅, the process reaches a configuration X2 withX2∩V1 = ∅ with probability p ≥ ( 1/n 1/n+(n-1)y )|V1| .

We can now prove the upper bound of Lemma 2.

Proof sketch of Lemma 2, Item 1. First, we show that the probability q of reaching configuration X1 such that V2 \ (X1 ∪ {u ∈ X1 : (u, v) ∈ E}) ̸= ∅ is at least 1/n 1/n+(n-1)y . Then, by using Lemma 3 on X1 we derive that the process reaches a configuration X2 with X2 ∩ V1 = ∅ with probability at least ( 1/n 1/n+(n-1)y )|V1| = q|V1| . While at configuration X2, the process changes configuration when either a resident in V1 replaces a mutant in V2, or vice versa. Recall that the probability that the first event occurs before the second is at least q. Repeating the process for all mutants in V2 \{v} (as v is already a resident in X2) we arrive in a configuration without mutants in V2 with probability at least q|V2|-1 . At this point all mutants have gone extinct, thus:

<!-- formula-not-decoded -->

The following lemma states that, starting from a configuration X that covers V2, the process makes all nodes in V2 mutants without losing any mutant in V1, with certain probability.

Lemma 4. From any configuration X that covers V2, the process reaches a configuration X∗ with V2 ∪ (X ∩ V1) ⊆ X∗ with probability p∗ ≥ ( x/n x/n+n )|V2| .

We can now prove the lower bound of Lemma 2.

Proof sketch of Lemma 2, Item 2. We consider 4 configurations; any configuration X that covers V2; X- with less mutants in V1 than X; X∗ with same mutants in V1 with X and all nodes in V2 being mutants; and X+ starting from X∗ includes at least one more mutant in V1. The Markov chain in Fig. 5 captures this process where states S1, S2, S3 and S4 denote that the process is in configurations X-, X, X∗ and X+, respectively. To prove the Lemma, we first bound the transition probabilities of Markov chain in Fig. 5. We prove that

<!-- formula-not-decoded -->

Note that p+ is lower-bounded by the probability that a random walk starting in S2 (i.e., X) gets absorbed in S4 (i.e., X+). Let xi be the probability that a random walk starting in Si gets absorbed in S4. We have x2 = p∗ ·x3+(1-p∗ ) ·x1 and x3 = q·x4+(1-q)·x2, with boundary conditions x1 = 0 and x4 = 1, whence x2 = q·p∗ 1-(1-q)·p∗ . Since X ⊂X+, the set X+ also covers V2, thus the reasoning repeats for up to n steps until fixation, resulting in fpG(X) ≥ (p+)n .

Figure 5: The Markov chain for the process of Lemma 4.

![Image](https://ijcai.org/proceedings/2024/fulltext/254/image_000004_830ba1b05ac845dd663689bfc11a7c154d8fa9238c67d272994e2a5a074da459.png)

## 5 Monotonicity and Submodularity

Theorem 1 rules out polynomial-time algorithms for any nontrivial answer to seed selection. Theorem 2 states that the problem remains NP-hard for mutant-biased graphs, but it permits potential tractable approximations. Indeed, here we prove that mutant bias renders the fixation probability submodular, thus seed selection admits a constant-factor approximation. Our proofs are based on coupling arguments. Instead of applying these arguments directly to the Heterogeneous Moran process, we propose a variant, the Loopy process, and show its equivalence to the Heterogeneous process in the sense of preserving the fixation probability.

The Loopy process. In the Loopy process, we slightly modify the underlying fitness graph G = (G, (m, r)) in each step based on the current configuration X. Without loss of generality, we let every node u ∈ V have a self-loop (u, u) ∈ E, by assigning w(u, u) = 0. Let fmax = maxu∈V {r(u),m(u)} be the maximum fitness. When the original process is at some configuration X, different nodes reproduce at different rates. When the Loopy process is at configuration X, we construct a fitness graph GX = (GX, (1, 1)), where 1 is the constant function u ↦→ 1, and GX = (V,E,wX) is a graph of the same structure as G, but with a weight function modified by adjusting the self-loop probability of each node as follows.

<!-- formula-not-decoded -->

where fX(·) denotes the fitness of nodes in the original process. Fig. 6 shows an instance of the Heterogeneous Moran process and its Loopy counterpart. All nodes in GX reproduce at equal rates as they have the same fitness regardless of type. The new weight function wX compensates for this reproduction rate uniformity: nodes that formerly had lower fitness acquire stronger self-loops, hence the probability distribution P[Xt+1|Xt+1 ̸= Xt], and thus the fixation probability, is identical in the two processes, as Lemma 5 states.

Figure 6: A fitness graph G (left) and its corresponding graph GX of the Loopy process (right). All nodes in GX have the same fitness.

![Image](https://ijcai.org/proceedings/2024/fulltext/254/image_000005_a774f2809e5c9266f58c817197199a306cad52f742af172683212c1cc38ea301.png)

Lemma 5. For any seed set, the Heterogeneous and Loopy Moran processes share the same fixation probability.

Relation to the Two-Graphs process. The Loopy process is a special case of the recent Two-Graphs Moran process [Melissourgos et al., 2022]. To obtain the Two-Graphs process, we define two graphs GM and GR for mutants and residents, respectively. For each edge (u, v), its weight wM(u, v) in GM and wR(u, v) in GR, is obtained from Eq. (2), considering that u ∈ X and u ̸∈ X, respectively. In turn, Lemma 5 implies that the hardness of Theorems 1 and 2 also hold for seed selection in the Two-Graphs model.

Monotonicity. The following monotonicity corollary follows from Lemma 5 and the monotonicity of the Two Graphs process [Melissourgos et al., 2022, Corollary 6].

Corollary 2. For any fitness graph G = (G, (m, r)) and any two seed sets S ⊆ S′ , we have fpG(S) ≤ fpG(S′ ).

Submodularity. We now turn our attention to the submodularity of the fixation probability in the Heterogeneous Moran process. Although the function is not submodular in general, we prove that it becomes submodular on mutant-biased fitness graphs. In particular, we show that for any two seed sets S, T ⊆ V , the following submodularity condition holds:

<!-- formula-not-decoded -->

Our proof is via a four-way coupling of the corresponding processes starting in one of the seed sets of Eq. (3).

Lemma 6. For any mutant-biased fitness graph G = (G, (m, r)), the fixation probability fpG(S) is submodular.

Proof. Let M1 = (X 1 t )t≥0, M2 = (X 2 t )t≥0, M3 = (X 3 t )t≥0, andM4 = (X 4 t )t≥0, be four Loopy processes with seed sets S, T, S ∪ T and S ∩ T, respectively. To prove submodularity, we employ two tricks forM3. First, along its configurations X 3 t , we also keep track of the set of mutants Yt (resp., Zt) that are copies of some initial node in S (resp., T ). Whenever a node v receives the mutant trait from a neighbor u, we place v in Yt+1 (resp., Zt+1) following the membership of u in Yt (resp., Zt). Initially, Y0 = S and Z0 = T . Second, with probability 1, every run of M3 that results in fixation, eventually (i.e., if we let the process run on) leads to the fixation of S or T (possibly both, assuming S ∩ T ̸= ∅); that is, every node is a copy of some node in S or T . We thus compute the fixation probability with seed S ∪T by summing over runs in which S or T fixates.

To prove submodularity, we consider this refined view of the process and establish a four-way coupling between M1, M2, M3 and M4 that guarantees the following invariants: (i) X 1 t ∪ X 2 t ⊆ X 3 t , (ii) X 4 t ⊆ X 1 t ∩ X 2 t , (iii) Yt ⊆ X 1 t , and (iv) Zt ⊆ X 2 t . Now, consider any execution in which M3 fixates. Since S or T eventually fixates in M3, due to invariants (iii) and (iv), at least one ofM1,M2 fixates as well. Moreover, if M4 also fixates, due to invariant (ii), bothM1 andM2 fixate. Thus the invariants guarantee submodularity.

The invariants hold at t = 0. Now, consider some arbitrary time t with the four processes at configurations X j t = Xj , for j ∈ {1, 2, 3, 4}, Yt = Y , and Zt = Z. To obtain X j t+1 , we sample the same node u for reproduction with probability 1/n in all processes. From invariants (i) and (ii), and since m(u) ≥ r(u), we derive that wX3 (u, u) ≤ wXj (u, u) ≤ wX4 (u, u) for j ∈ {1, 2}, as residents have a larger self-loop weight. In M3, we choose a neighbor v of u with probability wX3 (u, v) and propagate the trait of u to v. In M1, M2 and M4, if u = v, we perform the same update; otherwise, if u has the same type as in M3, we also perform the same update. From the invariants, if u is resident inM3 then the same holds in all other processes, while if u is a mutant in M3 then the same holds in at least one of M1, M2 (depending on whether u ∈ Y and u ∈ Z), and if that holds for M1 and M2, then it holds for M4. However, if u is resident in Mj for some j ∈ {1, 2} but mutant in M3, i.e., u ∈ X3 \Xj , then, due to invariant (ii), u is also resident inM4, i.e., u ∈ X3 \X4 ; then, inMj andM4, u propagates to itself with probability wXj (u, u)-wX3 (u, u) ≥ 0, and to v with the remaining probability 1 - (wXj (u, u) - wX3 (u, u)). It follows that all three invariants are maintained.

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

Theorem 3. Given a mutant-biased fitness graph G and budget k, let S∗ be an optimal seed set and Sgr the solution of the Greedy algorithm. We have fpG(Sgr) ≥ (1 - 1/e) fpG(S∗ ).

The Greedy algorithm builds the seed set iteratively by choosing the node that yields the maximum fixation probability gain. Finally, note that due to symmetry, on resident-biased fitness graphs (m(u) ≤ r(u) for all u), fpG(S) is supermodular, thus Greedy offers no approximation guarantees.

## 6 Experimental Analysis

Here, we present our experimental evaluation of the Greedy algorithm and other network heuristics, varying the seed size k and the maximum mutant fitness mmax.

Table 1: Dataset characteristics.

| Name       |   &#124;V &#124; |   &#124;E&#124; | Directed   | Edge-Weighted   |
|------------|------------------|-----------------|------------|-----------------|
| Facebook   |              324 |            5028 | ✗          | ✗               |
| Colocation |              242 |           53188 | ✗          | ✓               |
| Mammalia   |              327 |            1045 | ✓          | ✓               |
| Polblogs   |              793 |           15839 | ✓          | ✗               |

Datasets. We use four real-world networks from Netzschleuder, SNAP and Network Repository (Table 1).

- (1) Facebook: A Facebook ego network in which nodes represent profiles and edges indicate friendship.
- (2) Colocation: A proximity network of students and teachers of a French school. Edge weights count the frequency of contact between individuals during a two-day period.
- (3) Mammalia: An animal-contact network based on movements of voles (Microtus agrestis). Each edge weight counts the common traps the two voles were caught in.
- (4) Polblogs: A network of hyperlinks among a large set of U.S. political weblogs from before the 2004 election.

Figure 8: Fixation probability vs. mmax.

![Image](https://ijcai.org/proceedings/2024/fulltext/254/image_000006_9cd57f7744c9260ea2112ccfc50037cb328fa3478479101726b92bf3ac48baf4.png)

Our experiments are not meant to be exhaustive, but rather indicative of the performance of the greedy algorithm and common network-optimization heuristics on a few diverse networks. We set the resident fitness to 1, while the mutant fitness of each node u is determined by sampling a uniform distribution m(u) ∼ U(1,mmax). This results in mutantbiased graphs, for which Theorem 3 guarantees that the fixation probability admits a Monte Carlo approximation.

Greedy and Baselines. We evaluate the performance of the standard Greedy algorithm behind Theorem 3 [Nemhauser et al., 1978] against four common baseline algorithms from related literature on seed selection under diffusion processes [Brendborg et al., 2022; Zhao et al., 2021; Liu et al., 2017].

- (1) Random: select uniformly at random.
- (2) Degree: select by smallest degree.
- (3) Closeness: select by smallest closeness centrality.
- (4) PageRank: select by smallest PageRank score.

The Random selection strategy is a standard baseline to measure the intricacy of the problem. Degree is the only existing algorithm for seed selection in the Moran model, and is optimal for undirected and unweighted networks under the neutral setting (but underperforms when mmax &gt; 1). On the other hand, Closeness and PageRank take into account the structure of the graph and its connectivity. For these two centrality heuristics we also tried selecting the top-k-nodes by largest value, which resulted in worse performance. All Monte Carlo simulations were run over 5000 iterations.

Performance vs. k. Fig. 7 shows performance as the size constraint k increases for a fixed mutant fitness distribution. In agreement with Corollary 2 and Lemma 6, the performance of all algorithms rises as k grows, while Greedy has diminishing returns. Notably, Greedy outperforms all heuristics especially for small size constraints, while Pagerank forms high quality solutions for the undirected and unweighted graph Facebook. On the other hand, seed selection becomes more challenging for directed (Mammalia, Polblogs) and edge-weighted graphs (Colocation, Mammalia), in which only Greedy uncovers high-quality seed sets.

Performance vs. m. Fig. 8 shows performance as the mutant fitness interval [1,mmax] increases, for fixed size k. Random selection performs poorly, showing that the problem is not trivial, while the other two heuristics have mixed performance. On the other hand, Greedy achieves a steady, highquality performance in all datasets and problem parameters.

## 7 Conclusion

We studied a natural optimization problem pertaining to network diffusion by the Heterogeneous Moran process, namely selecting a set of seed nodes that maximize the effect of the invasion. To our knowledge, this is the first paper to study this standard optimization problem on Moran models. We showed that the problem is strongly inapproximable in general, but becomes approximable on mutant-biased graphs, although the exact solution remains NP-hard. Several interesting questions remain open for future work, such as, is seed selection hard in the Standard model; and are there tighter approximations for mutant-biased graphs?

## Acknowledgments

Work supported by grants from DFF (P.P. and P.K., 904100382B), Villum Fonden (A.P., VIL42117), and Charles University (J.T., UNCE 24/SCI/008 and PRIMUS 24/SCI/012).

## References

1. [Adlam et al., 2015] Ben Adlam, Krishnendu Chatterjee, and Martin A Nowak. Amplifiers of selection. Proceed- ings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 471(2181):20150114, 2015.
2. [Allen et al., 2017] Benjamin Allen, Gabor Lippner, Yu- Ting Chen, Babak Fotouhi, Naghmeh Momeni, Shing- Tung Yau, and Martin A Nowak. Evolutionary dynamics on any population structure. Nature, 544(7649):227-230, 2017.
3. [Anagnostopoulos et al., 2020] Aris Anagnostopoulos, Luca Becchetti, Emilio Cruciani, Francesco Pasquale, and Sara Rizzo. Biased opinion dynamics: When the devil is in the details. In Proceedings of the 29th International Joint Conference on Artificial Intelligence, IJCAI, pages 53-59, 2020.
4. [Becchetti et al., 2023] Luca Becchetti, Vincenzo Bonifaci, Emilio Cruciani, and Francesco Pasquale. On a Voter model with context-dependent opinion adoption. In Pro- ceedings of the 32nd International Joint Conference on Ar- tificial Intelligence, IJCAI, pages 38-45, 2023.
5. [Brendborg et al., 2022] Joachim Brendborg, Panagiotis Karras, Andreas Pavlogiannis, Asger Ullersted Ras- mussen, and Josef Tkadlec. Fixation maximization in the positional Moran process. In Proceedings of the 36th AAAI Conference on Artificial Intelligence, pages 9304-9312, 2022.
6. [Broom et al., 2010] M Broom, C Hadjichrysanthou, J Rychtář, and BT Stadler. Two results on evolutionary processes on general non-directed graphs. Proc. Royal Soc. A, 466(2121), 2010.
7. [Díaz et al., 2014] Josep Díaz, Leslie Ann Goldberg, George B Mertzios, David Richerby, Maria Serna, and Paul G Spirakis. Approximating fixation probabili- ties in the generalized Moran process. Algorithmica, 69(1):78-91, 2014.
8. [Domingos and Richardson, 2001] Pedro Domingos and Matt Richardson. Mining the network value of customers. In Proceedings of the 7th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 57-66, 2001.
9. [Durocher et al., 2022] Loke Durocher, Panagiotis Karras, Andreas Pavlogiannis, and Josef Tkadlec. Invasion dy- namics in the biased Voter process. In Proceedings of the 31st International Joint Conference on Artificial Intelli- gence, IJCAI, pages 265-271, 2022.
10. [Even-Dar and Shapira, 2007] Eyal Even-Dar and Asaf Shapira. A note on maximizing the spread of influence in social networks. In International Workshop on Web and Internet Economics, pages 281-286. Springer, 2007.
11. [Giakkoupis, 2016] George Giakkoupis. Amplifiers and sup- pressors of selection for the Moran process on undirected graphs. arXiv:1611.01585, 2016.
12. [Goldberg et al., 2019] Leslie Ann Goldberg, John Lapin- skas, Johannes Lengler, Florian Meier, Konstantinos Pana- giotou, and Pascal Pfister. Asymptotically optimal ampli- fiers for the Moran process. Theoretical Computer Sci- ence, 758:73-93, 2019.
13. [Ivanov et al., 2017] Sergei Ivanov, Konstantinos Theocharidis, Manolis Terrovitis, and Panagiotis Karras. Content recommendation for viral social influence. In Proceedings of the 40th International ACM SIGIR Con- ference on Research and Development in Information Retrieval, pages 565-574, 2017.
14. [Karp, 1972] Richard M Karp. Reducibility among combi- natorial problems. In Complexity of Computer Computa- tions, pages 85-103. Springer, 1972.
15. [Kempe et al., 2003] David Kempe, Jon Kleinberg, and Éva Tardos. Maximizing the spread of influence through a so- cial network. In Proceedings of the 9th ACM SIGKDD In- ternational Conference on Knowledge Discovery and Data Mining, pages 137-146, 2003.
16. [Kötzing and Krejca, 2019] Timo Kötzing and Martin S Kre- jca. First-hitting times under drift. Theoretical Computer Science, 796:51-69, 2019.
17. [Li et al., 2011] Yongkun Li, Bridge Qiao Zhao, and John CS Lui. On modeling product advertisement in large- scale online social networks. IEEE/ACM Transactions on Networking, 20(5):1412-1425, 2011.
18. [Li et al., 2019] Yuchen Li, Ju Fan, George V. Ovchinnikov, and Panagiotis Karras. Maximizing multifaceted network influence. In 35th IEEE International Conference on Data Engineering, ICDE, pages 446-457, 2019.
19. [Lieberman et al., 2005] Erez Lieberman, Christoph Hauert, and Martin A Nowak. Evolutionary dynamics on graphs. Nature, 433(7023):312-316, 2005.
20. [Liu et al., 2017] Qi Liu, Biao Xiang, Nicholas Jing Yuan, Enhong Chen, Hui Xiong, Yi Zheng, and Yu Yang. An in- fluence propagation view of pagerank. ACM Transactions on Knowledge Discovery from Data (TKDD), 11(3):1-30, 2017.
21. [Logins et al., 2020] Alvis Logins, Yuchen Li, and Panagio- tis Karras. On the robustness of cascade diffusion under node attacks. In The Web Conference, pages 2711-2717, 2020.
22. [Maciejewski and Puleo, 2014] Wes Maciejewski and Gre- gory J. Puleo. Environmental evolutionary graph theory. Journal of Theoretical Biology, 360:117-128, 2014.
23. [Melissourgos et al., 2022] Themistoklis Melissourgos, Sotiris E Nikoletseas, Christoforos L Raptopoulos, and Paul G Spirakis. An extension of the Moran process using type-specific connection graphs. Journal of Computer and System Sciences, 124:77-96, 2022.
24. [Mertzios and Spirakis, 2018] George B. Mertzios and Paul G. Spirakis. Strong bounds for evolution in net- works. Journal of Computer and System Sciences, 97:60-82, 2018.
25. [Moran, 1958] Patrick Alfred Pierce Moran. Random pro- cesses in genetics. In Mathematical proceedings of the Cambridge philosophical society, volume 54, pages 60- 71. Cambridge University Press, 1958.
26. [Mossel and Roch, 2007] Elchanan Mossel and Sebastien Roch. On the submodularity of influence in social net- works. In Proceedings of the 39th annual ACM Symposium on Theory Of Computing, STOC, pages 128-134, 2007.
27. [Nemhauser et al., 1978] George L. Nemhauser, Lau- rence A. Wolsey, and Marshall L. Fisher. An analysis of approximations for maximizing submodular set functions -I. Math. Program., 14(1):265-294, 1978.
28. [Nowak, 2006] Martin A Nowak. Evolutionary dynamics: exploring the equations of life. Belknap Press of Harvard University Press, Cambridge, Massachusetts, 2006.
29. [Pavlogiannis et al., 2018] Andreas Pavlogiannis, Josef Tkadlec, Krishnendu Chatterjee, and Martin A Nowak. Construction of arbitrarily strong amplifiers of natural se- lection using evolutionary graph theory. Communications Biology, 1(1):1-8, 2018.
30. [Petsinis et al., 2023] Petros Petsinis, Andreas Pavlogiannis, and Panagiotis Karras. Maximizing the probability of fix- ation in the positional Voter model. In 37th AAAI Confer- ence on Artificial Intelligence, pages 12269-12277, 2023.
31. [Petsinis et al., 2024] Petros Petsinis, Andreas Pavlogiannis, Josef Tkadlec, and Panagiotis Karras. Seed selection in the heterogeneous Moran process. arXiv:2404.15986, 2024.
32. [Svitkina and Fleischer, 2011] Zoya Svitkina and Lisa Fleis- cher. Submodular approximation: Sampling-based algo- rithms and lower bounds. SIAM J. Comput., 40(6):1715- 1737, 2011.
33. [Svoboda et al., 2023] Jakub Svoboda, Josef Tkadlec, Kam- ran Kaveh, and Krishnendu Chatterjee. Coexistence times in the Moran process with environmental heterogeneity. Proceedings of the Royal Society A, 479(2271):20220685, 2023.
34. [Tkadlec et al., 2021] Josef Tkadlec, Andreas Pavlogiannis, Krishnendu Chatterjee, and Martin A Nowak. Fast and strong amplifiers of natural selection. Nature Communica- tions, 12(1):1-6, 2021.
35. [Zhang et al., 2020] Kaichen Zhang, Jingbo Zhou, Donglai Tao, Panagiotis Karras, Qing Li, and Hui Xiong. Geode- mographic influence maximization. In Proceedings of the 26th ACM SIGKDD International Conference on Knowl- edge Discovery & Data Mining, pages 2764-2774, 2020.
36. [Zhao et al., 2021] Jinhua Zhao, Xianjia Wang, Cuiling Gu, and Ying Qin. Structural heterogeneity and evolutionary dynamics on complex networks. Dynamic Games and Ap- plications, 11:612-629, 2021.