To read the full version of this content please select one of the options below:

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

Yuzhong Chen (Fujian Key Laboratory of Scientific and Engineering Computing, Fuzhou University, Fuzhou, China)
Yang Yu (Fujian Key Laboratory of Scientific and Engineering Computing, Fuzhou University, Fuzhou, China)
Guolong Chen (Fujian Key Laboratory of Scientific and Engineering Computing, Fuzhou University, Fuzhou, China)

Engineering Computations

ISSN: 0264-4401

Article publication date: 28 October 2014

Downloads
171

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.

Keywords

Acknowledgements

The authors would like to thank the support of the Technology Innovation Platform Project of Fujian Province under Grant No. 2009J10027, the Project of Fujian Education Committee under Grant No. JA09002, the Project of Ministry of Education under Grant No. 210110, and the Project of Fujian Education Committee under Grant No. JK2012003.

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

Publisher

:

Emerald Group Publishing Limited

Copyright © 2014, Emerald Group Publishing Limited