基于位置的稀疏群体查询

摘要：

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

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

所属期刊栏目：15

分类号：TP393(计算技术、计算机技术)

资助基金：国家自然科学基金-广东联合基金;国家自然科学基金青年基金;广东省自然科学基金面上项目;中国博士后科学基金面上项目;高校青年教师培育项目;广东省基础与应用基础研究基金

在线出版日期：2021-11-17（万方平台首次上网日期，不代表论文的发表时间）

页数：共10页

页码：2151-2160