# Optimization Algorithms for Detection of Social Interactions
## 3 Immunological Algorithms
### Hybrid-IA
The Local Search designed and introduced in Hybrid-IA is the key operator to properly speed up the convergence of the algorithm, and, in a way, drive it towards more promising regions. Furthermore, it intensifies the search and explore the neighborhood of each solution using the well-known _Move Vertex_ approach (MV) [15]. The basic idea of the proposed LS is to assess deterministically if it is possible to move a node from its community to another one within its neighbors. The MV approach takes into account the _move gain_ that can be defined as the variation in modularity produced when a node is moved from a community to another. Before formally defining the move gain, it is important to point out that the modularity \(Q\), defined in Equation (1), can be rewritten as:  
\[Q(c)=\sum_{i=1}^{k}\left[\frac{\ell_{i}}{M}-\left(\frac{d_{i}}{2M}\right)^{2} \right], \tag{2}\]  
where \(k\) is the number of the found communities; \(c=\{c_{1},\dots,c_{i},\dots c_{k}\}\) is the set of communities that is the partitioning of the set of vertice V; \(l_{i}\) and \(d_{i}\) are, respectively, the number of links inside the community \(i\), and the sum of the degrees of vertices belonging to the \(i\) community. The _move gain_ of a vertex \(u\in c_{i}\) is, then, the modularity variation produced by moving \(u\) from \(c_{i}\) to \(c_{j}\), that is:  
\[\Delta Q_{u}(c_{i},c_{j})=\frac{l_{c_{j}}(u)-l_{c_{i}}(u)}{M}+d_{V}(u)\left[ \frac{d_{c_{i}}-d_{V}(u)-d_{c_{j}}}{2M^{2}}\right], \tag{3}\]  
where \(l_{c_{i}}(u)\) and \(l_{c_{j}}(u)\) are the number of links from \(u\) to nodes in \(c_{i}\) and \(c_{j}\) respectively, and \(d_{V}(u)\) is the degree of \(u\) when considering all the vertices \(V\). If \(\Delta Q_{u}(c_{i},c_{j})>0\), then moving node \(u\) from \(c_{i}\) to \(c_{j}\) produces an increment in modularity, and then a possible improvement. Consequently, the goal of MV is to find a node \(u\) to move to an adjacent community in order to maximize \(\Delta Q_{u}\):  
\[\operatorname*{argmax}_{v\in Adj(u)}\Delta Q_{u}(i,j), \tag{4}\]  
where \(u\in C_{i}\), \(v\in C_{j}\) and \(Adj(u)\) is the adjacency list of node \(u\). For each solution in \(P^{(select)}\), the Local Search begins by sorting the communities in increasing order with respect to the ratio between the sum of inside links and the sum of the node degrees in the community. In this way, poorly formed communities are identified. After that, MV acts on each community of the solution, starting from nodes that lie on the border of the community, that is, those that have at least an outgoing link. In addition, for communities, the nodes are sorted with respect to the ratio between the links inside and node degree. The key idea behind LS is to deterministically repair the solutions which were produced by the hypermutation operator, by discovering then new partitions with higher modularity value. Equation (3) can be calculated efficiently because \(M\) and \(d_{V}(u)\) are constants, the terms \(l_{c_{i}}\) and \(d_{c_{i}}\) can be stored and updated using appropriate data structures, while the terms \(l_{c_{i}}(u)\) can be calculated during the exploration of all adjacent nodes of \(u\). Therefore, the complexity of the move vertex operator is linear on the dimension of the neighborhood of node \(u\).