导　　师： 黄战

授予学位： 硕士

作　　者： (）;

机构地区： 暨南大学

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

关 键 词： 社区搜索 空间最优 主题感知

领　　域： []