Geo-Socially Tenuous Group Query

Abstract

In location-based social networks, it is important to find a specific group/community. Current research has focused on finding dense subgraphs of close relationships between groups. Compared with the dense group/subgraph, there are few studies on tenuous groups. Although the existing work has begun to study the tenuous population query, geo-socially tenuous group query has not been studied, and location-based services have a lot of demands in real life. Therefore, it becomes valuable to study the geo-socially tenuous group query. Geo-socially tenuous group query is to find a group of users, which not only satisfies a certain sparsity between users (i.e. the social distance between users is greater than [k]), but also minimizes the distance between users and the query location. To address this problem, this paper first proposes a basic processing algorithm based on c-neighbor (baseline), which uses stored c-neighbor information and distance pruning to help obtain query results quickly. However, the basic processing algorithm based on c-neighbor (baseline) uses too much space and the query efficiency is not high when parameter [k>c]. To solve these problems, a query optimization algorithm based on c-neighbor and reverse c-neighbor (ICN) is proposed, which not only utilizes stored c-neighbor information but also reverse c-neighbor information to effectively filter out invalid users and obtain query results quickly. The experimental results and theory show that the proposed two query processing methods are effective and correct.

Keywords

• location-based social network graph
• tenuous group
• c-neighbor
• distance pruning