空间最优的主题感知社区搜索算法研究

发布时间：2021-01-09 06:54

　　属性网络近年来非常普遍,例如社交网络和知识图谱,它们与大量的文档信息（例如,推文和维基页面）和位置信息（例如check-in数据）相关联。然而,这种大型网络所蕴含的丰富属性信息给社区搜索问题带来了巨大的挑战,其中主要原因在于其需要同时考虑大量数据下的可延展性和在文本、空间信息上的双重约束。目前的研究旨在搜索结构紧密的子图作为社交关系密切的社区,但这样通常会缺乏对表示主题兴趣的关键词或表示位置临近的空间距离的考虑,导致社区搜索问题不能具有更广泛的应用价值。本文提出空间最优的主题感知社区（TASOC）搜索问题,该问题旨在搜索包含以下特性的社区:i)结构紧密性:社区中的成员结构上紧密相连,ii)主题涵盖:社区中顶点属性包含一系列给出的主题关键词,并且,iii)空间最优性:社区的直径最小化。然而,空间最优的主题感知社区搜索问题是一个NP-hard问题。为了解决在大型属性图上的TASOC搜索问题,本文提出4个近似算法,分别是GKC、GRID、BIGRID和GRID+,它们均利用一种基于正方形设计的技术。这些提出的算法均更高效于基于现有方法修改成的基本算法。本文还提出一个以提出的最好近似算法为基础... 

【文章来源】：暨南大学广东省 211工程院校

【文章页数】：53 页

【学位级别】：硕士

【部分图文】：

TASOC示例


本文编号：2966177