# Opinion Diffusion in Graphs: An Adversarial Approach

Ahad N Zehmakan

<figure><img src="image_1.png" /></figure>

► To cite this version:

Ahad N Zehmakan. Opinion Diffusion in Graphs: An Adversarial Approach. 2024. [https://hal.science/hal-04812181v1](https://hal.science/hal-04812181v1)

HAL Id: hal-04812181

[https://hal.science/hal-04812181v1](https://hal.science/hal-04812181v1)

Preprint submitted on 29 Nov 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>
# Opinion Diffusion in Graphs: An Adversarial Approach*

Ahad N. Zehmakan†

The Australian National University, Canberra, Australia

## Abstract

We introduce and study a novel majority-based opinion diffusion model. Consider a graph $G$, which represents a social network. Assume that initially a subset of nodes, called seed nodes or early adopters, are colored either black or white, which correspond to positive or negative opinion regarding a consumer product or a technological innovation. Then, in each round an uncolored node, which is adjacent to at least one colored node, chooses the most frequent color among its neighbors.

Consider a marketing campaign which advertises a product of poor quality and its ultimate goal is that more than half of the population believe in the quality of the product at the end of the opinion diffusion process. We focus on three types of attackers which can select the seed nodes in a deterministic or random fashion and manipulate almost half of them to adopt a positive opinion toward the product (that is, to choose black color). We say that an attacker succeeds if a majority of nodes are black at the end of the process. Our main purpose is to characterize classes of graphs where an attacker cannot succeed. In particular, we prove that if the maximum degree of the underlying graph is not too large or if it has strong expansion properties, then it is fairly resilient to such attacks.

Furthermore, we prove tight bounds on the stabilization time of the process (that is, the number of rounds it needs to end) in both settings of choosing the seed nodes deterministically and randomly. We also provide several hardness results for some optimization problems regarding stabilization time and choice of seed nodes.

## 1 Introduction

In real life, we typically possess distinct perspectives pertaining to a multitude of subjects, including consumer goods, technological innovations, lifestyles, and political events. Through interactions with friends, family, and colleagues, our viewpoints are susceptible to influence. The dissemination of opinions and the propagation of (mis)information possess the capability to impact diverse facets of our lives, encompassing the economy, defense, fashion, and even personal matters. As a result, a burgeoning interest has emerged cf. [1, 18] in comprehending the mechanisms by which opinions are conceived and disseminated, owing to the presence of social bonds among members within a community, as well as how the structure of a social network can influence upon this process. Such understanding would empower us to achieve more accurate predictions of electoral outcomes, exercise control over the impact of marketing

<footnote>*A preliminary version of this paper appeared in the 35th AAAI Conference on Artificial Intelligence [50].</footnote>

<footnote>†Corresponding author; Email Address: ahadn.zehmakan@anu.edu.au, Postal Address: Room 2.18, the Hanna Neumann building, the Australian National University, ACT 2601, Australia.</footnote>
and political campaigns, and, in a general sense, enhance our comprehension of the cognitive processes that underlie social influence.

The study of opinion diffusion and the evolution of social dynamics on networks has at-
tracted the attention of researchers from a vast spectrum of disciplines such as economics [11],
epidemiology [40], social psychology [46], statistical physics [23], and political sciences [9]. It
has also gained significant popularity in theoretical computer science, especially in the quickly
growing literature focusing on the interface between social choice and social networks, cf. [5, 12].

From a theoretical viewpoint, it is natural to introduce and study mathematical frameworks
which emulate diverse manifestations of opinion dynamics. Of course in the real world, they are
too complex to be explained in purely mathematical terms. Nevertheless, the fundamental notion
is to grasp their general overarching principles and make crude approximations at discovering
certain pivotal aspects of them which are otherwise totally hidden by the intricate tapestry of
the full phenomenon.

In these models, it is usually assumed that we have a graph $G$ and initially some nodes are colored, say black or white. Then, in each round a group of nodes are colored or update their color based on a predefined rule. Graph $G$ is meant to represent a social network, where each agent is modeled as a node and edges indicate relations between them, e.g., friendship, common interests, advice, or various forms of interactions. Furthermore, black and white stand for the opinion of an agent regarding an innovation or a political party, etc.

In the plethora of opinion diffusion models, threshold-based ones are certainly the best known, cf. [30, 38, 48]. There, nodes (i.e., agents) adopt a color (i.e., opinion) if it is shared by a certain number or fraction of their connections. Particularly, the majority-based models, where each node chooses the most frequent color among its neighbors, have received a substantial amount of attention, cf. [14, 22, 25, 32, 49]. This imitating behavior can be explained in several ways: an agent that sees a majority agreeing on an opinion might think that her neighbors have access to some information unknown to her and hence they have made the better choice; also agents can directly benefit from adopting the same behavior as their friends (e.g., prices going down).

Nowadays, the identification of factors leading to a successful innovation cascade in a given market is a significant practical matter. Marketing endeavors frequently harness online social networks as a means to actively sway people's opinions in their favor, for instance by targeting segments of agents with free sample of their products or misleading information. Consequently, the study of control and manipulation of collective decision-making has gained increasing popularity in mechanism design, algorithmic game theory, and computational social choice, cf. [12]. Especially, majority-based models have been postulated as one potential explanation for the success or failure of collective action and the diffusion of innovations. For example for different majority-based opinion diffusion models, a substantial amount of attention has been devoted to the study of characterizing graph structures for which the dominant color at the end of the process is the same as the dominant color in the initial coloring, cf. [4].

## 1.1 Our Contribution

We introduce a novel majority-based opinion diffusion model and consider three different types
of attackers whose goal is to engineer the output of the diffusion process. Our central problem
is to characterize classes of graphs for which an attacker fails to reach its goal.
**Our model.** Consider a graph $G$. Assume that initially a subset of nodes, which are called the seed nodes, are colored black or white and the rest of nodes are uncolored. Then, in discrete-time rounds each node, which is uncolored and is adjacent to at least one colored node, chooses the most frequent color among its colored neighbors. In case of a tie, it chooses black color with probability (w.p.) $1/2$ independently and white otherwise.<fnref n="1" /> Please note that the process is monotone in the sense that once a node is colored, it no longer updates.

The seed nodes correspond to early adopters, who are the first customers to adopt a new product or technology before the rest of the population does and usually constitute 10-20% of the population. They are often called lighthouse customers because they serve as a beacon of light for the rest of the population to follow, which will take the technology or product mainstream. The term early adopters comes from the technology adoption curve, which was popularized by the book *Diffusion of Innovations* [43].

The seed nodes and their color might be chosen randomly or deterministically. We take an adversarial perspective and focus on the following three types of attackers, where we assume that $\alpha, \epsilon \in (0, 1/2)$ are some arbitrary constants and $n$ is the number of nodes in the underlying graph.

**Definition 1.1 (strong attacker)** An $(\alpha, \epsilon)$-strong attacker selects a seed set of size $\alpha n$ and color $(1/2 + \epsilon)$ fraction of its nodes white and the rest black.

**Definition 1.2 (moderate attacker)** An $(\alpha, \epsilon)$-moderate attacker selects a seed set of size $\alpha n$ and color each seed node white, independently, w.p. $(1/2 + \epsilon)$ and black otherwise.

**Definition 1.3 (weak attacker)** An $(\alpha, \epsilon)$-weak attacker selects each node to be a seed node, independently, w.p. $\alpha$ and then color each seed node white, independently, w.p. $(1/2 + \epsilon)$ and black otherwise.

Assume that the process runs for $t$ rounds. Then, the main goal of an attacker is to maximize the ratio of the number of black nodes to white ones at the end of the $t$-th round. We say that the attacker *wins* if this ratio is at least one half. (Note that once more than half of the nodes are white in the process, we can conclude that the attacker cannot win. This is because once a node is colored, it does not update.)

To better understand the aforementioned attacker models, you might think of an attacker as a marketer which desires to advertise an innovation or a product of poor quality and it can select the set of early adopters (i.e., seed nodes) in a random or deterministic fashion. Then, it manages to convince almost half of them to adopt a positive opinion about the product (i.e., choose black color). More precisely, a strong attacker can choose $(1/2 - \epsilon)$ fraction of the seed nodes to be black and a moderate/weak attacker colors each seed node black w.p. $(1/2 - \epsilon)$. The attacker's ultimate goal is that a majority of nodes are colored black after some number of rounds, even though initially white is the dominant color.

We observe that from a practical point of view, the moderate attacker is the most relevant setup since it assumes that the marketer can select the set of seed nodes to target but it does not have control over their choice of opinion. However, the main goal of studying the other two attacker models is to capture the two ends of the spectrum of adversarial power. More precisely, a strong attacker is as powerful as an attacker could get, that is, it not only chooses

<footnote n="1">¹We believe that the results provided in the present paper actually hold for any choice of the tie-breaking rule, but we do not cover that in this paper and our proofs leverage the symmetry assumption.</footnote>
the set of seed nodes, but also determines their opinion. On the other hand, a weak adversary follows a purely random strategy. Thus, any other adversarial model falls between these two extreme cases. For example, the classes of graphs which are resilient against a strong attacker are resilient against any attacker and the graphs which are vulnerable to a weak attacker are vulnerable to any attacker. (These concept are defined more formally below.)

As an extreme example, consider a star graph $S_n$, which includes $n-1$ leaves and an internal node of degree $n-1$. An $(\alpha, \epsilon)$-strong attacker can choose the internal node and $\alpha n - 1$ of the leaves to be the seed nodes and color the internal node black. See Figure 1 for an example. Then after one round of the process, all the remaining $(1-\alpha)n$ nodes will be colored black. Thus, the attacker wins. Even for an $(\alpha, \epsilon)$-weak attacker (which essentially has no real selection power and only runs a random procedure), the internal node is selected w.p. $\alpha$ and will be colored black w.p. $(1/2 - \epsilon)$. Hence, the attacker wins w.p. $(1/2 - \epsilon)\alpha$.

<figure><img src="image_3.png" /><figcaption>Figure 1: A star graph $S_{16}$, where a (1/4, 1/4)-strong attacker selects $(1/2 + \epsilon)\alpha n = 3$ white nodes and $(1/2 - \epsilon)\alpha n = 1$ black node (the internal node). The striped nodes are the uncolored nodes.</figcaption></figure>

Our main purpose is to characterize classes of graphs which are *resilient* to such attacks (i.e., an attacker cannot win) where we assume that the attacker has full knowledge of the graph structure. We should emphasize that for a moderate or weak attacker since each seed node is white independently w.p. $(1/2 + \epsilon)$, the probability that the attacker wins is at most 1/2. However, we are interested in graph structures where the probability of winning is “extremely small”.

**Strong attacker.** An $(\alpha, \epsilon)$-strong attacker is quite powerful. However, there are graphs, such as a complete graph, where it cannot win. We prove that if the graph is regular and has strong expansion properties, then a strong attacker fails. More precisely we prove that for a regular graph $G$ if $\sigma(G) \le \epsilon\sqrt{\alpha(1-\alpha)}$, then an $(\alpha, \epsilon)$-strong attacker cannot win, where $\sigma(G)$ is the second-largest absolute eigenvalue of the normalized adjacency matrix of $G$. (Please see Section 2 for a more detailed definition of $\sigma(G)$ and its relation to expansion.) We argue that expansion and regularity are not only sufficient conditions, but also somewhat necessary for a graph to be resilient to a strong attacker.

In a nutshell, since a strong attacker has the power to choose the seed nodes and their color, for a graph to be resilient, the “influencing power” should be distributed uniformly among all
nodes. In particular, the number of edges among each two node sets must be proportional to their size and this is what basically regularity and expansion provide.

**Moderate attacker.** Roughly speaking, if there is a small set of nodes of size $s$ with significant influencing power, then a moderate attacker can select them to be in the seed set. These nodes will be colored black w.p. $(1/2 - \epsilon)^s$, which is non-negligible for small $s$, and this can result in the attacker winning. A natural way to avoid such scenarios is to bound the maximum degree of the underlying graph. We show that if the maximum degree is not “too large”, then a moderate attacker fails asymptotically almost surely. (We say an event happens asymptotically almost surely (a.a.s.) if it occurs with a probability tending to 1 while we let $n$ go to infinity.) More precisely, we prove that for a graph $G$ and an $(\alpha, \epsilon)$-moderate attacker, if $\Delta \le (Cn/\log(1/\mu))^{\frac{1}{2t}}$ for some small constant $C_{\epsilon,\alpha} > 0$, the attacker cannot win in $t$ rounds w.p. at least $1 - \mu$, where $\Delta$ denotes the maximum degree. Furthermore, we argue the tightness of this statement. Note that one can assume that the attacker knows the value of $t$ and it does not impact our statement.

**Weak attacker.** As we discussed, an $(\alpha, \epsilon)$-weak attacker wins on a star graph $S_n$ w.p. at least $(1/2 - \epsilon)\alpha$. Loosely speaking, the graphs of this type, where there is a small subset of nodes with significant influencing power and a large set of nodes with very limited power, are problematic. Our goal is basically to show that graphs which do not fall under the umbrella of this type of structure are resilient to a weak attacker. We prove that if the maximum degree in a graph $G$ is sufficiently small or if a majority of nodes have rather large degrees, then a weak attacker will fail. More accurately, we show that for a graph $G$ and an $(\alpha, \epsilon)$-weak attacker, if $\Delta \le Cn/((\log n)^{C'} \log(1/\mu))$ for some suitable constants $C_{\alpha, \epsilon}, C'_{\alpha, \epsilon} > 0$ or if half of nodes are of degree at least $C'' \log(1/\mu)$ for a sufficiently large constant $C''_{\alpha, \epsilon}$, then the attacker fails w.p. at least $1 - \mu$. Note that the bound on $\Delta$ does not depend on $t$ unlike the case of a moderate attacker. For example, the bound on $\Delta$ is in the order of $\Theta(n/ploylog(n))$ with probability $1 - 1/\text{poly}(n)$.

**Stabilization time.** For a connected graph $G$, if the seed set is non-empty, then all nodes will be colored eventually. Recall that once a node is colored, it remains unchanged. The number of rounds the process needs to color all nodes is called the *stabilization time* of the process. As we discuss in Section 5, it is straightforward to prove that the stabilization time is upper-bounded by the diameter of $G$. This is, in particular, true for the setting of a strong/moderate attacker. However, what if the seed nodes are chosen at random (for example, in case of a weak attacker)? We prove that if each node is in the seed set independently w.p. $\alpha$, then the stabilization time is a.a.s. lower-bounded by $\Omega(\log_\Delta \log n^{1/\alpha})$ and upper-bounded by $O((1/\alpha\delta) \log n)$, where $\delta$ denotes the minimum degree in $G$. Furthermore, we argue that these bounds are both tight, up to a constant factor.

**Hardness results.** We provide some hardness results for a decision problem on the stabilization time and an optimization problem on the choice of seed set and its coloring. Assume that we are given a graph $G$ and some integers $t$ and $s$. We prove that the problem of determining whether there is a seed set of size $s$ for which the process takes $t$ rounds to end is NP-complete. Furthermore, suppose we are given a graph $G$ and some integers $b, w$, and $t$ as the input and our goal is to find the minimum (expected) number of white nodes after $t$ rounds if there are
$b$ black and $w$ white nodes initially. We prove the best possible approximation factor for this problem is larger than $n^{1-\zeta}$ for any $\zeta > 0$ unless P=NP.

## 1.2 Related Work

Numerous opinion diffusion models have been introduced to investigate how a group of agents modify their opinions under the influence of other agents, cf. [14, 29, 34, 48]. It is usually assumed that for a graph $G$, which represents a social network, initially some nodes are colored black (positive) or white (negative). Then, nodes update their color based on some predefined rule. Among these models, the threshold and majority model are perhaps the closest to ours. In both of them, initially each node is black or white. In the *majority model* [41], in each round all nodes simultaneously update their color to the most frequent color in their neighborhood (and no update in case of a tie). In the *threshold model* [30], each node $v$ has a threshold value $t_v$ and it becomes black as soon as it has at least $t_v$ black neighbors.

We should emphasize that different variants of these models have been considered; for example, asynchronous updating rule [4], various tie-breaking rules [42], random threshold values [30], with a bias toward one of the colors [3], with stubborn users [39], a room-based version [34], and random tie-breading rule [51].

Consider a marketer which advertises a new product. Assume that it can convince a subset of agents to adopt a positive opinion about its product, e.g., by giving them free samples of the product, and it aims to trigger a large cascade of further adoptions. Which agents should it target? A node set $A$ is a *target set* if black color eventually takes over all (or half) of nodes once $A$ is fully black. (This is sometimes also known as dynamic monopoly or percolating set.) For both the majority and threshold model, the minimum size of a target set has been extensively studied on various classes of graphs such as lattice [6], Erdős-Rényi random graph [44], random regular graphs [7], and power-law random graphs [2]. Furthermore, Berger [10] proved that there exist arbitrarily large graphs which have target sets of constant size under the majority model and it was shown in [5] that every $n$-node graph has a target set of size at most $n/2$ under the asynchronous variant.

Furthermore, it is known that the problem of finding the minimum size of a target set for a given graph $G$ is NP-hard for different variants of these models. For the majority model, Mishra, Radhakrishnan, and Sivasubramanian [36] proved that this problem cannot be approximated within a factor of $\log \Delta \log \log \Delta$, unless P=NP; however, there is a polynomial-time $\log \Delta$-approximation algorithm. For the threshold model, Chen [13] proved that the problem is NP-hard even when all thresholds $t_v$ are 1 or 2 and $G$ is a bounded-degree bipartite graph. On the other hand, the problem is traceable for special classes of graphs such as trees. We study a similar optimization problem in our setting and provide inapproximability results.

Many other adversarial scenarios where an attacker aims to engineer the output of an opinion diffusion process have been investigated. For example, assume that an attacker can manipulate almost half of initially colored nodes to choose black color in a random or deterministic manner, similar to our attacker models. Which graph structures are resilient to such attacks, i.e., at the end of the process the white color is still the dominant color? For the majority model, it was proven in [37] that a graph is resilient if it is a clique or very close to a clique. In [4] similar results were provided for the asynchronous setting. For our majority-based model, we prove that expansion, regularity, and maximum degree are chiefly responsible for resilience.

Other kinds of attackers with various manipulation powers, such as adding/deleting edges or changing the order of updates, have been considered, cf. [12, 16]. Moreover, the complexity
of the problem of finding an optimal strategy for different types of attackers has been studied, cf. [26].

In the majority model (see first paragraph in this section), since the updating rule is deterministic, the process eventually reaches a cycle of colorings (from the $2^n$ possible colorings, where $n$ is the number of nodes). The length of this cycle and the number of rounds the process needs to reach the cycle are called the periodicity and stabilization time of the process, respectively. It was proven in [24] that periodicity is always one or two. Recently, it was shown in [14] that it is PSPACE-complete to decide whether the periodicity is one or not for a given coloring of a *directed* graph. Regarding the stabilization time, Fogelman, Goles, and Weisbuch [19] showed that it is bounded by $O(n^2)$. It was proven in [21] that this bound is tight, up to some poly-logarithmic factor. It was shown in [28] that the problem of determining whether there exists a coloring for which the process takes at least $t$ rounds is NP-complete. As mentioned, we provide tight bounds and hardness results on the stabilization time of our diffusion process.

## 1.3 Preliminaries

**Graph definitions.** Let $G = (V, E)$ be an $n$-node graph (which is not necessarily connected). For two nodes $v, u \in V$, we define $d(v, u)$ to be the length of a shortest path between $v, u$ in terms of the number of edges, which is called the *distance* between $v$ and $u$ (for a node $v$, we define $d(v, v) := 0$). For $t \in \mathbb{N}_0$, we let $N_t(v) := \{u \in V : d(v, u) = t\}$ denote the set of nodes whose distance from $v$ is exactly $t$. In particular, $N_0(v) = v$ and $N_1(v)$ is the set of $v$'s neighbors. Furthermore, we define $\hat{N}_t(v) := \cup_{i=0}^t N_i(v)$ to be the $t$-neighborhood of $v$. Analogously, for a node set $S \subseteq V$ we have $N_t(S) := \{u \in V : d(S, u) = t\}$ and $\hat{N}_t(S) := \cup_{i=0}^t N_i(S)$, where $d(S, u) := \min_{v \in S} d(v, u)$. We let $\deg(v) := |N_1(v)|$ denote the *degree* of $v$ and define $\deg_S(v) := |N_1(v) \cap S|$. We also define $\Delta(G)$ and $\delta(G)$ to be respectively the maximum and minimum degree in graph $G$. For two node sets $S$ and $S'$, we define $e(S, S') := |\{(v, u) \in S \times S' : \{v, u\} \in E\}|$ where $S \times S'$ is the Cartesian product of $S$ and $S'$.

**Model definitions.** In our model, we will denote by $R_t$ the set of nodes which are colored in the $t$-th round for $t \in \mathbb{N}_0$. In other words, $R_0$ is equal to the seed set and $R_t := N_t(R_0)$ for $t \in \mathbb{N}$. We also define $\hat{R}_t = \cup_{i=0}^t R_i$. Moreover, we let $B_t$ (analogously $W_t$) denote the set of black (resp. white) nodes in $R_t$. Similarly, $\hat{B}_t$ and $\hat{W}_t$ denote the set of black and white nodes in $\hat{R}_t$, respectively. We also define $r_t := |R_t|$, $\hat{r}_t = |\hat{R}_t|$, $b_t := |B_t|$, $\hat{b}_t = |\hat{B}_t|$, $w_t := |W_t|$, and $\hat{w}_t = |\hat{W}_t|$. Note that these are random variables even when we choose the seed nodes and their color deterministically since we break a tie at random.

**Some inequalities.** Now, we present some standard probabilistic inequalities, cf. [17], which we utilize several times later.

**Theorem 1.4 (Markov's inequality)** Let $X$ be a non-negative random variable with finite expectation and $a > 0$, then

$$ \Pr[X \ge a] \le \frac{\mathbb{E}[X]}{a}. $$

**Theorem 1.5 (Chebyshev's inequality)** Let $X$ be a random variable with finite variance and $a > 0$, then

$$ \Pr[X \ge \mathbb{E}[X] + a] \le \frac{\mathrm{Var}[X]}{a^2}. $$
**Theorem 1.6 (Chernoff bound)** Suppose $x_1, \cdots, x_k$ are independent Bernoulli random variables and let $X$ denote their sum, then for any $0 \le \eta \le 1$

$$ \bullet \Pr[(1 + \eta) \mathbb{E}[X] \le X] \le \exp\left(-\frac{\eta^2 \mathbb{E}[X]}{3}\right) $$

$$ \bullet \Pr[X \le (1 - \eta) \mathbb{E}[X]] \le \exp\left(-\frac{\eta^2 \mathbb{E}[X]}{2}\right). $$

If we are given $k$ discrete probability spaces $(\Omega_i, \mathrm{Pr}_i)$ for $1 \le i \le k$, then their product is defined to be the probability space over the ground set $\Omega := \Omega_1 \times \Omega_2 \times \cdots \times \Omega_k$ with the probability function $\mathrm{Pr}[(\omega_1, \ldots, \omega_k)] := \prod_{i=1}^k \mathrm{Pr}_i[\omega_i]$, where $\omega_i \in \Omega_i$. Let $(\Omega, \mathrm{Pr})$ be the product of $k$ discrete probability spaces, and let $X: \Omega \to \mathbb{R}$ be a random variable over $\Omega$. We say that the effect of the $i$-th coordinate is at most $c_i$ if for all $\omega, \omega' \in \Omega$ which differ only in the $i$-th coordinate we have $|X(\omega) - X(\omega')| \le c_i$. Azuma's inequality states that $X$ is sharply concentrated around its expectation if the effect of the individual coordinates is not too big.

**Theorem 1.7 (Azuma's inequality)** Let $(\Omega, \mathrm{Pr})$ be the product of $k$ discrete probability spaces $(\Omega_i, \mathrm{Pr}_i)$ for $1 \le i \le k$, and let $X: \Omega \to \mathbb{R}$ be a random variable with the property that the effect of the $i$-th coordinate is at most $c_i$. Then,

$$ \mathrm{Pr}[X \le \mathbb{E}[X] - a] \le \exp\left(-\frac{a^2}{2 \sum_{i=1}^k c_i^2}\right). $$

Moreover, we sometimes use the basic inequalities $1 - z \le \exp(-z)$ for any $z$ and $4^{-z} \le 1 - z$ for any $0 < z < 1/2$.

**Assumptions.** All logarithms are to base $e$, otherwise we point out explicitly. Furthermore, we let $n$ (the number of nodes) tend to infinity and $\alpha, \epsilon \in (0, 1/2)$ be constants. We assume that the error probability $\mu$, to be defined explicitly later for example in Theorem 3.2, is larger than $1/\sqrt{n}$. (Actually, most of our proofs also work when $\mu > 1/f(n)$ for any function $f(n)$ sub-exponential in $n$.)

## 2 Strong Attacker

In this section, our goal is to prove that a regular expander graph is resilient to a strong attacker. Roughly speaking, one says a graph has strong expansion properties if it is highly connected. There exist different parameters to measure the expansion of a graph. We consider an algebraic characterization of expansion. However, since the relation between other measures, such as vertex and edge expansion, and ours is well-understood, cf. [27], our results can be immediately rephrased.

Let $\sigma(G)$ be the second-largest absolute eigenvalue of the normalized adjacency matrix of graph $G$. There is a rich literature about the relation between the value of $\sigma$ and the expansion of graph $G$. However for our purpose here, all one needs to know is that $G$ has stronger expansion properties when $\sigma$ is smaller. Now, we present the expander mixing lemma, cf. [27], which basically states that the number of edges between any two node sets is almost completely determined by their cardinality if the value of $\sigma$ is small.
**Lemma 2.1 (Expander mixing lemma)** For a d-regular graph G = (V, E) and S, S' ⊂ V

$$ \left| e(S, S') - \frac{|S| |S'| d}{n} \right| \le \sigma d \sqrt{|S| |S'|}. $$

**Theorem 2.2** For a d-regular graph G = (V, E) and an (α,ε)-strong attacker, if $\sigma \le \epsilon\sqrt{\alpha(1-\alpha)}$, then the attacker cannot win for any number of rounds.

**Proof.** We know that $w_0 = (1/2 + \epsilon)\alpha n > \alpha n/2$. We prove that $w_1 \ge (1 - \alpha)n/2$, which yields $w_0 + w_1 > n/2$. This would imply that for any number of rounds, white is the dominant color. Thus, it suffices to prove that $w_1 \ge (1 - \alpha)n/2$.

Let $A := V \setminus (R_0 \cup W_1)$ be the set of non-seed nodes which are black or uncolored after one round. It suffices to prove that $a := |A| \le (1 - \alpha)n/2$ (since this implies that $w_1 \ge (1 - \alpha)n/2$). For each node $v \in A$, $\deg_{W_0}(v) \le \deg_{B_0}(v)$ (because otherwise it would become white after one round). Hence, $e(A, W_0) \le e(A, B_0)$. By applying Lemma 2.1 to both sides of this inequality, we get

$$ e(A, W_0) \ge \frac{aw_0d}{n} - \sigma d \sqrt{aw_0} $$

and

$$ e(A, B_0) \le \frac{ab_0d}{n} + \sigma d \sqrt{ab_0} $$

whose combination gives us

$$ \frac{aw_0d}{n} - \sigma d \sqrt{aw_0} \le \frac{ab_0d}{n} + \sigma d \sqrt{ab_0}. $$

Dividing by $\sqrt{a}$ and re-arranging the terms give us

$$ \sqrt{a}(w_0 - b_0) \le \sigma n(\sqrt{w_0} + \sqrt{b_0}). $$

Since $\sqrt{w_0} + \sqrt{b_0} = \sqrt{(1/2 + \epsilon)\alpha n} + \sqrt{(1/2 - \epsilon)\alpha n} \le \sqrt{2\alpha n}$, $w_0 - b_0 = 2\alpha\epsilon n$, and $\sigma \le \epsilon\sqrt{\alpha(1 - \alpha)}$, we get

$$ \sqrt{a} \le \frac{\epsilon n \sqrt{\alpha(1-\alpha)} \sqrt{2\alpha n}}{2\alpha\epsilon n} \Rightarrow a \le (1-\alpha)n/2. \quad \square $$

**Random regular graphs.** The random d-regular graph $G_{n,d}$ is the random graph with a uniform distribution over all d-regular graphs on n nodes. It is proven by [20] that $\sigma(G_{n,d}) \le 2/\sqrt{d}$ for $d \ge 3$ a.a.s. Putting this statement in parallel with Theorem 2.2 implies that if $d \ge 4/(\alpha(1 - \alpha)\epsilon^2)$, then $G_{n,d}$ is resilient to an $(\alpha, \epsilon)$-attacker a.a.s.

**Irregular graphs.** So far, we limited ourselves to regular graphs. However, our result can be generalized to capture irregular graphs by applying basically the same proof ideas. All we need to do is to apply a more general variant of Lemma 2.1, cf. [27], and replace d with $\delta$ or $\Delta$, according to the case. Then, we can conclude that for a graph G = (V, E) and an $(\alpha, \epsilon)$-strong attacker, if $\sigma \le ((1 + \gamma)\epsilon/2 - (1 - \gamma)/4)\sqrt{\alpha(1 - \alpha)}$, then the attacker cannot win, where $\gamma := \delta/\Delta$. (This is equivalent to the statement of Theorem 2.2 for $\gamma = 1$.)
**Erdős-Rényi random graph.** In the Erdős-Rényi random graph $G_{n,p}$ each edge is added independently w.p. $p$ on a node set of size $n$. Let $K$ be a sufficiently large constant. It is proven by [31] that if $p \ge K \log n/n$, then $\sigma(G_{n,p}) = O(1/\sqrt{np})$ a.a.s. (recall that $\log n/n$ is the connectivity threshold). Furthermore, it is well known, cf. [17], that $\gamma \ge (1-\epsilon)$ for any $\epsilon > 0$ a.a.s. if $p \ge K \log n/n$. Combining the last two statements and our proposition about irregular graphs implies that $G_{n,p}$ for $p \ge K \log n/n$ is a.a.s. resilient to an $(\alpha, \epsilon)$-strong attacker.

**Tightness.** We believe that regularity and expansion are not only sufficient conditions for a graph to be resilient to a strong attacker, but also somehow necessary. To support this, we provide a regular non-expander graph and an irregular expander graph where a strong attacker has a winning strategy.

Let $\alpha$ and $\epsilon$ be arbitrary constants between 0 and $1/2$ and assume that $d \ge 2$. Consider an arbitrary $d$-regular graph $G_1$ on $(1/2 + \epsilon)\alpha n$ nodes and a $d$-regular connected graph $G_2$ on $n - (1/2 + \epsilon)\alpha n$ nodes. Let $G$ be the union of $G_1$ and $G_2$. Thus, $G$ is an $n$-node $d$-regular graph. An $(\alpha, \epsilon)$-strong attacker can simply color all nodes in $G_1$ white and $(1/2 - \epsilon)\alpha n$ arbitrary nodes in $G_2$ black. Then, the number of white nodes remains unchanged while black color eventually takes over all uncolored nodes. Therefore, the attacker wins.

Now, we provide an irregular expander graph which is not resilient to a strong attacker. Let $\alpha, \epsilon > 0$ be sufficiently small constants and assume that $G$ is a $d$-regular graph, for some fixed $d$, with strong expansion properties. Let $B$ and $W$ be two arbitrary disjoint node sets of size $(1/2 - \epsilon)\alpha n$ and $(1/2 + \epsilon)\alpha n$, respectively. Now, we add $d$ additional edges between each node $v \in B$ and nodes in $V \setminus (B \cup W)$ at random. One can show that this new graph has strong expansion properties. However, if an $(\alpha, \epsilon)$-attacker chooses $B_0 = B$ and $W_0 = W$, then a.a.s. each black node “generates” almost $2d$ new black nodes in the next round while each white node generates almost $d$ new white nodes a.a.s., i.e., $b_1 \approx 2db_0$ and $w_1 \approx dw_0$. Thus, the number of black nodes surpasses the number of white ones after one round. (We should stress that the given argument is not a formal proof since we left out several details. However, our goal here is only to provide an intuitive argument.)

## 3 Moderate Attacker

In this section, our main purpose is to prove Theorem 3.2. To do so, let us first provide Lemma 3.1.

**Lemma 3.1** For a graph $G = (V, E)$ and an $(\alpha, \epsilon)$-moderate attacker, $(1/2 + \epsilon)\alpha n - \alpha\epsilon n/2 \le w_0 \le (1/2 + \epsilon)\alpha n + \alpha\epsilon n/2 \text{ w.p. } 1 - \exp(-\Theta(\epsilon^2\alpha n))$.

**Proof.** Label the seed nodes arbitrarily from $v_1$ to $v_{\alpha n}$ (for the sake of simplicity, we are assuming $\alpha n$ is an integer, otherwise, we need to round it). We define Bernoulli random variable $x_i$ to be 1 if and only if $v_i$ is colored white. Then, $w_0 = \sum_{i=1}^{\alpha n} x_i$ and $E[w_0] = (1/2 + \epsilon)\alpha n$. Since $x_i$s are independent, applying the Chernoff bound (Theorem 1.6) for $\eta = \epsilon/2$ yields our claim. $\square$

**Theorem 3.2** For a graph $G = (V, E)$ and an $(\alpha, \epsilon)$-moderate attacker, if $\Delta \le (C_{\alpha, \epsilon}n/\log(1/\mu))^{1/2t}$ for some sufficiently small constant $C_{\alpha, \epsilon} > 0$, then the attacker cannot win in $t$ rounds w.p. at least $1 - \mu$. We assume that $\mu \ge 1/\sqrt{n}$.
We should emphasize that the dependency on $t$ in the upper bound on $\Delta$ comes from the limitation of our proof techniques and we believe a similar bound without dependency on $t$ should hold.

**Proof.** Let $r = \hat{r}_t - r_0$ be the number of nodes which are colored during rounds 1 to $t$. We define $X := \hat{w}_t - w_0$ to be the number of nodes which are colored white among these nodes. We prove that $X > r/2 - \alpha\epsilon n/2$ w.p. at least $1 - \mu/2$. Furthermore based on Lemma 3.1, $w_0 \ge r_0/2 + \alpha\epsilon n/2$ w.p. $1 - \exp(-\Theta(\epsilon^2\alpha n)) \ge 1 - 1/(2\sqrt{n}) \ge 1 - \mu/2$ (where we used our assumptions that $\alpha, \epsilon$ are constant and $\mu \ge 1/\sqrt{n}$). Therefore, we have $\hat{w}_t = X + w_0 > (r/2 - \alpha\epsilon n/2) + (r_0/2 + \alpha\epsilon n/2) = (r + r_0)/2 = \hat{r}_t/2$ w.p. at least $1 - \mu$, which implies that the attacker does not win in $t$ rounds.

It remains to prove that $X > r/2 - \alpha\epsilon n/2$ w.p. at least $1 - \mu/2$. Let us label all nodes in $R_0$ arbitrarily from $v_1$ to $v_{\alpha n}$. Corresponding to each node $v_i$ for $1 \le i \le \alpha n$, we define the probability space $(\Omega_i, \mathrm{Pr}_i)$. Then, $X: \Omega \to \mathbb{R}$ is defined over $\Omega$, where $(\Omega, \mathrm{Pr})$ is the product of discrete probability spaces $(\Omega_i, \mathrm{Pr}_i)$. Recall that we say the effect of the $i$-th coordinate is at most $c_i$ if for all $\omega, \omega' \in \Omega$ which differ only in the $i$-th coordinate we have $|X(\omega) - X(\omega')| \le c_i$. Obviously, if we change the color of node $v_i$, then the color of at most $|\hat{N}_t(v_i)| \le 2\Delta^t$ of the nodes, which are colored in the first $t$ rounds, will be affected. Therefore, $c_i \le 2\Delta^t$, which implies that $\sum_{i=1}^{\alpha n} c_i^2 \le 4\alpha n \Delta^{2t}$. Furthermore, $\mathbb{E}[X] \ge r/2$ since each node in $V \setminus R_0$ is white w.p. at least $1/2$. This should be intuitively clear since each node is colored white in the initial coloring with a higher probability. (Actually, one can get the stronger lower bound of $(1/2 + \epsilon)$ with a coupling argument, which is not needed here). Now, applying Azuma's inequality (Theorem 1.7) yields

$$ \mathrm{Pr}[X \le \frac{r}{2} - \frac{\alpha\epsilon n}{2}] \le \exp\left(-\frac{\alpha^2\epsilon^2 n^2}{8 \sum_{i=1}^{\alpha n} c_i^2}\right) \le \exp\left(-\frac{\alpha\epsilon^2 n}{32\Delta^{2t}}\right). $$

For a suitable choice of $C_{\alpha, \epsilon}$, we have $\Delta \le \left(\frac{\alpha\epsilon^2 n}{32 \log(2/\mu)}\right)^{\frac{1}{2t}}$. Thus, the above probability is at most $\mu/2$. $\square$

**Tightness.** Now, we provide Proposition 3.3 which asserts that if we could replace the exponent $1/2t$ with $1/t$ in Theorem 3.2, then our bound would be tight, up to some constant factor. We believe that this is actually doable with some case distinctions and more careful calculations; however, we only prove such statement for $t = 1$ here, in Proposition 3.4.

**Proposition 3.3** For any $\epsilon, \alpha, \mu > 0$ and $t \in \mathbb{N}$, there exists a graph $G$ with $\Delta = (C'_{\alpha, \epsilon} n / \log(1/\mu))^{\frac{1}{t}}$ for some constant $C'_{\alpha, \epsilon}$ such that an $(\alpha, \epsilon)$-moderate attacker can win in $t$ rounds w.p. larger than $\mu$.

**Proof.** The proof is essentially built on the simple fact that if in a complete $d$-ary tree the root $v$ is black (and the rest of nodes are uncolored), then after $t$ rounds $|\hat{N}_t(v)| \ge d^t$ nodes will be black.

Let $s = \log_2(1/\mu)/(2 + 8\epsilon)$. Assume graph $G$ is the union of a cycle on $\alpha n - s$ nodes and $s$ complete $d$-ary trees, each of size $((1 - \alpha)n + s)/s$. Suppose that

$$ d = ((3\alpha\epsilon n + 1)/s)^{\frac{1}{t}} = ((2 + 8\epsilon)(3\alpha\epsilon n + 1)/\log_2(1/\mu))^{\frac{1}{t}}. $$

Thus $G$ is an $n$-node graph with maximum degree $d+1$, which is equal to $\Delta = (C'_{\alpha, \epsilon} n / \log(1/\mu))^{\frac{1}{t}}$ for a suitable choice of $C'_{\alpha, \epsilon}$.
Assume that the attacker chooses the $\alpha n - s$ nodes on the cycle and $s$ roots of the $d$-ary trees to be the seed nodes. Then, the probability that all $s$ roots are colored black is

$$ \left(\frac{1}{2} - \epsilon\right)^s = 2^{-s} (1 - 2\epsilon)^s \ge 2^{-s} 4^{-2\epsilon s} = \sqrt{\mu} > 2\mu $$

where we used $(1-z) \ge 4^{-z}$ for $0 < z < 1/2$ and $s = \log_2(1/\mu)/(2+8\epsilon)$, respectively.

Furthermore, if all $s$ roots are black, then at least $sd^t = 3\alpha\epsilon n + 1$ uncolored nodes will be colored black after $t$ rounds (while no uncolored node will be colored white). Hence, w.p. more than $2\mu$, the number of black nodes increases by at least $3\alpha\epsilon n + 1$ while the number of white ones remains unchanged. Moreover based on Lemma 3.1, $w_0 \le b_0 + 3\alpha\epsilon n$ w.p. $1 - \exp(-\Theta(\epsilon^2\alpha n)) > 1 - 1/\sqrt{n} \ge 1 - \mu$, where we sued our assumptions that $\alpha, \epsilon$ are constant and $\mu \ge 1/\sqrt{n}$. Therefore, we can conclude that w.p. more than $1 - (1 - 2\mu) - \mu = \mu$, we have $\hat{b}_t > \hat{w}_t$, that is, the attacker wins. $\square$

Now, we prove Proposition 3.4, which as mentioned above proves a bound that is slightly stronger than the bound in Theorem 3.2 for the special case of $t = 1$. We particularly go from $1/(2t)$ to $1/t$ in this case, focusing on the dominating polynomial term.

**Proposition 3.4** For a graph $G = (V, E)$ and an $(\alpha, \epsilon)$-moderate attacker, if $\Delta \le C''_{\alpha, \epsilon} n / \log^2(1/\mu)$ for some sufficiently small constant $C''_{\alpha, \epsilon} > 0$, then the attacker cannot win in one round w.p. at least $1 - \mu$.

**Proof.** Suppose that $d_3^* := 4 \log(6/\mu)/\epsilon^2$. We define

$$ R_{1h} := \{v \in R_1 : \deg_{R_0}(v) \ge d_3^*\} $$

to be the set of high-degree nodes in $R_1$ and $R_{1l} := R_1 \setminus R_{1h}$ to be the set of low-degree nodes in $R_1$. Let $r_{1h} := |R_{1h}|$ and $r_{1l} := |R_{1l}|$. We also let $w_{1h}$ and $w_{1l}$ denote the number of white nodes in $R_{1h}$ and $R_{1l}$, respectively. Analogously, we define, $b_{1h}$ and $b_{1l}$ for black color.

First, we show that $w_{1h} \ge r_{1h}/2$ w.p. at least $1 - \mu/3$. Then, we prove that $w_{1l} > r_{1l}/2 - \alpha\epsilon n/2$ w.p. at least $1 - \mu/3$. Furthermore based on Lemma 3.1, we know that $w_0 \ge r_0/2 + \alpha\epsilon n/2$ w.p. $1 - \exp(-\Theta(\epsilon^2\alpha n)) \ge 1 - 1/3\sqrt{n} \ge 1 - \mu/3$ (where we used our assumptions that $\alpha, \epsilon$ are constant and $\mu \ge 1/\sqrt{n}$). Combining these three statements implies that $\hat{w}_1 = w_0 + w_{1h} + w_{1l} > (r_0 + r_{1h} + r_{1l})/2 = \hat{r}_1/2$ (i.e., the attacker does not win after one round) w.p. at least $1 - \mu$.

Let us first prove that $w_{1h} \ge r_{1h}/2$ w.p. at least $1 - \mu/3$. Consider an arbitrary node $v$ in $R_{1h}$ and let $u_i$ for $1 \le i \le d = \deg_{R_0}(v)$ be the neighbors of $v$ in $R_0$. We define Bernoulli random variable $x_i$ to be 1 if and only if $u_i$ is colored white. Let $X := \sum_{i=1}^d x_i$ denote the number of white neighbors of $v$ in $R_0$. Thus, we have $\mathbb{E}[X] = (1/2 + \epsilon)d$. Then, the probability that $v$ is colored black is at most

$$ \begin{aligned} \Pr[X \le d/2] &\le \Pr[X \le (1-\epsilon)(1/2+\epsilon)d] \\ &= \Pr[X \le (1-\epsilon)\mathbb{E}[X]] \\ &\le \exp(-\epsilon^2(1/2+\epsilon)d/2) \\ &\le \exp(-\epsilon^2 d_3^*/4) \\ &= \exp(-\log(6/\mu)) \\ &= \mu/6 \end{aligned} $$
where we used the Chernoff bound (Theorem 1.6). Therefore, the probability that an arbitrary node in $R_{1h}$ is colored black is at most $\mu/6$. This implies that $\mathbb{E}[b_{1h}] \le r_{1h} \mu/6$. Applying Markov's inequality (Theorem 1.4) gives us

$$ 
\begin{aligned}
\mathrm{Pr}[w_{1h} < \frac{r_{1h}}{2}] &= \mathrm{Pr}[b_{1h} \ge \frac{r_{1h}}{2}] \\
&\le \frac{\mathbb{E}[b_{1h}]}{r_{1h}/2} \\
&\le \frac{r_{1h} \mu/6}{r_{1h}/2} \\
&= \mu/3.
\end{aligned}
$$

It remains to prove that $w_{1l} > r_{1l}/2 - \alpha\epsilon n/2$ w.p. at least $1 - \mu/3$. Let $v_i$ for $1 \le i \le \alpha n$ be the nodes in $R_0$. Corresponding to each node $v_i$, we define the probability space $(\Omega_i, \mathrm{Pr}_i)$. Then, random variable $w_{1l} : \Omega \to \mathbb{R}$ is defined over $\Omega$, where $(\Omega, \mathrm{Pr})$ is the product of discrete probability spaces $(\Omega_i, \mathrm{Pr}_i)$ for $1 \le i \le \alpha n$. Recall that we say the effect of the $i$-th coordinate is at most $c_i$ if for all $\omega, \omega' \in \Omega$ which differ only in the $i$-th coordinate we have $|w_{1l}(\omega) - w_{1l}(\omega')| \le c_i$. We claim that $c_i \le \mathrm{deg}_{R_{1l}}(v_i)$ because if we change the color of node $v_i$, then the only nodes in $R_{1l}$ which might adopt a different color are the nodes in $N_{R_{1l}}(v_i)$. Therefore, we have that

$$ \sum_{i=1}^{\alpha n} c_i \le \sum_{i=1}^{\alpha n} \mathrm{deg}_{R_{1l}}(v_i) = \sum_{u \in R_{1l}} \mathrm{deg}_{R_0}(u) \le r_{1l} d_3^*. $$

Using $d_3^* = 4\log(6/\mu)/\epsilon^2$ and $r_{1l} \le n$ we get

$$ \sum_{i=1}^{\alpha n} c_i \le \frac{4n \log \frac{6}{\mu}}{\epsilon^2}. $$

Since $c_i \le \mathrm{deg}_{R_{1l}}(v_i) \le \Delta$, we have

$$ \sum_{i=1}^{\alpha n} c_i^2 \le \Delta \sum_{i=1}^{\alpha n} c_i \le \frac{4n\Delta \log \frac{6}{\mu}}{\epsilon^2}. $$

Furthermore, $\mathbb{E}[w_{1l}] \ge r_{1l}/2$ since each node in $R_{1l}$ is white w.p. at least $1/2$. Now, applying Azuma's inequality (Theorem 1.7) yields

$$ 
\begin{aligned}
\mathrm{Pr}[w_{1l} \le \frac{r_{1l}}{2} - \frac{\alpha\epsilon n}{2}] &\le \exp\left(-\frac{\alpha^2\epsilon^2 n^2}{8 \sum_{i=1}^{\alpha n} c_i^2}\right) \\
&\le \exp\left(-\frac{\alpha^2\epsilon^4 n}{32\Delta \log \frac{6}{\mu}}\right) \\
&\le \exp(-\log(3/\mu)) \\
&= \mu/3.
\end{aligned}
$$

In the second step from last, we used that for a suitable choice of $C''_{\alpha,\epsilon}$ we have

$$ \Delta \le \frac{C''_{\alpha,\epsilon} n}{\log^2 \frac{1}{\mu}} = \frac{\alpha^2 \epsilon^4 n}{32 \log \frac{6}{\mu} \log \frac{3}{\mu}}. $$

□
# 4 Weak Attacker

Theorem 4.1 states that if the maximum degree of a graph is sufficiently smaller than $n$ or if the degree of at least half of the nodes is pretty large, then it is resilient to a weak attacker. In other words, a weak attacker can be successful only on graphs with some nodes of very high degree and a large set of nodes with small degree such as a star graph.

**Theorem 4.1** For a graph $G = (V, E)$ and an $(\alpha, \epsilon)$- weak attacker, if $\Delta \le C_{\alpha, \epsilon}n/((\log n)^{C'_{\alpha, \epsilon}} \log(4/\mu))$ for some suitable constants $C_{\alpha, \epsilon}, C'_{\alpha, \epsilon} > 0$ or if half of the nodes are of degree at least $d_1^* := (6/\alpha\epsilon^2) \log(12/\alpha\epsilon\mu)$, then for any $t \in \mathbb{N}$ the attacker cannot win in $t$ rounds w.p. at least $1 - \mu$.

We observe that the bound on $\Delta$ in Theorem 4.1 does not depend on the number of rounds $t$, unlike the case of a moderate attacker. Furthermore for a moderate attacker, we cannot prove that if the degree of half of the nodes is larger than a certain degree threshold, then the attacker fails, except if the threshold is very large. Assume that graph $G$ is the union of a clique of size $\alpha n - 1$ and a clique of size $(1 - \alpha)n + 1$. Suppose that an $(\alpha, \epsilon)$-moderate attacker chooses all $\alpha n - 1$ nodes in the first clique and a node $v$ in the second one to be the seed nodes. If $v$ is colored black, then the attacker wins and this happens w.p. $(1/2 - \epsilon)$. Note that all nodes in $G$ are of degree at least $\alpha n - 2$.

To prove Theorem 4.1, we first need to present some necessary ingredients in Lemmas 4.2, 4.3, 4.4, and 4.5.

**Lemma 4.2** For a graph $G = (V, E)$ and an $(\alpha, \epsilon)$-weak attacker, $r_0/2 + \alpha\epsilon n/2 \le w_0 \le r_0/2 + 3\alpha\epsilon n/2$ w.p. at least $1 - \exp(-\Theta(\epsilon^2\alpha n))$.

**Proof.** We prove the lower bound. The proof of the upper bound is very similar. We know that $r_0/2 + \alpha\epsilon n/2 \le w_0$ is the same as $b_0 + \alpha\epsilon n \le w_0$ because $r_0 = w_0 + b_0$. Thus, it suffices to prove that $w_0 \ge (1/2 + \epsilon/2)\alpha n$ and $b_0 \le (1/2 - \epsilon/2)\alpha n$ w.p. $1 - \exp(-\Theta(\epsilon^2\alpha n))$. We prove the former and the latter is proven analogously. Assume that $v_1, \dots, v_n$ are the nodes of $G$. We define Bernoulli random variable $x_i$ to be 1 if and only if node $v_i$ is chosen as a seed node and is colored white. Then, we have $\Pr[x_i = 1] = (1/2 + \epsilon)\alpha$ and $w_0 = \sum_{i=1}^n x_i$. Thus, we get $\mathbb{E}[w_0] = (1/2 + \epsilon)\alpha n$. Applying the Chernoff bound (Theorem 1.6) yields

$$ \begin{aligned} \Pr[w_0 \le \left(\frac{1}{2} + \frac{\epsilon}{2}\right) \alpha n] &\le \Pr[w_0 \le \left(1 - \frac{\epsilon}{2}\right) \left(\frac{1}{2} + \epsilon\right) \alpha n] \\ &= \Pr[w_0 \le \left(1 - \frac{\epsilon}{2}\right) \mathbb{E}[w_0]] \\ &= \exp(-\Theta(\epsilon^2 \alpha n)). \end{aligned} $$

□

**Lemma 4.3** For a graph $G = (V, E)$ and an $(\alpha, \epsilon)$-weak attacker, every node whose degree is at least $d_2^* := 8 \log n/(\alpha\epsilon^2)$ is in $R_0 \cup W_1$ w.p. at least $1 - 2/n$.

**Proof.** Consider an arbitrary node $v$ such that $\deg(v) \ge d_2^*$. Let $X_w := |N(v) \cap W_0|$ and $X_b := |N(v) \cap B_0|$. Then,

$$ \Pr[v \notin R_0 \cup W_1] \le (1 - \alpha) \Pr[X_w \le X_b]. $$
This is because for the event of $v \notin R_0 \cup W_1$ to happen, we need $v$ not be selected in the seed set (which happens with probability $1 - \alpha$) and also not be in $W_1$ (which happens with probability at most $\text{Pr}[X_w \le X_b]$).

We prove that $\text{Pr}[X_w \le X_b] \le 2/n^2$. Thus, a union bound yields our desired statement.

Let $d = \text{deg}(v)$. We prove that $X_w \le \alpha dn/2$ w.p. at most $1/n^2$. Analogously, one can show that $X_b \ge \alpha dn/2$ w.p. at most $1/n^2$. Thus, we have $X_w \le X_b$ w.p. at most $2/n^2$. Let $u_i$ for $1 \le i \le d$ be the neighbors of $v$. We define Bernoulli random variable $x_i$ to be 1 if and only if $u_i$ is selected as a seed node and is colored white, which implies that $X_w = \sum_{i=1}^d x_i$. Since $\text{Pr}[x_i = 1] = (1/2 + \epsilon)\alpha$, we get $\mathbb{E}[X_w] = (1/2 + \epsilon)\alpha d$. Now, applying the Chernoff bound (Theorem 1.6) yields

$$ \begin{aligned} \text{Pr}[X_w \le \alpha d/2] &\le \text{Pr}[(1 - \epsilon)(1/2 + \epsilon)\alpha d] \\ &= \text{Pr}[(1 - \epsilon)\mathbb{E}[X_w]] \\ &\le \exp(-\epsilon^2(1/2 + \epsilon)\alpha d/2) \\ &\le \exp(-\epsilon^2\alpha d_2^*/4) \\ &= 1/n^2 \end{aligned} $$

where we used $d \ge d_2^* = 8 \log n/(\epsilon^2\alpha)$. $\square$

**Lemma 4.4** For a graph $G = (V, E)$ and an $(\alpha, \epsilon)$-weak attacker, the number of nodes which are colored exactly after the $t_1^*$-th round, for $t_1^* := (2/\alpha) \log(4/\alpha\epsilon)$, is at most $\alpha\epsilon n/2$ w.p. at least $1 - 1/4\sqrt{n}$.

**Proof.** If $N_{t_1^*}(v) = \emptyset$ for a node $v \in V$, then it will be colored in the first $t_1^* - 1$ rounds or it will never be colored. (Recall that $N_t(v) := \{u \in V : d(v, u) = t\}$.) Thus, we only need to focus on nodes in

$$ V' := \{v \in V : N_{t_1^*}(v) \neq \emptyset\}. $$

Let us define

$$ V'_h := \{v \in V' : |\hat{N}_{t_1^*}(v)| \ge (2/\alpha) \log n\} $$

and $V'_l := V' \setminus V'_h$. Then, we let

$$ X_h := |\{v \in V'_h : \hat{N}_{t_1^*}(v) \cap R_0 = \emptyset\}| $$

and

$$ X_l := |\{v \in V'_l : \hat{N}_{t_1^*/2}(v) \cap R_0 = \emptyset\}|. $$

The value of $t_1^*/2$ has been chosen appropriately for our argument on covariance below to follow.

We prove that $X_h = 0$ w.p. at least $1 - 1/8\sqrt{n}$ and $X_l \le \alpha\epsilon n/2$ w.p. at least $1 - 1/8\sqrt{n}$. We observe that if there is a seed node in distance at most $t_1^*$ (subsequently, $t_1^*/2$) of a node, then it will be colored in at most $t_1^*$ rounds. Hence, we can conclude that there are at most $\alpha\epsilon n/2$ nodes which are colored after the $t_1^*$-th round w.p. at least $1 - 1/4\sqrt{n}$.

Consider an arbitrary node $v \in V'_h$. Since $|\hat{N}_{t_1^*}(v)| \ge (2/\alpha) \log n$, then

$$ \begin{aligned} \text{Pr}[\hat{N}_{t_1^*}(v) \cap R_0 = \emptyset] &\le (1 - \alpha)^{(2/\alpha) \log n} \\ &\le \exp(-2 \log n) \\ &= 1/n^2. \end{aligned} $$
A union bound implies that $X_h = 0$ w.p. at least $1 - 1/n \ge 1 - 1/8\sqrt{n}$.

Now, we prove that $X_l \le \alpha\epsilon n/2$ w.p. at least $1 - 1/8\sqrt{n}$. Let $u_1, \cdots, u_k$ be the nodes in $V'_l$, where $k = |V'_l|$. We define Bernoulli random variable $x_i$ to be 1 if and only if $\hat{N}_{t_1^*/2}(u_i) \cap R_0 = \emptyset$. Thus, we have $X_l = \sum_{i=1}^k x_i$. Furthermore, $|\hat{N}_{t_1^*/2}(u_i)| \ge t_1^*/2$ because $\hat{N}_{t_1^*/2}(u_i) \ne \emptyset$. This implies that

$$ 
\begin{aligned}
\Pr[x_i = 1] &\le (1 - \alpha)^{t_1^*/2} \\
&\le \exp(-t_1^*\alpha/2) \\
&= \exp(-\log(4/\alpha\epsilon)) \\
&= \alpha\epsilon/4.
\end{aligned}
$$

Therefore, we have

$$ \mathbb{E}[X_l] \le \alpha\epsilon k/4 \le \alpha\epsilon n/4. \quad (1) $$

Now, the goal is to prove our claim by using Chebyshev's inequality, Theorem 1.5, which states that for a random variable $X$ with finite variance and $a > 0$, we have

$$ \Pr[X \ge \mathbb{E}[X] + a] \le \frac{\mathrm{Var}[X]}{a^2}. $$

Thus, we need to compute $\mathrm{Var}[X_l]$. We have

$$ \mathrm{Var}[X_l] = \sum_{i=1}^{k} \mathrm{Var}[x_i] + \sum_{1 \le i \ne j \le k} \mathrm{Cov}(x_i, x_j). $$

If $\hat{N}_{t_1^*/2}(u_i) \cap \hat{N}_{t_1^*/2}(u_j) = \emptyset$, then random variables $x_i$ and $x_j$ are independent, which implies that $\mathrm{Cov}(x_i, x_j) = 0$. On the other hand, if $\hat{N}_{t_1^*/2}(u_i) \cap \hat{N}_{t_1^*/2}(u_j) \ne \emptyset$, then $u_j \in \hat{N}_{t_1^*}(u_i)$, and we know that $|\hat{N}_{t_1^*}(u_i)| \le (2/\alpha) \log n$ (since $u_i \in V'_l$). Therefore, for a random variable $x_i$, corresponding to node $u_i$, there are at most $(2/\alpha) \log n$ variables $x_j$ such that $\mathrm{Cov}(x_i, x_j) \ne 0$. Now, by utilizing the fact that $\mathrm{Cov}(x_i, x_j) \le 1$ for two Bernoulli random variables $x_i, x_j$, we can conclude that

$$ \sum_{1 \le i \ne j \le k} \mathrm{Cov}(x_i, x_j) \le \frac{2k \log n}{\alpha}. $$

Furthermore, since $x_i$ is a Bernoulli random variable, $\mathrm{Var}[x_i] \le 1$. Thus, $\sum_{i=1}^k \mathrm{Var}[x_i] \le k$. Overall, we get

$$ \mathrm{Var}[X_l] \le k + \frac{2k \log n}{\alpha} \le \frac{(2 \log n + 1)n}{\alpha}. \quad (2) $$

By applying Chebyshev's inequality and using Equations (1) and (2), we get

$$ 
\begin{aligned}
\Pr[X_l \ge \frac{\alpha\epsilon n}{2}] &\le \Pr[X_l \ge \mathbb{E}[X_l] + \frac{\alpha\epsilon n}{4}] \\
&\le \frac{\mathrm{Var}[X_l]}{\alpha^2\epsilon^2n^2/16} \\
&\le \frac{16(2 \log n + 1)n}{\alpha^3\epsilon^2n^2} \\
&\le 1/8\sqrt{n}.
\end{aligned}
$$
□

Now, in Lemma 4.5, we show that if at least half of the nodes have a degree larger than a desired threshold, then the attacker cannot win. This then allows us to rule out such graphs in the proof of Theorem 4.1

**Lemma 4.5** For a graph $G = (V, E)$ and an $(\alpha, \epsilon)$-weak attacker, if half of the nodes are of degree at least $d_1^* := (6/\alpha\epsilon^2) \log(12/\mu\alpha\epsilon)$, then for any $t \in \mathbb{N}$ the attacker cannot win in $t$ rounds w.p. at least $1 - \mu$.

**Proof.** Let $V_h$ be a node set of size $n/2$ whose nodes are all of degree at least $d_1^*$ and define $\bar{V}_h := V \setminus V_h$. We prove that after one round w.p. at least $1 - \mu$ the number of white nodes is more than $n/2$ (that is, the attacker cannot win for any number of rounds). In the following, we provide three statements whose combination yields the above claim.

Firstly, let $X_1 := |\bar{V}_h \cap W_0|$. Then, we have $\mathbb{E}[X_1] = (1/2 + \epsilon)\alpha n/2 = \alpha n/4 + \alpha\epsilon n/2$. Very similar to the proof of Lemma 4.2, by applying the Chernoff bound (Theorem 1.6) we can prove that $X_1 \ge \alpha n/4 + \alpha\epsilon n/4$ w.p. at least $1 - \exp(-\Theta(\epsilon^2\alpha n)) \ge 1 - 1/3\sqrt{n} \ge 1 - \mu/3$ (where we used our assumptions that $\alpha, \epsilon$ are constant and $\mu \ge 1/\sqrt{n}$).

Furthermore, we define $X_2 := |V_h \cap B_0|$. Then, we have $\mathbb{E}[X_2] = (1/2 - \epsilon)\alpha n/2 = \alpha n/4 - \alpha\epsilon n/2$. Again, by applying the Chernoff bound (Theorem 1.6) we can show that $X_2 \le \alpha n/4 - \alpha\epsilon n/4$ w.p. at least $1 - \exp(-\Theta(\epsilon^2\alpha n)) \ge 1 - \mu/3$.

Finally, let $X_3 := |V_h \setminus (R_0 \cup W_1)|$. Consider an arbitrary node $v \in V_h$. Let $Y_W$ and $Y_B$ respectively denote the number of white and black neighbors of $v$ in $R_0$. Suppose that $u_1, \dots, u_d$ are the neighbors of $v$, where $d = \deg(v) \ge d_1^*$. We define Bernoulli random variable $y_i$ to be 1 if and only if $u_i$ is in $W_0$. Then, we have $\Pr[y_i = 1] = (1/2 + \epsilon)\alpha$ and $Y_W = \sum_{i=1}^d y_i$. Thus, we get $\mathbb{E}[Y_W] = (1/2 + \epsilon)\alpha d$. By applying the Chernoff bound (Theorem 1.6), we have

$$ \begin{aligned} \Pr[Y_W \le \alpha d/2] &\le \Pr[Y_W \le (1-\epsilon)(1/2+\epsilon)\alpha d] \\ &= \Pr[Y_W \le (1-\epsilon)\mathbb{E}[Y_W]] \\ &\le \exp(-\epsilon^2(1/2+\epsilon)\alpha d/2) \\ &\le \exp(-\epsilon^2\alpha d_1^*/4) \\ &\le \alpha\epsilon\mu/12. \end{aligned} $$

Following a similar argument, one can show that $\Pr[Y_B \ge \alpha d/2] \le \alpha\epsilon\mu/12$. Therefore, we have $Y_W \le Y_B$ w.p. at most $\alpha\epsilon\mu/6$. Note that if $Y_W > Y_B$ and $v \notin R_0$, then we have $v \in W_1$. This implies that

$$ \Pr[v \notin (R_0 \cup W_1)] \le (1-\alpha)\alpha\epsilon\mu/6. $$

Hence, $\mathbb{E}[X_3] \le (1 - \alpha)\alpha\epsilon\mu n/12$. Now, by applying Markov's inequality (Theorem 1.4), we get

$$ \Pr[X_3 \ge \frac{\alpha\epsilon n}{4}] \le \frac{\mathbb{E}[X_3]}{\alpha\epsilon n/4} \le \frac{4(1-\alpha)\alpha\epsilon\mu n}{12\alpha\epsilon n} \le \mu/3. $$

It remains to argue that the combination of the above three statements yields our claim. We proved that $X_2 \le \alpha n/4 - \alpha\epsilon n/4$ w.p. at least $1 - \mu/3$ and $X_3 < \alpha\epsilon n/4$ w.p. at least $1 - \mu/3$. Recall that $X_2 = |V_h \cap B_0|$ and $X_3 = |V_h \setminus (R_0 \cup W_1)|$. Thus, more than $n/2 - (\alpha n/4 - \alpha\epsilon n/4 + \alpha\epsilon n/4) = n/2 - \alpha n/4$ nodes in $V_h$ are white after one round w.p. at least $1 - 2\mu/3$. Furthermore, $X_1 = |\bar{V}_h \cap W_0| \ge \alpha n/4 + \alpha\epsilon n/4$ w.p. at least $1 - \mu/3$. Overall, we can conclude that after one round there are at least $(n/2 - \alpha n/4) + (\alpha n/4 + \alpha\epsilon n/4) = n/2 + \alpha\epsilon n/4$ white nodes, that is, the attacker cannot win after any number of rounds, w.p. at least $1 - \mu$. □
**Proof of Theorem 4.1.** Based on Lemma 4.5, if half of the nodes are of degree at least $d_1^*$, then the attacker cannot win for any number of rounds w.p. at least $1 - \mu$. Thus, we only need to prove that if $\Delta$ is smaller than the given bound, then after $t$ rounds, for any $t \in \mathbb{N}$, more than half of the colored nodes are white w.p. at least $1 - \mu$.

Assume $t' := \min(t, t_1^*)$, where $t_1^* = (2/\alpha) \log(4/\alpha\epsilon)$. Let $V_l := \{v \in V : \deg(v) \le d_2^*\}$, for $d_2^* = 8 \log n/(\alpha\epsilon^2)$, be the set of low-degree nodes and $V_h := V \setminus V_l$ be the set of high-degree nodes. Then, we define $w_{t'}^l := |V_l \cap (\hat{W}_{t'} \setminus W_0)|$ (analogously, $b_{t'}^l := |V_l \cap (\hat{B}_{t'} \setminus B_0)|$) to be the number of non-seed low-degree nodes which are colored white (resp. black) in the first $t'$ rounds. Similarly, we define $w_{t'}^h$ and $b_{t'}^h$ for non-seed high-degree nodes.

Based on Lemma 4.2, we have $w_0 \ge b_0 + \alpha\epsilon n$ w.p. at least $1 - \exp(-\Theta(\epsilon^2 an)) \ge 1 - 1/4\sqrt{n} \ge 1 - \mu/4$. Furthermore based on Lemma 4.3, we know that $b_{t'}^h = 0$ w.p. at least $1 - 2/n \ge 1 - 1/8\sqrt{n} \ge 1 - \mu/8$. We prove that $w_{t'}^l > b_{t'}^l - \alpha\epsilon n/2$ w.p. at least $1 - \mu/4$. Note that $\hat{w}_{t'} = w_0 + w_{t'}^l + w_{t'}^h$ and $\hat{b}_{t'} = b_0 + b_{t'}^l + b_{t'}^h$. Therefore, the combination of the above three statements implies that $\hat{w}_{t'} > \hat{b}_{t'} + \alpha\epsilon n/2$ w.p. at least $1 - 3\mu/4$. If $t' = t$, then we are done. Otherwise, we have $t > t' = t_1^*$. Based on Lemma 4.4, we know that at most $\alpha\epsilon n/2$ nodes get colored after the $t_1^*$-th round w.p. at least $1 - \mu/4$. In the worst case scenario, they all are colored black. Since $\hat{w}_{t_1^*} > \hat{b}_{t_1^*} + \alpha\epsilon n/2$ w.p. at least $1 - 3\mu/4$, we can conclude that $\hat{w}_{t'} > \hat{b}_{t'}$ w.p. at least $1 - \mu$.

It remains to prove that $w_{t'}^l > b_{t'}^l - \alpha\epsilon n/2$ w.p. at least $1 - \mu/4$. Let us consider a *modified* version of our process. This is the same as the original process except that when it is time for a non-seed high-degree node to be colored, it adopts white color, regardless of the color of its neighbors. Note that based on Lemma 4.3, we know that all non-seed high-degree nodes are colored white in the original process w.p. at least $1 - \mu/8$. That is, the original process is the same as the modified one w.p. at least $1 - \mu/8$. (This allows us to consider the modified process instead, up to the error factor $\mu/8$.) Therefore, if we show that $w_{t'}^l > b_{t'}^l - \alpha\epsilon n/2$ in the modified process w.p. at least $1 - \mu/8$, we can conclude that $w_{t'}^l > b_{t'}^l - \alpha\epsilon n/2$ in the original process w.p. at least $1 - \mu/4$. (We are basically conditioning on the event that all non-seed high-degree nodes are colored white.)

Now, we prove that $w_{t'}^l > b_{t'}^l - \alpha\epsilon n/2$ in the modified process w.p. at least $1 - \mu/8$. Recall that $r_0$ denotes the number of seed nodes and define $l := |V_l \cap \cup_{j=1}^{t'} R_j|$ to be the number of low-degree nodes which are colored during rounds 1 to $t'$. (We should emphasize that both $r_0$ and $l$ are random variables. Thus to be precise, in our calculations below we need to condition on $r_0 = r'_0$ or $l = l'$ for some $r'_0, l' \in \mathbb{N}$. However for the sake of simplicity, we abuse the notation and treat $r_0$ and $l$ as fixed values and show that our arguments hold regardless of the value of $r_0$ and $l$.) Our goal is to prove that $w_{t'}^l > l/2 - \alpha\epsilon n/4$ (because this implies that $w_{t'}^l > b_{t'}^l - \alpha\epsilon n/2$ by using $l = b_{t'}^l + w_{t'}^l$) w.p. at least $1 - \mu/8$.

Let us label the seed nodes from $v_1$ to $v_{r_0}$. Corresponding to each node $v_i$, for $1 \le i \le r_0$, we define the probability space $(\Omega_i, \text{Pr}_i)$. Then, $w_{t'}^l : \Omega \to \mathbb{R}$ is defined over $\Omega$, where $(\Omega, \text{Pr})$ is the product of discrete probability spaces $(\Omega_i, \text{Pr}_i)$ for $1 \le i \le r_0$. Recall that the effect of the $i$-th coordinate is said to be at most $c_i$ if for all $\omega, \omega' \in \Omega$, which differ only in the $i$-th coordinate we have $|w_{t'}^l(\omega) - w_{t'}^l(\omega')| \le c_i$. We say a node $u$ is *affected* by $v_i$ if switching the color of $v_i$ can result in $u$ adopting a different color. Hence, $c_i$ is upper-bounded by the number of nodes in $V_l \cap \cup_{j=1}^{t'} R_j$ which are affected by $v_i$. We observe that each node $v_i$ has at most $\Delta$ low-degree neighbors in $R_1$ which might be affected by $v_i$. Each of these nodes has at most $d_2^*$ low-degree neighbors in $R_2$ which might be affected by $v_i$. (Note that by the definition, a low-degree node has degree at most $d_2^*$.) Applying this argument for $t' - 2$ more times, we can conclude that
$c_i \le 2\Delta(d_2^*)^{t'-1} \le \Delta(d_2^*)^{t'}$. Note that we do not take the high-degree nodes into account since in the modified process they are deterministically colored white.

We should mention that our goal is to apply Azuma's inequality (Theorem 1.7) and for that we need to upper-bound $\sum_{i=1}^{r_0} c_i^2$. A trivial bound is $r_0\Delta^2(d_2^*)^{2t'}$, but this is too loose for our purpose here. We give a tighter bound by using a more careful counting argument.

Let $u$ be a low-degree node in $R_j$ for some $1 \le j \le t'$. Node $u$ is affected by a node $v_i$ if at least one of its low-degree neighbors in $R_{j-1}$ is affected by $v_i$. (Again, recall that high-degree nodes choose their color deterministically, it is why we only account for low-degree ones.) Since $u$ is a low-degree node, the number of such neighbors is at most $d_2^*$. Similarly, each of these neighbors is affected by $v_i$ if at least one of its low-degree neighbors in $R_{j-2}$ is affected by $v_i$. Repeating this argument, we reach some low-degree nodes in $R_1$, which are affected by $v_i$ if they are adjacent to it. Hence, we can conclude that each low-degree node $u$ in $\cup_{j=1}^{t'} R_j$ is affected by at most $2(d_2^*)^{t'}$ nodes in $R_0$. This implies that $\sum_{i=1}^{r_0} c_i \le 2l(d_2^*)^{t'} \le 2n(d_2^*)^{t'}$.

So far we showed that $c_i \le \Delta(d_2^*)^{t'}$ and $\sum_{i=1}^{r_0} c_i \le 2n(d_2^*)^{t'}$. Thus, we have

$$ \sum_{i=1}^{r_0} c_i^2 \le \Delta(d_2^*)^{t'} \sum_{i=1}^{r_0} c_i \le 2n\Delta(d_2^*)^{2t'}. $$

Recall that

$$ \Delta \le \frac{C_{\alpha, \epsilon} n}{(\log n)^{C'_{\alpha, \epsilon} \log(4/\mu)}}, \quad d_2^* = \frac{8 \log n}{\alpha \epsilon^2}, \text{ and } t' \le \frac{2}{\alpha} \log \frac{4}{\alpha \epsilon}. $$

Therefore, for a suitable choice of $C_{\alpha, \epsilon}$ and $C'_{\alpha, \epsilon}$ we get

$$ \Delta \le \frac{\alpha^2 \epsilon^2 n}{64 \log(4/\mu) (d_2^*)^{2t'}.} $$

Thus, we have $\sum_{i=1}^{r_0} c_i^2 \le \alpha^2 \epsilon^2 n^2 / (32 \log(4/\mu))$. Furthermore, since each node in $V_l \cap \cup_{j=1}^{t'} R_j$ is white w.p. at least $1/2$, we have that $\mathbb{E}[w_{t'}^l] \ge l/2$. Now, applying Azuma's inequality (Theorem 1.7) yields

$$ \Pr[w_{t'}^l \le \frac{l}{2} - \frac{\alpha \epsilon n}{4}] \le \exp\left(-\frac{\alpha^2 \epsilon^2 n^2}{32 \sum_{i=1}^{r_0} c_i^2}\right) \\ \le \exp(-\log(4/\mu)) = \mu/4. \quad \square $$

**Tightness.** The bound $(6/\alpha\epsilon^2)\log(12/\alpha\epsilon\mu)$ in Theorem 4.1 is tight in terms of $\mu$. However, we believe the dependency on $\alpha$ and $\epsilon$ is not best possible. The upper bound on $\Delta$ is also tight in $\mu$ and the dependency on $n$ is optimal, up to the poly-logarithmic term.

Consider some arbitrary $\epsilon, \alpha, \mu \in (0, 1/2)$ and let $s = (\log(\frac{1}{2}-\epsilon)\alpha \mu) - 1$. Consider an $n$-node graph $G$ which includes a node set $S$ of size $s$ and each node in $V \setminus S$ is adjacent to all nodes in $S$. For an $(\alpha, \epsilon)$-weak attacker, we have $S \subset B_0$ w.p. $(\alpha(1/2 - \epsilon))^s > \mu$. We observe that if $S \subseteq B_0$, then all uncolored nodes adopt black color in the first round. Then, the attacker wins w.p. more than $\mu$. Note that all nodes in $G$ are of degree at least $s$ which is equal to $C''\log(1/\mu)$ for a suitable choice of $C''_{\alpha, \epsilon} > 0$. Therefore, the bound $(6/\alpha\epsilon^2)\log(12/\alpha\epsilon\mu)$ in Theorem 4.1 is tight in terms of $\mu$.

Now, consider an $n$-node graph $G'$, which is the union of $s$ star graphs, each of size $n/s$. Again, an $(\alpha, \epsilon)$-weak attacker will select all the $s$ internal nodes to be seed nodes and color
them black w.p. $(\alpha(1/2 - \epsilon))^s > \mu$. If all the internal nodes are black initially, then all the uncolored nodes adopt black color in the next round. Therefore, the attacker wins w.p. more than $\mu$. Note that the maximum degree of $G'$ is equal to $(n/s) - 1 = C'''_{\alpha,\epsilon}n/\log(1/\mu)$ for some constant $C'''_{\alpha,\epsilon} > 0$. Therefore, the upper bound on $\Delta$ in Theorem 4.1 is tight in terms of $\mu$. The dependency on $n$ is also optimal, up to the term $(\log n)^{C'_{\alpha,\epsilon}}$. Recall from the proof of Theorem 4.1 that $C'_{\alpha,\epsilon} = (4/\alpha)\log(4/\alpha\epsilon)$. We can replace $C'_{\alpha,\epsilon}$ with $\log C'_{\alpha,\epsilon}$ by applying a fairly simple idea. However, to entirely get rid of this poly-logarithmic term, one perhaps needs proof techniques beyond the ones used in this paper.

# 5 Stabilization Time

In this section, we prove tight bounds on the stabilization time of our opinion diffusion process. Let $G$ be a connected graph. (Otherwise, we just need to consider the maximum stabilization time among all the connected components.) Note that stabilization time is only a function of the choice of seed nodes, not their color. After $t$ rounds, all nodes whose distance from the seed set is at most $t$ will be colored. Therefore, the stabilization time is upper-bounded by the diameter $D(G)$, which is the greatest distance between any pair of nodes in $G$. This bound is obviously tight. Consider two nodes $v, u$ such that $d(v, u) = D$. If $v$ is the only seed node, then it takes $D$ rounds until node $u$ is colored.

What if the seed set is chosen randomly (as in case of a weak attacker)? We prove that if each node is chosen to be a seed node independently w.p. $\alpha$, then a.a.s. the stabilization time is between $\Omega(\log_\Delta \log n^{1/\alpha})$ (see Theorem 5.4) and $O((1/\alpha\delta)\log n)$ (see Theorem 5.1). $\delta$ denotes the minimum degree in $G$.

**Theorem 5.1** For a graph $G = (V, E)$, if each node is a seed node independently w.p. $\alpha$, then the stabilization time is in $O((1/\alpha\delta)\log n)$ a.a.s.

To prove Theorem 5.1, we first provide Lemmas 5.2 and 5.3.

**Lemma 5.2** For a node $v$ in a graph $G = (V, E)$ and $t \in \mathbb{N}$, if $N_t(v) \neq \emptyset$, then $|\hat{N}_t(v)| \ge (t-1)\delta/3$.

**Proof.** Consider a triple $(N_{3i}(v), N_{3i+1}(v), N_{3i+2}(v))$ for some $0 \le i \le \lfloor (t+1)/3 \rfloor - 1$. Since $N_{3i+1}(v)$ is non-empty, it must include a node $u$. All the neighbors of $u$ are in this triple, i.e., $N(u) \subset N_{3i}(v) \cup N_{3i+1}(v) \cup N_{3i+2}(v)$. Since $\deg(u) = |N(u)| \ge \delta$, the triple must include at least $\delta + 1$ nodes. Thus, we get $|\hat{N}_t(v)| \ge \lfloor \frac{t+1}{3} \rfloor (\delta + 1) \ge (t-1)\delta/3$. $\square$

**Lemma 5.3** Assume each node in a graph $G = (V, E)$ is a seed node independently w.p. $\alpha$. Then, a.a.s. there is no node $v$ such that $|\hat{N}_t(v)| \ge (2/\alpha)\log n$ and $\hat{N}_t(v) \cap R_0 = \emptyset$.

**Proof.** The probability that $\hat{N}_t(v) \cap R_0 = \emptyset$ is equal to

$$ (1 - \alpha)^{|\hat{N}_t(v)|} \le (1 - \alpha)^{\frac{2\log n}{\alpha}} \le \exp(-2\log n) = \frac{1}{n^2}. $$

Thus, a union bound implies that w.p. $1 - 1/n$ there is no node $v$ such that $|\hat{N}_t(v)| \ge \frac{2}{\alpha}\log n$ and $\hat{N}_t(v) \cap R_0 = \emptyset$. $\square$
**Proof of Theorem 5.1.** Let $t_2^* := (6/\alpha\delta) \log n + 1$. If $N_{t_2^*}(v) = \emptyset$ for a node $v \in V$, it will be colored in less than $t_2^*$ rounds or it will never be colored. On the other hand, if $N_{t_2^*}(v) \neq \emptyset$, by Lemma 5.2 we have $|\hat{N}_{t_2^*}(v)| \ge (t_2^* - 1)\delta/3 = (2/\alpha) \log n$. By Lemma 5.3, we know that a.a.s. every node whose $t_2^*$-neighborhood is of size at least $(2/\alpha) \log n$ has a seed node in its $t_2^*$-neighborhood, and thus is colored in at most $t_2^*$ rounds. Hence, a.a.s. after $t_2^* = (6/\sigma\alpha) \log n+1 = \mathcal{O}((1/\alpha\delta) \log n)$ rounds every node is colored or it will never be colored. $\square$

**Tightness.** We prove that the upper bound in Theorem 5.1 is tight, up to a constant factor. For an arbitrary integer $\delta \ge 1$, let $C_n^\delta$ be the $\delta$-th power of a cycle $C_n$, which is a graph on the same node set, but two nodes are adjacent if their distance is between 1 and $\delta$ in $C_n$. (For example, $C_n^1 = C_n$.) Assume that we select each node to be a seed node independently w.p. $\alpha$. Since $C_n^\delta$ is $2\delta$-regular, based on Theorem 5.1 the stabilization time is in $\mathcal{O}((1/\alpha\delta) \log n)$ a.a.s. On the other hand, we prove that there is at least one node whose $t_3^*$-neighborhood does not include any seed node a.a.s. for $t_3^* := (1/16\alpha\delta) \log_2 n - 1$. This implies that this node will be colored after the $t_3^*$-th round, i.e., the process takes more than $t_3^* = \Omega((1/\alpha\delta) \log n)$ rounds to end. Thus, the upper bound given in Theorem 5.1 is asymptotically tight.

We observe that for a node $u$ in $C_n^\delta$, we have $|\hat{N}_{t_3^*}(u)| = 2\delta t_3^* + 1 \le (1/8\alpha) \log_2 n$. Thus, we can select $\sqrt{n}$ nodes $u_1, \dots, u_{\sqrt{n}}$ whose $t_3^*$-neighborhood is pair-wise disjoint. Now, we define Bernoulli random variable $x_i$ to be 1 if and only if there is no seed node in $\hat{N}_{t_3^*}(u_i)$. Then, we have

$$ \Pr[x_i = 1] \ge (1 - \alpha)^{\frac{\log_2 n}{8\alpha}} \ge 4^{-\frac{\log_2 n}{8}} = n^{-\frac{1}{4}}. $$

Let $X := \sum_{i=1}^{\sqrt{n}} x_i$. Since the $t_3^*$-neighborhood of $u_i$ is pair-wise disjoint, we get

$$ \Pr[X = 0] \le (1 - n^{-\frac{1}{4}})^{\sqrt{n}} \le \exp(-n^{\frac{1}{4}}). $$

Thus, a.a.s. there is a node $u_i$ whose $t_3^*$-neighborhood does not include any seed node.

**Theorem 5.4** For a connected graph $G = (V, E)$, if each node is a seed node independently w.p. $\alpha$, then the stabilization time is in $\Omega(\log_\Delta \log n^{\frac{1}{\alpha}})$ a.a.s.

**Proof.** Let $t_4^* := \log_\Delta \log_2 n^{\frac{1}{16\alpha}}$. We first want to show that there is a large set of nodes whose $t_4^*$-neighborhood is pair-wise disjoint. To prove that, consider the following recursive procedure. Suppose that initially all nodes are *unmarked* and consider a set $U = \emptyset$. As long as there is an unmarked node $u$, add it to $U$ and mark all nodes in $\hat{N}_{2t_4^*}(u)$. By construction, the $t_4^*$-neighborhood of each pair of nodes in $U$ is disjoint. Furthermore, when the procedure ends, $U$ includes at least $\sqrt{n}$ nodes since we mark at most $2\Delta^{2t_4^*} = 2\log_2 n^{\frac{1}{16\alpha}}$ (i.e., poly-logarithmically many) nodes every time we add a node to $U$ and we start with $n$ unmarked nodes.

So far, we proved that there exist $\sqrt{n}$ nodes $u_1, \dots, u_{\sqrt{n}}$ whose $t_4^*$-neighborhood is pair-wise disjoint. Now, we define Bernoulli random variable $x_i$ to be 1 if and only if $\hat{N}_{t_4^*}(u_i) \cap R_0 = \emptyset$. Since $|\hat{N}_{t_4^*}(u_i)| \le 2\Delta^{t_4^*} = (1/8\alpha) \log_2 n$, we have

$$ \Pr[x_i = 1] \ge (1 - \alpha)^{\frac{\log_2 n}{8\alpha}} \ge 4^{-\frac{\log_2 n}{8}} = n^{-\frac{1}{4}}. $$

Let $X := \sum_{i=1}^{\sqrt{n}} x_i$. Since the $t_4^*$-neighborhood of $u_i$ is pair-wise disjoint, $\Pr[X = 0] \le (1 - n^{-1/4})^{\sqrt{n}} \le \exp(-n^{1/4})$. Thus, a.a.s. there is a node $u_i$ such that $\hat{N}_{t_4^*}(u_i) \cap R_0 = \emptyset$, which implies that $u_i$ is colored after the $t_4^*$-th round. Hence, the stabilization time is at least $t_4^* = \Omega(\log_\Delta \log n^{\frac{1}{\alpha}})$. $\square$
**Tightness.** Consider an $n$-node complete $d$-ary tree $T = (V, E)$ for an arbitrary integer $d \ge 2$. We prove that the stabilization time is in $O(\log_d \log n^{1/\alpha})$ a.a.s. when we select each node to be a seed node independently w.p. $\alpha > 0$. This implies that the bound in Theorem 5.4 is asymptotically tight.

Let $L_i$ denote the set of nodes in depth $i$ and assume that $t_5^* := \log_d \log n^{2/\alpha} + 1$. Consider an arbitrary node $v \in V$. We claim that $|\hat{N}_{2t_5^*}(v)| \ge (2/\alpha) \log n$. If $v \in L_i$ for some $i \le \lfloor \log_d n \rfloor - t_5^*$, then it has at least $d^{t_5^*-1} = (2/\alpha) \log n$ nodes in its subtree which are in distance at most $t_5^*$ from $v$. Thus, we have $|\hat{N}_{2t_5^*}(v)| \ge |\hat{N}_{t_5^*}(v)| \ge (2/\alpha) \log n$. On the other hand, if $v \in L_i$ for some $i > \lfloor \log_d n \rfloor - t_5^*$, then it has a node $u$ in its $t_5^*$-neighborhood which is in $L_j$ for some $j \le \lfloor \log_d n \rfloor - t_5^*$. Since $|\hat{N}_{t_5^*}(u)| \ge (2/\alpha) \log n$ and $\hat{N}_{t_5^*}(u) \subseteq \hat{N}_{2t_5^*}(v)$, we have $|\hat{N}_{2t_5^*}(v)| \ge (2/\alpha) \log n$.

So far, we showed that $|\hat{N}_{2t_5^*}(v)| \ge (2/\alpha) \log n$ for any node $v$. Applying Lemma 5.3 implies that a.a.s. each node has a seed node in its $2t_5^*$-neighborhood. Therefore, a.a.s. in at most $2t_5^* = O(\log_d \log n^{1/\alpha})$ rounds, all nodes are colored and the process is over.

# 6 Hardness Results

Assume you are given a graph $G = (V, E)$ and some $t \in \mathbb{N}$. The goal is to determine whether there is a choice of the seed set for which the process needs exactly $t$ rounds to end. This problem is polynomial-time solvable. If $t > D$, where $D$ is the diameter of $G$, then the answer is No since the stabilization time is upper-bounded by $D$. If $t \le D$, then the answer is Yes. Assume that $d(v, u) = D$ for some nodes $v, u \in V$. Then, if the seed set is equal to $\hat{N}_{D-t}(v)$, the process takes exactly $t$ rounds.<fnref n="2" /> However, if in the above problem we require that the seed set must be of a given size $s$, then the problem becomes NP-hard. It is because the *t-hop dominating set problem*, which is proven to be NP-hard by [8], can be reduced to this problem. Assume we are given a graph $G$ and integers $t, s$ as input. In the *t*-hop dominating set problem, the task is to decide whether there is a node set $S \subseteq V$ of size $s$ such that $d(S, v) \le t$ for any $v \in V$. We observe that the answer to this problem is Yes if and only if there is a seed set of size $s$ for which the process takes at most $t$ rounds. Hence, this problem can be reduced to our stabilization time problem.

Now, assume that you are given an $n$-node graph $G$ and some integers $b, w$, and $t$. Your task is to choose a seed set of $b$ black nodes and $w$ white nodes such that $\hat{w}_t$ is as small as possible. (This is similar to what a strong attacker aims to do.) We call this the Minimum Influence (MI) problem.

**MINIMUM INFLUENCE (MI)**

*Instance:* Graph $G = (V, E)$, and $b, w, t \in \mathbb{N}$.

*Output:* Minimum expected number of white nodes after $t$ rounds (i.e., $\hat{w}_t$) if $b_0 = b$ and $w_0 = w$.

**Theorem 6.1** Let $\mathcal{A}$ be a polynomial-time $\beta$-approximation algorithm for the MI problem. Then, $\beta > n^{1-\zeta}$ for any $\zeta > 0$ unless $P=NP$.

**Proof.** Assume that there is a polynomial-time $\beta$-approximation algorithm $\mathcal{A}$ which solves the MI problem, for $\beta = n^{1-\zeta}$ and some $\zeta > 0$. Then, we prove that there exists a polynomial-time algorithm for the *clique problem*, which is one of Karp's 21 NP-complete problems [29]. In

<footnote n="2">²If we replace the term “exactly” with “at most” in the problem statement it still remains polynomial time solvable. This is because the answer is always Yes. If we replace with “at least” instead, again the problem is polynomial time solvable because the answer is Yes for $t \ge D$ and No for $t > D$.</footnote>
the clique problem, we are given a graph $G'$ and an integer $k$ as the input and the task is to determine whether $G'$ has a clique of size $k$ or not.

Let an $n'$-node graph $G'$ and an integer $k$ be the input of the clique problem. We will describe an $n$-node graph $G$, which can be constructed in polynomial time. Then, we prove that the solution of the MI problem on $G$ and for $b = k$, $w = \binom{k}{2}$, and $t = 2$ is $inom{k}{2}$ if $G'$ has a clique of size $k$ and more than $n^{1-\zeta}\binom{k}{2}$ if it does not. Hence, the output of algorithm $\mathcal{A}$ for $G$, $b = k$, $w = \binom{k}{2}$, and $t = 2$ is between $\binom{k}{2}$ and $n^{1-\zeta}\binom{k}{2}$ if and only if $G'$ has a clique of size $k$. This implies that we have a polynomial-time algorithm for the clique problem, which is not possible unless P=NP.

Now, let us explain how we construct $G$, step by step. Consider a copy of $G'$ on the node set $V' = \{v_1, \cdots, v_{n'}\}$. Let $\{v_i, v_{i'}\}$ be an edge in this graph, then we remove this edge and instead we add a new node $u$ and two edges $\{u, v_i\}$ and $\{u, v_{i'}\}$. Let us label these newly added nodes from $u_1$ to $u_{m'}$, where $m'$ is the number of edges in $G'$. Furthermore, corresponding to each node $v_i$ for $1 \le i \le n'$ (analogously, node $u_j$ for $1 \le j \le m'$) we add a node set $V_i$ (resp. $U_j$) of size $n'^{4/\zeta}$ and add a clique between nodes in $\{v_i\} \cup V_i$ (resp. $\{u_j\} \cup U_j$). To complete the construction of graph $G$, corresponding to each node $u_j$ for $1 \le j \le m'$ we add a node $q_j$ and edge $\{u_j, q_j\}$. Therefore, nodes in $\{v_i\} \cup V_i$ induce a clique of size $s+1$ and nodes in $\{u_j, q_j\} \cup U_j$ induce a clique of size $s+1$ and a leaf attached to it. Overall, graph $G$ has $n = n'(s+1) + m'(s+2) \le n'^2 s = n'^{2+4/\zeta}$ nodes.

<figure><img src="image_4.png" /><figcaption>Figure 2: An example of our transformer. On the left, a graph $G'$ with $n' = 4$ nodes and $m' = 5$ edges. On the right, graph $G$ constructed from $G'$. The node sets $V_i$ and $U_j$ are drawn only for $V_1$ and $U_1$. Leaf nodes $q_j$ are also only drawn for $u_1$ here.</figcaption></figure>

Assume that $G'$ has a clique of size $k$. Then, we show that the MI problem for $b = k$, $w = \binom{k}{2}$, and $t = 2$ on graph $G$ has a solution of size $\binom{k}{2}$. Assume that a node set $Z \subseteq V'$ induces a clique of size $k$ in $G'$. By our construction, the node set $Z$ also exists in $G$, but each edge of the clique has been replaced with a gadget on nodes in $\{u_j, q_j\} \cup U_j$ for some $1 \le j \le m'$. Let $U_Z$ and $Q_Z$ be the node sets which include all of these $u_j$s and $q_j$s respectively. We know that $|Q_Z| = \binom{k}{2}$ since $Z$ induces a clique in $G'$. Assume that we color all nodes in $Z$ black and all
nodes in $Q_Z$ white. Thus, there are $k$ black nodes and $\binom{k}{2}$ white nodes. We observe that each node $u_j \in U_Z$ is colored black in the next round since it has two black neighbors in $Z$ and only one white neighbor, namely $q_j$. Since $u_j$ is the only neighbor of $q_j$, the number of white nodes remains unchanged after any number of rounds.

It remains to prove that if $G'$ has no clique of size $k$, then the solution to the MI problem for $b = k$, $w = \binom{k}{2}$, and $t = 2$ on $G$ is at least $s/2$. Recall that $n \le n'^{2+\frac{4}{\zeta}}$ and $s = n'^{\frac{4}{\zeta}}$. Thus, we have

$$ \frac{s}{2} \ge \binom{n'}{2} n'^{\frac{4}{\zeta}-2} \ge \binom{k}{2} n'^{(\frac{4}{\zeta}+2)(1-\zeta)} > \binom{k}{2} n^{1-\zeta}. $$

For the sake of contradiction, assume that there is an initial coloring of $G$ with $b = k$ black nodes and $w = \binom{k}{2}$ white nodes such that $\mathbb{E}[\hat{w}_2] < s/2$. Then, let us partition the nodes of $G$ into four different types of node sets. For $1 \le i \le n'$, a set $\{v_i\} \cup V_i$ is a $v^b$-node set if $v_i$ is colored black initially and it is a $v^w$-node set otherwise. Furthermore for $1 \le j \le m'$, a set $\{u_j, q_j\} \cup U_j$ is a $u^b$-node set if both neighbors of $u_j$ in $V'$ are black and it is a $u^w$-node set otherwise. Note that this way we partition the nodes of $G$ into $n' + m'$ node sets.

For a node set $A$, let $b(A)$ and $w(A)$ denote the number of black and white nodes in $A$ in the initial coloring. We prove that

* $w(A) \le b(A)$ for a $v^w$-node set $A$

* $w(A) \le b(A) - 1$ for a $v^b$-node set $A$

* $w(A) \le b(A)$ for a $u^w$-node set $A$

* $w(A) \le b(A) + 1$ for a $u^b$-node set $A$.

Let $g$ denote the number of white nodes minus the number of black ones in the initial coloring. We want to find an upper bound on $g$. We define $n_{vb}$ and $n_{ub}$ to be the number of $v^b$-node sets and $u^b$-node sets, respectively. The combination of the above four claims implies that $g \le n_{ub} - n_{vb}$. If $n_{vb} = k$, then $n_{ub} \le \binom{k}{2} - 1$. This is because $G'$ has no clique of size $k$ and thus there cannot be more than $\binom{k}{2} - 1$ $u_j$ nodes such that both of their neighbors in $V'$ are black. Hence, in this case $g < \binom{k}{2} - k$. If $n_{vb} = k'$ for some $k' < k$, then $g \le \binom{k'}{2} - k' < \binom{k}{2} - k$. (We used the fact that $\binom{k'}{2} - k' < \binom{k}{2} - k$ for $k' < k$.) Thus, we proved that $g < \binom{k}{2} - k$. This contradicts our assumption that there are $k$ black nodes and $\binom{k}{2}$ white nodes initially. Therefore, we can conclude that there is no initial coloring with $b_0 = k$ and $w_0 = \binom{k}{2}$ such that $\mathbb{E}[\hat{w}_2] < s/2$.

Now, we prove the above four claims regarding the relation of $w(A)$ and $b(A)$, one by one. First, consider a $v^w$-node set $A = \{v_i\} \cup V_i$. We must have $w(A) \le b(A)$ because otherwise all uncolored nodes in $A$ choose white in the next round. In that case, we will have more than $s/2$ white nodes since $|A| = s + 1$.

Consider a $v^b$-node set $A = \{v_i\} \cup V_i$. If $w(A) \ge b(A)$, then the expected number of white nodes in $A$ after one round is at least $|A|/2 = (s+1)/2 > s/2$. Thus, we must have $w(A) \le b(A) - 1$.

Consider a $u^w$-node set $A = \{u_j, q_j\} \cup U_j$. We prove that if $w(A) \ge b(A) + 1$, then in expectation there are more than $s/2$ white nodes in two rounds (which implies that we must have $w(A) \le b(A)$). Obviously, we have $w(A \setminus \{q_j\}) \ge b(A \setminus \{q_j\})$. If there is at least one colored node in $A \setminus \{q_j\}$, then in the next round at least $|A \setminus \{q_j\}|/2 = (s+1)/2 > s/2$ nodes will be white in expectation. Otherwise, all nodes in $A \setminus \{q_j\}$ are uncolored and $q_j$ is white. Note that since $A$ is a $u^w$-node set, at most one of the $u_j$'s neighbors in $V'$ is black. Thus, w.p. at least
$1/2$, after one round $u_j$ becomes white and after another round all nodes in $A$ will be colored white. Thus, the expected number of white nodes after two rounds is at least $|A|/2 > s/2$.

Finally, consider a $u^b$-node set $A$. If $w(A) \ge b(A) + 2$, then $w(A \setminus \{q_j\}) \ge b(A \setminus \{q_j\}) + 1$. In that case, all uncolored nodes in $A \setminus \{q_j\}$ become white in the next round; that is, there will be more than $s/2$ white nodes after one round. Thus, we must have $w(A) \le b(A) + 1$. $\square$

# 7 Conclusion

It would be interesting to study other variants of our model or attackers. Our results apply to some other settings with some minor changes. For example, our propositions regarding the attackers should still hold if in each round only a random subset of nodes update their color or if each node does not follow the majority rule with some noise probability smaller than $\epsilon$. However, our proof techniques cannot immediately be applied to characterize graph structures resilient to an attacker which can choose the order of updates or add/delete edges. Hence, this is a potential avenue for further research.

The maximum degree in most of real-world social graphs is not too large, which makes them fairly resilient to a moderate and weak attacker. However, they are usually far from being regular or expander, and thus are vulnerable to a strong attacker. A counter-measure might be to add an Erdős-Rényi random graph on top of the underlying graph structure. In the real world, this is essentially the same as asking agents to choose a fraction of their connections at random. Our preliminary experiments on data from SNAP [33] suggest that such modification enhances the resilience significantly. However, a detailed and formal investigation of this subject is left for future research.

At first glance, our inapproximability result in Theorem 6.1 might create the confusion that a strong attacker is computationally impotent. However, it is possible that there is an optimal strategy for special classes of graphs; in particular, for the ones which commonly occur in the real world. Furthermore, assume that in the MI problem, the seed set is given as a part of the input and the attacker's task is only to decide on the color of the seed nodes. Then, the problem can be reduced to the *partial set multi-cover problem* [45], which has a constant factor approximation algorithm. Therefore, if the attacker has an effective heuristic method to select the seed set, then it can find a reasonably efficient solution. Further investigation of the computational power of an attacker in our model is a prospective research direction.

# References

[1] ABEBE, R., KLEINBERG, J., PARKES, D., AND TSOURAKAKIS, C. E. Opinion dynamics with varying susceptibility to persuasion. In *Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining* (2018), pp. 1089–1098.

[2] AMINI, H., AND FOUNTOULAKIS, N. Bootstrap percolation in power-law random graphs. *Journal of Statistical Physics* 155, 1 (2014), 72–92.

[3] ANAGNOSTOPOULOS, A., BECCHETTI, L., CRUCIANI, E., PASQUALE, F., AND RIZZO, S. Biased opinion dynamics: When the devil is in the details. In *IJCAI-20* (2020), pp. 53–59.

[4] AULETTA, V., CARAGIANNIS, I., FERRAIOLI, D., GALDI, C., AND PERSIANO, G. Minority becomes majority in social networks. In *WINE-15* (2015), pp. 74–88.
[5] AULETTA, V., FERRAIOLI, D., AND GRECO, G. Reasoning about consensus when opinions diffuse through majority dynamics. In *IJCAI-18* (2018), pp. 49–55.

[6] BALISTER, P., BOLLOBÁS, B., JOHNSON, J. R., AND WALTERS, M. Random majority percolation. *Random Structures & Algorithms* 36, 3 (2010), 315–340.

[7] BALOGH, J., AND PITTEL, B. G. Bootstrap percolation on the random regular graph. *Random Structures & Algorithms* 30, 1-2 (2007), 257–286.

[8] BASUCHOWDHURI, P., AND MAJUMDER, S. Finding influential nodes in social networks using minimum k-hop dominating set. In *ICAA-14* (2014), pp. 137–151.

[9] BEN-NAIM, E. Opinion dynamics: rise and fall of political parties. *EPL (Europhysics Letters)* 69, 5 (2005), 671.

[10] BERGER, E. Dynamic monopolies of constant size. *Journal of Combinatorial Theory, Series B* 83, 2 (2001), 191–200.

[11] BHARATHI, S., KEMPE, D., AND SALEK, M. Competitive influence maximization in social networks. In *International workshop on web and internet economics* (2007), Springer, pp. 306–311.

[12] BREDERECK, R., AND ELKIND, E. Manipulating opinion diffusion in social networks. In *IJCAI-17* (2017), pp. 894–900.

[13] CHEN, N. On the approximability of influence in social networks. *SIAM Journal on Discrete Mathematics* 23, 3 (2009), 1400–1415.

[14] CHISTIKOV, D., LISOWSKI, G., PATERSON, M., AND TURRINI, P. Convergence of opinion diffusion is pspace-complete. In *AAAI-20* (2020), pp. 7103–7110.

[15] CHOPIN, M., NICHTERLEIN, A., NIEDERMEIER, R., AND WELLER, M. Constant thresholds can make target set selection tractable. *Theory of Computing Systems* 55 (2014), 61–83.

[16] CORÒ, F., D'ANGELO, G., AND VELAJ, Y. Recommending links to control elections via social influence. *Algorithms* 12, 10 (2019), 207.

[17] DUBHASHI, D. P., AND PANCONESI, A. *Concentration of measure for the analysis of randomized algorithms*. Cambridge University Press, 2009.

[18] FALISZEWSKI, P., GONEN, R., KOUTECKÝ, M., AND TALMON, N. Opinion diffusion and campaigning on society graphs. *Journal of Logic and Computation* 32, 6 (2022), 1162–1194.

[19] FOGELMAN, F., GOLES, E., AND WEISBUCH, G. Transient length in sequential iteration of threshold functions. *Discrete Applied Mathematics* 6, 1 (1983), 95–98.

[20] FRIEDMAN, J. A proof of Alon's second eigenvalue conjecture. In *STOC-03* (2003), pp. 720–724.

[21] FRISCHKNECHT, S., KELLER, B., AND WATTENHOFER, R. Convergence in (social) influence networks. In *DISC-13* (2013), pp. 433–446.
[22] GÄRTNER, B., AND ZEHMAKAN, A. N. Majority model on random regular graphs. In *LATIN 2018: Theoretical Informatics: 13th Latin American Symposium, Buenos Aires, Argentina, April 16-19, 2018, Proceedings 13* (2018), Springer, pp. 572–583.

[23] GÄRTNER, B., AND ZEHMAKAN, A. N. Threshold behavior of democratic opinion dynamics. *Journal of Statistical Physics* (2020), 1–25.

[24] GOLES, E., AND OLIVOS, J. Periodic behaviour of generalized threshold functions. *Discrete mathematics* 30, 2 (1980), 187–189.

[25] GRANDI, U., KANESH, L., LISOWSKI, G., SRIDHARAN, R., AND TURRINI, P. Identifying and eliminating majority illusion in social networks. In *Proceedings of the AAAI Conference on Artificial Intelligence* (2023), vol. 37, pp. 5062–5069.

[26] GRANDI, U., STEWART, J., AND TURRINI, P. The complexity of bribery in network-based rating systems. In *AAAI-18* (2018), pp. 1047–1054.

[27] HOORY, S., LINIAL, N., AND WIGDERSON, A. Expander graphs and their applications. *Bulletin of the American Mathematical Society* 43, 4 (2006), 439–561.

[28] KAASER, D., MALLMANN-TRENN, F., AND NATALE, E. On the voting time of the deterministic majority process. In *MFCS-16* (2016).

[29] KARP, R. M. On the computational complexity of combinatorial problems. *Networks* 5, 1 (1975), 45–68.

[30] KEMPE, D., KLEINBERG, J., AND TARDOS, É. Maximizing the spread of influence through a social network. In *KDD-03* (2003), pp. 137–146.

[31] LE, C. M., LEVINA, E., AND VERSHYNIN, R. Concentration and regularization of random graphs. *Random Structures & Algorithms* 51, 3 (2017), 538–561.

[32] LESFARI, H., GIROIRE, F., AND PÉRENNES, S. Biased majority opinion dynamics: Exploiting graph $k$-domination. In *IJCAI 2022-International Joint Conference on Artificial Intelligence* (2022).

[33] LESKOVEC, J., AND KREVL, A. SNAP Datasets: Stanford large network dataset collection. http://snap.stanford.edu/data, June 2014.

[34] LI, S., AND ZEHMAKAN, A. N. Graph-based generalization of galam model: Convergence time and influential nodes. *Physics* 5, 4 (2023), 1094–1108.

[35] LIU, S., JIANG, C., LIN, Z., DING, Y., DUAN, R., AND XU, Z. Identifying effective influencers based on trust for electronic word-of-mouth marketing: A domain-aware approach. *Information sciences* 306 (2015), 34–52.

[36] MISHRA, S., RADHAKRISHNAN, J., AND SIVASUBRAMANIAN, S. On the hardness of approximating minimum monopoly problems. In *FSTTCS-02* (2002), pp. 277–288.

[37] MUSTAFA, N. H., AND PEKEČ, A. Majority consensus and the local majority rule. In *ICALP-01* (2001), pp. 530–542.
[38] N ZEHMAKAN, A., AND GALAM, S. Rumor spreading: A trigger for proliferation or fading away. *Chaos: An Interdisciplinary Journal of Nonlinear Science* 30, 7 (2020).

[39] OUT, C., AND ZEHMAKAN, A. N. Majority vote in social networks: Make random friends or be stubborn to overpower elites. *arXiv preprint arXiv:2109.14265* (2021).

[40] PASTOR-SATORRAS, R., AND VESPIGNANI, A. Epidemic spreading in scale-free networks. *Physical review letters* 86, 14 (2001), 3200.

[41] PELEG, D. Local majority voting, small coalitions and controlling monopolies in graphs: A review. In *SIROCCO-97* (1997), pp. 152–169.

[42] PELEG, D. Size bounds for dynamic monopolies. *Discrete Applied Mathematics* 86, 2-3 (1998), 263–273.

[43] ROGERS, E. M. *Diffusion of innovations*. Simon and Schuster, 1962.

[44] SCHOENEBECK, G., AND YU, F.-Y. Consensus of interacting particle systems on erdős-rényi graphs. In *SODA-18* (2018), pp. 1945–1964.

[45] SHI, Y., RAN, Y., ZHANG, Z., WILLSON, J., TONG, G., AND DU, D.-Z. Approximation algorithm for the partial set multi-cover problem. *Journal of Global Optimization* 75, 4 (2019), 1133–1146.

[46] YIN, X., WANG, H., YIN, P., AND ZHU, H. Agent-based opinion formation modeling in social network: A perspective of social psychology. *Physica A: Statistical Mechanics and its Applications* 532 (2019), 121786.

[47] ZAREIE, A., SHEIKHAHMADI, A., AND JALILI, M. Identification of influential users in social networks based on users’ interest. *Information Sciences* 493 (2019), 217–231.

[48] ZEHMAKAN, A. N. *On the spread of information through graphs*. PhD thesis, ETH Zurich, 2019.

[49] ZEHMAKAN, A. N. Opinion forming in erdős-rényi random graph and expanders. *Discrete Applied Mathematics* 277 (2020), 280–290.

[50] ZEHMAKAN, A. N. Majority opinion diffusion in social networks: An adversarial approach. In *Proceedings of the AAAI Conference on Artificial Intelligence* (2021), vol. 35, pp. 5611–5619.

[51] ZEHMAKAN, A. N. Majority opinion diffusion: when tie-breaking rule matters. *Autonomous Agents and Multi-Agent Systems* 38, 1 (2024), 21.

[52] ZHU, L., AND ZHANG, Z. A nearly-linear time algorithm for minimizing risk of conflict in social networks. In *Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining* (2022), pp. 2648–2656.