Research On Ant Colony Clustering Algorithm For Community Structure Detection In Complex Networks

Community structure of complex networks is one of the most popular andimportant properties, which means that nodes within a group are much moreconnected to each other than to the rest of the network. Detecting communitystructure is significant for understanding the features of topological structures,comprehending network function modules, recognizing hidden relations betweennodes and forecasting the future behaviors of complex networks. Although there are alot of methods have been proposed at present, how to further improve the clusteringaccuracy, especially how to discover reasonable community structure without priorknowledge such as the number of communities, and how to detect the communitystructure in large-scale complex networks quickly are still challenging researchproblems.Ant colony clustering algorithm as a swarm-intelligence based algorithm, itmakes ants that represent data self-organize into cluster dynamically, by simulatingthe ants’ behaviors of piling corpses. The algorithm is fast and efficient, and achieveshigh-quality clustering results without prior knowledge. It is suitable for solving highdimensional and complicated clustering problems. Combining with the features ofsmall complex networks and large-scale complex networks, we do the followingworks in this article by learning from the idea of ant colony clustering.(1)Combining the fitness perception with the pheromone diffusion mechanism,we propose the ant colony clustering algorithm to detect communities in complexnetworks. In this new algorithm, each ant represents a node of a complex network,and at the beginning, ants are randomly placed at different locations in a virtual grid.During the evolution process, the ants make use of the perception of the fitnessfunction to move to a new position or stay in the original position. Ant colony movingat each cycle will form a clustering result, whose quality has an influence on updatingthe pheromone of nodes. Meanwhile to reflect characteristics of the pheromonediffusion, a pheromone diffusion model is applied to the pheromone updating. Theevolution process is repeated till all ants find the most comfortable positions, and thenthe community structure of the complex network is visible in the grid. Experimentalresults on benchmark datasets compared with some classic methods show thealgorithm can achieve good clustering results. (2)With the contradiction that the scale of complex networks expands graduallyin realistic society, but the speed of clustering method is slower, we present the antcolony clustering algorithm based on sampling to discover communities in large-scalecomplex networks. Firstly, the algorithm reduces the scale of the problem by samplingnodes from network. Secondly, the method uses the ant colony clustering proposed inthe first work to cluster the sampled nodes, and lays the thought of label propagationto sign the sampled nodes. Thirdly, it assigns the un-sampled nodes into the detectedcommunity according to the similarity metric. Finally, we take the modularityfunction value as index, and correct the initial clustering result by merging.Experimental results on the benchmark datasets show that the new algorithm can notonly greatly improve the speed of detecting community structure, but also has theability to balance between getting high-quality solutions and operation efficiency.