# Online Social Space Identification. A Computational Tool for Optimizing Social Recommendations
## 6 Numerical Experiments
### Distributed Learning
\begin{table}
\begin{tabular}{l c c c c} \hline \hline \multicolumn{5}{c}{**Centralized Execution**} \\ \hline
**Model** & **InpDiam** & **OutDiam** & **OutN** & **OutP** \\ \hline ER(150,0.1) & 3.3 (0.48) & 2 (0) & 18.5 (3.53) & 25.5 (21.20) \\ ER(150,0.2) & 3 (0) & 2 (0) & 52.8 (38.30) & 387.4 (633.60) \\ ER(500,0.1) & 3 (0) & 3.4 (3.30) & 16.9 (9.60) & 34.9 (36) \\ ER(500,0.2) & 2 (0) & 2 (0) & 430.3 (68.50) & 20840.9 (6164) \\ ER(1500,0.1) & 2.43 (0.51) & 2 (0) & 105.4 (52.60) & 1278.5 (983.30) \\ \hline \hline \multicolumn{5}{c}{**Distributed Execution**} \\ \hline ER(150,0.1) & 3.2 (0.42) & 2 (0) & 18.8 (3.12) & 28.9 (18.30) \\ ER(150,0.2) & 3 (0) & 2 (0) & 53.3 (25.60) & 294.6 (298.90) \\ ER(500,0.1) & 3 (0) & 2.6 (1.1) & 42.6 (49) & 183.5 (496.30) \\ ER(500,0.2) & 2 (0) & 2 (0) & 346.6 (110.30) & 14519.9 (9588.90) \\ ER(1500,0.1) & 2.25 (0.46) & 2 (0) & 104.6 (22.70) & 1180.8 (645.30) \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Models (Erdos–Renyi), input diameter (InpDiam), output diameter (OutDiam), output nodes (OutN), output feasible pairs (OutP). The standard deviation is shown in brackets. \begin{table}
\begin{tabular}{l c c c c} \hline \hline \multicolumn{5}{c}{**Centralized Execution**} \\ \hline
**Model** & **Fit** & **Iter** & **CPU Time** & **Ratio** \\ \hline ER(150,0.1) & 18.5 (3.53) & 88.6 (14.90) & 43.47 (14.90) & 8.10 \\ ER(150,0.2) & 52.8 (38.30) & 267.6 (147.30) & 263.8 (120.10) & 2.84 \\ ER(500,0.1) & 16.9 (9.60) & 64.74 (27.32) & 295.83 (163.40) & 29.60 \\ ER(500,0.2) & 430.3 (68.50) & 46.09 (70.86) & 910.37 (1580.29) & 1.16 \\ ER(1500,0.1) & 105.4 (52.60) & 408.43 (235.08) & 1171.79 (1056.60) & 14.23 \\ \hline \hline \multicolumn{5}{c}{**Distributed Execution**} \\ \hline ER(150,0.1) & 18.8 (3.12) & 20.20 (5.2) & 47.50 (21.7) & 7.97 \\ ER(150,0.2) & 53.3 (25.60) & 59.80 (32.4) & 77.56 (32.13) & 2.81 \\ ER(500,0.1) & 42.6 (49.00) & 13.29 (10.57) & 119.80 (233.65) & 11.73 \\ ER(500,0.2) & 346.6 (110.30) & 4.33 (6.40) & 107.89 (522.38) & 1.44 \\ ER(1500,0.1) & 104.6 (22.70) & 112.50 (10.35) & 234.51 (247.24) & 14.34 \\ \hline \hline \end{tabular}
\end{table} 
Table 3: Models (Erdos–Renyi), best fitness (Fit), iteration (Iter), CPU Av. time., the ratio between input and output vertices. The standard deviation is shown in brackets. * Similarly to previous experiments, as we could not confront the problem's optimal solution, to evaluate the solution proposed by the genetic algorithm qualitatively, we report the ratio between the number of vertices of the input and the output graphs. Notice that the approximability of the problem was very hard to obtain (not approximable within a factor \(|V|^{1/2-\varepsilon}\), for each \(\varepsilon>0\)[47]). Considering our results, in particular the ratio in Table 3, we concluded that the most interesting solutions were those for which the larger the input graph (number of vertices), the lower the difference between the ratio and the unit. * Although the size of the identified communities did not seem to differ, the (average) number of iterations of the last level site (distributed execution) was much lower than the iterations reported by the standard, centralized evolution. This was also evident from the decrease in the average execution time per level, reported by the distributed process. Since GAs use the same parameters for the standard and the distributed evolution, this behavior could be traced back to the initialization that each lower level site received from the higher levels. * The computational cost seemed to depend on both the edge numbers (i.e., high expected connectivity of random models \(E(n,p)\)) and the number of input vertices. As the fitness computational complexity was related to the diameter computation, this assertion could be justified considering the diameter computational cost, which is known to be bounded by \(O(|V|^{3})\).