有向图上的最大truss社区搜索研究与应用

作     者：张纯鹤 

作者单位：沈阳航空航天大学 

学位级别：硕士

导师姓名：宗传玉;颜仕柱

授予年度：2023年

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 070104[理学-应用数学] 0701[理学-数学] 

主      题：社区搜索 truss 有向图 cycle三角形 flow三角形 

摘      要：社区搜索问题是指在给定的图数据中,找到所有包含查询顶点的密集连接的子图。truss是一种基于三角形结构的社区搜索模型,被用于搜索k-truss社区。有向图上最大truss社区搜索研究工作在实际应用中具有广泛的应用价值,然而在有向图上,现有的基于索引的truss社区搜索方法存在索引空间大、搜索效率低、社区内聚性低的缺点。为了解决这一问题,文中研究了在有向图上基于truss模型的最大社区搜索问题,研究内容分为最大kc-cycle truss社区搜索和最大kf-flow truss社区搜索,可以帮助揭示复杂网络中的社区结构,对于理解网络的功能、组织和演化过程具有重要意义。首先解决了有向图上的最大kc-cycle truss社区搜索问题,kc-cycle truss社区是一种基于cycle三角形的社区结构,文中设计一种cycle truss分解算法,并提出了两个重要的概念:cycle三角形连通和kc-层次等价。基于kc-层次等价设计了层次树索引Tree CIndex和表结构索引Super Table,并基于这两个新的索引,设计了两种高效的cycle truss社区搜索算法,与传统的对有向图进行大量耗时访问的社区搜索算法不同,文中提出的cycle truss社区搜索算法仅需访问层次树索引Tree CIndex与表结构索引Super Table即可搜索出最大cycle truss社区,提高了社区搜索效率。接着解决了有向图上的最大kf-flow truss社区搜索问题,kf-flow truss模型是一种基于flow三角形的社区结构,文中提出了社区内查询顶点能够访问任意其他顶点的概念,从而提高社区的内聚性,然后设计了一种基于flow truss分解的索引Flow Index,并设计了基于Flow Index的社区搜索算法。文中提出的算法通过剪枝的策略,减少了访问与社区不相关的边的次数,提升了搜索效率。在四个真实数据集上将文中提出的算法与已有的基于Truss Index与Equi Truss的社区搜索算法进行了比较,实验结果表明,Tree CIndex与Super Table比Truss Index与Equi Truss的索引占用空间节省至少41.5%,索引构建的时间节省8.2%至98.3%,且搜索最大kc-cycle truss社区的效率提升了一至两个数量级。Flow Index算法比Truss Index算法搜索最大kf-flow truss社区的效率提升了一个数量级。