Particle Swarm Optimization And Its Application To Network Community Detection

Network is ubiquitous. Network is changing our daily life unprecedentedly. Diverse complex systems in real life can be represented with complex networks which are composed of nodes and edges, where nodes represent the objects that compose the systems and the edges denote the relations among objects. To do research on the structure analysis of complex networks can help to understand the functionality of complex systems. The community feature is one of the notable features of complex network. It is of great importance to mine communities hidden behind the networks. It has raised wide attention to the research on community detection. This essay starts from the perspective of optimization and models the community detection problem as an optimization problem, then makes use of particle swarm optimization to solve it. The work of this essay is as follows:(1) It systematically illustrates the basic concepts of particle swarm optimization,including the rational of the basic particle swarm optimization and the corresponding variants of the basic particle swarm optimization algorithms. Moreover, it has illustrated the basic concepts of complex networks, including the basic features of complex networks such as the small world, the scale free properties, and with emphasis on the community feature. At last, it systematically illustrates the existing community detection methods, including the clustering methods and the optimization methods. The merits and demerits are also given.(2) In order to discover hidden community structure in an unsigned network, the paper modeled the task as optimization problem, based on the perspective of particle swarm optimization, combined with the prior knowledge of the network, the state of the particle has been redesigned, so is the status update rules of the particles flying equation,consequently, it proposed a framework based on discrete particle swarm optimization algorithm and it has been successfully applied to the complex network community mining problem. Experiments on simulated data and real data are tested, and 7algorithms existing in the literature are compared, in addition, statistical analysis is adopted to verify the validity of the algorithm. A large number of experiments proved the high effectiveness of the proposed algorithm.(3) Based on the above, the paper puts forward algorithm for solving unsigned web community mining, considering the reality of many network is signed, because the relations in real network members may be friendly or hostile, combined with the characteristics of signed network, an improvement is made to the above proposed particle swarm optimization algorithm so as to make it capable of handling signed networks. In order to accelerate the convergence speed of particles, the paper has devised a particle local learning strategies based on network connection. In order to verify the validity of the algorithm, experiments on simulated network data and real signed network are employed, and take a comparison with several existing algorithms in the literature. The experimental results show that the proposed algorithm is effective.