Range constrained group query on attribute social graph

Abstract

The geo-social group query is to find a group of users for the query point based on location and social information. In this paper, we propose the range constrained group query (RCGQ) on attribute social graph, considering social information, spatial information, keyword information and user group size. We prove that RCGQ problem is NP-hard. For the query, we propose four methods, namely the combination-based group expansion method (COM), the single–multi group expansion method (S–M), the single–single group expansion method (S–S) and the multi–multi group expansion method (M–M). The first method is based on combination. The last three methods are based on social relations. COM uses combination to find user groups. The social relations are not used in the combinatorial process. S–M, S–S and M–M use the social relations to find user groups. Pruning strategies are proposed for the four methods. Finally, experiments demonstrate the efficiency of the proposed methods.