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

Efficient search for the largest radius bounded k-core

作　　者：何佳 李继运 安云哲 HE Jia;LI Jiyun;AN Yunzhe(Dongan Engine Co.,Ltd,Harbin 150066,China;College of Computer Science,Shenyang Aerospace University,Shenyang 110136,China)

机构地区：[1]中国航发哈尔滨东安发动机有限公司,哈尔滨150066 [2]沈阳航空航天大学计算机学院,沈阳110136

出　　处：《沈阳航空航天大学学报》2024年第6期61-69,共9页Journal of Shenyang Aerospace University

基　　金：辽宁省教育厅重点攻关项目(项目编号:JYT19007)。

摘　　要：近年来,作为对现实世界关系的重要抽象手段,地理社会网络吸引了大批学者对其进行研究,其中半径有界k-core搜索聚合空间上邻近且相互之间关系密切的用户构成子图集合,在广告投放、社交关系分析等方面具有广泛应用价值。但各子图间高度的用户重叠降低了搜索效率,过多的集合数量造成了用户选择困难。为了解决这两个问题,提出了规模最大的半径有界k-core(largest radius bounded k-core,LRBK)搜索问题,旨在搜索满足空间和内聚性约束且规模最大的社区。结合已知最佳的半径有界k-core搜索算法RotC+,首先提出了一个基本算法,又结合有效的剪枝和优化策略提出了一个优化算法,最后在5个真实世界数据集上进行了大量实验。实验结果表明,优化算法对比基本算法的效率最高提升了约20倍。In recent years,geo-social networks have attracted a large number of scholars to study them as an important means of abstracting real-world relationships.Among them,the radius bounded k-core search aggregates users who are spatially neighboring and closely related to each other to form subgraph sets,which is widely used in multiple aspects such as advertisement placement and social relationship analysis.However,the high degree of user overlap among subgraphs reduces the search efficiency,and the excessive number of aggregates causes difficulties in user selection.To solve these two problems,the largest radius bounded k-core(LRBK)search problem was proposed,which aimed to search for communities with the largest size that satisfied spatial and cohesion constraints.Combining the known best radius bounded k-core search algorithm RotC+,the basic algorithm was first proposed.Then,an optimization algorithm was proposed by combining effective pruning and optimization strategies.Finally,extensive experiments on five real-world datasets were conducted.The experimental results show that the efficiency of the optimized algorithm is improved by up to about 20 times compared to the basic algorithm.

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

分 类 号：TP31[自动化与计算机技术—计算机软件与理论]