title: Deployment of check-in nodes in complex networks.
abstract: In many real complex networks such as the city road networks and highway networks, vehicles often have to pass through some specially functioned nodes to receive check-in like services such as gas supplement at gas stations. Based on existing network structures, to guarantee every shortest path including at least a check-in node, the location selection of all check-in nodes is very essential and important to make vehicles to easily visit these check-in nodes, and it is still remains an open problem in complex network studies. In this work, we aim to find possible solutions for this problem. We first convert it into a set cover problem which is NP-complete and propose to employ the greedy algorithm to achieve an approximate result. Inspired by heuristic information of network structure, we discuss other four check-in node location deployment methods including high betweenness first (HBF), high degree first (HDF), random and low degree first (LDF). Finally, we compose extensive simulations in classical scale-free networks, random networks and real network models, and the results can well confirm the effectiveness of the greedy algorithm. This work has potential applications into many real networks.
authors.affiliation: School of Cyber Engineering, Xidian University, Xi'an, Shaanxi 710071, China.
authors.forename: Zhong-Yuan
authors.initials: ZY
authors.lastname: Jiang
authors.affiliation: School of Cyber Engineering, Xidian University, Xi'an, Shaanxi 710071, China.|School of Computer Science and Technology, Xidian University, Xi'an, Shaanxi 710071, China.
authors.forename: Jian-Feng
authors.initials: JF
authors.lastname: Ma