基于k-truss的紧密社区查询算法研究

发布时间：2024-03-09 12:47

　　基于k-truss的紧密社区查询问题是根据给定的查询结点集合,返回一个包含所有查询结点且联系最紧密的社区。紧密社区所属的k-truss社区对应k值越大,社区内冗余结点越少,则紧密社区的质量越高,内部结点之间的联系越紧密。本文针对查找基于k-truss的高质量紧密社区问题进行研究,具体研究内容如下。首先,通过对现有算法进行分析,发现现有算法在第一阶段查找包含所有查询结点且k值尽可能大的初始k-truss社区时,扩张过程中加入过多无效结点,导致得到的初始k-truss社区k值偏小;在第二阶段删除初始k-truss社区中受“搭便车效应”影响的冗余结点时,现有批量删除策略并不能最大化的去除冗余结点,导致最终得到的紧密社区规模偏大。其次,针对已有算法第一阶段初始k-truss社区k值偏小的问题,提出基于边的Steiner Tree扩张策略,该策略通过Steiner Tree中两个邻接结点确定候选结点。与已有扩张策略相比,本文提出的改进策略对加入扩张子图的候选结点要求更为严格,在初始社区规模存在上限的情况下,能够加入更多有效结点,可得到k值更大的初始k-truss社区。再次,针对已有算法第二阶段删...

【文章页数】：57 页

【学位级别】：硕士

【文章目录】：
摘要
Abstract
第1章 绪论
    1.1 课题的研究背景与意义
    1.2 研究现状
    1.3 研究内容
    1.4 本文结构
第2章 基础知识概述
    2.1 基础知识
        2.1.1 搭便车效应
        2.1.2 紧密社区问题定义
    2.2 紧密社区查询的基本算法
        2.2.0 LCTC算法
        2.2.1 Basic算法
        2.2.2 BulkBasic算法
    2.3 本章小结
第3章 基于SteinerTree的优化策略
    3.1 问题分析
    3.2 基于边的扩张策略
        3.2.1 算法思想
        3.2.2 算法描述
        3.2.3 算法分析
    3.3 本章小结
第4章 基于批量删除的优化策略
    4.1 问题分析
        4.1.1 单结点删除策略
        4.1.2 批量结点删除策略
    4.2 BulkDelete++算法
        4.2.1 算法思想
        4.2.2 算法描述
    4.3 本章小结
第5章 实验及结果分析
    5.1 引言
    5.2 实验环境
        5.2.1 软硬件配置
        5.2.2 数据集
        5.2.3 评价指标
    5.3 性能分析与比较
        5.3.1 扩张策略效果比较
        5.3.2 删除策略效果比较
    5.4 本章小结
结论
参考文献
致谢



本文编号：3923443