# Optimization Algorithms for Detection of Social Interactions
## 1 Introduction  
In last few years, many approaches have been proposed to detect communities in social networks using diverse ways. Community detection is one of the most important research topics in network science and graph analysis. Informally, a community is defined as a set of network's elements that are highly linked within the group and weakly linked to the outside. Modeling and examining complex systems that contain biological, ecological, economic, social, technological, and other information is a very difficult process because the systems used for the real-world data representation contain highly important information, such as social relationships among people or information exchange interactions between molecular structures in a body. For this reason, the study of community structures inspires intense research activities to visualize and understand the dynamics of a network at different scales [1; 2; 3]. In order to evaluate the quality of node partitions of a network, the _modularity_ is certainly the most used quality index [4]. Taking the modularity (\(Q\)) into account as an evaluation measure, community detection can easily be seen as a combinatorial optimization problem, since the problem aims to find a clustering that maximizes \(Q\). It is also a hard optimization problem since Community Detection has been proven to be an \(\mathcal{NP}\)-complete problem [5]. Therefore, several search algorithms (both exact and approximate) for clustering problems have been proposed, and, generally, they have been proven to be robust in finding as cohesive as possible communities in large and complex networks [6; 7]. It is well known inthe literature that metaheuristics work better than exact methods in large, complex, and uncertainty environments. Indeed, they are approximation methods successfully applied on many hard and complex problems able to find good solutions within reasonable computing times [8]. In this paper, we propose two Immunological Algorithms for the community detection problem, called Opt-IA and Hybrid-IA, respectively. The first is based on a random and blind search, and employs specifically designed stochastic operators to carefully explore the search space, while Hybrid-IA uses a Local Search (LS) technique that deterministically tries to refine the solutions found so far. The main goal in this paper is to prove the efficiency, robustness, and reliability of the two immune-inspired algorithms in community detection problem, as they have been successfully applied to several other areas and optimization tasks on networks. The efficiency and robustness of both algorithms were tested on several social networks (with different sizes), and, further, a comparison with seven other metaheuristic methods has also been performed in order to assess the reliability of Opt-IA and Hybrid-IA with respect to the state-to-the-art on community detection. In view of such comparisons, we are able to assert that both immunological algorithms outperforms all other methods used for comparison, and find the best modularity in all tested networks. By reducing the comparison to only Opt-IA and Hybrid-IA, it is possible to assert overall that the algorithms are comparable, although the first one, as expected, needs a higher number of generations due to its random and blind search. Finally, it is important to underline the fact that, differently than all other algorithms used for comparison, which have been tested and refined over the years, Opt-IA and Hybrid-IA are already very competitive and successful, even though they are at a first stage of development in community detection tasks, and still need a deep study of their key parameters and operators. The rest of the paper is organized as follows. In Section 2, the problem of community detection is introduced and the definition of the modularity measure are formulated.