Variable Neighborhood Search Approach to Community Detection Problem

Abstract

Community detection on graphs can help people gain insight into the network’s structural organization, and grasp the relationships between network nodes for various types of networks, such as transportation networks, biological networks, electric power networks, social networks, blockchain, etc. The community in the network refers to the subset of nodes that have greater similarity, i.e. have relatively close internal connections. They should also have obvious differences with members from different communities, i.e. relatively sparse external connections. Solving the community detection problem is one of long standing and challenging optimization tasks usually treated by metaheuristic methods. Thus, we address it by basic variable neighborhood search (BVNS) approach using modularity as the score for measuring quality of solutions. The conducted experimental evaluation on well-known benchmark examples revealed the best combination of BVNS parameters. Preliminary results of applying BVNS with thus obtained parameters are competitive in comparison to the state-of-the-art methods from the literature.