Q-MeaMetaVC: An MVC Solver of a Large-Scale Graph Based on Membrane Evolutionary Algorithms

Abstract

In recent years, the rapid development of the internet and the advancement of information technology have produced a large amount of large-scale data, some of which are presented in the form of large-scale graphs, such as social networks and sensor networks. Minimum vertex cover (MVC) is an important problem in large-scale graph research. This paper proposes a solver Q-MeaMetaVC based on the MVC framework PEAF and the membrane evolution algorithm framework MEAF. First, the graph is reduced and divided into two types of connected components (bipartite graph and non-bipartite graph) to reduce the scale of the problem. Second, different membrane structures are designed for different types of connected components to better represent the connected component features and facilitate solutions. Third, a membrane evolution algorithm (MEA), which includes fusion, division, cytolysis, and selection operators, is designed to solve the connected components. Then, Q-MeaMetaVC is compared with the best MVC solver in recent years on the test set, and good experimental results that are obtained verify the feasibility and effectiveness of Q-MeaMetaVC in solving the MVC of large-scale graphs.

Keywords

• membrane evolutionary algorithm
• minimum vertex cover
• large-scale graphs
• membrane computing