检索结果-南通市图书馆

检索条件"主题词=k桁架"

共 2 条记录，以下是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桁架子图最大化启发式搜索

来源：

同方学位论文库评论

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

一种在大型符号网络中挖掘最大符号θ团的方法

一种在大型符号网络中挖掘最大符号θ团的方法

引用

作者：吴艳萍浙江工商大学

学位级别：硕士

最大团问题,即寻找具有最大规模的团,其中团中的每个顶点都彼此相邻。该问题可以找到许多实际应用,并且以其对许多组合问题建模的能力而著称。然而,大多数现有研究都侧重于处理无符号图,即将每个连接视为相等的。在实际应用中,图的边通... 详细信息

最大团问题,即寻找具有最大规模的团,其中团中的每个顶点都彼此相邻。该问题可以找到许多实际应用,并且以其对许多组合问题建模的能力而著称。然而,大多数现有研究都侧重于处理无符号图,即将每个连接视为相等的。在实际应用中,图的边通常与符号信息相关联,即正边或负边。由于其特殊性质,针对符号图分析在近年来引起了极大的关注。本文首先分析了现有符号模型的缺点,然后提出了一种新的团模型,最大符号θ团。给定一个带符号的图G和一个子图S,设S中顶点u的正邻居数量为d（u）,S中顶点u的负邻居的数量是d（u）。本文说子图S是一个符号θ团,如果（4）4))S是一个团,（4）4)4)4))S中的每个顶点u满足d（u）-d（u）≥,并且（4）4)4)4)4)4))它是最大的,即包含最多数量的边。本文表明识别最大符号θ团的问题是NP难的。本文提出了新的修剪技术来减少搜索空间。此外,还开发了有效的搜索策略以扩展大型图。本文在8个真实世界数据集进行了综合实验,以证明所提方法的有效性和效益。在大型数据集中,基线算法在24小时内无法返回结果,而本文提出的查找最大符号θ团的算法可以在100秒内返回结果。基于最大符号θ团的定义,本文还提出了符号图上的符号（6）6),)桁架。一个子图是一个符号（6）6),)桁架,如果（4）4))每条边包含在至少6)6)个平衡三角形中,（4）4)4)4))每条边最多包含在个不平衡三角形中,并且（4）4)4)4)4)4))它是最大的,即,它的超图不满足先前的约束。不同于无符号图中传统的6)6)桁架模型,符号图中可能存在多个（6）6),)桁架。由于问题的NP难度,本文首先提出了一个贪心算法的框架。为了加速搜索,本文开发了新颖的修剪技术和搜索算法。最后,本文在真实的符号图上进行实验,以证明所提出的模型和技术的优点。实验表明,即使在大型符号网络中,本文设计算法只需不到100秒的时间即可返回结果。最后,本文针对已有研究提出了一些需要改进和提升的地方,这些方向也会成为以后科研的研究目标。总得来说,这些方面主要包括符号二部图分析方面和高效算法设计方面。

关键词：符号网络团结构 k桁架

来源：

同方学位论文库评论

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

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

共1页 << < 1 > >>

回到顶部

执行限定条件

欢迎您,

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

在线全文

在线全文

请选择保存的检索档案：

请选择收藏分类：

通借通还

欢迎您,

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

在线全文

在线全文

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：