# Optimization Algorithms for Detection of Social Interactions
## 4 Results
### On the Computational Complexity of Opt-IA and Hybrid-IA
* The operator \(\text{Precompetition}()\) randomly selects two vertices, checks their community numbers, and, if they are the same, it deletes with probability \(1/2\) the one with lower fitness. Since the fitness value was already computed, the overall cost of the operator is clearly \(\mathcal{O}(1)\). * The operator \(\text{StochasticAging}()\) goes through all the elements of the population and removes an element with the user defined probability \(P_{die}\). Thus, its overall cost is \(\mathcal{O}(N)\). * Finally, the operator \(\text{Selection}()\) chooses, without repetition of fitness values, the best \(d\) B cells among \(P_{a}^{(pre)}\) and \(P^{(hyp)}\). As we underlined before, the number of elements in these two populations is constant with respect to the size of the input, so we can simply say that the cost of the operator is \(\mathcal{O}(1)\). In summary, the cost of one iteration of Opt-IA has a computational upper bound \(\mathcal{O}(N^{2}+N)=\mathcal{O}(N^{2})\). Finally, let us take into consideration the number of iterations. We mentioned that for all the experiments concerning Opt-IA the number of generations was fixed to 1000. For the bigger graphs, it is a number smaller than the number of edges and about five times the number of vertices. It is clear, though, that, contrary to the other parameters, the number of generations cannot be considered independent from the size of the input. The bigger the input, the bigger is the number of generations that we expect to need. However, how does it grow with respect to \(N\)? The possibility of keeping it constant for large graphs, and the results of our experiments tell us that such a growth is at worst linear with respect to \(N\). Thus, if we want to be very cautious in estimating the overall complexity of Opt-IA, we can say that we need at most \(c\cdot N\) generations to obtain good results. If we check again Figure 1, we see that. after about \(250\sim 2.5|V|\) generations, Opt-IA reaches the optimal solution. In general, we estimate that the number of generations is at most \(5\cdot|N|\). If we add such a bound on the overall computational analysis of Opt-IA, we can certainly claim that the upper bound for its running time is \(\mathcal{O}(N^{3})\). If we study the computational cost of Hybrid-IA, we find very few differences with what we saw for Opt-IA. Namely,  
* The operator \(\text{Hypermutation}()\) in the worst case moves all the vertices from one community to another, but it is still obviously \(\mathcal{O}(N)\). * The operator \(\text{Aging}()\) goes through all the elements of the populations which we consider a constant number, again independent from the size of the input graph, so, all in all, it is \(\mathcal{O}(1)\). * The operator \(\text{LocalSearch}()\) acts on every vertex of the given graph and explores its vicinity. Therefore, we can estimate that its work has an upper bound \(\mathcal{O}(N^{2})\). In summary, the cost of one iteration of Hybrid-IA has a computational upper bound \(\mathcal{O}(N^{2})\), just like Opt-IA, though clearly higher internal constant factors. Such a constant factor is balanced by the number of generations. We fixed it to 100 for all the experiments, including the very large synthetic graphs, where we noted we should have probably had a larger number of generations. Once again, the number of generations cannot be considered independent from the size of the input. However, certainly for Hybrid-IA, it is asymptotically not larger than what we estimated for Opt-IA. Moreover,even assuming that its growth is linear with respect to \(|V|\), the constant factor is definitively smaller. In any case, we can conclude that, also for Hybrid-IA, we have a computational upper bound \(\mathcal{O}(N^{3})\).