高效搜索规模最大的半径有界k-core

摘要

近年来，作为对现实世界关系的重要抽象手段，地理社会网络吸引了大批学者对其进行研究，其中半径有界k-core搜索聚合空间上邻近且相互之间关系密切的用户构成子图集合，在广告投放、社交关系分析等方面具有广泛应用价值。但各子图间高度的用户重叠降低了搜索效率，过多的集合数量造成了用户选择困难。为了解决这两个问题，提出了规模最大的半径有界k-core(largest radius bounded k-core,LRBK)搜索问题，旨在搜索满足空间和内聚性约束且规模最大的社区。结合已知最佳的半径有界k-core搜索算法RotC+，首先提出了一个基本算法，又结合有效的剪枝和优化策略提出了一个优化算法，最后在5个真实世界数据集上进行了大量实验。实验结果表明，优化算法对比基本算法的效率最高提升了约20倍。

关键词

地理社会网络 / 半径有界k-core / 规模最大 / 内聚性 / 空间约束