Research On Community Detection In Networks Based On Multi-objective Optimization Algorithm

The study of complex networks has received an enormous amount of attention from the scientific community in recent years. A plenty of systems in the world such as social relationship networks, Internet, biology networks and transportation networks can be modeled as complex networks. In a network, each node indicates an object in a system while the relation between which can be shown in the edges of the network. Community structure which indicates different division to the nodes in a certain networks is one of the most important features of networks. Communities of a network are the groups of vertices within which connections are dense, but between which connections are sparser. Detecting the communities of a network is of great help for us to analysis the relationship between the objects in the network and has a good knowledge of the whole structure of it. For this reason, research on the community detection methods is a significant topic.Many of the existed community detection technologies such as the spectral methods require the number of the communities previously. However, in the real world, the number of the communities in a complex networks is always undiscovered by us in advance. Therefore, methods which can determine the number of communities automatically should be proposed. The methods based on optimization can solve this problem. However, single objective optimization algorithm can only obtain one solution through each run, this means only one determined partition to the network is given. Real-life systems are hierarchical networks, so the methods which can output a series of solutions with different hierarchical partitions to a network are of great practical value.In this paper, we propose a multi-objective approach, named NNIA-Net, to discover communities in networks by employing Non-dominated Neighbor Immune Algorithm (NNIA). Then the method based on optimization algorithm is used to deal with the community detection problem in dynamic networks.Our innovative points are as follows:1. An improved initialization method has been proposed. This method is based on locus-based coding mode. The experimental results show that our new initialization method is higher in efficiency than existed methods.2. The second innovation of this paper is that the proposed community detection method produces a series of solutions which represent various divisions to the networks at different hierarchical levels. The number of subdivisions is automatically determined by the non-dominated individuals resulting from our algorithm.3. It is a community detection technology in dynamic networks based on the evolutionary clustering framework which is called DNNIA-Net. This method is used to deal with the community detection problem in gradually changing networks by analysis the present network and its history state. With the history information, this method can reflect the evolutionary process of the network.This work was supported by the National Natural Science Foundation of China (Grant Nos.60703107), the National High Technology Research and Development Program (863Program) of China (Grant No.2009AA12Z210), the Program for New Century Excellent Talents in University (Grant No. NCET-08-0811), the Program for New Scientific and Technological Star of Shaanxi Province (Grant No.2010KJXX-03), and the Fundamental Research Funds for the Central Universities (Grant No. K50510020001).