Majority Vote in Social Networks: Make Random Friends or Be Stubborn to Overpower Elites

1 Introduction

When facing a decision or forming an opinion about a topic such as a consumer product, a technological innovation, or a political event, humans often consult friends, family or others in their close circle for advice. Additionally, we often consider the opinions of the figures whose opinions we value in some way; for example, politicians we usually agree with, celebrities whom we look up to, or well-established scientists. In this way, an individual's opinion is influenced by the opinions of the people around her. Furthermore, due to the rise of online social networking, opinions are formed and changed at a higher pace. Consequently, there has been a growing demand for a quantitative understanding of the opinion forming process.

Recently, within the field of computer science, especially computational social choice and algorithmic game theory, there has been a rising interest in developing and studying mathematical opinion diffusion models, which aim to mimic the process of opinion forming in a society. At a high level of abstraction, in these models one usually consider a graph G and some initial coloring of the nodes, where each node is colored either black or white. This graph is meant to represent a social network, in which the agents are modeled as nodes and an edge between two nodes corresponds to a relation between the respective agents, e.g. friendship, common interests, or advice. The color of a node represents its opinion on an innovation or a political party, etc. After initialization, in each round a group of nodes update their color based on a predefined rule.

Plentiful instances of the aforementioned abstract model have been introduced and studied. Among them, the majority model has attracted considerable attention, cf. [Auletta et al., 2015]. In the majority model, for a graph G and an initial coloring, in each round all nodes simultaneously update their color to the most frequent color in their neighborhood. In case of a tie, a node keeps its current color. We also consider the (ψ1, ψ2)-majority model, for some ψ1, ψ2 > 1/2. Here, a black (resp. white) node changes its color if at least ψ1 (resp. ψ2) fraction of its neighbors hold the opposite color from itself. We observe that this is the same as the majority model for ψ1 = ψ2 = ψ for a ψ slightly larger than 1/2.

Several different variants of the majority model have been studied by prior work (cf. [Keller et al., 2014]). We will focus on the following two variants. Assume that each node v has an influence factor r(v). Here also each node chooses the majority color, but it counts the color of a neighbor v, r(v) times. By default we assume that r(v) = 1 for each node v, otherwise it is mentioned explicitly. Note that if all nodes have influence factor one, we recover the majority model. Secondly, we consider the variant in which we assign a stubbornness factor γ(v) ∈ (0, 1) to each node v. Then, a node v changes its color if at least γ(v) fraction of its neighbors have the opposite color. We observe that if we assign a fixed stubbornness factor γ to all nodes, this would coincide with the (ψ1, ψ2)-majority model for ψ1 = ψ2 = γ.

All the updating rules that we study in this paper are deterministic. Furthermore, for an n-node graph G, there are 2n possible colorings. Therefore, after at most 2n rounds the process reaches a cycle of colorings. The number of rounds the process needs to reach the cycle and the length of the cycle are called the stabilization time and period of the process. We say a color (black or white) wins if more than half of the nodes share that color in the final configuration.

Moreover, a color takes over if all nodes share that color in the final configuration. We say a set of nodes form a white/black coalition if they are all white/black. A node set S is said to be a winning set (resp. dynamo) if black color wins (resp. takes over) once nodes in S form a black coalition.

1.1 Our Contribution

Question 1. What is the number of black nodes required for the black color to win or take over? Alternatively, more realistically speaking, if a marketing campaign can convince a group of individuals to adopt a new product, and the goal is to trigger a large cascade of further adoptions building on collective decision-making, which set of individuals should it target and how large this set needs to be? When considering graphs of real world Social Networks (SNs), [Avin et al., 2019] experimentally observed that in such graphs, if a small set of nodes (e.g. 1% of nodes) with the highest degrees form a black coalition and have an influence factor slightly larger than the rest of nodes, the black color wins. Such a small set of high-degree nodes are meant to approximate the elites, which are a relatively small and well-connected set of individuals (i.e., nodes) with substantial economic or social power, cf. [Avin et al., 2017].

Several random graph models have been introduced to simulate the real world SNs. Arguably, one of the most wellstudied such graph models is the Preferential Attachment (PA) random graph [Barab´asi and Albert, 1999]. In contrast to the real world SNs, [Avin et al., 2019] observed that in the PA graphs, with comparable number of nodes and edges, a small set of black nodes is not capable of enforcing the victory of the black color, unless they have extremely large influence factors. Therefore, they suggested for future work to propose graph models which not only retain well known characteristics of the real world SNs, but also support the existence of a small set of nodes with a significant disproportionate power in the majority model.

The fact is even though the PA model possesses some crucial features of the real world SNs, it also suffers from lack of some fundamental properties such as a high clustering coefficient (that is, two neighbors of a node are likely to be adjacent), cf. [Krioukov et al., 2010]. Hence, the aforementioned result by [Avin et al., 2019] is just another indication that the PA model is not a decent choice to represent the SNs. On the other hand, Hyperbolic Random Graph (HRG) [Krioukov et al., 2010] is known to possess all the desired fundamental properties, including a high clustering coefficient, making it an interesting and suitable model to consider, leading to our first contribution.

Contribution 1. Our experiments on HRG matches the results for the real world SNs; that is, almost the same number of highest degree black nodes with a rather small influence factor suffices for the black color to win. (The parameters of the HRG selected suitably to make it comparable to the respective SN. See Section 1.2, for more details.)

Given this disproportionate amount of controlling power of the elites, a natural question that arises is whether one can develop a counter measure to overpower them.

A proposed countermeasure ideally should not require significant changes in the graph structure or the updating rule. Furthermore, it should be easy for the agents to implement, e.g. it should not require them to have a full knowledge of the graph structure or memorize the history of the process.

Contribution 2. We propose two countermeasures and support their effectiveness both experimentally and theoretically. Firstly, we show that if we require every agent to make a certain number of new connections at random, a small set of elite nodes cannot control the output of the majority model anymore. More formally, we prove that if we add a graph with strong expansion properties on top of any graph, including a real world SN, for the black color to win a significant number of nodes must be black initially. Secondly, we show that if each agent changes her color only if a "sufficiently" large fraction of her neighbors hold a different color, no small set of nodes can determine the output of the process. This is realized by assigning a high stubbornness factor to each node. Furthermore, we demonstrate that our experiments support these theoretical findings.

Question 2. What is the probability that the black color wins (or takes over) if we assume that initially each node is colored black independently with some probability pb ∈ (0, 1)?

It is known (cf. [Zehmakan, 2020]) that in the majority model on "nearly" regular graphs with strong expansion properties, such as random regular graphs and Erd˝os-R´enyi random graph (See Section 1.2 for a formal definition), if pb is "slightly" more (resp. less) than 1/2, then black (resp. white) color takes over asymptotically almost surely. (We say that an event occurs asymptotically almost surely (a.a.s.) if it happens with probability tending to 1 when we let the number of nodes go to infinity.)

Contribution 3. We provide experimental results confirming the existence of this threshold behavior in the Erd˝os-R´enyi and regular random graphs, and show that this behavior is also observed in the PA random graph. However, the majority model turns out to exhibit a different behavior on real world SNs and HRG. That is, the black (resp. white) color might not take over even when pb (resp. 1 - pb) is significantly larger than 1/2. However, we show that upon the addition of a d-regular random graph for a reasonably large d we recover the aforementioned threshold behavior.

We study the above question for the (ψ1, ψ2)-majority model as well. We prove that for a dense Erd˝os-R´enyi random graph, the process exhibits a threshold behavior with two phase transitions: (i) the white color takes over if pb < 1-ψ1 (ii) both colors will survive (i.e., no color takes over) if 1 - ψ1 < pb < ψ2 (iii) the black color takes over if ψ2 < pb a.a.s. Furthermore, our experiments suggest that such a threshold behavior is also present in the PA random graph, sparse regular random graphs, HRG, and the real world SNs, but for different threshold values.

As mentioned, the majority model on the Erd˝os-R´enyi random graph Gn,q is well understood when pb is smaller or larger than 1/2. What if we have pb = 1/2? [Benjamini et al., 2016] conjectured if q is "sufficiently" larger than 1/n, then a.a.s. one of the two colors almost takes over (i.e., all nodes share the same color at the end, except a sub-linear number of them). [Fountoulakis et al., 2020] proved that the conjecture is true when q is larger than 1/√n, but it has remained open for q smaller than 1/√n.

Contribution 4. We perform experiments whose results support this conjecture. More precisely, we observe that in the majority model on Gn,q with pb = 1/2 if q = c/n for c ≥ 12, one of the two colors almost takes over. However, if c ≤ 8, the process reaches a configuration where almost half of the nodes are black.

Question 3. What is the stabilization time and period of the process? For the majority model on a graph G = (V,E), [Goles and Olivos, 1980] proved that the period is always one or two. Furthermore using some algebraic tools, [Poljak and Turz´ık, 1986] showed that the stabilization time is in O(|E|), which [Frischknecht et al., 2013] proved to be tight, up to some poly-logarithmic factor. However, if we start from a random coloring, where each node is black independently with probability pb, the probability that an extremal coloring, for which the process takes a long time, emerges is fairly small. Hence, a natural question that arises here is whether one can provide stronger bounds on the expected stabilization time (i.e., the expected number of rounds the process needs to reach a cycle of colorings from a random initial coloring). It is widely believed that a poly-logarithmic upper bound must exist, but this is proven only for some special classes of graphs, cf. [Zehmakan, 2020].

Contribution 5. As our first evidence for a poly-logarithmic upper bound, we prove that the expected stabilization time of the majority model is at most logn when the underlying graph is a cycle Cn. Furthermore, we experimentally investigate the expected stabilization time of the majority model on different random graph models and real world SNs and our findings support the conjectured poly-logarithmic bound. It is worth to stress that the process takes the longest at the threshold value pb = 1/2.

We study the stabilization time of the (ψ1, ψ2)-majority model too and, building on a potential function argument, prove that it is also bounded by O(|E|) when ψ1 = ψ2. For the proof, we set a connection between the number of edges whose endpoints have opposite colors in the initial coloring and the number of rounds the process needs to end. As we will explain, this technique might be useful to prove a polylogarithmic bound on the expected stabilization of the majority and (ψ1, ψ2)-majority model.

1.2 Preliminaries

Graph Definitions. Let G = (V,E) be an n-node graph. For a node v ∈ V , N (v) := {u ∈ V : {u, v} ∈ E} is the neighborhood of v. For a set S ⊂ V , we define N (S) :=

⋃v∈S N (v) and NS (v) := N (v) ∩ S. Moreover, d (v) := |N (v) | is the degree of v in G and dS (v) := |NS (v) |.

Furthermore, for two node sets S and S′ , we define e (S, S′ ) := |{(v, u) ∈ S ×S′ : {v, u} ∈ E}| where S ×S′ is the Cartesian product of S and S′ .

Note that whenever graph G is not clear from the context, we add a superscript, e.g. we write dG(v), dGS (v), and eG(S, S′ ).

Random Graphs. Let Gn,q denote the Erd˝os-R´enyi random graph, which is the random graph on the set {1, · · · , n}, where each edge is present independently with probability q. We denote by Gn,d the d-regular random graph, which is the random graph with a uniform distribution over all d-regular graphs on n nodes.

Models. For a graph G = (V,E), a coloring is a function C : V → {b,w}, where b and w represent black and white, respectively. For a node v ∈ V , the set N C a (v) := {u ∈ N (v) : C (u) = a} includes the neighbors of v which have color a ∈ {b,w} in coloring C. Assume that we are given an initial coloring C0 on a graph G. In a model M, Ct (v), which is the color of node v in the t-th coloring for t ∈ N, is determined based on a predefined updating rule. We are mainly interested in the following two models, where Ct (v) is defined by a deterministic updating rule as a function of Ct-1 (u) for u ∈ N (v) ∪ {v}.

MajorityModel. In the majority model

(ψ1, ψ2)-Majority Model. In the (ψ1, ψ2)-majority model for some ψ1, ψ2 ∈ (1/2, 1]

In these models, we define Bt and Wt for t ∈ N0 to be the set of black and white nodes in Ct.

Experimental Setup. We run our experiments for the graph data of the Facebook (FB) and YouTube (YT) SN from [Viswanath et al., 2009] and [Mislove et al., 2007] and Twitter (TW) and Slashdot (SD) graph data from [Leskovec and Krevl, 2014].Furthermore, we focus on several random graph models such as Erd˝os-R´enyi (ER) Random Graph, Random Regular Graph (RRG), Preferential Attachment (PA) Random Graph, and Hyperbolic Random Graph (HRG). To make our experiments on the random graph models and real world SNs comparable, we set the parameters of random graphs in a way that they have the same number of nodes and edges in expectation. For the generation of the RRG and HRG, we rely on the (approximation) algorithms of [Steger and Wormald, 1999] and [Staudt et al., 2015] respectively, and the implementations in [Hagberg et al., 2008]. To generate HRG, in addition to the number of nodes and edges, one needs to provide the exponent of the power-law degree distribution β and the temperature T as the input parameters. Throughout this paper, we set β = 2.5 and T = 0.6. Experiments which required random choice of edges or colors were executed 8 times and then the average output was considered. Furthermore, (several) experiments were carried out on an Intel Xeon E3 CPU, with 32 GB RAM, and a Linux OS.

1.3 PriorWorks

Opinion Diffusion Models. In the plethora of opinion diffusion models, considerable attention has been devoted to the study of different variants of the majority model, such as an asynchronous updating rule [Anagnostopoulos et al., 2020], various tie-breaking rules [Schoenebeck and Yu, 2018], and randomized updating rules [Mossel et al., 2013]. Even more complex models such as the one considered in [Ferraioli and Ventre, 2017] which follows an averaging-based updating rule, or the models in [Faliszewski et al., 2018] and [Brill et al., 2016] can be seen as extensions of the majority model.

In the present paper, we consider variants of the majority model previously studied by cf. [Avin et al., 2019] and [Auletta et al., 2017]. Furthermore, the (ψ1, ψ2)-majority model, which is a generalization of the model studied in [Balister et al., 2010].

Minimum Size of a Winning Set. Determining the minimum size of a winning set and a dynamo has been considered in various majority based models and for different classes of graphs such as ER [Benjamini et al., 2016], PA [Avin et al., 2019], and lattice [Balister et al., 2010]. For general graphs, [Berger, 2001] proved that there exist arbitrarily large graphs which have dynamos of constant size under the majority model and it was shown in [Auletta et al., 2018] that every n-node graph has a dynamo of size at most n/2 under the asynchronous variant.

Random Initial Coloring. The majority model with a random initial coloring has been investigated for different classes of graphs such as hypercubes and preferential attachment trees, cf. [Balister et al., 2010]. As stated, special attention has been devoted to the study of ER when each node is black independently with probability pb = 1/2, cf. [Benjamini et al., 2016].

Stabilization Time and Period. [Goles and Olivos, 1980] proved that the period of the majority model is always one or two. Recently, it was shown by [Chistikov et al., 2020] that it is PSPACE-complete to decide whether the period is one or not for a given coloring of a directed graph. Furthermore, [Poljak and Turz´ık, 1986] proved that the stabilization time of the majority model on a graph G = (V, E) is upper-bounded by O(|E|). Stronger bounds are known for special classes of graphs. For instance, for a d-regular graph with strong expansion properties the stabilization time is in O(logd n), cf. [Zehmakan, 2020].

2 Power of Elites and Countermeasures

[Avin et al., 2019] observed that in real world SNs, if a small set (e.g. 1%) of the elite nodes are provided with a constant influence factor (e.g. 8), they are capable of determining the outcome of the majority model, i.e., they form a winning set. In the PA random graphs with comparable parameters, in contrast, these authors showed that for a small set of elite nodes to form a winning set, they must have an extremely large influence factor. As mentioned earlier, the PA random graph lacks the presence of a high clustering coefficient cf. [Krioukov et al., 2010]. We believe this is the source of such discrepancy. On the other hand, HRG is known [Krioukov et al., 2010] to possess all the aforementioned properties, justifying our choice to investigate the majority model on HRG.

Our experiments demonstrate that the size and influence factor required for a set of elites to form a winning set is approximately the same in the real world SNs and HRGs with comparable parameters. This is depicted for YT SN in Figure 1 (left), and other SNs are included in the full version of this paper. Figure 1 (left) also covers PA, which was already investigated by [Avin et al., 2019].

Disproportionate Power of Elites. Naturally, the question arises how to prevent a small set of elite nodes from determining the outcome of the majority model. To this end, we propose two countermeasures to overpower the elites. Firstly, we prove that if we add a sufficiently dense RRG on top of any graph, in particular a SN, no small winning set will exist. Secondly, we show that if we assign a sufficiently large stubbornness factor to each node, no small set of elites can create a winning set.

Countermeasure 1. Adding a RRG on top of a SN is essentially the same as asking agents (nodes) to make a set of connections at random. Consider a small set S of elite nodes who form a winning set in a SN. Intuitively speaking, the randomly added connections for each node are unlikely to be chosen from set S, thus reducing the influencing power of the elite nodes in S. We formally state our result in Theorem 2, of which the proof can be found in the full paper version.

Theorem 2. Let G1 = (V,E1) be an arbitrary graph with average degree ¯ d, G2 = (V,E2) be a d-regular graph and Z ⊂ V be an arbitrary set of nodes in G = (V,E1 ∪ E2) with |Z| = 0.05n and n = |V |. Let G1 = (V,E1) be an arbitrary graph with average degree ¯ d and G2 = (V,E2) be a d-regular graph. Suppose that Z ⊂ V is an arbitrary set of nodes in G = (V,E1 ∪ E2) and |Z| = 0.05n, where n = |V |. Consider the majority model on G, where B0 = Z and all nodes in Z have influence factor r ≤ 10 (while it is 1 for the rest of nodes). If σ(G2) ≤ β and d = cr ¯ d for a suitable choice of constants c, β > 0, the white color wins.

Corollary. [Friedman, 2003] proved that for a random dregular graph Gn,d, σ (Gn,d) ≤ 2/√d a.a.s. when d ≥ 3. This implies that the statement of Theorem 2 holds a.a.s if G2 = Gn,d for a sufficiently large d. Therefore, if we add a Gn,d on top of a SN, there is no winning set which includes less than 5% of the nodes. Recall that based on [Avin et al., 2019] the real world SNs usually allow winning sets of much smaller size than 5%; for example in YT SN, a set of highest degree nodes of size 0.15%. As we will discuss, our experiments support even stronger bounds than the one given in Theorem 2. Lastly, it is worth to mention that the constraint r ≤ 10 can be relaxed, but cannot be lifted entirely because if a set S of elites in a SN have extremely large influence factors, even after adding a complete graph on top of the SN, S is a winning set.

Countermeasure 2. Note that we consider the setting in which initially a set of elites form a black coalition, and the rest of nodes (or most of them) are white. Hence intuitively speaking, if most nodes become very reluctant to change their color (i.e., have a large stubbornness factor), one would expect most of the white nodes to keep their color unchanged. We state this observation more formally in Theorem 3, proven in the full version of this paper.

Theorem 3. Consider a graph G = (V,E). Let Z ⊂ V such that |Z| < n/2 and dZ(v) ≤ fd(v) for some f ∈ (0, 1) and every v ∈ V \ Z. Consider the majority model where all nodes in Z have influence factor r ∈ N. If for each node v ∈ V \ Z the stubbornness factor γ(v) > r r+ 1-f f , then Z is

not a winning set.

Observe that the statement of Theorem 3, in particular, is true when Z includes the nodes of highest degree and they all

have influence factor r (while it is 1 for the rest of nodes). Experiments of Countermeasures. The experimental results of both countermeasures applied to FB SN are depicted in Figure 1 (right), which confirm their effectiveness. (The plots for other SNs are given in the full version of the paper) For instance, our experiments indicate that in FB SN an elite set consisting of 0.4% of nodes with influence factor 16 form a winning set, but after applying countermeasure CM1 (adding a RRG) and CM2 (assigning high stubbornness factor) an elite set of size 10% and 33%, respectively, is required to win, with the same influence factor.

3 Random Initial Coloring

We experimentally investigate the majority and (ψ1, ψ2)- majority model on various real world SNs and random graph models, where initially each node is black independently with probability pb. We aim to determine the final fraction of black nodes (i.e., the number of black nodes in the final configuration divided by the number of all nodes) for different values of pb.

Majority Model with Random Coloring. Our experimental results for the majority model on SD SN and several random graph models with comparable parameters are depicted in Figure 2 (left). (The plots for other real world SNs can be found in the full version of the paper). We observe that the majority model is a fair density classifier on ER, RRG, and PA. That is, for pb < 1/2 (resp. pb > 1/2), the white (resp. black) color takes over. This confirms some prior theoretical results, cf. [Zehmakan, 2020]. However for SD SN and HRG, the white (resp. black) color might not take over even when pb (resp. 1-pb) is much smaller than 1/2. Lastly, we note that upon the addition of a RRG with the same average degree on top of SD SN, the aforementioned fair density classification behavior emerges. (See CM1 in Figure 2 (left)) Uniform Random Coloring. In prior work, special attention has been devoted to the study of the majority model on the Erd˝os-R´enyi random graph Gn,q for pb = 1/2. In particular, [Benjamini et al., 2016] conjectured that if q is sufficiently larger (resp. smaller) than 1/n, the process reaches an almost monochromatic coloring (resp. an almost balanced coloring) a.a.s. In an almost monochromatic coloring, all nodes share the same color, except a sub-linear number of them, and in an almost balanced coloring the difference between the number of black and white nodes is sub-linear. Our experiments on Gn,q for n = 1000000 indicate that for q ≥ 12/n (resp. q ≤ 8/n) the process reaches an almost monochromatic coloring (resp. an almost balanced coloring). Hence, our results support the correctness of the conjecture. (ψ1, ψ2)-Majority Model with Random Coloring. We prove that in the (ψ1, ψ2)-majority model on Gn,q a.a.s., for q sufficiently larger than logn/n (which is the connectivity threshold): (i) the white color takes over if pb < 1 - ψ1 (ii) both colors will survive (i.e., no color takes over) if 1 -ψ1 < pb < ψ2 (iii) the black color takes over if ψ2 < pb. The proof of this proposition can be found in the full version of this paper. Furthermore, we experimentally investigate the (ψ1, ψ2)-majority model, for certain values of ψ1, ψ2, with a random initial coloring on various real world SNs and random graph models with comparable parameters. Our results for TW SN and corresponding random graphs are depicted in Figure 2 (right). (Similar plots are provided in the full version of the paper for other real world SNs.) We observe that a similar threshold behavior with two phase transitions is also present in TW SN, PA, HRG, and RRG but the threshold values are different from 1 - ψ1 and ψ2.

4 Stabilization Time and Period

Stabilization in Majority Model. As discussed, prior work has shown that the stabilization time and period of the majority model are bounded by O(|E|) and 2. However, in the random setting a poly-logarithmic bound on the expected stabilization time is believed to exist (but only proven for a some special classes of graphs). We provide evidence to support this conjecture. Firstly, we prove in Theorem 4that the expected stabilization time of the majority model on a cycle Cn is at most logn. The proof of this theorem can be found in the full version of the paper.

Theorem 4. Consider the majority model on a cycle Cn. If each node is initially black independently with probability pb, then the process stabilizes in log n rounds a.a.s.

Furthermore, we investigate the expected stabilization time of the majority model on several real world SNs and random graph models. This is depicted for SD SN and random graphs with comparable parameters in Figure 3 (left). (See the full version of the paper for other SNs.) In our experiments on all these graphs the process ends in less than 30 rounds, while the number of edges is around m = 500000. Thus, loosely speaking, the expected stabilization time here seems to be poly-logarithmic in m rather than linear. Furthermore, we observe that adding a RRG on top of SD SN (similar to our first countermeasure in Section 2) speeds up the process. Hence, adding random edges not only helps the color with initial majority to win, but also makes this happen faster.

Stabilization in (ψ1, ψ2)-Majority Model. Consider the (ψ1, ψ2)-majority model, for ψ1 = ψ2, on a graph G = (V,E). Building upon a potential function argument, we prove in Theorem 5 that the stabilization time and period of the process are upper-bounded by 4m∗ and 2, respectively, where m∗ denotes the number of bichromatic edges in the initial coloring. (Recall that an edge is bichromatic if its endpoints have opposite colors.) Note that m∗ ≤ |E| and the (ψ, ψ)-majority model coincides with the majority model when ψ is slightly larger than 1/2. Thus, Theorem 5, as a special case, bounds the stabilization time of the majority model with O(|E|), previously proven by [Poljak and Turz´ık, 1986]. The main idea of our proof is to establish a relation between the (ψ, ψ)-majority model on G and a process called the periodic majority model on a weighed graph H, which is constructed fromG. Then, we argue that in this new process the summation of weights of bichromatic edges decreases in each round. The proof is given in the full version of this paper.

Theorem 5. Consider the (ψ, ψ)-majority model, for some ψ ∈ (1/2, 1], on a graph G = (V,E). The stabilization time is upper-bounded by 4m∗ , where m∗ is the number of bichromatic edges in the initial coloring, and the period is always one or two.

Furthermore, we experimentally analyze the expected stabilization time of the (ψ1, ψ2)-majority model. See Figure 3 (right) for our results on TW SN (and random graph models with comparable parameters) and the full version of this paper, for other real world SNs. We observe that the initial probabilities pb for which the process takes the longest to stabilize, are identical to the empirically observed threshold values depicted in Figure 2 (right). We note that this is also the case in the majority model, as the stabilization time peaks at pb = 1/2 (visible in Figure 3 (left)), at which also the phase transition occurs (visible in Figure 2 (left)).

5 Conclusion

We showed that in the real world social networks, an extremely small set of high-degree nodes (i.e., elites) can determine the output of an opinion forming process. We developed two countermeasures which can be applied to overpower such a small set of elite nodes. In general, motivated from the study of effective marketing strategies, the problem of finding a small set of agents whose opinion governs the final dominant opinion has been extensively studied for various models. However, the current understanding of the development of countermeasure mechanisms to subdue such a small group with disproportionate influencing power is limited. We aspire this work to be a starting point for further investigation of effective countermeasures for a large spectrum of models.

Furthermore, we proved that the (ψ1, ψ2)-majority model exhibits a threshold behavior with two phase transitions at 1 - ψ1 and ψ2 when the underlying graph is a dense Erd˝osR´enyi random graph. Our experiments suggest that a similar threshold behavior might exist for other classes of graphs, but the threshold values are different from 1-ψ1 and ψ2. It would be interesting to determine these values in the future work.

In addition, we provided several experimental and theoretical evidence to support the widely believed conjecture of a poly-logarithmic upper bound on the expected stabilization time of the majority model; however, it remains open in its full generality. For the (ψ1, ψ2)-majority model, for ψ1 = ψ2, we proved that the stabilization time is bounded by 4 times the number of bichromatic edges in the initial coloring. We believe this can be an important milestone to settle the conjecture. Specifically, if one can prove that from a random coloring the process reaches a coloring with poly-logarithmically many bichromatic edges in a poly-logarithmic number of rounds in expectation, then our result yields the conjecture.