Dynamics of opinion polarization

For decades, researchers have been trying to understand how people form their opinions. This quest has become even more pressing with the widespread usage of online social networks and social media, which seem to amplify the already existing phenomenon of polarization. In this work, we study the problem of polarization assuming that opinions evolve according to the popular Friedkin-Johnsen (FJ) model. The FJ model is one of the few existing opinion dynamics models that has been validated on small/medium-sized social groups. First, we carry out a comprehensive survey of the FJ model in the literature (distinguishing its main variants) and of the many polarization metrics available, deriving an invariant relation among them. Secondly, we derive the conditions under which the FJ variants are able to induce opinion polarization in a social network, as a function of the social ties between the nodes and their individual susceptibility to the opinion of others. Thirdly, we discuss a methodology for finding concrete opinion vectors that are able to bring the network to a polarized state. Finally, our analytical results are applied to two real social network graphs, showing how our theoretical findings can be used to identify polarizing conditions under various configurations.


Introduction
With the rise of social media and online social networks, online interactions have started playing an increasingly important role in how people form their opinions, to the point that news consumption itself is now often mediated by social interactions [1,2]. Social networks, though, do not merely provide a transparent technological substrate that facilitates interactions in the online dimension. Their algorithmic personalization, aimed at highlighting content that is more interesting to each of us, effectively reinforces our cognitive biases, reducing the cognitive discomfort we experience when exposed to opinions challenging our beliefs but at the same time reducing the diversity and range of opinions we are exposed to. By reinforcing consonant opinions and downplaying, or even removing, discordant ones, social networks cradle us into curated filter bubbles and comfortable echo chambers. However, whether this leads to actual polarization [3,4,5] is still debated. Some argue that the very nature of social networks, i.e., the socialization of information consumption, may counteract the above effects [6], others that individual choices (to bond with similar others and to prefer concordant information) are more predominant than algorithmic filtering [7], others again that exposure to opposing views is more likely to actually backfire than to widen our perspectives [8]. To make matter worse, information may not only be partisan but it could also be blatantly fake [9]. This quest towards a better understanding of the impact of the social algorithm [10] and misinformation on our societies is ingrained with a more general question that, even when removing the cyber-dimension, still remains unsolved: how do people form their opinions? This question has fascinated sociologists and economists alike since much before the advent of the Internet, but it has recently gained new momentum, with computational sociologists and control theorists now weighing in. The literature on opinion dynamics is vast, with many models being proposed that aim at capturing a variety of cognitive and social mechanisms that lead to forming an opinion, such as social influence (which determines whose opinion you are affected by), cognitive dissonance (which triggers your willingness to adapt), anchoring to one's own opinion (which captures our prejudices). So-called averaging models are one of the most popular classes of such opinion dynamics models [11,12,13]. In these models, the final opinions (also known as expressed opinions) are a function of a repeated weighted averaging of the opinions of neighboring (in the influence graph) nodes. The strengths of averaging models lie in their mathematical tractability [14], ability to capture strong 1 opinion diversity [16], their general flexibility (e.g., they can capture the wisdom of the crowd phenomenon [17] or include prominent agents [18] such as media sources and politicians that may be systematically biased and not willing to change their opinion at all), and having been validated on small and medium-sized groups [19,20].
The Friedkin-Johnsen (FJ) model [13] is the most popular averaging model in the related literature. Focusing on it, our first contribution is to provide a comprehensive review of all the major variants of the FJ model and of the polarization metrics described in the related literature. For them, we will highlight their key features and the differences between each other. We found that polarization metrics are linked together through an invariant relationship. As a second contribution, we derive the conditions under which the FJ model yields polarization, for each of the polarization metrics identified before. In addition, we also prove that the polarizing opinion vectors can be found analytically in most cases. All the results obtained are exploited to identify polarizing conditions, under different configurations, with two popular datasets of real social networks.

Background and motivation
The simplest averaging model is the DeGroot's model [11], whereby the opinion of a node is simply the average opinion of its neighbours, weighted by the strength of their social influence. This model, however, is not considered realistic, since, when it converges (i.e., if the nodes' opinions stabilize), it always leads to consensus, i.e., to a final state in which all nodes have exactly the same opinion [21]. To overcome this problem, Friedkin and Johnsen [13] proposed a variation on the Groot's model that introduces a certain degree of stubbornness in nodes. Their hypothesis is that a personal opinion always remains at least partly anchored to the initial opinion (or prejudice), more or less so depending on the individual's attitude to be influenced by others. The Friedkin-Johnsen model does not lead to consensus (except in very particular cases [22]) and has been widely popular in the related literature [23,24,25,26,27,14,28,20,22]. The FJ model has enjoyed two main avenues of research: on the one hand, the derivation of the conditions for convergence or consensus has been the main focus of the research efforts from the control theory domain [29,28,30,31]. On the other hand, the graph-theoretical efforts have been focused on understanding the effects of the underlying influence graph on opinion formation, polarization, and on how to interfere with the opinion formation process in order to obtain a desired outcome (e.g., shifting the opinion in a specific direction, minimizing polarization and/or disagreement) [24,32,27,33,23,26,34]. However, while all the above works refer to the opinion dynamics model they leverage as Friedkin-Johnsen, they are often relying on a simplified version of it. Specifically, they use the more mathematically tractable version (which we refer to, later on, as rFJ), which, however, is not able to capture polarization (we discuss this point later in the paper). This has resulted in great confusion regarding which finding holds under which hypothesis. The second gap in the related literature, and a direct consequence of the above confusion, lies in whether the FJ model is actually able to capture polarization or not. Indeed, despite being opinion polarization a fundamental feature of a realistic opinion formation process, only Gionis et al. [23] and Dandekar et al. [33] have explicitly tackled this problem. Analyzing the problem on undirected social networks, they have proved that two variants of the FJ model are neither capable of changing the average opinion of the social network nor of increasing the weighted difference of opinions among nodes of the same neighbourhood. However, what happens with the general FJ model and with other polarization metrics is yet unknown.

Modelling framework
We explicitly differentiate between the social graph and the influence graph. They both comprise the same set V of n vertices and the same set of edges E, but the weights of the edges are different and have different meanings. The social graph, denoted with S, represents people (vertices) and the social relationships between them (through the edge weightsŵ ij ). The strength of a social relationship is typically measured in terms of the number of interactions that two people have [35] and for this reason the few results on polarization in the related works assume that the social graph is undirected [33,23]. In this paper, we will consider the general case of a directed social graph, specifying how results change in the specific case of an undirected one. The influence graph I describes how a node's opinion is influenced by that of its neighbours. The existence of an edge from node i to node j in I implies that node j exerts an influence on the opinion of node i, and the strength of this influence is expressed by the edge weight w ij . Lacking additional information, the influence graph can be derived from the social graph, leveraging the intuition that stronger social relationships will influence more than weak ones. Specifically, starting from the social weightsŵ ij , the influence w ij can be computed as w ij =ŵ ij n j=1ŵ ij . Please note that this definition is the only one that allows a unique correspondence between all the variants of the FJ model. The matrix W = (w ij ) is called influence matrix and is assumed to be row-stochastic (because it captures how the influence a node is subject to is split among its neighbours). The influence matrix is in general asymmetric (corresponding to a directed influence graph), even starting from a symmetric social matrixŴ = (ŵ ij ), because the influence weight w ij expresses the relative importance of j with respect to all i's social relationships. Hence, the same social relationship intensity can weigh very differently depending on the strength of other relationships.

The Friedkin-Johnsen family of opinion dynamics models
A discrete-time opinion dynamics model tracks the evolution of z i (k), the opinion expressed by a node i at time k.
Opinions are generally assumed to be real-valued, i.e., continuous in a certain reference interval. Similarly to the related literature [19,23,24], here we assume that opinions belong to [−1, 1]. Thus, extremes -1 and 1 represent opposing viewpoints on an issue. For a given configuration of its input parameters, the model is said to be convergent if z i (k + 1) → z i for all i as k grows to infinity. A convergent model is said to reach consensus if z i (k + 1) → z for all i as k grows to infinity. In the Friedkin-Johnsen model family, before the opinion formation process starts, each node i has an initial opinion s i , often referred to as internal or fixed opinion (or prejudice). In contrast, the opinion z i (k) is often referred to as the expressed opinion at time k. In Table 1 we summarize the variants of the FJ models that can be found in the literature and we discuss them separately hereafter. We denote with N (i) the neighborhood set of node i. vFJ: rFJ:

The generalized Friedkin-Johnsen model -gFJ
(1) in Table 1 corresponds to the more general version of the model originally proposed by Friedkin and Johnsen [13].
The outermost weighted average depends on parameter λ i , corresponding to the susceptibility of node i to the opinions of other nodes. The innermost weighted average depends on the influence w ij that node j exerts on node i. Two main mechanisms are at play here: anchoring, to the node i's internal opinion s i , and variable susceptibility λ i , to other nodes' opinions. Nodes with zero susceptibility value are stubborn nodes and they never change their opinion. A common matrix-formulation of the model is the following: where Λ is a diagonal matrix containing the susceptibility values λ i , while W is the influence matrix. Note that the opinion of a node i depends both on its initial prejudice s i (by a weight 1 − λ i ) and on its current opinion (by a weight λ i w ii ). The only case in which this does not happen is when the node is stubborn (λ i = 1) or when w ii = 0. Λ and W are sometimes coupled via the condition 1 − λ i = w ii [30], however we do not make this assumption here. The conditions under which the gFJ model achieves convergence and consensus have been thoroughly studied in the related literature [22,29,14]. A sufficient condition for convergence [28] is reported below, which we will use often in the rest of the paper. Theorem 1 (Sufficient condition for the gFJ). If ΛW is stable, the gFJ model is convergent and its only stationary point z (i.e., steady-state solution) is given by the following: We refer the reader to the SI Appendix for a brief summary of the main findings on the topic of opinion convergence.

The variational Friedkin-Johnsen model -vFJ
Dandekar et al. [33] and Matakos et al. [32] use a variant of FJ that we call the variational Friedkin-Johnsen model (vFJ), whose update function can be found in (2) of Table 1. According to this model, the current opinion of a node is the weighted average between its prejudice and the current opinion of the other nodes. Thus, in this variant of the FJ model, the current opinion of the node itself is not taken into account. We can formulate the expressed opinion in matrix form in the following way: where D is the diagonal degree matrix ( jŵ ij for the i-th diagonal element), A is the adjacency matrix (whose i, j element isŵ ij and the diagonal is null) andÃ is a diagonal matrix whose i-th diagonal entry is equal toŵ ii . To model stubborn nodes, we can admitŵ ii to be equal to ∞. In this case, matrixÃ contains infinite values and (6) should be treated as discussed in the SI Appendix. The relation between vFJ and gFJ has never been explicitly discussed in the related literature, where the two are implicitly treated as interchangeable and generically referred to as Friedkin-Johnsen model. However, the two models are not mathematically equivalent: the vFJ does not include node i's current opinion z i in the averaging process, while gFJ pools both the initial opinion s i and the current opinion z i 2 . The different flexibility of the two models becomes clear when observing that while the vFJ only features the matrixŴ = (ŵ ij ) as parameters of the model (leading to a maximum n 2 degrees of freedom, with n = |V|), the gFJ includes also matrix Λ, thus in total its degrees of freedom are n 2 + n. From a practical point of view, however, the only difference between the two models is the parameter w ii , which, in gFJ, takes into account node i's opinion z i in the averaging process, as we will see in the proof of Corollary 8.

The restricted Friedkin-Johnsen model -rFJ
The vFJ model withŵ ii set to 1 as in (3) of Table 1 is very popular in the related literature, mainly due to its mathematical tractability. The model has been used in [24,23,26,27,36]. The main difference between the rFJ and the vFJ model is the absence of the weight for s i , so the parameters are onlyŵ ij for all i = j thus implying n 2 − n degrees of freedom. Note that, since the weightsŵ ij are free to vary (ŵ ij ≥ 0), it is impossible to control the susceptibility (i.e., the importance of one's own initial opinion), even indirectly. A common matrix-formulation of the rFJ model is the following: where D and A are defined as described for vFJ. The solution to the above problem can be written as z = (L + I) −1 s, where L = D − A is the Laplacian matrix. The formulation of the rFJ model is particularly convenient from a mathematical standpoint (since L + I is symmetric and many useful matrix formulas leverage symmetry), and this is the reason why it has been so often used in the related literature.

The matrix representation of the FJ model
In the whole set of FJ models, the final opinion z of the opinion formation process can be expressed as z = Hs, where H is a matrix that varies depending on the specific FJ version considered, whose formulas are summarized in Table 2.
In the remaining of the paper, we will see that those matrices will be the key to the analysis of FJ polarization. vFJ: rFJ:

Polarization metrics
In an opinion formation process, polarization is observed when there is a variation in a target index Φ between the initial opinion and the final opinion of nodes. A rigorous definition is provided in the following.
Definition 1 (Polarization). For a polarization index Φ, we say that the opinion formation model M is Φ-polarizing or polarizing for Φ if it exists at least an initial opinion vector s such that the corresponding final opinion vector z satisfies the following inequality: In this case, we say that s yields to Φ-polarization and its induced polarization is measured in terms of the polarization shift, i.e by the function ∆ Φ defined as: If the model M is not polarizing, we say that it is Φ-depolarizing or depolarizing for Φ.
Please observe that the definitions of polarizing and depolarizing model M are not symmetric: to depolarize, a model M should let opinions evolve in such a way that, at the end of the process, Φ is always decreasing for all possible choices of internal opinions (s i ); instead, M is polarizing if Φ does not decrease for at least one initial opinion vector s. The justification of the asymmetry lies in the importance of determining whether a model can capture the polarization phenomenon, which means that it does it in at least one case. Please note that, for the sake of brevity, in the following we may simply refer to the opinion vector as opinion, omitting the word "vector".
For the polarization index Φ, the related literature has explored several different metrics, each capturing a different property of an opinion vector. Below we have collected the most popular definitions, for which we provide a short discussion.
Definition 2. For an opinion x = (x i ) ∈ [−1, 1] n the following polarization indices are defined: The Network-disagreement Index (NDI) [33,26,24,27,32] is the sum, over all nodes, of the weighted disagreement in each node pair, which represents (except for the division by n) the average disagreement in the network as a whole. NDI is the only topology-dependent metric, in the sense that the same opinions may give rise to a completely different NDI depending on how the vertices are connected. The Global Disagreement Index [33] (GDI) measures the conflict between all the users in the network, regardless of whether they share a social link or not. P 1 [26], corresponding to the mean-centered 2-norm of opinions, measures the polarization as a deviation of the opinions from the average. The definitions of P 2 [32] and P 3 [27], instead, intend the polarization as the deviation from the complete neutrality, represented with the value 0 (the middle ground between the two extremes -1 and 1). Finally, P 4 is referred to as total absolute opinion and has been introduced by Friedkin and Johnsen [19]. While all previous indices were related to 2-norms, the total opinion is equivalent to the 1-norm . Similarly to P 2 and P 3 , the index P 4 measures the "absolute total" opinion in the network and has the same semantic: it measures the deviation from the neutrality (represented by 0). While not directly a measure of polarization, the concept of choice shift caused by the opinion formation process (see definition below) is sometimes used in the related literature as an intermediate step in gauging the direction towards which opinion moves.
Definition 3 (Choice shift). A choice shift occurs when the mean attitude of the group at the end is different from the mean attitude at the beginning: The choice shift has been analyzed, for rFJ, by Gionis et al. in [23], where it is found that, if the social graph is undirected (w ij = w ji ), changing the graph topology will not determine a choice shift. In the following, we will discuss if this finding carries over to gFJ and under which conditions.

Polarization invariants
The above polarization indices have been introduced in the literature mostly as standalone metrics. In the remaining of the section, we establish equivalence relationships among them (Lemmas 1-2) and we derive a polarization invariant (Lemma 3). Lemma 1. It holds that GDI(x) = |V| · P 1 (x), thus the two metrics GDI and P 1 are equivalent.
Proof. See SI Appendix.
Lemma 2. It holds that P 3 (x) = |V| · P 2 (x), thus the two metrics P 2 and P 3 are equivalent.
Proof. Differently from Lemma 1, the proof is trivial and the thesis can be derived straightforwardly from Definition 2.
Leveraging the results above, we can classify the polarization indices into four main classes of equivalence (Table 3), in the sense that the behavior of a model is invariant in each class. The four classes capture four different concepts of polarization. However, they are correlated by the following important invariant that will be used in the next section and whose proof is given in the SI Appendix. Lemma 3 (Polarization invariant). For all opinion vectors x, the following inequality holds: From this relation the following corollary follows trivially. Corollary 1. When there is no choice shift the polarization moves in the same direction for both P 1 and P 3 .
Corollary 1 says that, when there is no choice shift, the polarization with P 1 implies the polarization with P 3 and vice versa. A straightforward remark is that, in all the cases when the choice shift is null (for example when opinions are positive and W is symmetric, as shown by Gionis et al. [23]), the Dispersion and Absolute classes of polarization are identical and represent the only global class of polarization.

gFJ is globally polarizing but locally depolarizing
We start by focusing on the most general Friedkin-Johnsen model, the gFJ, and we investigate whether in this case the dynamics of the process lead to polarization or not

Polarization under NDI
The first result is about the local polarization captured by the NDI index. Theorem 2 (gFJ: local polarization with NDI). The gFJ model is always depolarizing with respect to N DI, in the sense that, for every prejudice s, we have that N DI(z) ≤ N DI(s).
Proof. As stated in Theorem 1, the gFJ model converges to the vector z obtained from z = (I − ΛW ) −1 (I − Λ)s. For each node i, consider the following cost function: which penalizes opinion z i if far from s i (i's initial prejudice) and from n j=1 w ij z j (the mean opinion of i's neighborhood). We can prove that the expressed opinion (z i ) i of gFJ provided by (5) is the Nash Equilibrium of cost function (21) (for details, please refer to the SI), i.e. z i minimizes f i for all i, so that we obtain that N DI(s) ≤ N DI(z) and, as a consequence, it follows that the gFJ is N DI-depolarizing.
The result described above is intuitive: by definition, gFJ captures the willingness of each node to reduce the conflict (weighted by the matrix W ) caused by the discordance of opinions with its neighbours, which is exactly what N DI measures. For this reason, the gFJ model is depolarizing in a local sense, but this however does not imply anything about global polarization. On the contrary, we will prove that gFJ can be polarizing at the global level depending on the interplay between the social network weights and nodes' susceptibility to the opinion of others. This is a key result, since it proves that gFJ does capture the polarization phenomenon in social networks.
3.2 Polarization under P 2 , P 3 , and P 4 We start by deriving the conditions under which gFJ is polarizing for the global metrics P 2 , P 3 , and P 4 (the proof is provided in the SI Appendix). Theorem 3 (gFJ: global polarization with P 2 , P 3 , P 4 ). gFJ is polarizing with P 2 , P 3 , P 4 if and only if matrix H g defined in (8) is not doubly stochastic. Furthermore, we can distinguish the following two cases: (i) if there are naive nodes (i.e., ∃i ∈ V : λ i = 1), matrix H g is never doubly stochastic and thus gFJ is polarizing; (ii) if there are no naive nodes (i.e., ∀i ∈ V, λ i < 1), matrix H g is not doubly stochastic, and equivalently gFJ is polarizing with P 2 , P 3 , P 4 , if and only if the following condition holds true for at least one node i ∈ V: Intuitively, the fact that H g is not double-stochastic is a measure of the presence of nodes that are more influential than others. This is straightforward to see in the case of naive nodes (Theorem 3.(i)), where all the non-naive nodes play the role of influencers (because they are always able to sway the naive nodes' opinions towards theirs), potentially increasing the polarization. When there are no naive nodes, the intuition behind Theorem 3 is more difficult to grasp. Let us split the effect of social influence and individual susceptibility. To isolate the former, let all nodes have the same susceptibility λ. Since (22) is reduced to j∈V w ji = 1, W not being double-stochastic becomes the condition for polarization, which corresponds to the case where the social influence out of any node i is equivalent to the incoming social influence. However, in the general case, pure social influence is dampened by individual susceptibility: stubborn nodes are not swayed, regardless of the social influence they are subject to. The condition in (22) exactly captures this interplay between susceptibility and social influence.
When gFJ is depolarizing, it is also unable to produce choice shift, as the following corollary states. Corollary 2. When H g is doubly stochastic and thus gFJ is depolarizing with P 2 , P 3 , P 4 , for all opinion vector s, it holds that P 4 (z) = P 4 (s) and i z i = i s i .

How to find polarizing opinion vectors
In Theorem 3 we have derived the sufficient and necessary condition for gFJ to be polarizing. We can give a first characterization of the polarizing vectors with P 2 , P 3 , and P 4 : they can always be chosen with concordant entries (i.e., sgn(s i ) = sgn(s j ), ∀i, j). This is what is affirmed by the following theorem. Theorem 4 (P 2 , P 3 , P 4 polarizing vectors can be obtained with concordant entries). Whenever the model is polarizing with P i , i = 2, 3, 4, and s is a polarizing opinion vector, ±|s| (that have concordant entries) are polarizing vectors inducing greater or equal (than that of s) polarization. Furthermore, if the network has no naive nodes and ΛW is irreducible (i.e. the graph induced by ΛW is strongly connected), the polarizing opinion vector that maximises the polarization has concordant entries.
This result is important and also pretty intuitive: since the P 2,3,4 polarization captures the shift from a neutral state (close to 0) to an extreme state (close to 1 or −1), the polarization calculated on the same vector with all the entries concordant must be greater or equal, because it is easier for nodes to cooperatively move toward the corresponding extreme. Instead, when entries are discordant, nodes have to mitigate between discordant opinions and thus are less free to vary in one of the two directions. This always occurs if the nodes are susceptible and non-stubborn, otherwise there would be disconnected communities and the cooperation would be impossible (this is what the conditions of the second part guarantee).
We can go one step further and provide (Theorems 5-6 below) concrete cases of initial opinion vectors under which gFJ is polarizing with P 2 , P 3 , and P 4 . In the specific case of P 2 and P 3 , we prove that finding the prejudice vector that yields maximum polarization, i.e. the maximum of function ∆ P2,3 defined in (12), is NP-hard, so we also discuss a possible approximation algorithm (Corollary 3). Theorem 5 (gFJ: polarizing initial opinions for P 2 , P 3 ). Whenever the model is polarizing for P 2 , P 3 (i.e. according to the conditions of Theorem 3), the polarizing prejudices s B2(1) , s B2(t) , s max P 2,3 can be derived as follows.
(i) Two polarizing prejudices ±s B2(1) correspond to the unitary eigenvectors associated with the largest eigenvalue of matrix H T g H g and they correspond to the point of local maximum for the P 2 , P 3 -polarization on the L 2 -ball of radius 1 B 2 (1) = {x ∈ [0, 1] n : x 2 ≤ 1}. In particular, it holds exactly ∆ P3 (±s B2(1) ) = σ 2 where σ 1 is the greatest singular value of the matrix H g . Both these vectors have concordant entries.
(ii) The opinion vectors ±s B2(t) that yield the local maximum for P 2 , P 3 -polarization on the L 2 -ball of radius denoting the largest entry of s B2(1) . In particular, its polarization is exactly t 2 times the polarization of s B2 (1) . Both these vectors have concordant entries.
(iii) The global maximum for P 2 , P 3 -polarization is achieved for the initial opinion vectors ±s max P 2,3 = ± i α i v i , whose components α = (α i ) can be obtained as the solution to the following optimization problem: where σ 1 , . . . , σ n are the singular values of H g , α = (α 1 , . . . , α n ) T is the vector of the coefficients that express s max with respect to the basis B = {v 1 3 , . . . , v n } composed of the unitary eigenvectors of H T g H g , and B is the matrix whose columns are the vectors of B. The constraint guarantees that the solution s max P 2,3 has positive (and −s max P 2,3 has respectively negative) is a proper opinion vector in [−1, 1] with concordant entries. This optimization problem, being quadratic non-convex programming, is NP-hard.
Corollary 3 below tells us that, in case matrix H g has more than one singular value greater than one, it is possible to design sub-problems of the optimal problem described in (23) over spaces larger than B 2 (t) but smaller than the entire domain. These sub-problems are convex-quadratic programming and can be solved in polynomial time. Depending on the dimension of the network, numerical solutions may still not be found. Thus, we have designed a heuristic that always finds a solution ±s heu V>1 whose polarization is greater than that of ±s B2(t) . The corresponding derivations can be found in the SI Appendix. Corollary 3 (gFJ: polarizing initial opinions for P 2 , P 3 on the subspaces V >1 and V ≥1 ). When matrix H g has more than one singular value greater than one, it is possible to design sub-problems of the optimal problem in (23) over V >1 (vector space generated by the eigenvectors associated with the singular values strictly greater than 1) and over V ≥1 (vector space generated by the eigenvectors associated with the singular values greater or equal to 1). These sub-problems yield polarizing vectors s V>1 , s V ≥1 , respectively, and they are convex-quadratic programming (with polynomial time complexity). A heuristic that always finds a solution ±s heu V>1 is proposed.
With Theorem 5 and Corollary 3, we are able to identify the initial opinion vectors ±s max P 2,3 , ±s B2(1) , ±s B2(t) , ±s V >1 , ±s V ≥1 leading to polarization maxima on the corresponding subspaces. While computing the opinion ±s max P 2,3 yielding the global maximum is an NP-hard problem (Theorem 5.(iii)), an approximate solution could be obtained using standard numerical solvers (not in all cases, as we discuss in the Experimental Evaluation section).
The local polarization maxima are found reducing the problem on the subspaces corresponding to eigenvectors of H T g H g associated with singular values strictly greater or weakly greater than one. In particular, the vectors ±s B2(t) of Theorem 5.(ii) (which are a scalar multiple of ±s B2(1) in Theorem 5.(i)) are the vector that maximize the P 2 , P 3polarization on the space generated by the eigenvectors ±s B2(1) of H T g H g (also denoted with v 1 in Theorem 5.(iii)) that correspond to the singular value σ 1 > 1. The vectors ±s V>1 in Corollary 3 maximize the polarization on the larger subspace V >1 generated by all the eigenvectors that correspond to the singular values strictly greater than one. Finally, the vectors ±s V ≥1 in Corollary 3 maximize P 2 , P 3 -polarization on the even larger subspace V ≥1 generated by all the eigenvectors that corresponds to the singular values weakly greater than one. Since these vectors correspond to the maximum of polarization over subspaces that are subset of each other, it is trivial to derive the following inequality: for Φ = P 2 , P 3 .
While the results in Theorem 5 and Corollary 3 do not have an immediate practical interpretation, we can get the gist of them with a simple numerical example. Consider a network composed of three nodes -a naive node A, a node B with susceptibility value equal to 0.5, and a stubborn node C -with mutual weights equal to 0.5. Applying Theorem 5, we obtain that s B2(1) = (0, 0.30, 0.95) and, dividing by 0.95 as in Theorem 5.(ii), we obtain s B2(t) = (0, 0.31, 1), which leads to a final opinion vector (0.8, 0.61, 1). The prejudice of the naive node A is opposite to that of stubborn node C, and A's opinion shifts significantly (from 0 to 0.8). The opinion of the intermediate node B is approximately doubled. The opinion vector achieving maximum polarization s max P 2,3 is instead (0, 0.75, 1), whose corresponding final opinion is (0.95, 0.89, 1). In this case, the combined effect of non-naive nodes' strong prejudices pushes A's final opinion to the opposite extreme. In some way, it is as if s B2(t) (which only takes into account one singular value of H) selected the prejudice that maximizes the shift leveraging only to the most influential node (node C). Instead, the s max P 2,3 (which yields the global maximum) is able to enforce a synergy between non-naive nodes. In this simple case since H has only one singular value greater than 1, we cannot obtain the vectors s V>1 and s V ≥1 .
Theorem 6 (gFJ: polarizing vectors for P 4 ). Whenever the model is polarizing for P 4 (i.e. according to the conditions of Theorem 3), the following hold true.
(i) Two prejudice vectors ±s B1(1) that yields to P 4 -polarization are the j-th vector of the standard basis in R n (i.e., a vector whose components are all zero, except the j-th that equals 1) and its opposite, where j = argmax j i h ij (i.e., j corresponds to the index of the column of H g = {h ij } ij with the greatest column-sum). This prejudice vector is also the point of maximum of P 4 -polarization on the 1-norm ball B 1 (1) = {x ∈ [0, 1] n : x 1 ≤ 1} and its polarization is exactly given by ∆ P4 (±s B1(1) )) = H g 1 − 1.
(ii) With the same notations of Theorem 5, the global maximum for P 4 -polarization is achieved for the initial opinion vectors ±s max P 4 = ± i α i v i with concordant entries, whose components α = (α 1 , . . . , α n ) T can be obtained as the solution to the following optimization problem: This optimization problem is a linear programming problem that can be numerically solved.
As observed for P 2 , P 3 -polarization, it is holds that:

Polarization under P 1 and GDI
We conclude the analysis of gFJ by studying the polarization under P 1 and GDI. For this case, Theorem 7 asserts that whenever gFJ does not polarize in P 2 , P 3 , P 4 , it does not polarize in P 1 , GDI either. Instead, when gFJ is polarizing in P 2 , P 3 , P 4 , we can guarantee that it also polarizes in P 1 , GDI only if the sufficient condition in Theorem 7 is satisfied. Again, the proof of the theorem below can be found in the SI Appendix.
Theorem 7 (gFJ: global polarization with P 1 , GDI). For polarization indices P 1 and GDI, the following results hold: (i) if gFJ is depolarizing for P 2 , P 3 , P 4 , then it is also depolarising for P 1 , GDI; (ii) gFJ is polarizing in s if the following condition holds true: where α = (α 1 , . . . , α n ) T is the expression of s in terms of the basis B of the unitary eigenvectors of H T g H g ;

The role of stubborn and naive nodes
We now show (Corollary 4 below, proof in SI Appendix) a general result regarding stubborn nodes (i.e., nodes whose opinion is not at all swayed by that of their peers, which translates into λ i = 0), whose role has not a direct impact on polarization. In fact, we will see that even if their strong anchoring attitude would intuitively suggest that they always have an effect on the final opinion, the network structure can instead invalidate it. Corollary 4. While naive nodes tend to make polarization easier, stubborn nodes do not have a clear directional effect on the polarization with P 2 , P 3 , P 4 .
Leveraging Theorems 3 and 7, we can also study a special case involving naive nodes. This result, whose proof can be found in the SI Appendix of this paper, emphasizes the role of naive nodes (the ones with λ i =1), which essentially forget their prejudice and move their opinion towards the opinion of the other nodes. Corollary 5. Let us assume that the set of nodes V is composed of two disjoint groups, I and J , such that all non-naive nodes have the same opinion τ , while the naive nodes' opinions are free to vary in [−1, 1], or equivalently: (28) Then, the final opinion z is exactly the vector z = τ 1. In addition, this configuration is never polarizing for P 1 and GDI, while, as long as |s i | < 1 for at least one node i, it always exists a τ value such that P 2 , P 3 , and P 4 are polarizing.

vFJ polarizes when gFJ does
As already observed, in vFJ the opinion of a node i at step k does not take into account its own opinion at step k − 1 (as it happens, instead, with gFJ, which weighs it with w ii ). Thus, from a mathematical standpoint, the two models are different. However, apart from this specific contribution (i.e. in the case w ii is null), vFJ can be manipulated to exactly yield the same polarization as gFJ, if in an indirect and less intuitive way. In fact, in gFJ the susceptibility parameter directly captures the innate tendency of a node to be influenced (and to which degree) by others. In vFJ, instead, the rate at which a node is influenced by its peers is captured by: (i) the social strength of the node with all its neighbourŝ w ij , (ii) the anchoring-degree of the node itselfŵ ii , i.e. the importance it assigns to its initial prejudice.
Theorem 8 below establishes a complete equivalence, in terms of polarization properties, between gFJ and vFJ. Theorem 8 (vFJ: local and global polarization). For all polarization metrics, the vFJ model yields polarization under exactly the same conditions as gFJ. Specifically, if we replace matrix H g with the vFJ matrix H v and we setŵ ii = 0 for naive nodes (if present), the results of Theorems 3-7 and Corollaries 5-6 hold true. In particular, the condition for H v not being doubly stochastic reduces from (22) to the following one: Proof. The proof consists in the derivation of vFJ from gFJ. This can be done using the following mapping: Thus, the thesis follows from the results obtained for gFJ.
(29) simplifies when the social graph is undirected (which corresponds to the matrixŴ being symmetric). As stated in Corollary 6 below, in that case, when the self-weights are identical for all nodes (i.e.,ŵ ii =ŵ, ∀i) vFJ is never polarising in any metric and the average opinion is invariant to the opinion formation process.
Corollary 6 (vFJ on undirected social graphs). When the social graph is undirected (i.e. matrixŴ is symmetric), vFJ is polarizing with P 2 , P 3 and P 4 if and only ifŵ ii are not identical for all i. Whenŵ ii =ŵ, ∀i, vFJ is never polarising in any metric and it holds that i z i = i s i , i.e., there is never a choice shift in the network and the average final opinion is the same as the average initial opinion.

The rFJ model is never polarizing in undirect networks
In this section, we derive the results of polarization on the rFJ model. We already know from Bindel et al. [24] that rFJ does not polarize according to the local definition N DI, and, from Gionis et al. [23], that in the specific case of undirected social graph it does not polarize according to the global definition P 4 . Here, we generalize these findings. To this aim, note that rFJ is equivalent to vFJ after setting w ii = 1. Thus, Theorem 8 also applies in this case. The condition for H r (the equivalent of H g but for rFJ) not being doubly stochastic, simply reduces from (29) to the following one: And when the social graph is undirected, we obtain an even stronger result, summarized in Corollary 7 below. Corollary 7 (rFJ on undirected social graphs). The rFJ model is never polarizing, in any polarization metrics, for any initial opinion vector. In addition, it holds that i z i = i s i , i.e., there is never a choice shift in the network and the average final opinion is the same as the average initial opinion.
Remark: while polarization was still possible under vFJ on undirected social graph, with rFJ polarization never happens. The practical implication of this result for undirected social graphs is that polarization (in all its variations) can never be induced "naturally" by an opinion formation process following rFJ. Even more interestingly, polarization cannot be induced by altering the social graph (as long as it stays symmetric). Thus, when an initial state s is given, the final state z with rFJ can only naturally evolve towards non-polarization. Vice versa, when the social graph is directed, the above result does not hold since, in a directed graph, the opinion of nodes with stronger social power tends to steer the opinion of the others. While relationship-oriented online social networks, like Facebook, tend to feature undirected graphs, directed social graphs are common in information-driven online social networks like Twitter.

Experimental evaluation
In this section we analyze the theoretical results on two real social network graphs: the Karate Club graph [35] and a Facebook graph [37]. The former is smaller and less clustered, the latter is larger, with three big and well-delineated communities. WhileŴ is determined by the weights in the graphs, for the susceptibility we test three configurations: individual susceptibility λ i of a node i proportional to its Pagerank centrality C i , inversely proportional, and all susceptibilities set to 0.8 (see Materials and Methods for details).
We can now search for the initial opinion vectors that yield polarization in the social network, by applying Theorems 5-6 and Corollary 3. For the sake of brevity, in the following we will consider only the positive polarizing vectors but analogous results can be obtained for negative ones, as stated in the corollaries. We compute the polarizing vectors (1) , s max P 4 as described in Theorems 5-6 and Corollary 3, and we compare their polarization with the one of an opinion vector s unif with entries randomly drawn from a uniform distribution in [0, 1]. Table 4 shows the polarization induced by the above vectors on the Karate social network, for the three susceptibility configurations we are considering. Recall that the polarization shift ∆ Φ (s) for a given polarization metric Φ (with Φ = P 1 , . . . , P 4 , N DI, GDI) and initial opinion s is derived as Φ(Hs) − Φ(s). When ∆ Φ (s) is positive, then gFJ polarizes in s. We can see in Table 4 that the theoretical results are confirmed (this is not surprising, since our theorems are obtained without any approximation). A random prejudice vector s unif leads to depolarization for all the polarization metrics. Instead, the prejudices from Theorem 5 and Corollary 3 yield to P 2 , P 3 -polarization. As expected, according to (24), their corresponding P 2 , P 3 -polarization shifts are progressively increasing moving from s B2(1) to s max P 2,3 (because the solution is searched for into a larger domain). Note that, since the network is small, the numerical solver is able to find the solutions s max P 2,3 and s V>1 (the latter is not applicable to the case λ i = 0.8, because its H g has only one singular value greater than 1). It is interesting to observe that the solution s heu V>1 found with the heuristic is, in one case, exactly equal to the one obtained numerically (s V>1 ) and, in the other case, extremely   Table 4: gFJ in the Karate network: values of ∆ Φ for all polarization metrics, for the three scenarios where λ i is directly proportional to the PageRank centrality, inversely proportional and equal to 0.8. The shadowed area highlights were the corresponding opinion vectors s are expected to yield polarization. close to it, which confirms the heuristic validity. The prejudice vectors found according to Theorem 6, instead, yield to P 4 -polarization, and satisfy the inequality in (26). With respect to P 1 , GDI-polarization, while Theorem 7 cannot tell us whether polarization is achieved in general, we can use it to predict whether P 1 , GDI-polarization is achieved with the same prejudices that yield P 2 , P 3 or P 4 polarization. We find that the condition (sufficient for polarization) of Theorem 7 is verified only for the P 2 , P 3 -polarizing prejudices and λ i ∝ C −1 i . The columns ∆ P1 and ∆ GDI of Table 4 confirm polarization in these cases. Finally, as expected from Theorem 2, gFJ is always depolarizing in N DI.
Similar results are obtained with the Facebook network (Table 5). Two points are worth emphasizing. First, the centrality of nodes in the Facebook graph is extremely skewed, with one very central node dominating the graph. Thus, when λ i ∝ C i , there are very few susceptible nodes and polarization is harder to achieve. The opposite effect is observed when λ i ∝ C −1 i , and the polarization shifts are higher. Second, note that since the Facebook network size is large, the global solutions (s max P 2,3 and s max P 4 ) could not be found numerically and s V>1 could only be obtained for λ i ∝ C i . This example showcases the importance of the heuristics derived in the previous section, which can always return a polarizing vector.
We conclude this section by having a closer look at how polarizing prejudices are structured. In Figure 1, each arrow corresponds to one node in the Karate graph, and it starts at its prejudice and ends at its final opinion. For P 2 , P 3 , P 4 , an increase in polarization is linked, intuitively, to some opinions moving from more neutral states (close to 0) to more extreme states (close to 1). Indeed, this is what happens in all the cases presented in the figure. In particular, the vectors s max P 2,3 and s max P 4 that maximize the polarization feature the maximum number of components with initial opinion equal to 1 (with respect to the other opinion vectors): in this way, the nodes with more extreme opinions work synergistically to push the others' opinions closer to theirs. For selecting such an optimal "cooperative" group of extreme nodes, one should be able to search for a solution to the optimization problem within the entire domain of opinions.  Table 5: gFJ in the Facebook network: values of ∆ Φ for all polarization metrics, for the three scenarios where λ i directly proportional to the PageRank centrality, inversely proportional and equal to 0.8. The shadowed area highlights were the corresponding opinion vectors are expected to yield polarization.
When this is not the case, only suboptimal polarization is achieved. For example, the vectors s B2(1) , s B2(t) , s B1 (1) , only manage to select one single extreme node responsible for pushing the more neutral opinions of others, while s V >1 is in an intermediate position, being able to select more extreme nodes than s B2(t) and fewer than s max P 2,3 . We can also observe that in panels A and B of Figure 1, where the susceptibility varies across nodes, the nodes with initial opinion 1 are always the most stubborn, so that they create a field of attraction for more susceptible nodes. Effectively, the susceptibility assigned to nodes overrides their centrality in the network, hence very central nodes can become attractors or attractees depending on how stubborn they are. Vice versa, when the susceptibility of all nodes is the same (panel C of Figure 1), we observe the unfiltered effect of centrality: the most polarizing prejudices are those in which the most central nodes have initial opinions close to 1, and their final opinion changes much less than the others' opinions. This also confirms that the PageRank centrality is able to capture the ability of nodes to convince the others, and thus it identifies the most influential nodes.
In Figure 2 we can see the results obtained with the Facebook network. In this case, since the network is large, it is not possible to find the global solutions s max P 2,3 and s max P 4 . However, the considerations we made for the Karate graph hold also in this case. In particular, the polarizing vectors assign to more stubborn nodes initial opinions closer to 1, so that they can influence susceptible nodes to which they are connected. In the Facebook network, though, due to the scale-free topology with just a few hubs and many poorly connected nodes, we also observe very susceptible nodes that do not change their opinions (Figure 2, panel B). These nodes have typically a single edge towards a stubborn node sharing its opinion.

Conclusions
In this work we have investigated under which conditions the popular Friedkin-Johnsen model yields polarised opinions. The first contribution of the work has been to systematize the variety of FJ models used in the literature, and the many definitions of polarization. Then, as the main contribution of the work, we have derived the conditions under which the FJ models yield to polarization, for each of the polarization classes identified from the related literature. Moreover, we have identified a methodology for obtaining polarizing prejudices in most cases. When exact solutions could not be found (because the corresponding problem was NP-hard), we have defined heuristics to find a sub-optimal solution. Our theoretical results have then been tested on two real-life social networks. Through this evaluation, we have seen that both the centrality of nodes in the social network as well as their individual susceptibility to the opinions of other nodes play a key role in defining their influence power, hence their ability to polarize.
In each panel, on the left the opinions yielding P 2 , P 3 -polarization, on the right the opinions yielding P 4 -polarization. With the dotted and dashed line we denote the average initial and final opinion, respectively.

Materials and methods
The Karate Club dataset [35] corresponds to an unweighted graph composed of 34 members. The Facebook dataset is a Facebook snapshot comprising 4039 users [37]. Also in this case the graph is unweighted. After discarding isolated nodes (since they do not contribute at all to the opinion formation process), we end up with a network of 1519 nodes. With these datasets we obtain the valuesŵ ij that describe the social links between different users.
For both graphs, we obtain the influence matrix from the social matrixŴ normalizing by rows, i.e. w ij =ŵ ij kŵ ik . To proceed with the analysis we should set the susceptibility values of nodes, which are not fixed by the social network. To this aim, since both networks have a few very central nodes, as displayed in the SI Appendix, we decided to use a centrality measure to set them. In the following we will show the results obtained considering the PageRank centrality, which is the centrality measure that better captures the influence among nodes [30], but similar results hold with other centrality measures (betweenness, degree, eigenvector and k-shell centrality). In our experiments, if the Pagerank centrality of a node i is C i , we assign λ i the value of C i (and C −1 i ) rescaled to (0, 1), so that the more central the nodes (and, respectively, the less central), the higher their susceptibility values. Furthermore, we will also show the case in which all nodes have the same susceptibility, set to 0.8. In the SI Appendix, we provide a visualization of the social networks we consider and of the susceptibility values obtained in this way for both datasets.
In each panel, on the left the opinions yielding P 2 , P 3 -polarization, on the right the opinions yielding P 4 -polarization. With the dotted and dashed line we denote the average initial and final opinion, respectively.
[35] Wayne W Zachary. An information flow model for conflict and fission in small groups. Journal of anthropological research, 33 (4)

A Preliminaries
In this section, we will summarize the main notions from graph theory, linear algebra and spectral theory that are used in the paper. The aim is to provide a brief exposition of the basic concepts so that readers who are not familiar with them will still be able to follow the discussion.

A.1 Graphs
We will start this excursus with the definition of graphs and their properties. Definition 4 (Graphs). A graph G = (V, E) is a pair composed by a set V that collect the nodes of the graph and a setE ⊂ V × V that define the edges of the graph, which defines the links among the graph nodes. A graph is said undirected whether (i, j) ∈ E if and only if (j, i) ∈ E for each pair (i, j). On the contrary, the graph is said directed.
The definition of a graph can be refined to include some additional information on the edges, i.e. their "strength". This is done with the notion of weighted graph. Definition 5 (Weighted graph). A weighted graph is a graph where all edges (i, j) ∈ E have a weight w ij that define the strength of the link. More formally it s a triple G = (V, E, W ) where V, E are defined as in the definition 4, while W is a matrix whose entry w ij represents the weight of the edge (i, j).
Another way to define a graph is to start from a matrix using the following definition. Some important properties of a graph are related to its connectivity, which determines if and how it is possible to walk within the graph from one node to another one crossing the edges. These definitions are given for undirected graphs.
Formally we have the following definition: Definition 7 (Walks). A walk of length k on the graph G from node i to node j is a sequence of k nodes i 0 , . . . , i k such that i 0 = i, i k = j, and (i l , i l+1 ) ∈ E for l = 0, . . . , k − 1. If the walk does not contain intersections, i.e. i r = i s for r = s, is said a path.
Walks are the notion used to define graph connectivity. Definition 8 (Strong connectivity). A graph G is said strongly connected if any pairs of nodes i, j is connected by a walk.
A graph defines also some matrices that we have used in the paper. Definition 9 (Adjacency matrix, diagonal degree matrix, Laplacian matrix). Given a weighted graph G = (V, E, W ) it is defined the adjacency matrix the matrix A = (a ij ) whose elements are given by a ij = w ij for i = j and 0 otherwise. The diagonal degree matrixis a diagonal matrix D = (d ij ) whose i-th diagonal element is d ii = j =i w ij . The Laplacian matrix is the matrix L defined as L = D − A, so that its (i, j)-th entry is given by:

A.2 Nonnegative matrices and M-matrices
Some fundamental properties of nonnegative matrices that will be used throughout the paper are summarized in the following.
is strongly connected.
Nonnegative matrices benefit from the spectral property related to an eigenvector corresponding to the biggest eigenvalue of the matrix itself. This is what the Perron-Frobenius theorem states. Theorem 9 (Perron-Frobenius). For a nonnegative matrix M , the spectral radius ρ(M ) ≥ 0 is an eigenvalue which has a real nonnegative eigenvector. In particular, if the matrix M is irreducible, the eigenvalue ρ(M ) is simple which has a real eigenvector with strictly positive entries.
Another property that is used in the paper is related to nonnegative matrices that are also stochastic. Lemma 4. If B is a nonnegative stochastic matrix, all its eigenvalues have modulus smaller or equal to 1.
Proof. Let B = (b ij ) and consider the i-th row of B. For the Gerschgorin Disk Theorem, the i-th eigenvalue is contained in the disk centred in b ii and radius r i = j =i |b ij | = j =i b ij . This means λ i has modulus in But this is obvious, because, for stochasticity, A special class of nonnegative matrices is that of M-matrices. Definition 11. A square matrix N is an M-matrix if it admits a decomposition in the form N = rI − C, where r ≥ ρ(C) and the matrix C is nonnegative.
The following proposition provides a criterion to determine if a matrix is an M-matrix. Proposition 1. Let Z = (z ij ) be a square matrix that satisfies the two following conditions: Then, Z is an M-matrix, i.e. it admits a decomposition Z = rI − C where A is nonnegative and ρ(A) ≤ s whenever s ≥ max i z ii .
The M-matrices have some nice properties and one of them is about its inverse.  Table 6: Notation used in the paper B Supplemental information on the modeling framework In Table 6 we have summarized the notation used through the main paper and in the rest of this SI.

The generalized Friedkin-Johnsen model -gFJ
We summarise here the main findings in the related literature [22,29,14] about the conditions under which the gFJ model achieves convergence and consensus. Recall that convergence only implies that nodes have reached a steady-state opinion (i.e., their opinion doesn't change anymore), while consensus is much stronger (and unrealistic) since it implies that the steady-state opinions are all equal. Theorem 10 (Convergence of gFJ). Under the following conditions, the gFJ model is convergent: Sufficient condition: If ΛW is stable, the gFJ model is convergent and the only stationary point z (i.e., steady-state solution) is given by the following [28]: In turn, a sufficient condition for gFJ convergence [29] is that the influence graph is strongly connected and Λ = I, i.e., at least one agent anchored to its initial opinion exists 4 .
Necessary and sufficient condition: The gFJ model is convergent if and only if ΛW is regular, i.e., the limit lim k→∞ (ΛW ) k exists and is finite [14].
We now provide the conditions under which consensus is reached.
Theorem 11 (Consensus with gFJ). Assuming that the gFJ model is convergent (i.e. ΛW is regular), for the gFJ model to reach consensus regardless of the nodes' initial opinions, this sufficient condition must hold [22]: the graph of ΛW contains an unique strong component with at most one node with λ i < 1 and the rest of nodes have λ i = 1.
Note that the condition for consensus is pretty restrictive (it entails all nodes but one being 100% susceptible to others' opinions, without any personal preference). For this reason, a consensus is not a common outcome of the gFJ opinion formation process.

B.1 The variational Friedkin-Johnsen model -vFJ
As highlighted in the main paper, vFJ is not able to capture the same varieties of scenarios of the gFJ since the degrees of freedom are fewer in the vFJ. Here we would like to put in evidence how the vFJ can be obtained from the gFJ by a specific mapping. In detail, when the gFJ is modified such that the current opinion z i is not influential in forming a new opinion (i.e., w ii = 0), the gFJ and vFJ models are indeed interchangeable. Specifically, fixing the desired susceptibility λ i for the gFJ model, theŵ ii of vFJ can be obtained as follows:ŵ ii = (1−λi) λi j∈N (i)ŵ ij . The above is simply obtained by forcing the weights anchoring both models to s i to be equal, i.e.,ŵ ii j∈N (i)ŵ ij = 1 − λ i .

B.2 The restricted Friedkin-Johnsen model -rFJ
The advantage offered by rFJ lies in the fact that L + I is symmetric (and so is its inverse), while (I − ΛW ) −1 (I − Λ) in (34) is not (Λ is symmetric, W is not, in general, but, even if it were, symmetry does not carry over to the product, in general). Many useful matrix formulas rely on the symmetry assumption, which does not hold here. Incidentally, this is also the most interesting case, since it avoids the unrealistic case of no choice shift, as discussed in [38].

C Polarization invariants
In this section, we include the proof of the results of the main paper.

C.0.1 Proof of Lemma 1
The thesis is trivial by observing that: We can rewrite the definition of where t x = x, 1 . So, we can derive easily that: Now, it is obvious to observe that t x = x, 1 ≤ |x|, 1 = P 4 (x), which is an equality if x ≥ 0. Thus, applying these relations to (35) we obtain the thesis. This concludes the proof.

D Classes of polarization: numerical examples
In this section, we discuss in more detail the classes of polarization. The result in Lemma 3 of the main paper highlights the correlation among them and shows how the dynamics of one of them influence the dynamics of the others. However, it cannot be so immediate to understand case examples where they behave differently. For this reason, in the following we will provide three examples of networks where we show that the three classes behave differently, i.e. they can either increase or reduce their polarization independently from the other classes. Example 1. Here we will provide an example in which gFJ is not polarizing according to the Dispersion class, but it is polarizing according to the Total and Absolute Classes. Consider the network in Figure 3.
Node A is naive, node C is stubborn and node B has susceptibility equal to 0.5. For the prejudice vector s = (0, 1, 1), it is easy to see that the final opinion is z = (1, 1, 1), since the naive node moves its opinion according to that of the other two. The nodes are in agreement in the end and thus the GDI, P 1 -polarization is negative, because the spread around the average is reduced. Instead, since opinions move toward the extreme 1, the polarization with P 2 , P 3 , P 4 is positive. Two of the nodes (A and D) are stubborn and thus they only influence others' opinions; the other two have susceptibility equal to 0.5. For the prejudice vector equal to s = (0, 0.5, 0.5, 1) we can calculate that the final opinion is z = (0, 0.6, 0.4, 1), thus the non-stubborn nodes move their opinions towards the stubborn ones. Since the final opinion is more spread around the average (equal to 0.5 as for the prejudice), the polarization increases for GDI, P 1 . The same happens for P 2 , P 3 because the movement of node C's opinion determines an increase in the quadratic closeness to the extreme 1. Instead, the linear closeness to extreme 1 is the same, and thus we have negative polarization with P 4 . This proves that the Total class behaves differently with respect to the Absolute and Dispersion classes.
Example 3. In this last example, we modify an edge of Example 2 so that gFJ becomes polarizing according to the Dispersion class and not polarizing for the Total and Absolute class. As can be seen in Figure 3.(c), we increase the weight of the edge between the node A and C, obtaining then an influence matrix given by: In this way, starting from the same the prejudice vector s = (0, 0.5, 0.5, 1), the final opinion becomes more unbalanced toward neutrality (the opinion of the stubborn node A), since z = (0, 0.59, 0.35, 1). The final opinion is still more spread around the average (equal to 0.5 as for the prejudice), and the polarization is positive for GDI, P 1 . Instead, both the linear and the quadratic distance to the extreme 1 become smaller and this results in P 2 , P 3 , P 4 non-polarization.

E Polarization with the FJ models
In this section, we provide the proofs of theorems that are not included in the main paper.

E.1 Proof of Theorem 2 (gFJ: local polarization with NDI)
Let z be the stable opinion of gFJ. In the following, we prove that the equilibrium z = (I − ΛW ) −1 (I − Λ)s of gFJ (given by Theorem 1 in the main paper) is the collection of Nash equilibria, for all nodes of the network, of all the cost functions of (21) in the main paper, i.e. f i (z This result will provide the basis for showing the gFJ is non-polarizing with NDI. Consider the iteration x(k) of gFJ at step k. The value x i (k + 1) that minimize the function f i evaluated in x(k) can be easily computed as follows: which corresponds to the (k + 1)-th iteration of the gFJ model. This means that the iteration problem of gFJ is exactly the point that for each node i minimizes f i , and thus the unique convergence point is the minimum of the cost function, i.e. the Nash equilibrium.
Based on the above result, z is the Nash equilibrium of the functions f i of equation (21) in the main paper. Thus, by definition, we have that, for all i, f i (z i ) ≤ f i (s i ). This means that the following holds: From the above, we obtain: and summing over i we get: Since, by definition, 1−λi λi ≥ 0 and (s i − z i ) 2 ≥ 0, the thesis is proven.

E.2 Preliminary lemmas for the polarization proofs
In the following, we will provide a list of preliminary considerations that will allow deriving the results on polarization for the whole set of FJ models. Matrix H has two nice properties: it is stochastic and nonnegative.

Lemma 5.
Matrix H is stochastic and nonnegative.
Proof. We start by proving that H g , defined as H g = (I − ΛW ) −1 (I − Λ), is stochastic, i.e. H g 1 = 1. We can write the latter as follows: and multiplying both the sides by (I − ΛW ) we have that: which is true because W is stochastic. Now we prove that matrix H g is nonnegative because it is the product of two nonnegative matrices, which are (I − ΛW ) −1 and (I − Λ). Obviously (I − Λ) is nonnegative because λ i < 1. Instead, (I − ΛW ) −1 is nonnegative because it is the inverse of an M-matrix (see Definition 11). In fact, I − ΛW is an M-matrix with r = 1 and C = ΛW , because ΛW is substochastic (its i-th row is obtained multiplying λ i for the i-th row of W whose sum is 1), and thus ρ(ΛW ) < 1. M-matrices have some nice properties, one being that any invertible M-matrix is such that its inverse is nonnegative, which is exactly what we needed.
For what concerns H v and H r , the thesis comes, thanks to the mapping in (30) and (31), which reduces vFJ and rFJ to gFJ. In fact, with this mapping, also H v and H r can be written as (I − ΛW ) −1 (I − Λ) with W stochastic. Thus, the thesis derives.
Since H is stochastic and nonnegative, we have as a trivial consequence that for every p ∈ [1, ∞), the p-norm of H, defined as the norm induced by the p -norm on R n , is such that: being H1 = 1 for stochasticity. In terms of polarization, this implies it exists an s such that Hs p ≥ s p . Because H is stochastic, the 1-and 2-norm values of H are strictly connected to the structure of H. This is what the following lemma states. Lemma 6. Let H be a stochastic matrix. The following three conditions are equivalent: (i) H is doubly stochastic; (ii) H has 2-norm equal to 1; (iii) H has 1-norm equal to 1.
Proof. It is sufficient to prove that (i) is equivalent to (ii) and to (iii). Let us now start proving the equivalence of (i) and (ii). In particular, we will prove that any stochastic matrix B is doubly stochastic if and only if B 2 = 1. Please observe that this will also imply that in the case of H not being doubly stochastic, its norm would be strictly greater than 1.
Suppose B is doubly stochastic; then so it is B T B, which is the conjugate transpose of B. The 2-norm of a matrix and the greatest eigenvalue of its conjugate transpose are linked by the following relation: B 2 2 = ρ(B T B) = 1, where the last identity stems from a well-known result in linear algebra [39]. Conversely, suppose that B 2 = 1; we have to that B is column-stochastic, i.e. B T is row stochastic, which in matrix form can be written as B T 1 = 1. In order to prove this, we have to derive some properties of B T , of which we know that B T 2 = B 2 = 1. For the stochasticity of B, we can write the following chain of inequalities: Since the first and the last terms are identical, ties must occur in the two inequalities above and these are sufficient for us to derive the claim. In fact, they respectively imply that B T has the following properties: (i) B T 1 = c1, for c > 0, and (ii) B T 1 2 = B T 2 1 2 which, applying (i), becomes c 1 2 = c 1 2 , thus c = 1. Finally, we get that B T 1 = 1, which proves that B is doubly stochastic. Now we will prove the equivalence of (i) and (iii). Let us start by proving that (i) implies (iii). It is well known that the 1-norm of a matrix can be computed as the maximum among the sums of its column elements, i.e.
which is equal to 1 in the case of double-stochasticity. Instead, suppose that the 1-norm of H is equal to 1. Ad absurdum, if H would not be doubly stochastic, for what we have already proved H 2 would be greater than one. But, since it holds that, by Hölder's inequality, H 2 2 ≤ H 1 · H ∞ = H 1 (because for stochasticity H ∞ = 1), we would obtain a contradiction. This concludes our proof.

E.3 Proof of Corollary 2
Since H g is doubly stochastic, for Lemma 6, we have that the 1-and 2-norms of H g are equal to one. It is a trivial remark that H g is doubly stochastic if and only if H −1 g is doubly stochastic and, as well, this fact is equivalent to the 1and 2-norm of H −1 g being equal to one. By hypothesis, for all s, the P 2 , P 3 , P 4 depolarization implies that: Dynamics of opinion polarization and P 4 (H g s) − P 4 (s) = H g s 1 − s 1 ≤ 0.
(48) But, we have also that: where z = H g s. In (49) we have used the matrix-norm property given by H −1 g z 1 ≤ H −1 g 1 z 1 and in (50) the fact that H −1 g 1 = 1. By (51) and (48) we obtain that for all s: which proves the first part of the thesis. We can observe that: where in (53) we have used the double-stochasticity of H g . This proves the second part of the thesis.

E.4 Proof of Theorem 3, Theorem 5.(i), and Theorem 6.(i)
The proof is composed of four parts. In Part 1, we prove that if H g is doubly stochastic, gFJ is depolarizing for P 2 , P 3 and P 4 , i.e. Φ(z) ≤ Φ(s). In Part 2 prove that if H g is not doubly stochastic, gFJ is polarizing for P 2 , P 3 and P 4 , i.e. for Φ = P 2 , P 3 , P 4 it exists a prejudice vector s 0 such that the corresponding final opinion z 0 satisfies Φ(z 0 ) > Φ(s 0 ). The proof is constructive and and will identify the vectors of Theorems 5.(i) and 6.(i). Thus, from the first two parts we derive the first part of Theorem 3. In Part 3, we see that the polarization implies that for a node i it holds the following condition: This implies the thesis of Theorem 3.(ii). Finally, in Part 4 we discuss the role of naive nodes, and thus we prove Theorem 3.(i).
PART 1. We assume that H g is doubly stochastic, thus, for Lemma 6, it has 2-norm and 1-norm equal to 1. These matrix norms are defined as The hypothesis implies that for p = 1, 2 and for all s = 0, Obviously, this inequality holds as an equality also for the prejudice s = 0, and this implies that the model is depolarizing for P 4 in the case p = 1 and for P 2 and P 3 in the case p = 2. This proves this part.
In this part of the proof we have shown (ad absurdum) that if gFJ is polarizing with P 2,3,4 , then matrix H g is not doubly stochastic. This corresponds to the necessary condition of the first part of Theorem 3.
PART 2. Now, suppose that the matrix is not doubly stochastic and let determine the polarization with P 2 , P 3 and P 4 . For Lemma 5, we know that H g is stochastic and thus, for Lemma 6, the 1-norm and the 2-norm of H g is necessarily strictly greater than one (it cannot be smaller than one since H g 1 = 1). Being H g p > 1 (p = 1, 2), from the definition of p-norm as in (55), we have that it exists a p-unitary vector s 0 that realizes the p-norm of H g , i.e. that is the maximum of the ratio Hgs p s p . Please observe that such s 0 depends on the p considered, meaning that the vector s 0 that realizes H g 2 is different from the vector that realizes H g 1 . We will see that, however, in both cases such a vector yields to the maximum value of the function s → H g s p − s p on the ball B p (1). In fact, it holds that H g p = H g s 0 p > 1 = s 0 p and for all s ∈ B p (1) it holds: This equation implies that for all s ∈ B p (1), it holds: where in (58) we have used the inequality (56) and in (59) we have used that s p is positive and smaller than 1. Thus, that such s 0 is the polarizing vector that yields to the maximum polarization of P 2 and P 3 on B 2 (1) if p = 2, whereas to the maximum polarization of P 4 on B 1 (1) if p = 1. Since B 2 (1) ⊂ [−1, 1] n and B 1 (1) ⊂ [−1, 1] n , both vectors are for opinion vectors. Thus, to obtain the thesis we need to identify s 0 separately for p = 1, 2 and prove that they have concordant entries and that also −s 0 is a point of maximum.
Let now start with p = 2. It is a well-known result that the 2-norm of a matrix H g is equal to its singular value σ, i.e. the square root of the largest eigenvalue of matrix H * g H g (where H * g denotes the conjugate transpose of H g , equivalent to H T g since H g is real-valued).
To be more precise σ and H g are linked by the following relation: Let s 0 be the vector that realizes the 2-norm (and thus that leads to the P 2 , P 3 -polarization) is then the unitary eigenvector associated with σ 2 and chosen with all positive entries. In fact, assuming that it is possible to choose the eigenvector s 0 in such a way, ±s 0 verify the following: which proves that gFJ is polarizing with P 3 (and, given their equivalence, with P 2 ) in ±s 0 . In (63), we have leveraged the identity between the squared 2-norm of a vector and its inner product, the identity , as well as the identity H T g H g s 0 = σ 2 s 0 (σ, the largest singular value of H g , is by definition the square root of the largest eigenvalue of H T g H g ). Since s 0 is unitary, s 0 , σ 2 s 0 can be replaced with σ 2 . The fact that σ 2 is greater than 1 follows from the identity H g 2 = σ (we are assuming that H g 2 > 1 for first part of the proof).The relationship s 0 2 2 ≤ 1 follows from s 0 being unitary. To conclude the proof for p = 2, we need to show that, it is possible to choose a unitary eigenvector s 0 (corresponding to eigenvalue σ 2 ) with positive entries. This simply follows from the nonnegativity of H g . In fact, for the Perron-Frobenius theorem, every nonnegative matrix B is such that it is possible to choose a unitary eigenvector with positive entries for the eigenvalue ρ(B). Please observe that such an eigenvector is a valid choice for a prejudice vector since being unitary and with positive entries, its components lie in the interval [0, 1] for sure.
Finally, we focus on p = 1 and identify the 1-norm unitary prejudice vector that realizes H g 1 . As already observed in (46), the 1-norm of a matrix can be computed as the maximum among the sums of its column elements. The j-th column of H g is exactly H g e j , where e 1 , . . . , e n is the standard basis in R n , and besides we obtain that: Since we are in the hypothesis of being H g 1 strictly greater than 1, one of the standard basis vectors, let say e j , is unitary and such that H g 1 = H g e j 1 = H g (±e j ) 1 > 1 = ± e j 1 . Thus s 0 = e j is the opinion vector that we were searching for. This concludes the proof.
In this part of the proof we have shown if matrix H g is not doubly stochastic, then gFJ is polarizing with P 2,3,4 . This corresponds to the sufficient condition of first part of Theorem 3. Furthermore we have identified the polarizing vectors ±s B2(1) and ±s B1(1) of Theorems 5.(i) and 6.(i) respectively.
PART 3. We now prove that the doubly stochasticity of H g is equivalent to having that, for all i, j wij 1−λj = 1 1−λi holds true. Being H g invertible by hypothesis, H g is doubly stochastic if and only if its inverse is doubly stochastic too, in fact H T g 1 = 1 implies the following: Now we only have to write matrix H −T g , which can easily be obtained in the following way: Looking at the above elements of H −T g , the equality in (65) is satisfied if and only if, for all i, it holds the following: Thus, when the above condition is not satisfied, the inequality between Φ(z) and Φ(s) becomes strict (i.e., Φ(z) > Φ(s)) and P 2 and P 3 become polarizing for gFJ.
Summing up, in this third part we have proven that the non-doubly-stochasticity of matrix H g implies condition (54) being true for at lest an index i, i.e item (ii) of Theorem 3.
PART 4. We now study the case in which naive nodes are present in the social network. Recall that naive nodes are nodes that do not value at all their prejudice and are completely swayed by the opinion of the other nodes. Modelling-wise, this translated into λ i = 1 for these nodes. As seen for Theorem 3, the polarization properties of gFJ are linked to the properties of matrix H g = (I − ΛW ) −1 (I − Λ), which is the one that transforms the prejudice s into the vector of final opinion z = H g s. From what we have already proved, it is sufficient to prove that H g is not doubly stochastic, so that gFJ would be depolarizing. To this aim, let us study matrix H g , which is equal to (I − ΛW ) −1 (I − Λ). Recalling that I denotes the set of naive nodes and J the others, without loss of generality, we can assume that I = {1, . . . , |I|} (i.e., the first |I| nodes are naive), so that matrix I − Λ can be written as: where Λ J ,J denotes the sub-matrix of Λ with entries in (J , J ). Matrix I − Λ does not have a full rank, hence it is not invertible (and, as a consequence, neither is H g ). Now, using the same node ordering, we can write (I − ΛW ) −1 in the following way: (72) guarantees that H g cannot be doubly stochastic (the first I columns sum to 0).
In this part of the proof we have shown that, when naive nodes are present, it always exists an initial opinion vector that yields strict polarization. This corresponds to item (i) of Theorem 3.

E.5 Proof of Theorem 4 (P 2 , P 3 , P 4 polarizing vectors have concordant entries)
We start by proving that, for all prejudice vectors s and for the polarization indices P i with i = 2, 3, 4, we have that: For all vectors s in R n it holds that: Since the matrix H is nonnegative for Lemma 5, it holds that: Now, for P 4 we can write that: Furthermore, we have: where in (77) we have used (75) for the first addend. This proves our claim for P 4 . Let us now consider P 3 (from which we derive the thesis also for P 2 ). In this case we have:

Dynamics of opinion polarization
And similarly to (78), we have: Now we can prove the first part of the thesis. In fact, if s is a polarizing vector, also ±|s| are polarizing vectors with concordant entries inducing larger polarization. For the second part, we suppose ad absurdum that the prejudice vector that maximizes the polarization has no concordant entries, so there exist two nodes n, p such that s n < 0 and s p > 0 and thus the inequalities in (74) become strict. Now, if all nodes were stubborn the model would not polarize because: So, in the hypothesis of the gFJ model being polarizing, it exists a node k non-stubborn. Since we are assuming that G[ΛW ] is strongly connected, there exist two walks (i 1 = k, . . . , i l1 = n) and (j 1 = k, . . . , i l1 = p) that connect k and n, p respectively in the graph G[ΛW ]. Thus, the (k, p), (k, n) entries of the matrix (ΛW ) l1l2 are strictly positive, and the same holds true for H. In fact: thus for j = n, p the first term is strictly positive (please recall that neither node is naive) and the second is positive. From this we derive that: where in (82) we have used that s j ≥ −|s j | for all j and that H is nonnegative, while in (83) we have used that s p −|s p | because s p is strictly positive. Analogously, we have that: where in (85) we have used that s j ≤ |s j | for all j and that H is nonnegative, while in (86) we have used that s n −|s n | because s n is strictly negative. This implies that the equation in (75) becomes strict on both sides, and thus also for (78) and (81). In conclusion, ±|s| bring about a polarization strictly greater than that of s, which contradicts the hypothesis. This concludes the proof.
E.6 Proof of Theorem 5.(ii-iii) (gFJ: polarizing initial opinions for P 2 , P 3 ) We have already seen in the section above that in the hypothesis of non-double stochasticity of H, we can identify two unitary vectors ±s 0 that maximise the polarization ∆(s) = H g s 2 2 − s 2 2 on the L 2 ball B 2 (1) = {x ∈ R n : x 2 ≤ 1}. This was the proof of item (i) of Theorem 5. Let us move to item (ii). It is obvious that, for all t > 1, t s 0 would achieve a greater value of ∆(s) than those calculated on ±s 0 , because, for the sub-linearity of the matrix norm operator, we have that ∆(t s 0 ) = t 2 ∆(s 0 ). The maximum admissible t is the largest for which t(±s 0 ) are opinion vectors, i.e. they lie in the ∞-norm unitary ball B ∞ (1) = {x ∈ R n : x ∞ ≤ 1} (note that here we use the norm to denote the domain of s 0 , not in relation to the polarization metrics). This vector can be determined easily: let k be the index of the largest component of s 0 (the vector with positive entries), i.e.: thus, t can be taken as t = 1/s k 0 . In fact, t(±s 0 ) are opinion vectors because for all components i, 0 ≤ t s i 0 ≤ t s k 0 = 1 and 0 ≥ −t s i 0 ≥ −t s k 0 = −1, and obviously they are polarizing vectors because t H (±s 0 ) 2 = t H (±s 0 ) 2 > t (±s 0 ). These vectors lead to the maximum of the function ∆ on the compact set B 2 (t) ∩ B ∞ (1). Thus, point (ii) of Theorem 5 is proven. Now we move to Theorem 5.(iii). By Theorem 4, the polarizing vectors can be searched with concordant entries. We will describe how to proceed for the one with positive entries s max P 2,3 ; then −s max P 2,3 is the one with negative entries with the same polarization value (by Theorem 4). We will proceed in several steps: at first we derive the basis B and we describe some convenient properties of that basis; secondly we derive the optimization problem of (23); finally we prove that the problem is NP-hard.
Let us start with the first step and build another basis of R n that is the basis B of the statement. Being the matrix H T g H g real and symmetric, for the theory of diagonalization we have that: • its eigenvalues σ 2 i are real and they are the square of the singular values of H g . We can sort them in decreasing order, so that we have σ 2 1 ≥ σ 2 2 ≥ · · · ≥ σ 2 n ≥ 0, counting them with their multiplicity; • its eigenvectors constitute an orthogonal basis of R n and, after normalization, they can be supposed to be unitary. We can denote them as v 1 , . . . , v n , assuming that v i is the unitary eigenvector of H T g H g corresponding to the eigenvalue σ 2 i , i.e.
In general, the eigenvectors v i are not opinion vectors, since their components can be negative. But, for the Perron-Frobenius theorem, as already seen in the proof of Theorem 3, the eigenvector related to the biggest eigenvalue σ 2 1 has concordant entries and thus, unless substituting it with its opposite, can be taken with positive entries. In particular, v 1 = s B(1) . In the end, we have obtained an orthornormal basis B = {v 1 , . . . , v n }. As it follows from standard linear algebra, the matrix B whose i-th column is the vector v i expressed in the standard coordinates determines the change of basis between B and the standard basis in R n . To be more precise, matrix B is expressed by: where we have denoted with v (k) i the k-th entry of v i . In other terms, if a vector v is expressed in B as the combination v = i β i v i , where β i ∈ R and β = (β 1 , . . . , β n ) T , β is the vector that expresses v in terms of the basis B, whereas Bβ expresses v in its standard coordinates in R n . We can also observe another characteristic of the basis B, which we will use in the following: the vectors H g v 1 , . . . , H g v n , the images of the vectors of B through the operator H g , are orthogonal and have 2-norms equal to H g v i 2 2 = σ 2 i . In fact, we have that: where δ ij is the Kronecker delta, which gives 1 if i = j and 0 otherwise. This concludes the first step.
With the second step we describe the optimization problem and which is the opinion vector s max P 2,3 that maximizes the P 2 , P 3 polarization. In fact, a generic opinion vector s can be expressed in terms of the basis B as a linear combination of its elements, i.e. s = i α i v i with α i ∈ R. Since s is with positive entries, its standard coordinates in R n have to lie in [0,1]. For what we have observed in the first step, this can be easily expressed by Bα ∈ [0, 1] n that is exactly the constraint in (23).
We have derived the constraint of the problem. To derive the objective function, we have to express the polarization of this generic s in terms of α. We thus can observe that: where in (94) we have used the property derived in (93) and in (95) the orthonormality of B. Thus the vector s max P 2,3 is the one that maximises ∆(s) = i α 2 i (σ 2 i − 1), which is associated with the vector α max P 2,3 that maximizes the objective function of the optimization problem in (23). This proves that the solution of (23) gives the vector that yields the maximum of P 2 , P 3 polarization.
We now prove that the problem is NP-hard. In fact, let us consider the matrix Q provided by: the problem in (23) can be rewritten as: since ∆(s) = 1 2 α T Qα. This formulation highlights that the problem is a quadratic programming problem and is non convex because Q is not positive semi-definite but rather it is indefinite, i.e. neither positive nor negative semi-definite. In fact, since we are in the hypothesis of gFJ being polarizing, from the proof of Theorem 3, σ 1 > 1 and thus the first entry of Q is positive. The last entry, instead, cannot be positive: since H g is nonnegative and stochastic, all its eigenvalues λ 1 , . . . , λ n have modulus smaller or equal that 1 for Lemma 4, and for the Weyl's inequality it holds that: |λ 1 · · · · · λ n | = σ 1 · · · · · σ n .
The left-hand side of the equation is smaller than or equal to 1 and, since in the right-hand side σ 1 1, at least σ n 1.
It follows that Q is indefinite and that the objective function is non-convex. Thus, the problem is a non-convex quadratic optimization problem with linear constraints, which is NP-hard. This concludes the proof.
E.7 Proof of Corollary 3 (gFJ: polarizing initial opinions for P 2 , P 3 on the subspaces V >1 and V ≥1 ) In the case of matrix H g having more than one singular value greater than one, it is possible to design a sub-problem of the optimal problem described in Theorem 5.(iii). The detailed formulation of Corollary 3 in the main paper is provided below.
Corollary 3 (extended version). Under the same hypotheses of Theorem 5 and if matrix H g has singular values greater than or equal to 1, it holds the following.
(i) If H g has singular values strictly greater than 1, say σ 1 ≥ · · · ≥ σ l , and V >1 is the vector space generated by V = {v 1 , . . . , v l }, the opinion vectors ±s V>1 that yield the local maximum for P 2 , P 3 -polarization on V >1 have concordant entries. The positive vector s V>1 is given by s V>1 = l i=1 α i v i , where vector α that express s V>1 in terms of B is α = (α 1 , . . . , α l , 0, . . . , 0) T and its l nonnull coordinatesα = (α 1 , . . . , α l ) T are the unique solution to the following optimization problem: whereB denotes the n × l submatrix of B. Please note that the solution to the problem is different from the vector s max P 2,3 , because it only searches along the dimensions associated with greater-than-1 singular values. This problem is a convex quadratic optimization.
Let us prove item (i). In particular, we will prove that if the global problem in 98 is restricted to the subspace V >1 generated by the vectors v i corresponding to singular values σ i > 1, it is possible to determine the vectors on V >1 that maximize the P 2 , P 3 polarization with standard solvers. As done in the proof of Theorem 5, we will describe how to proceed for the the vector s V>1 with positive entries. Then, the vector −s V>1 with negative entries is still in V >1 (because V >1 is a vector space) and has the same polarization value (as stated by Theorem 4). Consider the singular values σ i greater than one; in particular, since they are sorted in decreasing order, if l is the greatest index for which σ l > 1, they are the σ i with i = 1, . . . , l. Then, if we restrict the problem to the subspace V >1 = v 1 , . . . , v l , we have to consider only the opinion vectors that can be written as s = α 1 v 1 + · · · + α l v l , i.e. that have coordinates in B equal to α = (α 1 , . . . , α l , 0, . . . , 0) T . The problem in (98) can thus be rewritten as: whereα = (α 1 , . . . , α l ) T is the projection of α on V ,Q andB denote the n × l submatrices of Q and B respectively, whereas in (104) we intend 0 and 1 to be the l-dimensional vectors of 0's and 1's respectively. Differently from the problem in (98), this problem is a convex quadratic programming with linear constraints, because the matrixQ is strictly positive definite, thus the problem has one and only one optimal solution s V>1 ∈ R l . This optimum can be found using standard algorithms as the ellipsoid or the interior point methods, which run in polynomial time with the input data (in this case the input data are multiple of l). The unique solution α V>1 = (α 1 , . . . , α l ) T of (104), which corresponds to the vector s V>1 = α 1 v 1 + · · · + α l v l , leads to the maximum of the objective function in (100) over V and its value on ∆ is not smaller than whose of s B(t) at the point (ii) of Theorem 5, i.e. ∆(s V>1 ) ≥ ∆(s B(t) ) because s B(t) ∈ V >1 . This proves point (i) of Corollary 3.
Finally, we conclude the proof by considering item (ii). Specifically, if there are singular values σ i equal to one, we determine all the vectors that yield the maximum polarization on the subspace V ≥1 generated by the vectors v i corresponding to singular values σ i ≥ 1. To do this, we will see that the value of ∆ for all points on V ≥1 is exactly the same value on their corresponding projections on V >1 . With the same notation used before, let us denote with σ 1 , . . . , σ l the singular values strictly greater than 1 and with σ l+1 , . . . , σ l+m the singular values equal to 1 (please remind that we have enumerated them with their multiplicity). Furthermore, let us indicate, for convenience of notation, with V =1 the subspace v l+1 , . . . , v l+m . The opinion vectors obtained as: are all and the only optimal points of ∆ on the subspace V ≥1 = V >1 ∪ v l+1 , . . . , v l+m . In fact, every vector ±s in V ≥1 can be written as ±s = l i=1 (±α i )v i + m j=1 (±α l+j )v l+j , which can be seen as the sum of a vector s >1 ∈ V >1 and a vector s =1 ∈ V =1 , where obviously s >1 = l i=1 α i v i and s =1 = m j=1 α l+j v l+j . We have already seen that the function ∆ is such that: this quantity is trivially equal to ∆(±s >1 ) + ∆(±s =1 ). Now, for all s =1 ∈ V =1 , the value of ∆ is null because the σ l+j = 1 for all j = 1, . . . , m and thus the second addend of (106) is null. In other terms, ∆(±s) = ∆(±s >1 ) and we can deduce that for all s ∈ V ≥1 , holds that: Please observe that here ±s >1 is the projection of a generic vector ±s on the subspace V >1 , whereas ±s V>1 is the vector obtained in Corollary 3.(i) which maximises the polarization on V >1 . In conclusion, (107) proves that ±s V ≥1 as in (101) are the only maximal points of ∆ on V ≥1 .
Since all the solutions ±s V ≥1 simply come from the solutions of problem 100 by adding a combination of the unitary eigenvectors of H T g H g (as in (101)), the complexity of the problems is equal to that of problem 100, and thus it can be solved in polynomial time.

E.8 Heuristic for solving Corollary 3.(i)
In this section we will describe the heuristic summarized in Algorithm 1 to find a sub-optimal solution of Corollary 3. We will describe the process to find the vector with positive entries. The negative one will be obtained as its opposite. The algorithm starts by choosing s B2(t) that maximizes the polarization on the vector space of the eigenvector v 1 (line 3) and we iteratively add a component of the subspace generated by the eigenvector v i for all i that corresponds to the singular values σ i > 1. Intuitively, this means that at each step k, the algorithm tries to find an optimum over the vector space v i1 , . . . , v i k , which are the k eigenvectors corresponding to singular values greater than one. In the following, we denote with V {>1} the vector space generated by these eigenvalues, i.e.
and with s(k) the vector obtained with the heuristic at step k. At the k-th step, s(k) is in the form: where v is one of the eigenvectors of V {>1} that were not selected in the previous steps, i.e. v ∈ V \ s(k − 1) . At each step, we select the best candidate pair (α, β) such that the polarization increases. We now prove that an appropriate choice of α and β in (109) leads to increased (or at least unchanged) polarization. For the sake of understanding, we will illustrate this for s (2), but all the consecutive steps work analogously. Please note that the vector that we want to determine is s(2) = αs B2(t) − βv i for an i = 2, . . . , l (recall that l is the number of eigenvalues greater than one), whose polarization is given by: (110) Given that our goal is to increase the polarization, we need to select the largest possible |α| > 1. This choice guarantees that the polarization increases at each step. If it is not possible to operate such a choice of α, the algorithm simply returns s(2) = s (1). Besides guaranteeing that the polarization does not decrease, the selected (α, β) pair must guarantee that s(k) in (109) is a positive opinion vector (i.e., s(k) (i) ∈ [0, 1], ∀i). This implies that the following system of inequalities should be satisfied: Thus, at first we select from V a vector v for which it is possible to obtain an opinion vector from (109) for which |α| > 1. To do this we have to consider two set of indices. The first one corresponds to the indices where s(1) is zero, i.e. Z = {i : s(1) (i) = 0}. If Z is non empty, the corresponding components of s(2) must satisfy: that admits a solution β only if all the entries v (i) are concordant for the indices i ∈ Z. The second set is the set of indices of s(1) that are equal to one (which at least contains k, where k is as in Theorem 5(ii)), i.e. O = {i : s(1) (i) = 1}. The corresponding components of s(2) must satisfy: If there exist two discordant entries, say v (o1) > 0 and v (o2) < 0, with o 1 , o 2 ∈ O, this region can be visualized as in Figure 4, and it is obvious that the admissible |α|s (which should be searched within the overlapped areas) are smaller than one, which would not guarantee the increase of polarization.
The reason to take the vector with the smallest index is that its corresponding singular value is the greatest and thus it may produce a higher polarization due to the term β 2 (σ 2 i − 1) in (110). If it is not possible to identify a vector as in (114) (because all the vectors have discordant entries in Z or in O), the algorithm returns s(1) (line 28). Otherwise, without loss of generality, we can assume that v (o) are positive for all o ∈ O (please note that if this is not true, we can replace v with −v in V without changing any properties of the eigenvectors, as done in line 9). Let us observe that, since O is nonempty (as already observed, it contains the index k of Theorem 5.(ii))), the sign of v is uniquely determined. We will see, during the explanation of the heuristic, that at the vector found at each iteration will have a component equal to 1, so that the set each step it is possible to uniquely determine the sign of the eigenvector considered.
We now assume that we were able to select a v satisfying the conditions discussed above. At this point, we have to search for an optimal (α, β) pair. For convenience of notation, in the following we denote with U the set of indices that belong neither to Z nor O. We can then rewrite the system of inequalities in (111) as follows: For each component i ∈ Z ∪ U ∪ O, we denote with r 1 are vertical lines that intersect α axis in β = 0, −1/v (i) respectively; when i ∈ U ∪ O, they are oblique lines with positive slope v (i) /s (i) and intersect β axis in α = 0, β s(1) (i) + 1 s(1) (i) . In order to assess, at each step k, if a new s(k) can be found that increases the polarization, we have to consider three cases: (C1) the set Z is non-empty and all the corresponding components v (z) are positive, (C2) Z is non-empty and all the corresponding components v (z) are negative and (C3) Z is empty.
Let us start with the case (C1) in which v (i) are positive for all i ∈ Z. In this case, the lower bound on the first inequality of (115) (which holds for i ∈ Z) says that β is negative and Algorithm 1 calls, at line 12, the function find_solution_beta_negative that is presented in Algorithm 2. Let us describe how this function works. The lower bound of the second and third inequalities in (115) tell us that α ≥ βv for i ∈ U. These regions are drown above lines going through the origin, which have positive slope for i ∈ O. Since we know from the first inequality that β ≤ 0, the tighter bound on α in the region β ≤ 0 is achieved when , the region α ≥ mβ describes the lower bounds of (115) for the (α, β) admissible regions (this in computed at line 1). Note that the slope m can be either positive or negative (because even if v (i) is positive for i ∈ O, there are no assumptions on v (i) when i ∈ U). Let us now focus on the upper bounds of (115). The inequalities for i ∈ O tell us that α ≤ βv (i) + 1, which is a line r (i) 1 with positive slope intersecting axis β in α = 1. This implies that α < 1 in the region β < 0, regardless of the specific value of v (i) . Hence our search for |α| > 1 is necessarily restricted to α < −1. Please recall that, since the (α, β) admissible region found with the lower bounds is given by α ≥ mβ, if the slope m is negative, α is forced to be greater than zero in the region β ≤ 0. This means that it is not possible to find α < −1 and we can stop the search for a solution at this iteration and the algorithm yields s(2) = s(1) (line 2 of Algorithm 2). In Figure 5.  (115), related to components in i ∈ Z, simply limit the value of β and reduce to β ≥ max i∈Z − 1 v (i) . Let us denote with z ∈ Z the index where the maximum is reached. We can visualize these set of inequalities as the area on the right side of the vertical line r which is simply the area below the lines r (i) 1 . Note that the slopes of this lines can be positive or negative and they intersect the α axis in 1 s(1) (i) , which is greater than 1. In conclusion, the search ends up with the smallest α < −1 that lies above r  Recalling that j is the index associated with the tighter bound on α r (j) 0 and that z is the index where the lower bound on β is reached, this point is (α P , β P ) where α P is given by: 1 . Please observe that it is not guaranteed that the intersection determines an α P smaller than −1, because it depends on the slope of all the lines. For this reason, at lines 7-9, the function sets s(2) equal to (α P s(1) − β P v) if the polarization is increased, otherwise it sets s(2) = s(1). With this trick, it is guaranteed that the polarization of s(2) is greater than or equal to that of s(1). To conclude the case (C1), we want to observe that the vector s(2) has at least one component equal to 1, i.e. that even at the next step k = 3 the set O will be nonempty. This is trivial when the algorithm had returned s(2) = s(1). In the other case, being (α P , β P ) the intersection of the line r  (118), it is obvious that (α P , β P ) ∈ r (h) 1 , which tells exactly that the h-th components of s(2) is equal to one, in fact it holds: Please note that the same holds true for all s(k), since, by construction, s(k) = s(k − 1) (which inductively has at least a component equal to 1, or lies on a line r (j) 1 for a j (and thus has the corresponding j component equal to 1). Let us proceed with the case (C2) in which v (i) are negative for all i ∈ Z. In this case, the lower bound on the first inequality of (115) (which holds for i ∈ Z) says that β is positive and Algorithm 1 calls, at line 15, the function find_solution_beta_positive that is presented in Algorithm 3. In the same way as for (C1), the lower bound of the second and third inequalities in (115) tell us that α ≥ βv (i) = β v (i) s(1) (i) for i ∈ O and α ≥ v (i) s(1) (i) for i ∈ U. These regions are drown above lines going through the origin, which have positive slope for i ∈ O. In contrast to the previous case, from the first inequality we have that β ≥ 0, and the wider bound on α in the region β ≥ 0 is achieved when s(1) (i) , the region α ≥ mβ describes the lower bounds of (115) for the (α, β) admissible regions (this in computed at line 3). Note that the slope M is necessarily positive, because v (i) is positive for i ∈ O. This implies that α > 0 in the region β > 0 and hence our search for |α| > 1 is necessarily restricted to α > 1. Let us now focus on the upper bounds of (115). The inequalities for i ∈ O tell us that α ≤ βv (i) + 1, which is a line r  (115), related to components in i ∈ Z, simply limit the value of β and reduce to β ≥ min i∈Z − 1 v (i) (this is a positive number because in (C2) v (i) are negative for all i ∈ Z). Let us denote with z ∈ Z the index where the maximum is reached. We can visualize these set of inequalities as the area on the left side of the vertical line r  (115) is the area α ≤ v (i) s(1) (i) β + 1 s(1) (i) for all i ∈ U, which is simply the area below the lines r (i) 1 . Note that the slopes of this lines can be positive or negative and they intersect the α axis in 1 s(1) (i) , which is greater than 1. In conclusion, the search ends up with the highest α > 1 that lies above r  1 for i = j to find the point with greatest α, let call it (β P , α P ) (lines 5-8). In Figure 6 we can see an example of how the final point is found after two iterations. Since it is not guaranteed that the α found is greater than 1 (because the final value α P depends on the lines r (i) 1 ), the polarization is checked at line 10 and the vector s(2) is updated to (α P s(1) − β P v) if its polarization is greater than those of s(2), otherwise it is set to s(2). To conclude the case (C2), we want to observe that the vector s(2) has at least one component equal to 1, i.e. that even at the next step k = 3 the set O will be nonempty. This is trivial when the algorithm had returned s(2) = s(1). In the other case, (α P , β P ) lies on a line r (j) 1 by construction, which tells exactly that the j-th components of s(2) is equal to one, in fact it holds: The same holds true for all the vectors s(k) found at each iterations k (with the same line of reasoning of (C1).
Finally, consider the case (C3) in which Z is empty. In this case, the inequalities in the first line of (115) is never verified and, in particular, the sign of β is not determined. This means that the problem would admit solutions with both β positive or negative. Thus, algorithm 1 searches, at first, the solution s(2) − with β < 0 calling the function find_solution_beta_negative (line 17), which we have already described in (C1). Secondly, the algorithm calls the function find_solution_beta_positive (line 18), described in (C2), and finds a solution s(2) + with β > 0. Finally, Algorithm 1 returns s(2) equal to the one of s(2) + , s(2) − that has the greatest polarization (line 21). Please Once s(2) is computed following one of the three possibilities just described, Algorithm 1 removes v from the set of eigenvectors V (line 25) and continues until V is empty (at maximum in l − 1 steps).

E.8.1 How to use Algorithm 1
Here, we apply the heuristic to a toy scenario, with the aim of helping the reader understand how the heuristic operates. Consider the network of four nodes determined by matrixŴ given by: and the influence matrix W obtained fromŴ by normalization. Assume then that the suscepibility values are 0.9, 0.1, 0.1, 0.5 respectively, so that we obtain that matrix H g is given by: Following Theorem 5.(ii), from s 0 we obtain r 0 = (0.0632164, 1., 0.40088, 0.168103) and, in particular, r 0 can be written in terms of B as r 0 = ts 0 + 0s 1 + 0s 2 , with t = 1/s (2) 0 = 1.09223. Then we can proceed using the heuristic of Algorithm 1: we initialize r = r 0 , k = 2 and the set I 0 , of all the indices i = 0 for which the corresponding singular values σ i are greater than 1, meaning that I 0 = {1}. The corresponding eigenvector is s 1 has the second component nonnull and thus, by summing to r 0 a positive multiple of s 1 , we would increase polarization. We only have to be guaranteed to obtain a vector with components in [0,1]. This is what we obtain from the algorithm, that finds a vector r 1 = (0.0549607, 0.733446, 1., 0.32813). The algorithm then stops because we do not have any other positive singular value, i.e. I 0 = ∅. The P 3 -polarization shifts ∆ 3 = P 3 (Hs) − P 3 (s) for s 0 , r 0 , r 1 are given by: Algorithm 1 find_global_max: this algorithm compute the sub-optimal positive solution Require: H g Ensure: A polarizing vector that yields to a global sub-optimum of the polarization ∆ 1: Take all the singular values of H g greater than one: σ 1 ≥ σ 2 ≥ · · · ≥ σ l ≥ 1 2: Take V = {v 1 , . . . , v l } the set of the corresponding unitary eigenvectors of H T g H g v 1 is the only one that has concordant entries (for the Perron-Frobenius Theorem), thus, unless taking its opposite, we can assume it is positive. if there exist vectors in V that has concordant entries in both O and Z then 8: choose the vector v ∈ V with lower index (and thus that corresponds to higher singular value) 9: This is a technical passage 10: end if 11: if Z = ∅ and v is positive on Z then We have guaranteed the sign of β in αs(k) − βv is negative 12: Compute s(k + 1) = find_solution_beta_negative 13: else 14: if Z = ∅ and v is negative on Z then We have guaranteed the sign of β in αs(k) − βv is positive 15: Compute s(k + 1) = find_solution_beta_positive In this case we only obtain an α ∈ [0, 1] for the candidate vector αs(k) − βv, which is likely to decrease the value of ∆ 3: else In this case |α P | can be increased 6: Set α P = min{α i : (β i , α i ) = r ∩ r (i) 1 , i ∈ I}, and let β P the correspondent point and suppose it is reached for r ∩ r Set I = I \ {h} and r = r (h) 1 . 8: end while 9: Set s cand = α P s(k) − β P v This is the candidate vector 10: if ∆(s cand ) > ∆(s(k)) then return s cand 11: else 12: return s(k) 13: end if P 3 (Hs 0 ) − P 3 (s 0 ) = 0.505183 (121) P 3 (Hr 0 ) − P 3 (r 0 ) = 0.602663 (122) P 3 (Hr 1 ) − P 3 (r 1 ) = 0.623852. (123) E.9 Proof of Theorem 6.(ii) Using the same notation as in the proof of Corollary 3, we search the prejudice vectors ±s (we intend s to be with positive entries) that maximize the value P 4 [H g (s)] − P 4 (±s). We will determine the vector with positive entries, and the one with negative entries will be its opposite which has the same value of polarization according to Theorem 4. We write the unknown vector s in terms of the basis B, i.e. s = i α i v i , with α i ∈ R. Thus, we have that: where in (124) we have used the stochasticity of matrix H g . Thus the vector s max P 4 that maximizes the polarization is associated with α max P 4 that maximises i α i (σ 2 i − 1) v i , 1 , which is the objective function of the problem in (25). The constraint, as for the proof of Theorem 5.(iii), guarantees that the vector found is an opinion vector. This concludes the proof.
E.10 Proof of Theorem 7 (gFJ: global polarization with P 1 , GDI) Let us start with item (i) and thus suppose that gFJ is depolarizing with P 2 , P 3 , P 4 . By Theorem 3, we have that i (H g s) i = i s i and also [ i (H g s) i ] 2 = ( i s i ) 2 . Thus, using the result of Lemma 3, we obtain that: (127) that proves that gFJ is depolarizing with P 1 (and, equivalently, GDI).
We will prove item (ii), i.e., that, for a generic s being P 1 , GDI-polarizing is equivalent to (27). In fact, s is P 1 , GDI-polarizing if P 1 (H g s) − P 1 (s) is greater than zero or, in other terms that: P 3 (H g s) − P 3 (s) > 1 n P 4 (H g s) 2 − P 4 (s) 2 .
The vector s can be expressed, in terms of the basis B, as s = i α i v i . Thus, we compute the difference P 3 (H h s) − P 3 (s) as the difference of these two terms: This difference is exactly the left-hand side of (27). Let now focus on the values P 4 (H g s) and P 4 (s): where in (131) we have used the stochasticity and the nonnegativity of H g . Now, expressing P 4 (H g s) 2 − P 4 (s) 2 as the product of (P 4 (H g s) + P 4 (s)) and (P 4 (H g s) − P 4 (s))) we obtain the right hand side of (27). In other terms, (27) is equivalent to (128) and thus we obtain the thesis.

E.11 Proof of Corollary 4
Does the presence of stubborn nodes have some implications on the polarization? Being invariant the network topology, does it guarantee that the gFJ leads to a greater polarization with respect to the case in which all nodes are not stubborn? At first glance, we could imagine that stubborn nodes constitute a sort of opinion drivers and thus they can be able to push the overall opinion more than they would have done if they were non-stubborn. However, this is a false intuition; in fact, not only the susceptibility values of nodes, but also the weights of the edges play a fundamental role in the opinion formation; actually, they can enhance the opinions' movement towards the extreme even more than the stubbornness of nodes.
To help the intuition, we will provide a toy example where we will see that, being invariant the network topology, the polarization can be increased or not when passing from a network with stubborn nodes to a network without stubborn nodes. Consider the network with social and influence matrices respectively given by:  of nodes 2 and 3 enhances the configuration L (2) to be the one that mostly can move opinions towards the extreme value 1.

E.12 Proof of Corollary 5
The proof essentially consists in observing that, in the hypothesis, the matrices Λ and I − Λ are of a particular shape, which allows us to verify that the final opinion vector z = τ 1 resolves the stable equation of gFJ. For convenience of notation and without loss of generality, we can assume that I = {1, . . . , |I|} and J = {|I| + 1, . . . , N } (obviously if this is not true, we can rearrange the basis). So, the matrices W and Λ can be written in block form in the following where O is the null matrix. It is now straightforward to verify that z = τ 1 is the solution of the gFJ, since it verifies the stable condition z = ΛW z + (I − Λ)s. In fact, replacing z with τ 1 in the latter equality, we have that:    where in (135) we have used the stochasticity of W in the rows corresponding to I, while in line (135) we have used the stochasticity of W in the rows corresponding J . In (134), the asterisks denote the values (any is possible) for the initial opinion of the nodes in I.
Having proved the converge of the final opinion towards z = τ 1, we now focus on the polarization. For P 4 , we need to compute and compare the 1-norm of z and s. We obtain z 1 = τ (|J | + |I|) and s 1 = τ |J | + i∈I |s i |, thus any Simplifying, we obtain i w ii z i = i w ii s i . But since w ii =ŵ, ∀i ∈ V, we get i z i = i s i (no polarization in P 4 and no choice shift).

E.14 Corollary 7 (rFJ on undirected social graphs)
The N DI-depolarization of rFJ is proved in [24] and the relation i z i = i s i is proved in [23]. The N DIpolarization result can also be derived from Theorem 8, while the rest derives from Corollary 6, since in for rFJ the matrixŴ is symmetric andŵ ii = 1 for all i.

F Supplemental information on the experimental evaluation
In Figure 7 we plot the the Karate Club graph [35] and a Facebook graph [37] with the dimension of nodes proportional to their PageRank centrality. The Karate graph is smaller and less clustered, the Facebook graph is larger, with three big and well-delineated communities. Obviously, being the former quite small, we can distinguish well the most central nodes: 1, 2, 3, 33 and 34. The susceptibilities chosen for the evaluation belong to three configurations: individual susceptibility λ i of a node i proportional to its Pagerank centrality C i , inversely proportional, and all susceptibilities set to 0.8, and they are plotted in Figure 8.