基于truss模型的社区查询算法研究

发布时间：2022-12-11 04:03

　　基于truss模型的社区查询问题是根据给定的查询结点q以及参数k,返回包含查询结点的所有k-truss社区。随着信息技术的发展,网络用户数量的爆发式增长,社区查询问题在学术领域开始被广泛关注,而因为truss模型可以很好的模拟现实世界中网络社区的特性,因此可以通过truss模型解决社区查询的问题。然而,目前现有的社区查询方法存在因冗余操作导致查询效率低的问题。本文针对基于truss模型的社区查询问题进行研究,具体研究内容如下。首先,在创建索引阶段,提出一种基于truss等价的索引构建方法。该方法直接在原始图中将边界边所在的超级结点标记到自身的supnode属性中,作为创建超级边的前提,进而创建索引。与现有算法相比,该方法无需对原始边进行边trussness值相等的集合划分,在创建超级边时避免了对超级结点的冗余遍历操作,从而能够快速完成超级边的创建,加速整个索引的创建过程。其次,在k-truss社区查找阶段,提出一种高效的k-truss社区查询方法。该方法在已有索引结构的基础上,通过使用基于散列表的快速定位技术,在不丢失原始边的前提下,可以快速定位到查询结点所在的超级结点集合,并设计了相... 

【文章页数】：56 页

【学位级别】：硕士

【文章目录】：
摘要
Abstract
第1章 绪论
    1.1 课题的研究背景与意义
    1.2 研究现状
    1.3 研究内容
    1.4 本文结构
第2章 基础知识概述
    2.1 基础知识
    2.2 社区结构
    2.3 truss等价
    2.4 基于索引的社区查询算法
        2.4.1 基于TCP-Index的社区查询算法
        2.4.2 基于EquiTruss的社区查询算法
    2.5 本章小结
第3章 基于truss等价的索引构建
    3.1 问题分析
    3.2 基于Truss等价的索引构建
        3.2.1 ETCI算法思想
        3.2.2 ETCI算法描述
        3.2.3 ETCI算法分析
    3.3 本章小结
第4章 基于索引的社区查询算法
    4.1 问题分析
    4.2 KTCS算法思想
    4.3 KTCS算法描述
    4.4 KTCS算法分析
    4.5 本章小结
第5章 实验及结果分析
    5.1 引言
    5.2 实验环境
        5.2.1 软硬件配置
        5.2.2 数据集
        5.2.3 评价指标
    5.3 性能分析与比较
        5.3.1 索引构建时间比较
        5.3.2 社区查询时间比较
    5.4 本章小结
结论
参考文献
攻读硕士学位期间承担的科研任务与主要成果
致谢


【参考文献】：
期刊论文
[1]路网环境下访问序列受限的多标签路线查询算法[J]. 张金增,文洁,孟小峰.  计算机学报. 2012(11)



本文编号：3718105