-
题名基于邻域k-核的社区模型与查询算法
- 1
-
-
作者
张琦
程苗苗
李荣华
王国仁
-
机构
北京理工大学计算机学院
-
出处
《软件学报》
EI
CSCD
北大核心
2024年第3期1051-1073,共23页
-
基金
国家重点研发计划(2021VEB3301301)
国家自然科学基金(62072034,U2241211)
中国博士后科学基金(2023M730251,2023TQ0026)。
-
文摘
现实生活中的网络通常存在社区结构,社区查询是图数据挖掘的基本任务.现有研究工作提出了多种模型来识别网络中的社区,如基于k-核的模型和基于k-truss的模型.然而,这些模型通常只限制社区内节点或边的邻居数量,忽略了邻居之间的关系,即节点的邻域结构,从而导致社区内节点的局部稠密性较低.针对这一问题,将节点的邻域结构信息融入k-核稠密子图中,提出一种基于邻域连通k-核的社区模型,并定义了社区的稠密度.基于这一新模型,研究了最稠密单社区查询问题,即返回包含查询节点集且具有最高稠密度的社区.在现实生活图数据中,一组查询节点可能会分布在多个不相交的社区中.为此,进一步研究了基于稠密度阈值的多社区查询问题,即返回包含查询节点集的多个社区,且每个社区的稠密度不低于用户指定的阈值.针对最稠密单社区查询和基于稠密度阈值的多社区查询问题,首先定义了边稠密度的概念,并提出了基于边稠密度的基线算法.为了提高查询效率,设计了索引树和改进索引树结构,能够支持在多项式时间内输出结果.通过与基线算法在多组数据集上的对比,验证了基于邻域连通k-核的社区模型的有效性和所提出查询算法的效率.
-
关键词
社区搜索
邻域结构
k-核子图
-
Keywords
community search
neighborhood structure
k-core subgraph
-
分类号
TP311
[自动化与计算机技术—计算机软件与理论]
-
