检索结果-南通市图书馆

检索条件"主题词=子图最大化"

共 1 条记录，以下是1-10 订阅

全选清除本页清除全部题录导出标记到"检索档案"

详细简洁

排序：

基于k核与k桁架的稠密子图最大化算法研究

基于k核与k桁架的稠密子图最大化算法研究

引用

作者：孙新天津大学

学位级别：硕士

稠密子图挖掘是图分析领域的一个重要环节,人们可以利用稠密子图来分析图的连通性、中心性、鲁棒性等重要性质。在众多稠密子图模型中,k核(k-core)和k桁架(k-truss)模型是目前的研究热点,这主要得益于它们可以在多项式时间内将图降解为... 详细信息

稠密子图挖掘是图分析领域的一个重要环节,人们可以利用稠密子图来分析图的连通性、中心性、鲁棒性等重要性质。在众多稠密子图模型中,k核(k-core)和k桁架(k-truss)模型是目前的研究热点,这主要得益于它们可以在多项式时间内将图降解为层次结构。近年来,稠密子图最大化问题在现实生活中展现出了广泛的应用前景,譬如:增强社交网络的活跃度,识别军事网络中缺失的防御结点或链接,提高P2P(Peer-to-Peer)网络中资源交换的稳定性等。其中,k-core子图最大化问题主要是向图中插入一些有益的新边来增广k-core子图,然而已有启发式方法存在效率低的问题,难以在大规模图数据上应用;k-truss最大化问题目前尚未被研究过,然而我们发现该问题在很多现实应用中非常具有价值。因此,本文针对上述问题围绕k-core和k-truss这两个稠密图模型展开研究。首先,本文针对k-core最大化算法效率低的问题,提出了一种基于图划分和快速搜索策略的新算法命名为FactCM+。该算法的核心思想为:首先使用图划分算法将图中的重要节点划分为不同的连通分量,然后独立考虑每个分量,以完全转换和部分转换两种方式将不同的分层顶点转换到k-core中,最后针对不同分量设计动态规划算法来合理选择最合适的增广新边。进一步,本文从理论上给出了 FactCM+算法的时间复杂度为O(n(m+b)),比时间复杂度为O(bmn2)的当前最好算法EKC具有明显优势,其中n、m、b分别表示图中的顶点数、边数和插入边的数量。最后在十一个大规模图数据集上进行实验比较,结果表明本文算法FactCM+在大图上的运行速度比已有最好算法EKC快74,000倍,同时求得的插入边也能更好地增广k-core。进而,本文首次提出并研究了 k-truss最大化问题。由于该问题目前尚未被研究过,所以本文首先从两个真实世界应用(包含飞机航线网络连接性增强和社交网络参与度提升)中揭示了该问题具有丰富的应用场景和价值。接下来从理论上证明了 k-truss最大化是NP难问题,并继续分析了 k-truss新来者函数不具有子模性,进而设计了高效的启发式算法。本文首先识别图结构中高效的候选边,提出一种使用单边插入的贪心算法,进而通过精简候选边来提升效率。最后,提出一种基于分量的动态规划算法,它可以平衡预算分配并向所有分量同时插入多条边。通过在九个大规模真实世界图数据上的实验验证了本文提出算法的有效性、高效性和实用性。本文通过上述两个研究提升了目前子图最大化问题的求解效率、增广了其应用范围和解决方案,也为其他稠密子图最大化算法的设计与应用提供了一条新途径。

关键词： k核 k桁架子图最大化启发式搜索

来源：

同方学位论文库评论

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

全选清除本页清除全部题录导出标记到“检索档案”

共1页 << < 1 > >>

回到顶部

执行限定条件

欢迎您,

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

在线全文

请选择保存的检索档案：

请选择收藏分类：

通借通还

欢迎您,

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

在线全文

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：