有向图上基于层次树索引的最大cycle truss社区搜索

作     者：宗传玉 张纯鹤 夏秀峰 ZONG Chuanyu;ZHANG Chunhe;XIA Xiufeng

作者机构：沈阳航空航天大学计算机学院沈阳110136 

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

出 版 物：《计算机应用》 (journal of Computer Applications)

年 卷 期：2024年第44卷第1期

页      码：190-198页

摘      要：社区搜索旨在从信息网络中找出包含用户查询顶点的高内聚连通子图,cycle truss是一种基于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社区的效率分别高出了一个和两个数量级。

主 题 词：有向图 社区搜索 cycle truss cycle三角形 层次等价 层次树索引 

学科分类：081203[081203] 08[工学] 0835[0835] 0812[工学-测绘类] 

D　O　I：10.11772/j.issn.1001-9081.2023010071

馆 藏 号：203125850...