计算机应用

作者：宗传玉, 张纯鹤, 夏秀峰

单位：沈阳航空航天大学 计算机学院，沈阳 110136

关键词：有向图,社区搜索,cycletruss,cycle三角形,层次等价,层次树索引

基金：国家自然科学基金资助项目(61802268);辽宁省自然科学基金资助项目(2022-MS-303)

社区搜索旨在从信息网络中找出包含用户查询顶点的高内聚连通子图，cycletruss是一种基于cycle三角形的社区搜索模型，而现有的基于索引的cycle truss社区搜索方法存在索引空间大、搜索效率低、社区内聚性低的缺点。为了解决这一问题，提出一种基于层次树索引的最大cycle truss社区搜索方法。首先，提出了k-cycle truss分解算法，并引入了两个重要的概念：cycle三角连通与k-层次等价。基于k-层次等价设计了层次树索引TreeCIndex与表结构索引SuperTable，在此基础上，并基于这两个新的索引，提出了两个高效的cycle truss社区搜索算法。在4个真实数据集上与已有的基于TrussIndex与EquiTruss的社区搜索算法进行了比较，实验结果表明，TreeCIndex与SuperTable比TrussIndex与EquiTruss节省至少41.5%的空间，索引构建的时间节省8.2%至98.3%，且搜索最大cycle truss社区的效率分别高出了一个和两个数量级。

来源：2024年第1期

《计算机应用》期刊编辑部

查看计算机应用杂志2024年第1期