基于位置的稀疏群体查询  

Geo-Socially Tenuous Group Query

作　　者：李娜[1,2] 朱怀杰 刘威 印鉴[1,2] LI Na;ZHU Huaijie;LIU Wei;YIN Jian(School of Data and Computer Science,Sun Yat-Sen University,Guangzhou 510006,China;Guangdong Key Laboratory of Big Data Analysis and Processing,Guangzhou 510006,China)

机构地区：[1]中山大学数据科学与计算机学院,广州510006 [2]广东省大数据分析与处理重点实验室,广州510006

出　　处：《计算机科学与探索》2021年第11期2151-2160,共10页Journal of Frontiers of Computer Science and Technology

基　　金：国家自然科学基金-广东联合基金(U1911203,U1811264);国家自然科学基金青年基金(61902438,61902439);广东省自然科学基金面上项目(2019A1515011704,2019A1515011159);中国博士后科学基金面上项目(2018M643307,2019M663237);高校青年教师培育项目(19lgpy214,19lgpy223);广东省基础与应用基础研究基金(2019B1515130001)。

摘　　要：在基于位置的社交网络中,找到一个特殊的群体/社区是非常重要的。现在的研究都集中于寻找群体之间关系紧密的密集子图。相对于紧密的群体/子图,对于稀疏群的研究少之又少。虽然现有工作开始研究稀疏群体查询问题,但是还没有研究基于位置的稀疏群体查询问题,而基于位置的服务在现实生活中有很多需求。因此,研究基于位置的稀疏群查询的问题变得有研究价值。基于位置的稀疏群体查询是为了找到一群用户,不仅用户之间满足一定的稀疏性(即用户之间的社交距离大于k),且最小化用户到查询位置的距离和。针对这个问题,首先提出基于c-邻居的基本处理算法(简称baseline),其主要利用存储的c-邻居信息以及距离剪枝来帮助快速获得查询结果。但是baseline算法的空间消耗太大,且在稀疏阈值参数k>c时查询效率不高。为了解决这些问题,进一步提出基于c-邻居和反向c-邻居的查询优化算法(简称ICN),不仅利用存储的c-邻居且利用反向c-邻居信息来处理参数k>c的情况,从而快速获得查询结果。实验结果和理论表明,提出的两种查询处理方法是有效的和正确的。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 cneighbor 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.

关 键 词：基于位置的社交网络图 稀疏群 c-邻居 距离剪枝 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]