检索结果-南通市图书馆

计算机工程与科学 2022年第2期44卷 306-311页

作者：罗晓霞王佳罗香玉李嘉楠西安科技大学计算机科学与技术学院陕西西安710054

随着图规模的急剧增长,对动态图进行实时处理的需求日益增加。大多现有的算法针对静态图划分是有效的,直接用其处理动态图会带来较大的通信开销。针对该问题,提出一种基于GN算法的动态图划分方法。首先收集一段时间内加入动态图中的顶点... 详细信息

随着图规模的急剧增长,对动态图进行实时处理的需求日益增加。大多现有的算法针对静态图划分是有效的,直接用其处理动态图会带来较大的通信开销。针对该问题,提出一种基于GN算法的动态图划分方法。首先收集一段时间内加入动态图中的顶点;然后,利用GN算法对这些新加入的顶点进行预划分,产生若干个内部联系紧密的社区;最后,将预划分产生的社区结果插入到已经划分好的当前图中。实验从交叉边数和负载均衡度两方面将该方法与传统流式划分方法进行比较,结果表明,在公开数据集上,该方法的交叉边数降低了13%,负载均衡度减少了42.3%。由此可见,该方法的划分质量明显优于传统的流式划分方法。

关键词：动态图划分 GN算法交叉边负载均衡度

来源：

维普期刊数据库

同方期刊数据库评论

在线全文

学校读者我要写书评

暂无评论

具有指定路-Hamilton边数的一类极图

引用

中北大学学报（自然科学版） 2006年第2期27卷 95-96页

作者：孟巍李胜家山西大学数学科学学院山西太原030006

无向图G=(V,E)的一条边e∈E被称为是路-H am ilton边,如果存在G中的一条H am ilton-路包含e.本文描述了一类具有给定路-H am ilton边数的极图,并证明了对任意给定的一个自然数a,恰好具有a+1个顶点和a条路-H am ilton边的无向图的最大边... 详细信息

无向图G=(V,E)的一条边e∈E被称为是路-H am ilton边,如果存在G中的一条H am ilton-路包含e.本文描述了一类具有给定路-H am ilton边数的极图,并证明了对任意给定的一个自然数a,恰好具有a+1个顶点和a条路-H am ilton边的无向图的最大边数为[(a2+3)/4].

关键词： Hamilton-路路-Hamilton边交叉边

来源：

维普期刊数据库

同方期刊数据库评论

在线全文

学校读者我要写书评

暂无评论

大图结构特征对划分效果的影响

引用

计算机应用 2018年第1期38卷 1-5页

作者：罗晓霞司丰玮罗香玉西安科技大学计算机科学与技术学院西安710054

针对大图结构特征如何影响划分效果这一问题,提出一种通过顶点度分布特征来描述大图结构特征的方法。首先,基于真实的图数据产生若干顶点数和边数相同、但结构特征不同的仿真数据集,通过实验计算真实图与仿真图之间的相似度,证明该方法... 详细信息

针对大图结构特征如何影响划分效果这一问题,提出一种通过顶点度分布特征来描述大图结构特征的方法。首先,基于真实的图数据产生若干顶点数和边数相同、但结构特征不同的仿真数据集,通过实验计算真实图与仿真图之间的相似度,证明该方法对描述真实大图结构特征的有效性。然后,通过Hash和点对交换划分算法,验证图结构特征与划分效果之间的关系。当点对交换划分算法执行到5万次时,划分一个有6301个顶点和20777条边的真实图其交叉边数比Hash划分算法降低了54.32%,划分仿真图数据集中结构特征差异明显的两个图时,交叉边数分别为6 233和316。实验结果表明,点对交换划分算法能够减少交叉边数,图的顶点度分布差异越大,划分后交叉边数越少,划分效果越好,因此大图结构特征影响其划分效果,这为建立图的结构特征与划分效果之间的关系模型研究奠定了基础。

关键词：大图分布式处理大图划分图结构特征负载均衡交叉边

来源：

维普期刊数据库

同方期刊数据库评论

在线全文

学校读者我要写书评

暂无评论

基于社区发现的动态图划分方法研究

基于社区发现的动态图划分方法研究

引用

作者：王佳西安科技大学

学位级别：硕士

随着网络的快速发展,以网络为载体的信息量迅速增长,使得图的规模也随之扩大。由于大规模图数据无法使用单机环境进行处理,因此分布式图计算应运而生。分布式图计算需要将图数据合理地分布到每个节点,对图进行合理划分是实现分布式图计... 详细信息

随着网络的快速发展,以网络为载体的信息量迅速增长,使得图的规模也随之扩大。由于大规模图数据无法使用单机环境进行处理,因此分布式图计算应运而生。分布式图计算需要将图数据合理地分布到每个节点,对图进行合理划分是实现分布式图计算的前提。现实世界的图处于不断的动态演化之中,如何对动态图进行合理划分是当前的一个研究热点。针对动态图划分问题,本文的主要研究内容如下:首先,研究新增图社区性对动态图划分质量的影响。将给定数量的动态图中更新的顶点看成一张新增图,采用不同的社区发现算法对其进行划分,得到模块度不同的子图。通过实验,将使用不同社区发现算法产生的划分结果进行对比,结果表明,新增图划分后的模块度越大,社区性越强,对动态图的划分质量越好。由此证明,新增图的社区性强弱影响动态图的划分质量,为下一步设计动态图划分方法奠定了基础。其次,针对动态图划分问题,提出了一种基于社区发现的划分方法。其基本思想是收集给定数量的图更新操作,对于顶点的加入操作,利用社区发现算法对这些顶点进行预划分,将预划分产生的社区结果插入到已经划分好的当前图中,其余的顶点删除、边的加入/删除操作,分别根据收集的信息依次更新。在公开数据集上进行实验,从交叉边数和负载均衡度两方面将本方法与传统流式划分方法进行比较,结果表明,本方法的交叉边数降低了 13%,负载均衡度减少了 42.3%。由此可得,本方法的划分质量明显优于传统的流式划分方法,能够对动态图进行高效处理,降低子图之间的通信开销。最后,为了对动态图的划分结果进一步优化,使划分后的子图内部联系紧密,子图之间耦合度低,又避免对整个动态图重新划分,提出了一种基于模拟退火的动态图顶点更新方法。传统顶点更新方法仅根据相邻节点判断顶点位置是否转移,会造成局部最优。本方法在传统顶点更新方法基础上加入了随机扰动的因素,通过对能量函数、更新概率、冷却计划的设计,避免顶点更新陷入局部最优的后果,使得各个子图之间的交叉边数最少,达到全局最优的效果。通过实验,将本方法与传统的顶点更新方法和基于社区发现的动态图划分方法进行比较,结果表明,本方法比传统顶点更新方法交叉边数降低了12.4%,负载均衡度减少了11.7%,比基于社区发现的动态图划分方法交叉边数降低了9.3%,负载均衡度减少了2.2%,由此可得,优化后的方法只通过部分顶点位置更新实现对动态图的划分,能够有效避免对整个动态图进行重新划分,提高了图的划分质量。

关键词：动态图划分社区发现交叉边负载均衡模拟退火

来源：

同方学位论文库评论

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

欢迎您,

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

在线全文

在线全文

在线全文

在线全文

请选择保存的检索档案：

请选择收藏分类：

通借通还

欢迎您,

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

在线全文

在线全文

在线全文

在线全文

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：