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

Maximum cycle truss community search based on hierarchical tree index on directed graphs

作　　者：宗传玉 张纯鹤 夏秀峰 ZONG Chuanyu;ZHANG Chunhe;XIA Xiufeng(School of Computer Science,Shenyang Aerospace University,Shenyang Liaoning 110136,China)

机构地区：[1]沈阳航空航天大学计算机学院,沈阳110136

出　　处：《计算机应用》2024年第1期190-198,共9页journal of Computer Applications

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

摘　　要：社区搜索旨在从信息网络中找出包含用户查询顶点的高内聚连通子图,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社区的效率分别高出了一个和两个数量级。Community search aims to find highly cohesive connected subgraphs containing user query vertices in information networks.Cycle truss is a community search model based on cycle triangle.However,the existing index-based cycle truss community search methods suffer from the drawbacks of large index space,low search efficiency,and low community cohesion.A maximum cycle truss community search method based on hierarchical tree index was proposed to address this issue.Firstly,a k-cycle truss decomposition algorithm was proposed,and two important concepts,cycle triangle connectivity and k-level equivalence were introduced.Based on k-level equivalence,the hierarchical tree index TreeCIndex and the table index SuperTable were designed.On this basis,two efficient cycle truss community search algorithms were proposed.The proposed algorithms were compared with existing community search algorithms based on TrussIndex and EquiTruss on four real datasets.The experimental results show that the space consumptions of TreeCIndex and SuperTable are at least 41.5%lower and the index construction time is 8.2%to 98.3%lower compared to TrussIndex and EquiTruss;furthermore,the efficiencies of searching for maximum cycle truss communities is increased by one and two orders of magnitude.

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

分 类 号：TP391.1[自动化与计算机技术—计算机应用技术]