Minimizing Polarization and Disagreement in Social Networks via Link Recommendation
Year: 2022

Abstract:
Individual’s opinions are fundamentally shaped and evolved by their interactions with other people, and social phenomena such as disagreement and polarization are now tightly woven into daily life. The quantification and optimization of these concepts have been the subject of much recent research behind a wealth of high-impact data mining applications. In particular, researchers have addressed the question of how such concepts can be optimized by influencing the opinion of a small number of individuals or by designing the network from scratch. Here, rather than a “design-from-scratch” approach or altering the initial opinion, we study the optimization problem of recommending k new links to minimize the sum of polarization and disagreement in a social network with n nodes and m edges. We show that our objective function of this combinatorial optimization problem is not submodular, although it is monotone. We propose a simple greedy algorithm with a constant-factor approximation that solves the problem in cubic running time, and we provide theoretical analysis of the approximation guarantee for the algorithm. To overcome the computation challenge for large networks, we also provide a fast algorithm with computation complexity Õ(mk −2) for any > 0, where the Õ(·) notation suppresses the poly(log n) factors. Extensive experiments on real datasets demonstrate both the efficiency and effectiveness of our algorithms.

heading: 1 Introduction
text: Social networks and social media play a prominent part in the propagation, evolution, and formulation of opinions [32], leading to fundamental changes in how humans share and shape opinions. Particularly, in recent years, the tremendous prevalence of online social media platforms produces various social phenomena, such as polarization and disagreement. The identification [48] and optimization [50] of these quantities are fundamental tasks behind a myriad of high-impact data mining applications, and thus have received considerable attention.
We focus on the phenomena of disagreement and polarization. Disagreement [39, 16] characterizes how much acquaintances disagree in their opinions, globally across the network. Polarization [39, 36, 16] measures how equilibrium expressed opinions deviate from their average. However, existing recommender systems, trained on real-data, with the goal to increase user engagement may stop the user from being exposed to diverse opinions and naturally end up creating “echo-chambers”. In other words, the recommended links minimizing disagreement may lead to greater polarization [39] since connections between users with similar mindsets are preferred for such systems. Yet, exposure to diverse content is necessary to obtain a complete picture about a topic [27]. Thus, there is a need
∗Corresponding author.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
for a radically different approach to suggest links that decrease both disagreement and polarization, which motivates our work.
In this paper, we address the following optimization problem: given a social network with n nodes and m edges, and an integer k, how to strategically recommend k links to the individuals so that the polarization and disagreement is minimized. We show that our objective function of this combinatorial optimization problem is not submodular, although it is monotone. To tackle the exponential computation complexity, we resort to greedy algorithm extended for non-submodular function [5] by iteratively adding the most promising edges. We propose a simple greedy algorithm with a constant-factor approximation that solves the problem in cubic running time. To confront the computation challenge for large networks, we also provide a fast algorithm with computation complexity Õ(mk −2) for any > 0, where > 0 is the error parameter and the Õ(·) notation suppresses the poly(log n) factors. We confirm our theoretical and algorithmic performance by executing extensive experiments on various real networks, which show that our algorithms are efficient and effective, outperforming several other strategies of creating edges.
Omitted proofs and implementation are provided as supplementary material.

heading: 2 Related work
text: We review the related literature from the following three perspectives, including modeling opinion dynamics, optimization problems in opinion dynamics, and link recommendation strategies.
Modeling opinion dynamics. Opinion dynamics has been the subject of intense recent research to model social learning processes in various disciplines [29, 19, 4]. These models capture the mechanisms and factors influencing opinion formulation, shedding light on understanding the whole process of opinion shaping and diverse phenomena taking place in social media. In the past decades, numerous relevant models have been proposed [40], among which the Friedkin-Johnsen (FJ) model [20] is one of the most popular models. After its establishment, the FJ model has been extended in a variety of ways [29, 28, 47, 13], by incorporating different factors affecting opinion dynamics, such as peer pressure [42], susceptibility to persuasion [1], and opinion leader [25]. Under the formalism of the FJ model or its variants, some relevant quantities, properties and explanations have been broadly studied, including the equilibrium expressed opinions [18, 6], sufficient condition for the stability [41], the average initial opinion [18], interpretations [24, 6], and so on.
Optimization problems in opinion dynamics. Recently, several optimization problems related to opinion dynamics have been formulated and studied for different objectives. For example, a long line of work has been devoted to maximizing the overall opinion by using different strategies, such as identifying a fixed number of individuals and setting their expressed opinions to 1 [25], changing agent’s internal opinions [49, 47], as well as modifying individuals’ susceptibility to persuasion [1, 8]. [46] studies the problem of allocating seed users to opposing campaigns with a goal to maximize the expected number of users who are co-exposed to both campaigns. In additon, [23] studies the problem of balancing the information exposure. These studies have far-reaching implications in product marketing, public health campaigns, and political candidates. Another major and increasingly important focus of research is optimizing some social phenomena, such as maximizing the diversity [35, 37], minimizing conflict [12], disagreement [21], and polarization [36]. A recent work considers the problem of minimizing the sum of polarization and disagreement by changing the underlying network topology [39]. Different from the “design-from-scratch” approach, we instead concentrate on edge recommendation, a practical incremental approach that suggests modifications to an existing network to achiever our goal. Moreover, our proposed algorithms differ significantly from existing ones, in spite of the fact that our objective function is identical to that in [39].
Link recommendation strategies. Our problem aims to optimize an objective via link recommendation. Here, we review some instances of related edge recommendation problems. [15, 43, 17] improve the centrality of a node and [3] strategically fight opinion control in social networks. As for opinion dynamics, the operation of creating edges is actually convenient and practical, which is equivalent to making friendship between individuals. In [22], the edge addition strategy is explored on the endorsement graph, with an aim to reduce controversy, and it also takes account of the acceptable probability of the recommended edge. In [6], addition of edges is discussed in order to reduce the social cost, namely the lack of agreement. Finally, [12] exploits link recommendation strategy to reduce the risk of conflict, [27] considers link insertions to reduce structural bias which may trap a
reader in a “polarized” bubble with no access to other opinions. Our work is motivated in part by these studies, while we address a new optimization problem, and present two new algorithms, with the faster one being nearly linear.

heading: 3 Preliminaries
text: In this section, we give a brief introduction to some essential concepts and tools, in order to facilitate the description of the studied problem and its related greedy algorithms.
Graph and Related Matrix. Let G = (V,E) be a connected undirected simple graph (network) with |V | = n nodes and |E| = m edges. The adjacency relation of all nodes in G is encoded in its adjacency matrix A = (aij)n×n. If nodes i and j are adjacent by an edge e, then aij = aji = 1; aij = aji = 0 otherwise. Let Ni be the set of neighbours of node i satisfying Ni = {j|{i, j} ∈ E}. Then, the degree di of node i is di = ∑n j=1 aij = ∑ j∈Ni aij , and the diagonal degree matrix of G is defined as D = diag(d1, d2, . . . , dn).
The Laplacian matrix of G is defined to be L = D −A. There is also an alternative construction of L by using the incidence matrix B ∈ R|E|×|V |, an m× n signed edge-node incidence matrix. The element bev, e ∈ E and v ∈ V , of B is defined as follows: bev = 1 if node v is the head of edge e, bev = −1 if node v is the tail of edge e, and bev = 0 otherwise. For an edge e ∈ E with two end nodes i and j, the row vector of B corresponding to e can be written as bij , be = e i − ej where e i denotes the i-th standard basis vector of appropriate dimension. Then the Laplacian matrix L of G can also be represented as L = B>B , which indicates that L is symmetric and positive semidefinite. Moreover, the Laplacian matrix L of a connected graph G has a unique zero eigenvalue. Let 0 < λ1 ≤ λ2 ≤ · · · ≤ λn−1 be the nonzero eigenvalues of L of a connected graph G, and u i be the corresponding orthonormal eigenvectors. Then, L has an eigendecomposition of form L = UΛU> = ∑n−1 i=1 λiu iu > i where Λ = diag (0, λ1, λ2, .., λn−1) and u i is the i-th column of matrix U . Let λmax and λmin be, respectively, the maximum and nonzero minimum eigenvalue of L. Then, λmax = λn−1 ≤ n [45], and λmin = λ1 ≥ 1/n2 [34]. The forest matrix of graph G is defined as Ω = (I + L)−1 = (ωij)n×n [26, 11]. Matrix Ω is a doubly stochastic matrix [9, 10], satisfying Ω1 = 1 and 1>Ω = 1> where 1 denotes the all-ones vector. For a pair of nodes i and j, their forest distance rij is defined as rij , b>ijΩbij , obeying relation 0 ≤ rij ≤ 2. Greedy Algorithms for Non-Submodular Functions. For submodular maximization problems, the greedy algorithm has become a prevalent choice for solving them with a guaranteed (1− 1/e) approximation ratio. However, there are a large class of important set functions optimization in network topology design fail to be submodular. To alleviate this issue, a generalized approximation ratio has been proved and further provides a performance guarantee for non-submodular functions based on two quantities: submodularity ratio γ and curvature α, which characterize how close these functions are from being sub- or supermodular [5].
For consistency, we first give the definitions of submodular ratio and curvature below. We use ρT (W ) def = f(T ∪W )− f(W ) to denote the marginal benefit of the set T ⊆ X with respect to the set W ⊆ X .
Definition 3.1 (Submodular Ratio [5]) The submodular ratio of a nonnegative set function f is the largest γ ∈ R+ such that for any subset W,T ⊆ X , ∑ i∈W\T ρi(T ) ≥ γρW (T ).
Definition 3.2 (Curvature [5]) The curvature of a nonnegative set function f is the smallest α ∈ R+ such that for any subset W,T ⊆ X and any element j ∈ T\W , it follows that ρj(T\j ∪W ) ≥ (1− α)ρj(T\j).
Notice that for a non-decreasing function f , it follows that its submodular ratio γ ∈ [0, 1] and γ = 1 if and only if f is a submodular function; and its curvature α ∈ [0, 1] and α = 0 if and only if f is a supermodular function. Given those two quantities, the greedy algorithm enjoys a tight approximation guarantee of 1α (1− e −αγ) for a larger class of optimization problems [5].

heading: 4 Problem Formulation
text: In this section, we briefly discuss the FJ model of opinion formation, as well as the definitions and measures for disagreement and polarization. Then we formally introduce the problem for optimizing the polarization-disagreement index in a social network.
Friedkin-Johnsen Model. The FJ model is one of the most popular models for opinion dynamics [20]. In the FJ model, each node i ∈ V has two opinions: internal (or innate) opinion and the expressed opinion, both in the interval [0, 1]. The internal opinion for each node, denoted by si, remains unchanged. Let z i(t) be the expressed opinion of node i at time t, which evolves as
z i(t+ 1) = si +
∑ j∈Ni aijz j(t)
1 + ∑ j∈Ni aij
. (1)
Let s = (s1, s2, . . . , sn)> be the initial opinion vector. Let z = (z 1, z 2, . . . , zn)> be the equilibrium expressed opinion vector, which can be represented as z = Ωs [6].
In the FJ model, individuals interact with their acquaintances and exchange opinions whereas the opinions of nodes often do not reach consensus, leading to disagreement, polarization and other important phenomena, which have been the subject of many recent works. In this paper, we study the disagreement and polarization using definitions given in [39].
For a graph G = (V,E) with expressed opinion vector z , its disagreement D(G) is defined as D(G) = ∑ (i,j)∈E(z i−z j)2. Let z̄ be the mean-centered equilibrium vector given by z = z− z>1 n 1.
Then the polarization P (G) is defined as: P (G) = ∑ i∈V z 2 i = z
>z . We further introduce the polarization-disagreement (P-D) index, i.e., the objective we are concerned with. For a graph G = (V,E) with expressed opinion vector z , the polarization-disagreement index I(G) is the sum of the polarization P (G) and disagreement D(G) : I(G) = P (G) +D(G). Convenient matrix-vector expressions for the above quantities are provided by the following proposition [12, 39, 48].
Proposition 1 D(G), P (G) and I(G) can be conveniently expressed in terms of quadratic forms as
D(G) = z>Lz = z>Lz = s>ΩLΩs, P (G) = z>z = s>Ω2s, I(G) = z>Lz + z>z = s>Ωs.
Remark 1 In this paper, we will generally assume that the internal opinions s are mean-centered, that is, s̄ = s . Note that in such case, z will also be mean-centered. In fact, as will be shown in supplementary material, whether the opinions s are mean-centered or not, the edges which we select to augment the network are the same since the variation of our objective remains unchanged.
Formulation of Problem. Our problem is based on the following fact. For a connected undirected network G(V,E), if we augment the network by adding the edges in set T , which is a subset of the candidate edge set EC consisting of specified nonexistent edges, the P-D index of the new graph will not increase. In our subsequent analysis, we will use the following notation to improve readability of our lemmas. We use G + T to denote the graph augmented by adding the edges in T , that is G + T = (V,E ∪ T ). To evaluate the variation of the P-D index when adding edges, we define an objective function on the edge set f : 2EC → R+ as
f(T ) = I(G)− I(G + T ), (2) in the sequel, we will use f(e) and G + e, respectively, to denote f({e}) and G + {e} for simplicity. The variation of the P-D index under the perturbation of a single edge can be expressed by the following lemma.
Lemma 4.1 For a candidate edge e ∈ EC connecting node u and v with row vector be = eu − ev , one obtains
f(e) = s>Ωbeb > e Ωs
1 + b>e Ωbe =
(zu − z v)2
1 + ruv ≥ 0. (3)
Lemma 4.1 indicates that the addition of any nonexisting edge can reduce the P-D index. Then the following problem arises naturally: given a candidate edge set EC , how to optimally select a
subset T of EC subject to a cardinality constraint, so that the polarization-disagreement index of the new graph is minimized. Such an optimization problem has been the subject of many recent papers [21, 39]. Yet we focus on edge recommendation rather than global structural results due to the following reasons: in practice, graph edits can typically be made only in small amounts, either because of budget constraints, or because of practical considerations. A similar idea was previously used in [12]. We now give a mathematical formulation of Problem 1 in a formal way as follows.
Problem 1 Given a connected graph G = (V,E), an integer k, a candidate edge set EC consisting of nonexistent edges, find a subset T ⊂ EC with |T | = k, and add them to G forming a new graph G + T = (V,E ∪ T ), so that the polarization-disagreement index I(G + T ) is minimized. That is:
minimize T⊂EC , |T |=k
I(G + T ). (4)

heading: 5 SPGREEDY: Simple Greedy Algorithm
text: In this section, we first study the characterization of our problem, and then propose a simple greedy algorithm, followed by some analysis in terms of the approximation guarantee.
Problem Characterization. We start with detailing the theoretic challenges of Problem 1. The complexity of Problem 1 comes along two dimensions—searching for the best edge subset delivering the maximum of the objective, and assessing the impact of a given subset of edges upon the objective. The former is inherently a combinatorial problem, which is computationally infeasible to solve in a naïve brute-force manner while the latter involves cubic-time matrix inversion. To be specific, for each augmented edge set T coming from (|EC | k ) possible subsets, we need to compute the P-D index
of the resultant graph, yielding an exponential complexity O ((|EC |
k
) · n3 ) .
To tackle the exponential complexity, we resort to a greedy heuristic. Firstly, the objective function is monotone respect to the edge set T , as we mentioned in Lemma 4.1. But, we show that, unlike in the case in other standard optimization settings, neither submodularity nor supermodularity holds for our objective function. We present above results in the following theorem.
Theorem 5.1 The function f(T ) defined above is a non-submodular monotonically increasing function of the edge set T .
Thanks to the empirical success of applying greedy strategy on a significantly larger class of nonsubmodular functions [5], in spite of the non-submodularity of our objective f(T ), the greedy algorithm can still become a proper choice for solving Problem 1, the details of which will be discussed in the next subsection.
Simple Greedy Algorithm. Our simple greedy algorithm, denoted as SPGREEDY, exploits the performance guarantee for non-submodular functions. The general approach is as follows. We will first assess candidate edges with respect to how much their addition to the network decreases the term I(G), and then iteratively add the most promising edges to the network until budget is reached. The augmented edge set T is initialized with an empty set. Then k edges are iteratively selected to the augmented edge set from setEC \T . At each iteration of the greedy algorithm, the edge e in candidate set is chosen that gives the largest marginal gain f(e). The algorithm stops until k edges are selected to be added to T . The naïve greedy algorithm takes time O(k|EC |n3), which is computationally intractable even for small-size networks. Actually, as shown in the proof of Lemma 4.1, with Ω already computed, we can view the addition of a single edge e as a rank-1 update to the original matrix Ω, which can be calculated in time O(n2) by using Sherman-Morrison formula [38], instead of inverting the matrix again in O(n3) in each loop.
The above analysis leads to a simple greedy algorithm SPGREEDY(G, EC , k, s), which is outlined in Algorithm 1. To begin with, this algorithm requires O(n3) time to compute the inverse of I + L, and then it performs in k rounds, with each round mainly including two steps: computing f(e) (Line 4) in O(|EC |n2) time, and updating Ω (Line 8) in O(n2) time. Thus, the total running time of Algorithm 1 is O(n3 + k|EC |n2), which is much faster than the naïve algorithm. Approximation Guarantee. As we mentioned before, the performance of the greedy algorithm for non-submodular function can be evaluated by its submodularity ratio γ and curvature α. Hence, we derive the bounds for these two quantities of our Problem 1.
Algorithm 1: SPGREEDY(G, EC , k, s) Input : A connected graph G; a candidate edge set EC ; an integer k ≤ |EC |; an initial opinion vector s Output : A subset of T ⊂ EC and |T | = k
1 Initialize solution T = ∅ 2 Compute Ω 3 for i = 1 to k do 4 Compute f(e) for each e ∈ EC \ T 5 Select ei s.t. ei ← arg maxe∈EC\T f(e) 6 Update solution T ← T ∪ {ei} 7 Update the graph G ← G(V,E ∪ {ei}) 8 Update Ω← Ω− Ωbeb > e Ω
1+b>e Ωbe
9 return T
Lemma 5.1 Let λ1(L) be the smallest non-zero eigenvalue of Laplacian matrix L for graph G, and let λn−1(LEC ) be the largest eigenvalue of Laplacian matrix LEC for the augmented graph G +EC . Then, the submodularity ratio γ of set function f(T ) = I(G)− I(G + T ) is bounded by 1 > γ ≥(
1+λ1(L) 1+λn−1(LEC )
)2 > 0, and its curvature α is bounded by 0 < α ≤ 1− ( 1+λ1(L)
1+λn−1(LEC )
)2 < 1.
Lemma 5.1, together with the approximation guarantee stated before, yields a performance analysis for the greedy algorithm. As will be shown in the Experiment Section, the greedy algorithm has been shown to perform very close to the optimal solutions for our problem in the experimental aspect.

heading: 6 FASTGREEDY: Fast Greedy Algorithm
text: Compared with the naïve algorithm, computation time of Algorithm 1 is significantly reduced. However, it is still computationally unacceptable when employed on large networks with millions of vertices. In this section, we address this challenge by presenting an efficient approximation algorithm, solving the problem in time Õ(mk −2).
The core step for solving Problem 1 is to calculate the impact of each edge upon the objective i.e., f(e). According to (3), to evaluate f(e), we need to estimate two terms s>Ωbeb>e Ωs and b>e Ωbe. We will show how to approximate these two quantities in nearly linear time using JohnsonLindenstrauss (JL) Lemma [30, 2] and Fast SDDM (symmetric, diagonally-dominant M-matrix) Solvers[44]. Moreover, the results returned by our algorithm are demonstrated to provide proper approximations to f(e).
Lemma 6.1 (JL Lemma [30]) Given fixed vectors v1, v2, · · · , vn ∈ Rd and a real number > 0. Let p be a positive integer such that p ≥ 24 log n/ 2 and Rp×d a random matrix with each entry being 1/ √ p or −1/√p with identical probability. Then, with probability at least 1 − 1/n, the following statement holds for any pair of i and j, 1 ≤ i, j ≤ n: (1− )‖v i − v j‖2 ≤ ‖Rv i −Rv j‖2 ≤ (1 + )‖v i − v j‖2.
Lemma 6.2 (Fast SDDM Solver [44]) There is a nearly linear time solver y = SOLVE(S , b, ) which takes an SDDM matrix Sn×n with m nonzero entries, a vector b ∈ Rn, and an error parameter δ > 0, and returns a vector x ∈ Rn satisfying ‖y − S−1b‖S ≤ δ‖S−1b‖S with high probability, where ‖y‖S def = √ y>Sy . The solver runs in expected time Õ(m) .
We first approximate the term b>e Ωbe in the denominator of (3), which can be written as b > e Ωbe = b>e Ω(I +L)Ωbe = b > e Ω ( I + B>B ) Ωbe = ‖Ωbe‖2 +‖BΩbe‖2. In this way, we have reduced
the estimation of the denominator of (3) to the calculation of the quadratic form of ‖BΩbe‖2 and ‖Ωbe‖2 in Rm and Rn. To reduce the computation cost, we will apply the JL lemma to reduce the dimensions. Let Qp×m and Pp×n be two random ±1/ √ p matrices where p will be decided later,
then we can simply project matrices BΩ and Ω onto low-dimensional subspace QBΩ and PΩ. However, this still does not help to reduce the computation time, since direct computation of the above `2 norm involves matrix inversion, leading a running time of O(n3). In order to avoid inverting matrix I + L, we will utilize the fast SDDM linear system solvers [44] to approximate the above two terms.
Let X = QB ,X = BΩ,X ′ = QX , let X̃ i = SOLVE(I + L,X i, δ1), satisfying ‖X̃ i − X ′i‖I+L ≤ δ1‖X ′ i‖I+L with δ1 ≤ √ 2(1− /12) 32n(n+1) √ (1+ /12)(n+1) . Making use of Lemmas 6.1 and 6.2, the term ‖QBΩbe‖2 can be efficiently approximated as stated in the following lemma.
Lemma 6.3 Given an undirected graph G = (V,E) with Laplacian matrix L, a parameter ∈ (0, 12 ), then, the following relation holds:
(1− 12 )2‖Xbe‖2 ≤ ‖X̃ be‖2 ≤ (1 + 12 )2‖Xbe‖2. (5)
In a similar way, let Y = P ,Y = Ω,Y ′ = PY , let Ỹ i = SOLVE(I + L,Y i, δ2) with
δ2 ≤ √
2(1− /12) 32(n+1) √ (1+ /12)(n+1) . Then, the following lemma holds, giving an efficient approximation to
‖QΩbe‖2.
Lemma 6.4 Given an undirected graph G = (V,E) with Laplacian matrix L, a parameter ∈ (0, 12 ), then, the following relation holds:
(1− 12 )2‖Ybe‖2 ≤ ‖Ỹ be‖ ≤ (1 + 12 )2‖Ybe‖2. (6)
Having Lemma 6.3, 6.4, the term b>e Ωbe can be efficiently approximated by ‖X̃ be‖2 + ‖Ỹ be‖2 satisfying
(1− 3
)b>e Ωbe ≤ ‖X̃ be‖2 + ‖Ỹ be‖2 ≤ (1 + 3 )b>e Ωbe.
We continue to approximate the numerator of f(e), which can be written as ‖Ωs‖2 beb>e . We will use the fast SDDM matrix solver again to approximate this term.
Lemma 6.5 Given an undirected graph G = (V,E) with Laplacian matrix L and forest matrix Ω, a parameter ∈ (0, 12 ), and the internal opinion vector s , let q = SOLVE (I + L, s, δ3), where δ3 ≤ 9n2 . Then, the following relation holds: ∣∣∣‖q‖2beb>e − ‖Ωs‖2beb>e ∣∣∣ ≤ 3 . Algorithm 2: COMP(G, EC , s, ) Input : A graph G; a candidate edge set EC ; an initial opinion vector s; a real number 0 ≤ ≤ 1/2 Output : {(e, f̂(e)|e ∈ EC}
1 Set δ1, δ2, δ3 according to Lemmas 6.3, 6.4 and 6.5, 2 p← ⌈ 24 logn/( 12 )2 ⌉ 3 Generate random Gaussian matrices Pp×n,Qp×m 4 Compute approximations q to Ωs , X̃ to X def= BΩ, and Ỹ to Y def= Ω 5 for i = 1 to p do 6 q ← SOLVE(I + L, s, δ3) 7 X̃ i ← SOLVE(I + L,X i, δ1) 8 Ỹ i ← SOLVE(I + L,Y i, δ2) 9 for each e ∈ EC do
10 compute f̂(e) = b > e qq >be
1+‖X̃ be‖2+‖Ỹ be‖2
11 return {(e, f̂(e)|e ∈ EC}
Having considerably approximately computing each part of f(e), we are now able to propose an algorithm COMP approximating f(e) for every edge e in the candidate set EC based on Lemmas 6.3, 6.4 and 6.5. The outline of algorithm COMP is shown in Algorithm 2, whose performance is given in Theorem 6.1.
Theorem 6.1 For 0 ≤ ≤ 1/2, the value f̂(e) returned by COMP satisfies |f(e)− f̂(e)| ≤ 45 with high probability.
Exploiting Algorithm 2 to approximate f(e), we develop a fast greedy algorithm FASTGREEDY(G, EC , s, k, ) in Algorithm 3 to solve Problem 1. Overall, it follows the greedy strategy (Algorithm 1). In detail, Algorithm 3 performs k rounds (Lines 2-6). In each round, it takes time Õ(m −2) to call COMP to compute the approximation of the marginal gain f̂(e), then iteratively select the element with the highest impact score and update. Therefore, the time complexity of Algorithm 3 is Õ(mk −2).
Algorithm 3: FASTGREEDY(G, EC , s, k, ) Input : A graph G; a candidate edge set EC ; an initial opinion vector s; an integer k ≤ |EC |; a real number 0 ≤ ≤ 1/2 Output : T : a subset of EC and |T | = k
1 Initialize solution T = ∅ 2 for i = 1 to k do 3 {e, f̂(e)|e ∈ EC \ T} ← COMP(G, EC \ T, s, ) 4 Select ei s.t. ei ← arg maxe∈EC\T f̂(e) 5 Update solution T ← T ∪ {ei} 6 Update the graph G ← G(V,E ∪ {ei}) 7 return T

heading: 7 Experiments
text: In this section, we present numerical results to evaluate the performance of our two greedy algorithms SPGREEDY and FASTGREEDY. To this end, extensive experiments are designed and executed on real networks of various types and scales to validate the effectiveness and efficiency of our algorithms.
Datasets. The studied realistic networks are representatively selected from various domains, which are publicly available in the KONECT [31] and SNAP [33]. For each network, we implement our experiments on its largest components. The characteristics of the largest components for all networks are summarized in Table 1.
Machine and reproducibility. All experiments were conducted on a machine equipped with 32G RAM and 4.2 GHz Intel i7-7700 CPU. All algorithms in our experiments are executed in Julia. In our algorithms, we use the SDDM solver SOLVE [44], the Julia implementation of which is available at https://github. com/danspielman/Laplacians.jl.
Methods. The sets of k edges are found with the following seven strategies. (1) Optimum: selecting edge set |T | = k with minimum I(G + T ) by exhaustive search. (2) Random: selecting k edges at random. (3) Betweenness: selecting top-k edges with the highest betweenness [7]. (4) DegProduct: selecting top-k edges with the largest product of two end-points degrees. (5) DegSum: selecting top-k edges with the largest sum of two end-points degrees. (6)FastGreedy: selecting top-k edges with maximum f(e) returned by algorithm FASTGREEDY. (7) SpGreedy: selecting top-k edges with maximum f(e) returned by algorithm SPGREEDY. Opinions and evaluation metrics. We investigate three different distributions for the initial opinions: uniform distribution, exponential distribution, and power-law distribution. For the uniform distribution, the initial opinion si of each node i is distributed uniformly in the range of [0, 1]. For the latter two distributions, we use randht.py file in [14] to generate and normalize opinions to the range of [0, 1] according to a exponential distribution and a power law with a given slope. Note that there is always a node with internal opinion 1 due to the normalization operation. The performance of all above-mentioned methods is evaluated by the impact of their selected edges on the drop of the P-D index ∆I(G) = I(G + T )− I(G), with a smaller ∆I(G) corresponding to an more effective method.
Results. We first evaluate the effectiveness of our algorithms, we execute experiments on four small realistic networks: Karate with 34 nodes and 78 edges, Dolphins with 62 nodes and 159 edges, Netscience with 379 nodes and 914 edges, and Diseasom with 516 nodes and 1188 edges. These networks are small, allowing us to compute the optimal set of edges. For each case, we add k = 1, 2, . . . , 8 edges to augment the network from |EC | = 30 candidate edges. For the approximation algorithm FASTGREEDY, we set = 0.3. Note that a smaller corresponds to a stronger approximation ratio but less efficiency. As shown in Figures 1, for all three initial opinion distributions, the solutions returned by our two greedy algorithms and the optimum solution are almost the same so that the three curves are overlapped, demonstrating that our greedy algorithms perform much better than the theoretical guarantee. In addition, both of our algorithms are much better than those returned by the random scheme.
To further show the effectiveness of our algorithms, we proceed to compare the results of our methods with the baseline schemes on four relatively larger real-world networks: Yeast with 1458 nodes and 1948 edges, GridWorm with 3507 nodes and 6531 edges, Erdös992 with 5094 nodes and 7515 edges, and Reality with 6809 nodes and 7680 edges, for which it is almost impossible to get the optimal solutions by brute-force search. For each network, the performance of different methods for
varying k and |EC | = 10000 candidate edges are displayed in Figures 2. We can see that SPGREEDY achieves the best performance as expected, and the proposed FASTGREEDY (a): is very close to the SPGREEDY method, and (b): consistently outperforms all four alternative methods.
In Table 1 we provide the results of running time and the drop of the P-D index ∆I(G) returned by our two greedy algorithms. We observe that FASTGREEDY is significantly faster than SPGREEDY, especially for large networks, while both algorithms almost yield the same value on ∆I(G). It is worth noting that SPGREEDY is not applicable to the last eight networks marked with "∗" due to the limitations of time and memory. In comparison with SPGREEDY, FASTGREEDY approximately computes ∆I(G) within several hours. Therefore, our algorithm FASTGREEDY achieves remarkable improvement in efficiency and is scalable to large networks with more than 106 nodes.

heading: 8 Conclusions
text: In this paper, we considered the problem of minimizing the disagreement polarization index I(G) by strategically recommending k links. This problem belongs to the class of discrete optimization that has found vast applications in various domains. We showed the objective function is monotone but non-submodular. We then presented two greedy algorithms to solve the optimization problem: the former returns a constant-factor approximation of the optimum solutions in time O(n3), while the latter runs in time Õ(mk −2). On the theoretic side, we provided analysis of the approximation guarantee for these two algorithms. On the experimental aspect, we performed extensive experiments on real-life networks, which demonstrate that both of our algorithms lead to almost optimal solutions, and consistently outperform several alternative baseline heuristics. Particularly, our second algorithm could yield a good approximation solution quickly on networks with more than one million nodes within 2 hours, demonstrating excellent scalablity to massive networks.
Acknowledgments and Disclosure of Funding
This work was supported by the National Key R & D Program of China (No. 2018YFB1305104), the National Natural Science Foundation of China (Nos. U20B2051 and 61872093), Shanghai Municipal Science and Technology Major Project (Nos. 2018SHZDZX01 and 2021SHZDZX03), ZJ Lab, and Shanghai Center for Brain Science and Brain-Inspired Technology.

Review summaries:
The paper studies the problem of recommending k links to a given graph G from a candidate pool of candidate links Ec. The goal is to minimize the index of disagreement-polarization as introduced by Musco et al. The authors prove that the objective is not submodular, but they analyze the performance of greedy, and provide a fast version based on random projections. They apply their methods on real-world data, with synthetic opinions. 

The problem considered is adding links to a network to decrease the polarization+disagreement ratio. The proposed method is the greedy algorithm: adding links one-by-one to maximize the improvement. Showing approximation ratio based on the approximation result of [5] (in ICML'17, showing that the  polarization+disagreement  is close enough to being submodular.   Evaluating a greedy step exactly required a matrix inversion, hence it is slow. The authors also offer a faster approximate solution using Johnson-Lindenstrauss lemma

In this paper, the authors study an opinion dynamics problem using the Friedkin-Johnsen model, where one aims to minimize the polarization + disagreement by adding up to k edges. The authors derive a greedy algorithm for this problem and show that it has a constant factor approximation. They then derive a faster version of the greedy algorithm (but without a constant factor approximation) involving random matrix projections, JL, and fast SDDM solvers. Empirically, they show that their methods are close to optimal for small k, and that their fast greedy algorithm scales well to large networks.

In this paper the authors propose the task of adding links to a social network to minimize notions of disagreement and polarization across the network.  In particular, they define disagreement across neighbors in the graph and polarization by the variance in expressed opinions of the nodes.  The paper then offers two approximate algorithms for greedily adding a fixed number of edges to the graph to minimize the sum of the disagreement and polarization.  They show that their algorithms are both theoretically and empirically tractable, outperform naive baselines, and in some cases close to optimal.