# Optimization Algorithms for Detection of Social Interactions
## 4 Results
### On the Computational Complexity of Opt-IA and Hybrid-IA  
Both our algorithms are population based algorithms; therefore, any analysis of their computational complexity must deal not only with the size of the input problems and its implementation, which in turn implies the analysis of the computational cost of computing the fitness of any individual, but also with the choice of the key parameters, such as the number of elements in the population \(d\), the total number of iterations \(MaxGen\), etc. We will discuss these issues properly in what follows. When we look at the code for Opt-IA, we have the following:  
* Any element of the population, i.e., a tentative solution, is an array of length \(N\), where \(N\) is the number of vertices of the input graph. * The operator InitializePopulation(\(d\)) randomly creates a population of \(d\) tentative solutions. Thus, total cost is \(\mathcal{O}(dN)\). However, we stress here the fact that \(d\), which is set experimentally, is actually constant, i.e., it does not depend on the size of the input. In our case, we fixed to the value 100 for all of the experiments. This allows us to say that the cost of the procedure is actually \(\mathcal{O}(N)\). \begin{table}
\begin{tabular}{c c c c c c} \hline \hline  & \multicolumn{2}{c}{Hybrid-IA} & \multicolumn{2}{c}{Louvain} & \multicolumn{2}{c}{Difference} \\ \cline{2-7} \((|V|,k_{r},\mu_{t})\) & \(Q\) & \(NMI\) & \(Q\) & \(NMI\) & \(Q\) & \(NMI\) \\ \hline \((1000,20,0.1)\) & 0.8606 & **0.9980** & 0.8607 & 0.9931 & \(-0.0001\) & \(+0.0049\) \\ \((1000,20,0.2)\) & 0.7622 & **0.9970** & 0.7622 & 0.9909 & 0.0 & \(+0.0061\) \\ \((1000,20,0.3)\) & 0.6655 & **0.9927** & 0.6642 & 0.9790 & \(+0.0013\) & \(+0.0137\) \\ \((1000,20,0.4)\) & 0.5668 & **0.9905** & 0.5656 & 0.9588 & \(+0.0012\) & \(+0.0317\) \\ \((1000,20,0.5)\) & 0.4685 & **0.9857** & 0.4685 & 0.9393 & 0.0 & \(+0.0464\) \\ \((1000,20,0.6)\) & 0.3687 & **0.9767** & 0.3658 & 0.9084 & \(+0.0029\) & \(+0.0683\) \\ \((1000,20,0.7)\) & 0.2707 & **0.9127** & 0.2635 & 0.6969 & \(+0.0072\) & \(+0.2158\) \\ \((5000,20,0.1)\) & 0.8923 & **0.9991** & 0.8934 & 0.9589 & \(-0.0011\) & \(+0.0402\) \\ \((5000,20,0.2)\) & 0.7927 & **0.9966** & 0.7948 & 0.9399 & \(-0.0021\) & \(+0.0567\) \\ \((5000,20,0.3)\) & 0.6929 & **0.9967** & 0.6959 & 0.9282 & \(-0.0030\) & \(+0.0685\) \\ \((5000,20,0.4)\) & 0.5931 & **0.9945** & 0.5975 & 0.9076 & \(-0.0044\) & \(+0.0869\) \\ \((5000,20,0.5)\) & 0.4936 & **0.9953** & 0.5001 & 0.8789 & \(-0.0065\) & \(+0.1164\) \\ \((5000,20,0.6)\) & 0.3939 & **0.9976** & 0.4027 & 0.8518 & \(-0.0088\) & \(+0.1458\) \\ \((5000,20,0.7)\) & 0.2929 & **0.9942** & 0.3033 & 0.8064 & \(-0.0104\) & \(+0.1878\) \\ \((5000,20,0.7)\) & 0.2929 & **0.9942** & 0.3033 & 0.8064 & \(-0.0104\) & \(+0.1878\) \\ \hline \hline \end{tabular}
\end{table} 
Table 3: Comparison between Hybrid-IA and Louvain on Synthetic Networks with 1000 and 5000 vertices, with respect to modularity (\(Q\)) and \(NMI\) evaluation metrics. * The operator \(\text{ComputeFitness}()\) computes the fitness for all the \(d=100\) elements of the population. A bound on the cost of the procedure can easily be computed using Equation (1), and it clearly is \(\mathcal{O}(N^{2})\). * The operator \(\text{Cloning}()\) creates \(dup\) copies of each of the elements of the population. As you can see from our settings, \(dup\) is a parameter which does not depend on the size of the input graph, but just on the nature of the algorithm. This allows us to say that the cost of \(\text{Cloning}()\) is \(\mathcal{O}(N)\). * The operator \(\text{Hypermutation}()\) mutates each element of the population with constant probability \(m\). As we described earlier, we have three different implementations. In all three cases, we have either the random selection of a vertex or the random selection of a cluster. In the two most time-consuming implementations, namely _destroy_ and _fuse_, we might have the reallocation of several vertices. Thus, all in all, \(\text{Hypermutation}()\) has an upper bound \(\mathcal{O}(N)\).