社区搜索用于返回包含给定查询结点且符合查询条件的密集连通子图.目前,大部分已有社区搜索方法主要关注社区的结构,没有考虑到特定应用中资源受限的情况,且忽略了社区的属性特征,无法满足用户对社区搜索的个性化要求.针对该问题,本文...社区搜索用于返回包含给定查询结点且符合查询条件的密集连通子图.目前,大部分已有社区搜索方法主要关注社区的结构,没有考虑到特定应用中资源受限的情况,且忽略了社区的属性特征,无法满足用户对社区搜索的个性化要求.针对该问题,本文提出了规模受限的影响力社区搜索(Size-Constrained Influential Community search,SCIC),设计了基于深度优先搜索的基础算法,在此基础上进一步提出了基于结点预处理、剪枝规则和贪心策略的优化算法,用于减少冗余计算,加速枚举过程.在10个不同规模的数据集上进行实验,实验结果表明基础算法在搜索获得的社区规模和影响力上均优于已有算法,同时,本文提出的优化算法能够显著提升搜索效率,将响应时间缩减至基础算法的1%.展开更多
文摘社区搜索用于返回包含给定查询结点且符合查询条件的密集连通子图.目前,大部分已有社区搜索方法主要关注社区的结构,没有考虑到特定应用中资源受限的情况,且忽略了社区的属性特征,无法满足用户对社区搜索的个性化要求.针对该问题,本文提出了规模受限的影响力社区搜索(Size-Constrained Influential Community search,SCIC),设计了基于深度优先搜索的基础算法,在此基础上进一步提出了基于结点预处理、剪枝规则和贪心策略的优化算法,用于减少冗余计算,加速枚举过程.在10个不同规模的数据集上进行实验,实验结果表明基础算法在搜索获得的社区规模和影响力上均优于已有算法,同时,本文提出的优化算法能够显著提升搜索效率,将响应时间缩减至基础算法的1%.