# Measuring Polarization in Online Debates
## 4 Finding the Most Polarized Partition  
In this section, we present a greedy local search optimization algorithm for finding a bipartition \((L,R)\) of \(\mathcal{G}=\langle\mathcal{C},\mathcal{E},\mathcal{S},\mathcal{W}\rangle\) with a high value for \(BipPol(L,R,\mathcal{G})\) that follows the same basic idea of common greedy algorithms for the maxcut problem, with the goal to find a partition with a polarization value that is close to the highest one. It seems very unlikely that we can have exact polynomial-time algorithms for our problem, as it can be shown that the maxcut problem can be reduced to a slight generalization of our optimization problem. The algorithm follows these steps:  
1. Initialize vertices in either \(L\) or \(R\). The most obvious idea is to order vertices by polarity, and then assign the negative ones to \(L\) and the rest to \(R\). Although this clearly gives the best possible value for \(SC(L,R,\mathcal{G})\), other assignments could make improvements to the value of \(SWeight(L,R,\mathcal{G})\). That is, it could be that the best partition (with respect to its value of \(BipPol(L,R,\mathcal{G})\)) is not a partition where all users' opinions of the same polarity are found on the same side of the partition because the value of \(SWeight(L,R,\mathcal{G})\) can be significantly higher when some users' opinions with different polarity are placed on the same side. This class of users would be users that are, to some extent, inconsistent, in the sense that they seem to support one side of the debate, but at the same time, they seem to attack a significant number of users' opinions of the same side. To consider these kinds of partitions as possible solutions for our search algorithm, we propose two possible ways to initialize the partition \((L,R)\):  
1. Place each user's opinion uniformly at random in either \(L\) or \(R\). This way, we do not initially force a bias toward consistent partitions. 1. Place each user's opinion \(C_{i}\) randomly in \(L\) with probability \(P_{L}=\frac{1-\mathcal{S}(C_{i})}{2}\) and in \(R\) with probability \(1-P_{L}\). In this second way, only users with a strict disagreement (\(\mathcal{S}(C_{i})=-1\)) or a strict agreement (\(\mathcal{S}(C_{i})=1\)) will have a unique possible side on the initial partition. 2. Perform local improvement (regarding the value of _BipPol_) steps: at each iteration, find a good candidate from \(L\) (to be moved to \(R\)) and a good candidate from \(R\) (to be moved to \(L\)). The pseudocode is shown in Algorithm 1. ```
Input:\(\mathcal{G}\)= \(\langle\mathcal{C},\mathcal{E},\mathcal{S},\mathcal{W}\rangle\) Output: a bipartition \((L,R)\) of \(\mathcal{G}\) with high bipartite polarization \((L,R):=getInitBPart(\mathcal{G})\)// Get Initial bipartition improving \(:=true\) steps \(:=0\) while(improving \(\mathcal{SG}\) steps \(\leq\) maxsteps)do  improving \(:=false\) if\(\exists v\in L,\text{BipPol}(L\setminus v,R\cup v,\mathcal{G})>\text{BipPol}(L,R, \mathcal{G})\)then \((L,R):=(L\setminus v,R\cup v)\)// improved bipartition improving \(:=true\) if\(\exists v^{\prime}\in R,\text{BipPol}(L\cup v^{\prime},R\setminus v^{ \prime},\mathcal{G})>\text{BipPol}(L,R,\mathcal{G})\)then \((L,R):=(L\cup v^{\prime},R\setminus v^{\prime})\)// improved bipartition improving \(:=true\) steps \(:=steps+1\) return\((L,R)\)
```  
**Algorithm 1**Finding a local optimal solution for a bipartition of \(\mathcal{G}\)= \(\langle\mathcal{C},\mathcal{E},\mathcal{S},\mathcal{W}\rangle\) with high bipartite polarization. Figure 4 shows the result of applying Algorithm 1 using the UDebG of Figure 3 as input. Nodes in red color are the nodes in the L set, and nodes in blue color are the nodes in the R set. The algorithm used to compute the initial partition is g1, and after this initialization, the algorithm performs a few steps depending on the randomness of g1. These steps are to reallocate nodes 1, 2, 3 and 5 to the sets that increase more the \(\text{BipPol}(L,R,\mathcal{G})\) value, in case they are not already there.