Section 10

Variable Neighborhood Search for a Multi-Objective Community Detection Problem

Sergio Pérez-Peló, Jesús Sánchez-Oro Calvo, Antonio Gonzalez-Pardo, Abraham Duarte

In the last years, Social Networks and their analysis have become more and more popular due to the large amount of data that can be analyzed to extract valuable information. This information can be related to the users or to their interactions. There are different problems that can be addressed in the context of Social Network Analysis. In this work, the boarded problem is the Community Detection Problem (CDP). The main objective in this type of problems is to distribute users included in the social network in several communities, grouping similar users in the same community. In this work, we use a Variable Neighborhood Search (VNS) methodology to tackle a Multi-Objective Community Detection Problem. The objective functions to be optimized are Ratio Cut (RC) and Negative Ratio Association (NRA). Both objectives have been proven to be in conflict, so we cannot improve one of them without making the the other worse. The performance of the proposed algorithm is compared against a well-known Multi-Objective Evolutionary Algorithm, extracted from the State-of-the-art, called LMOEA. The experimentation phase considers synthetic and real social networks, and the obtained results are evaluated using two popular CDP metrics: Modularity and NMI.

Measuring the influence of users in social networks using Variable Neighborhood Search

Isaac Lozano-Osorio, Jesús Sánchez-Oro Calvo, Oscar Cordón García, Abraham Duarte

Social networks have become an important part of our society, mainly due to the amount of data generated by their users. This information is interesting for areas such as disease propagation analysis or viral marketing, among others. This task can be addressed by solving the Social Network Influence Maximization Problem (SNIMP). A social network is modeled as a graph G=(V,E), where the set of nodes V represents the users and the set of edges E, relations between users. The goal is to select the users that are able to spread information to the maximum number of users in the network. Since each user transmits the information to their related ones with a certain probability, it is necessary to perform a Monte Carlo simulation to evaluate the quality of a solution, which slows down the process. This work presents an efficient algorithm for dealing with SNIMP following the Basic Variable Neighborhood Search framework. The proposed method starts from a solution generated with a greedy randomized constructive procedure, and then systematically explores the neighborhoods generated by performing swap moves, replacing a selected node with a non-selected one. The local search defined follows a surrogate-assisted-swap approach in order to increase the efficiency.

Which are the most critical nodes in a network? A Basic Variable Neighborhood Search approach

Iván M. de San Lázaro, Jesús Sánchez-Oro Calvo, Abraham Duarte

The Critical Node Detection Problem (CNDP) is an optimization problem arising in the context of networks. Let us model a network as a graph G=(V,E), where V is the set of nodes and E represents the connections between nodes. The CNDP tries to identify which are the K key nodes in the network, with the aim of minimizing the pairwise connectivity by removing those K nodes. In the context of disease transmission, CNDP is useful to identify the most important members of a community in order to vaccinate them, reducing the expansion of the disease. Additionally, it can be a powerful tool to identify the key nodes in a terrorist network. In this work, the CNDP is tackled with a Basic Variable Neighborhood Search (BVNS) algorithm, leveraging metrics derived from social network analysis to improve the obtained solutions. The initial solution is constructed with a greedy algorithm, while the neighborhoods explored are based on swap moves. The performance of the search is improved by using a connected component algorithm. Experimental results shows that BVNS emerges as a competitive algorithm with the state-of-the-art methods for the CNDP, requiring small computing times when compared to them.

DOI: 10.1007/978-3-030-69625-2_1

A Variable Neighbourhood Search for the Dynamic Repatriation Scheduling Problem

Sameh Al-Shihabia, Nenad Mladenović

Severe acute respiratory syndrome coronavirus 2 (SARS-CoV-2), which the World Health Organization declared a pandemic in March 2020, has caused the most extensive global lockdown in history. Because commercial flights were suspended, many countries had to repatriate their citizens from other countries. To accomplish this, decision-makers had to schedule repatriation flights via the country’s flag-carrying airlines. These flights were constrained by the airline’s fleet capacity and the availability of quarantine locations. Consequently, flight schedules had to account for these two capacity-related constraints, in addition to the reason that forced the citizens to return. In this work, we examine this problem, which we call the repatriation scheduling problem (RSP). We develop a mixed-integer linear program (MILP) to minimize the penalties associated with keeping a country’s citizens abroad. We use priority values as penalty measures for the different individuals based on their reasons to return. We also develop a variable neighborhood search (VNS) algorithm to solve this problem. To test the suggested VNS algorithm, we develop a set of 162 instances that we solve using both the suggested VNS algorithm and a commercial exact solver.