Shortest distance estimation in large scale graphs: A landmark selection strategy based on multi-objective PSO

Abstract

Purpose

Shortest distance query between a pair of nodes in a graph is a classical problem with a wide variety of applications. Exact methods for this problem are infeasible for large-scale graphs such as social networks with hundreds of millions of users and links due to their high complexity of time and space. The purpose of this paper is to propose a novel landmark selection strategy which can estimate the shortest distances in large-scale graphs and clarify the efficiency and accuracy of the proposed strategy in comparison with currently used strategies.

Design/methodology/approach

Different from existing strategies, the landmark selection problem is regarded as a binary combinational optimization problem consisting of two optimization objectives and one constraint. Further, the original binary combinational optimization problem with constraints is transformed to a proper form of optimization objectives without any additional constraints and the equivalence of solutions is proved. Finally the solution of the optimization problem is performed with a modified multi-objective particle swarm optimization (MOPSO) integrating the mutation operator and crossover operator of genetic algorithm.

Findings

Four real networks of large scale are used as data sets to carry out the experiments and the experiment results show that the proposed strategy improves both of the accuracy and time efficiency to perform shortest distance estimation in large scale graph compared to other currently used strategies.

Originality/value

This paper proposes a novel landmark selection strategy which regards the landmark selection problem as a binary combinational optimization problem. The original binary combinational optimization problem with constraints is transformed to a proper form of optimization objectives without constraints and the equivalence of these two optimization problems is proved. This novel strategy also utilizes a modified MOPSO integrating the mutation operator and crossover operator of genetic algorithm.

Citation

Chen, Y., Yu, Y. and Chen, G. (2014), "Shortest distance estimation in large scale graphs: A landmark selection strategy based on multi-objective PSO", Engineering Computations, Vol. 31 No. 8, pp. 1635-1647. https://doi.org/10.1108/EC-11-2012-0286