Community Mining Algorithm Based On Evolutionary Computation And Research On Its Application

In our life, the network can be used to represent a large number of complex systems, such as friendship networks, transport networks, the Internet, telephone line networks, metabolic networks, food chain networks and so on. In recent years, complex networks have become a hot research topic, attracting the attention of a growing number of researchers in various fields at home and abroad. In earlier studies, we found that complex networks with small world and scale-free property, but in the follow-up study, the researchers also found that a complex network also has an extremely important community structure characteristics, community structure is defined as: within the same community, the connections between the nodes are close relatively, while between the different communities, the connection are sparse relatively. Mining Complex network community structure, we can analyze the structure of the network better, so that understand the function of the network. In addition, the network will help us discover potential law and thus can make a prediction of the network behavior, so the community mining has great significance and wide application prospect. In order to study complex networks, researchers have proposed many communities mining algorithms. These algorithms generally fall into three categories: based on figure segmentation method, based on hierarchical clustering method and modularity optimization method. In these three methods, the researchers are most interested in the modularity optimization method. Modularity is proposed by Newman and Girvan, which is an objective function used to measure of the quality of the divided community. Generally speaking, the value of the modularity greater, the community obtained by dividing will be more obvious.Memetic algorithm has been the concern of many researchers in the field of evolutionary computing recently. In addition to its search based on overall population, it also has based on heuristic search in local individuals. This combination make it higher search efficiency than traditional genetic algorithm in solve some problems. We use the advantages of memetic algorithm and applied to community mining of network. In this paper, the main work is done as follows:(1) Studied the problem of resolution limitation by used the modularity optimization method, we use a new objective function, general modularity density to solve this problem. The objective function can solve the problem of resolution limitations by adjusting the parameters in it.(2) Based on the study the basic theory of memetic algorithm, proposed an algorithm which can be applied to community mining of complex networks. We issue community mining of complex network as a single-objective optimization problem, the modularity Q and general modularity densityas the objective function, and use memetic algorithm optimized both goals, obtained two kinds of mining algorithms based on the MA-Net framework: MA-Net(Q) and MA-Net().Subsequently, we conducted experiments both in synthetic and real-world networks, show that compared to traditional genetic algorithm, memetic algorithm is fast convergence, noteasy to fall into local optimum, and community mining is more accuracy. Finally, the algorithm is compared with the GN algorithm, validate the algorithm is effective.