# On the Complexity of the Bipartite Polarization Problem:
## 5 A Random Generator Model for UDebG Instances  
We present a random generator of UDebG instances, where the goal is to control the expected bipartite polarization of the instance by means of a single parameter \(\alpha\), that lies in the range \((0,1]\), and where the number of nodes (users) is given by a parameter \(m\). Note that, for \(\alpha=0\), all the nodes would have \(\mathcal{S}(C_{i})=0\). This extreme case corresponds to the trivial problem where the bipartite polarization is zero for any bipartition. For this reason, \(\alpha=0\) is not considered in our random generator. The generation process consists of the two following steps:  
1. Generation of the set of nodes \(\mathcal{C}\) with their \(\mathcal{S}(C_{i})\) value. Each node \(C_{i}\) is generated with a value \(\mathcal{S}(C_{i})\) from \([-\alpha,\alpha]\), obtained with a bimodal distribution that arises as a mixture of two different truncated normal distributions \(TN(-\alpha,0,\mu_{1},\sigma_{1})\) and \(TN(0,\alpha,\mu_{2},\sigma_{2})\). The first distribution is defined on the interval \([-\alpha,0]\) with mean \(\mu_{1}\) and standard deviation \(\sigma_{1}\) equal to: \[\mu_{1}=-\alpha,\;\sigma_{1}=\frac{1}{1+20\alpha}.\] And, analogously for the second distribution, but now defined on the interval \([0,\alpha]\), and with values: \[\mu_{2}=\alpha,\;\sigma_{2}=\frac{1}{1+20\alpha}.\] So, with this bimodal distribution, the values are concentrated around the two modes (\(-\alpha\) and \(\alpha\)), but how tightly they concentrate is inversely proportional to \(\alpha\), so the higher the value of \(\alpha\), the smaller the standard deviation. 2. Generation of the set of edges \(\mathcal{E}\) with their \(\mathcal{W}(i,j)\) value. For each node \(i\), we randomly select a set of \(k\) target vertices \(\{j_{1},j_{2},\ldots,j_{k}\}\), with \(k\) randomly selected from \([1,\lceil\log_{10}(m)\rceil]\), to build outgoing edges from \(i\) to those vertices. The value of \(\mathcal{W}(i,j)\) is generated with a truncated normal distribution on the interval \([-2,2]\) with \(\mu\) and \(\sigma\) that depend on the values of \(\mathcal{S}(C_{i})\) and \(\mathcal{S}(C_{j})\) as follows: \[\mu=\left\{ \begin{array}{ll}2\cdot|\mathcal{S}(C_{i})|-|\mathcal{S}(C_{i})- \mathcal{S}(C_{j})|,&\text{ if $C_{i}$ and $C_{j}$ are on the same side}\\ -|\mathcal{S}(C_{i})|\cdot|\mathcal{S}(C_{i})-\mathcal{S}(C_{j})|,&\text{ if $C_{i}$ and $C_{j}$ are on different side}\end{array} \right.\] \[\sigma=\frac{2}{3+10|\mu|}.\] So, when the users \(C_{i}\) and \(C_{j}\) are on the same side (\(\mathcal{S}(C_{i})\) and \(\mathcal{S}(C_{j})\) are both either positive or \(\leq\)0), the mean of the distribution will be positive, and the more similar the values \(\mathcal{S}(C_{i})\) and \(\mathcal{S}(C_{j})\) are, and the closer \(|\mathcal{S}(C_{i})|\) is to 1, the closer \(\mu\) will be to 2. By contrast, when the users \(C_{i}\) and \(C_{j}\) are on different sides, the more different the values \(\mathcal{S}(C_{i})\) and \(\mathcal{S}(C_{j})\) are, and the closer \(|\mathcal{S}(C_{i})|\) is to 1, the closer \(\mu\) will be to \(-2\). Observe that the sign of \(\mu\) depends on the sign of users \(i\) and \(j\). Regarding the absolute value \(|\mu|\), it depends on both \(\mathcal{S}(C_{i})\) and \(\mathcal{S}(C_{j})\), but more on the first one. This is because, in principle, the overall sentiment \(\mathcal{W}(i,j)\) (answers from user \(i\) to user \(j\)) is not necessarily equal to \(\mathcal{W}(j,i)\), although it is natural to think that there will be some positive correlation between them. In any case, we think that it makes sense to force the sign of the mean to be the same when generating \(\mathcal{W}(i,j)\) and \(\mathcal{W}(j,i)\). As for the absolute value, it is natural that users with stronger opinions (those with \(|\mathcal{S}(C_{i})|\) closer to 1) have stronger sentiments towards the rest of the users.