A link prediction algorithm based on ant colony optimization

摘要

The problem of link prediction has attracted considerable recent attention from various domains such as sociology, anthropology, information science, and computer sciences. In this paper, we propose a link prediction algorithm based on ant colony optimization. By exploiting the swarm intelligence, the algorithm employs artificial ants to travel on a logical graph. Pheromone and heuristic information are assigned in the edges of the logical graph. Each ant chooses its path according to the value of the pheromone and heuristic information on the edges. The paths the ants traveled are evaluated, and the pheromone information on each edge is updated according to the quality of the path it located. The pheromone on each edge is used as the final score of the similarity between the nodes. Experimental results on a number of real networks show that the algorithm improves the prediction accuracy while maintaining low time complexity. We also extend the method to solve the link prediction problem in networks with node attributes, and the extended method also can detect the missing or incomplete attributes of data. Our experimental results show that it can obtain higher quality results on the networks with node attributes than other algorithms.