Research On Community Detection Problem Of Bipartite Network And Signed Network

In real life,all kinds of complex systems can be studied by using corresponding complex networks,such as group ecosystem,economic system,biological system and other complex systems.Community structure mining is an important research content in the field of complex networks.The community structure of a complex network can be expressed as: in the community,the nodes are connected relatively closely,while the edges of the community connecting the external community are relatively sparse.Since communities usually correspond to some basic functional units,a community is often relatively independent in structure.Finding the hidden community structure in complex network provides a new method to reveal the organization principle and function analysis of complex network.Different from the unipartite network,the bipartite network belongs to a special kind of complex network.Bipartite networks are composed of two kinds of heterogeneous vertices,and edges only exist between different types of vertices.Many complex networks in the real world can be represented as bipartite networks.For example: audience-songs network,disease-gene network,actors-films network,scientists-paper cooperation network and so on.Therefore,it is of great theoretical significance and practical value to mine the community of bipartite network for the study of complex network.In the real world,there are many kinds of relationships between the entity objects of social networks,such as the relationship between support and opposition,the relationship between cooperation and competition,the relationship between friends and enemies,and so on.This kind of social network with positive and negative connections is called signed network.As a special case of social network,signed network has become one of the research hotspots of scholars.As the basis of signed network research,signed network community detection is of great significance to the theoretical research and application of user feature analysis,personalized recommendation,prediction and other related fields.In this paper,community detection in bipartite network and signed network is deeply studied,mainly including the following aspects.(1)The discrete particle swarm optimization algorithm is applied to the community detection of bipartite network.A new initialization method of particle swarm optimization algorithm for community detection in bipartite networks is proposed,which can accelerate the convergence speed of the proposed multi-objective discrete particle swarm optimization algorithm MODPSO-BN.The MODPSO-BN algorithm modifies the update rules of the position and velocity vectors of the traditional discrete particle swarm optimization(DPSO)algorithm to make the algorithm’s results more accurate.In addition,in the MODPSO-BN algorithm,a local search function is innovatively proposed,which can quickly drive the particles to the promising region and make the algorithm jump out of the local optimal solution with a certain probability.The experimental results verify the correctness and effectiveness of the MODPSO-BN algorithm and show that it is superior to the two compared algorithms.(2)Memetic algorithm is applied to community detection in bipartite networks.The proposed algorithm is named MATMCD-BN.First,a new population initialization method is proposed,which helps to speed up the convergence of the population.Secondly,a new crossover operator and a new mutation operator are proposed,which are helpful to improve the accuracy of the solution and accelerate the convergence speed of MATMCD-BN algorithm.Finally,a local search function is proposed,which can improve the quality of the final solution of the algorithm and speed up the convergence speed of the algorithm.This function can also make the algorithm jump away from the local optimal solution and reach the global optimal solution with a certain probability.A large number of experiments show that MATMCD-BN algorithm has good detection ability.Experimental results show that the MATMCD-BN algorithm is significantly better than the MODPSO-BN algorithm and the other three comparison algorithms.(3)An improved artificial bee colony(ABC)algorithm is applied to community detection in bipartite networks.The proposed algorithm is named IABC-BN.First,a new population initialization process of artificial bee colony algorithm for community identification in bipartite networks is proposed.This initialization method can improve the diversity of the initial population of ABC algorithm and accelerate the convergence speed of the algorithm.Secondly,in the employed bees search step of the algorithm,a new combinatorial search formula is proposed.By using this combination formula and the increased parameter disturbance frequency,the development ability of the algorithm is further improved.Third,in the onlooker bees phase,another new combination search formula was proposed and a opposition-based learning(OBL)method was introduced to improve the exploitation ability of the algorithm.Finally,a new strategy to generate new food sources is used in the scout bees phase,which improves the exploration ability of the algorithm and enhances the population diversity of the algorithm.The experiment verifies the effectiveness of the IABC-BN algorithm and shows that it is superior to the MODPSO-BN algorithm and the MATMCD-BN algorithm.(4)A memetic algorithm MACD-SN for signed network community discovery is proposed.Firstly,a new population initialization algorithm is proposed to accelerate the convergence speed of MACD-SN algorithm.Secondly,a new crossover operation and a new mutation operation are proposed.The new crossover operation and the new mutation operation can significantly improve the accuracy of the operation results of the MACD-SN algorithm and reduce the running time of the algorithm.Finally,a local search subroutine is proposed,which can greatly improve the accuracy of the final results of the algorithm and reduce the time of finding the optimal solution.This subroutine can also make the algorithm jump out of the local optimal solution and quickly approach the global optimal solution with a certain probability.The experimental results prove that the MACD-SN algorithm is a good signed network community detection algorithm,which is better than the four comparison algorithms in the experiment.(5)An improved artificial bee colony(ABC)algorithm IABC-SN is proposed for community detection in signed networks.First,a new population initialization method is proposed,which speeds up the convergence speed of the population and improves the diversity of the population.Secondly,in the employed bees phase,a new combination solution search formula is proposed,which is guided by the better neighbor solution of the current solution and the global optimal solution.By using this combination formula and increasing the parameter disturbance frequency,the exploitation ability of IABC-SN algorithm is further improved.In the onlooker bees step,another new combination food source search formula is proposed to enhance the exploitation ability of the algorithm.In addition,at this phase,a opposition-based learning(OBL)method is also used to improve the optimization ability of the IABC-SN algorithm.Finally,in the scount bees phase,the method of generating new food sources for multiple exhausted food sources is used to enhance the exploration ability of the algorithm and improve the population diversity of the algorithm.A large number of experiments show that IABC-SN algorithm is better than MACD-SN algorithm.