核分解最优参数选取问题的研究

发布时间：2024-02-14 18:47

　　图模型被广泛应用于表示实体之间的关系,并衍生了大量实际应用。随着信息技术的高速发展,人们正在众多领域中采集越来越大且越来越多的图数据。在计算机科学、生物学、社会科学和脑科学等领域,理解网络是极为重要的。然而,由于网络的庞大规模,大多数网络分析算法已经不能正常工作。另一方面,内聚子图挖掘算法既能揭示图的关键性质,又能有效地在海量图上进行计算。k-core模型是稠密子图挖掘领域中研究最多的模型。k-core的模式和它的层次分解被广泛应用于许多领域,例如社会学,万维网和生物学。相关研究的算法通常需要一个输入参数k,但却没有手工选取参数以外的确定方式。在本文中,给定一张图和一个社区评分标准,需快速找到最佳的k值令k-core set或k-core的评分最高。这个问题极具挑战性,因为现有各种各样的社区评分指标并且它们在大型数据集上的计算代价高昂。通过精心设计的顶点排序技巧,本文设计了计算最优的k值的算法,算法具有最优的时间和空间复杂度,并且能够使用于大多数社区评分指标。本文设计的算法也能够计算每个k-core和每个k-core set的评分,并且能够帮助其他k-core相关问题的算法设计。在10...

【文章页数】：63 页

【学位级别】：硕士

【文章目录】：
摘要
Abstract
第一章 绪论
    1.1 研究背景
    1.2 相关工作
    1.3 主要内容
    1.4 组织结构
第二章 基本概念
    2.1 图模型
    2.2 k-Core及核分解
    2.3 社区评分指标
    2.4 问题定义
    2.5 常用符号列表
第三章 最优k-Core Set选取
    3.1 基线算法
    3.2 最优邻居查询的顶点排序
    3.3 改进算法
    3.4 三角形与三联体的相关计算
第四章 最优k-Core社区选取
    4.1 k-Core层次结构
    4.2 基线算法
    4.3 改进算法
第五章 实验评估
    5.1 实验背景
    5.2 不同k的社区质量
    5.3 高分k-Core案例分析
    5.4 算法运行时间
    5.5 其他问题的应用
第六章 总结与展望
    6.1 工作总结
    6.2 未来展望
致谢
硕士期间学术成果
参考文献



本文编号：3898434