图划分

摘要： 最大团问题是一个经典的组合优化问题,在蛋白质功能推测、竞胜标确定、视频对象分割等领域有广泛的应用。随着图例规模的增大,最大团问题求解难度增加,常规图例最大团求解算法已逐渐被大规模图例最大团求解算法取代。介绍求解大规模图例最大团问题的技术支撑点,重点总结基于大规模图例的最大团问题算法,并在大数据计算背景下对融合单层图划分方法和多层图划分方法的MapReduce框架和Spark框架进行优缺点分析。此外,比较k-core方法与k-community方法的应用场景,从算法分类的角度总结不同类型算法的优缺点,对求解大规模图例最大团问题的确定型算法进行梳理,并对代表性的求解算法在公开数据集中的表现进行对比分析。基于分析结果,指出不同算法在求解大规模图例最大团问题时需要重点关注的方面,并展望了智能优化算法、分层式深度强化学习方法、图结构相变分析技术的未来研究方向。

摘要： 图卷积神经网络通过特征传播,学习卷积核,实现图卷积,它的核心在于卷积算子的构建。在应用具体的图数据时,卷积核的适用性往往因应用场景的不同而受到限制。本文从图过滤的角度看待卷积核,在图过滤框架下,视结点的数据特征为图信号,应用低通滤波器对其进行平滑处理,将提取的平滑图信号放在拓扑图上进行谱域中的卷积。在此过程中,局部的图结构信息将被整合进结点的相似度表征中以完成图嵌入学习。为了提高图形滤波器的灵活性,实现更精细的设计,在原有模型的基础上,本文引入新的平移参数,从而在不增加神经网络的可训练权重数量的情况下,也可以轻松控制滤波器的平滑力度以满足各种场景的滤波需求,其作用机理则是控制频率响应函数的水平位移。通过在3个引文网络和1个知识图谱上设置多种参数值执行图嵌入学习的任务,本文验证了引入平衡参数的有效性,并从图划分的角度对此提出了更为全面的见解。

摘要： 数模混合仿真是理解真实电网运行情况,支撑电网安全保障的重要手段。复杂的电网拓扑与硬实时的仿真需求对其计算性能提出了很高的要求。目前数模混合仿真多采用并行计算技术提高计算性能。随着处理器和集群技术的发展,异构集群系统逐渐成为高性能计算系统的主要构建方式。针对多层次的系统架构,已有的电网划分方式无法充分利用集群计算能力。如何应对多层次核间通信延迟变化问题,及引入设备交互导致的节点资源不对称问题是数模混合仿真任务划分与映射的新挑战。针对中国电力科学研究院自研电磁暂态仿真系统ADPSS,基于最小割划分设计了两阶段的电网划分与进程映射一体化优化算法,在计算负载均衡和最小化通信上取得更好的平衡,进一步降低了电磁暂态仿真的通信时间。同时,该算法有效解决了集群节点资源不对称情况下的任务优化映射问题。通过在西北和华东真实电网算例上的模拟测试,所提出算法较ADPSS默认划分与映射算法取得了平均40%和50%的通信性能提升,平均10%和12%的总体计算性能提升。

摘要： 针对交通路网控制子区的划分问题,提出了基于均衡k划分的动态子区划分方法。首先建立交叉口和路段权重模型,将路网抽象成为带权拓扑图;再针对拓扑图划分的NP问题,采用改进的禁忌搜索算法进行优化求解,同时为降低算法的复杂度设计了一种启发式算法为禁忌搜索算法获取初始近似解;最后利用路网实际数据与已有方法进行对比分析。结果显示:以任意子区内节点权重之和最小与连接不同子区的边权之和最小为目标,可以实现子区划分在宏观意义上的路网类均衡性和微观意义上的区间弱关联性,进而验证了本文所提算法的可行性和有效性。采用的启发式方法为禁忌搜索算法提供初始近似解,能够有效降低其复杂度,提高计算的实时性,并且利用所提方法划分的子区能够降低路网协调控制的难度,避免多个高负荷交叉口聚集而影响路网运行效率。

摘要： 现有外存图计算系统中,外存I/O带宽不足成为性能瓶颈。使用整体并行模型将导致冗余计算,使用异步并行模型则将引入额外的优先级计算开销和负载不均衡。本文提出了基于块坐标下降法(BCD)的外存异步图计算系统(BCDG),设计了一次选择多轮优先的调度策略,降低了优先级计算的平均开销;设计了基于优先级的块预取策略,解决了优先选择会破坏顺序执行流水线的问题;设计了计算调度分离的划分策略,实现了均衡地按边计算和按点调度。实验结果表明,相较于目前最先进的外存图计算系统GridGraph和Lumos,所提系统平均性能分别提升10.30倍与8.72倍。整体计算过程中,中央处理器(CPU)等待外存I/O的时间仅占10%~30%。

摘要： 知识图谱是人工智能的重要基石,因其包含丰富的图结构和属性信息而受到广泛关注.知识图谱可以精确语义描述现实世界中的各种实体及其联系,其中顶点表示实体,边表示实体间的联系.知识图谱划分是大规模知识图谱分布式处理的首要工作,对知识图谱分布式存储、查询、推理和挖掘起基础支撑作用.随着知识图谱数据规模及分布式处理需求的不断增长,如何对其进行划分已成为目前知识图谱研究的热点问题.从知识图谱和图划分的定义出发,系统性地介绍当前知识图谱数据划分的各类算法,包括基本、多级、流式、分布式和其他类型图划分算法.首先,介绍4种基本图划分算法:谱划分算法、几何划分算法、分支定界算法、KL及其衍生算法,这类算法通常用于小规模图数据或作为其他划分算法的一部分;然后,介绍多级图划分算法,这类算法对图粗糙化后进行划分再投射回原始图,根据粗糙化过程分为基于匹配的算法和基于聚合的算法;其次,描述3种流式图划分算法,这类算法将顶点或边加载为序列后进行划分,包括Hash算法、贪心算法、Fennel算法,以及这3种算法的衍生算法;再次,介绍以KaPPa、JA-BE-JA和轻量级重划分为代表的分布式图划分算法及它们的衍生算法;同时,在其他类型图划分算法中,介绍近年来新兴的2种图划分算法:标签传播算法和基于查询负载的算法.通过在合成与真实知识图谱数据集上的丰富实验,比较了5类知识图谱代表性划分算法在划分效果、查询处理与图数据挖掘方面的性能差异,分析实验结果并推广到推理层面,获得了基于实验的知识图谱划分算法性能评价结论.最后,在对已有方法分析和比较的基础上,总结目前知识图谱数据划分面临的主要挑战,提出相应的研究问题,并展望未来的研究方向.

摘要： 请将此图划分为面积相等、形状相同的8等份,每块上要有3只响着的喇叭和3只不响的喇叭。试试看,你能很快完成吗?

摘要： 复杂网络的研究已经广泛地应用到生物、计算机等各个学科领域.如今,网络规模十分巨大,如何对这些大规模图数据进行有效率的挖掘计算,是研究复杂网络的首要任务.并行计算技术是现在最成熟、应用最广、最可行的计算加速技术之一.而图划分技术是提高并行计算性能的有效手段.图划分问题的研究是随着实际应用的需求而驱动.针对异构计算环境下的分布式集群,本文提出了一种异构感知的流式图划分算法.该方法既考虑到集群中网络带宽及节点计算能力的不同,同时又考虑到了以InfiniBand为代表的高速网络环境下核之间的共享资源的竞争.实验以图算法BFS、SSSP和PageRank为例,相对于未考虑异构环境的流算法,图计算效率分别平均提高了38％、45.7％、61.8％.同时针对流式图划分过程中邻点缓存查找效率低下问题,本文又设计了一种邻边结构的缓存查找算法,在相同条件下,图划分的效率平均提高了 13.4％.仿真实验结果表明,本文设计的异构感知图划分算法实现了异构集群环境下图计算效率的提升.

摘要： 传统的社区发现算法中网络节点相似度多以空间距离度量,这种度量往往不容易理解,或者只能从距离的角度予以解释.本文提出一种基于文本内容相似度的谱聚类方法,它以网络社区用户的文本信息的相似性来度量网络节点的属性相似度,考虑网络结构的同时使节点的属性联系更有意义.在此基础上使用谱聚类的思想进行社区划分.本文以实际数据进行实验发现,发现划分结果的模块度和节点平均相似度较高,聚类效果良好.

摘要： 现代超级计算机具有越来越多的计算结点,同时结点内具有多个处理器核。由于互联带宽的差异,结点间与结点内构成两个通信性能不同的通信层次,后者的通信性能好于前者。但是,目前MPI程序的默认进程映射未考虑该通信层次差异,无法利用结点内较好的通信带宽,严重束缚了超级计算机的性能发挥。针对该问题,本文设计实现了能利用层次通信差异的MPI程序自动进程优化映射工具POM,提供了高效、低开销获取MPI程序通信信息的方法,最终通过优化通信在通信层次上的分布提高了程序的通信效率,从而提高了应用程序的性能。本文解决了硬件平台通信层次的抽象、MPI程序通信信息的低开销获取与映射方案的计算三个问题。首先,按照通信能力差异将超级计算机结构抽象为高速互联的不同计算结点与相同结点上的多个处理器核两层。其次,提出了将集合通信转化成点到点通信的简单实现方法。最后,利用无向加权边图来表示MPI程序的进程间通信关系,将MPI程序的进程映射问题转化为图划分问题。在曙光5000A和曙光4000A上的实验结果表明,利用POM工具能够显著提高MPI程序的性能。

摘要： 三维几何模型分解是对模型的几何和拓扑信息作进一步处理的基础,在计算机图形学,计算机辅助几何设计和数字几何处理等方面有着广泛的应用,是当前的热点研完领域.模型分解的优化问题可等价转化为使分割边数目最小的图划分NP-完全问题.概述了模型分解的原理,属性和应用,系统地介绍了这一领域的工作成果并进行了分类,分析了各方面典型算法的优缺点,最后展望了这一技术的发展前景。

摘要： 医学图像分割是一种重要的医学图像处理技术,它的准确性直接影响后续处理的有效性,因此具有十分重要的意义.目前,许多算法被应用于图像分割问题,基于图论的图像分割方法就是其中之一.Shi和Malik将图像分割转化为图的划分问题,提出了归一化割准则,这种分割方法没有把局部特征和一致性度量作为解决问题的关键,而是着重于提取整幅图像的特征,因此取得了较好的分割结果.归一化割准则不仅度量了不同分组之间的总体不相似性,同时度量了各个组之内的总体相似性.本文具体研究了该算法,并将它应用于医学图像分割中,取得了较好的结果。

摘要： 医学图像分割是一种重要的医学图像处理技术,它的准确性直接影响后续处理的有效性,因此具有十分重要的意义.目前,许多算法被应用于图像分割问题,基于图论的图像分割方法就是其中之一.Shi和Malik将图像分割转化为图的划分问题,提出了归一化割准则,这种分割方法没有把局部特征和一致性度量作为解决问题的关键,而是着重于提取整幅图像的特征,因此取得了较好的分割结果.归一化割准则不仅度量了不同分组之间的总体不相似性,同时度量了各个组之内的总体相似性.本文具体研究了该算法,并将它应用于医学图像分割中,取得了较好的结果。

摘要： 医学图像分割是一种重要的医学图像处理技术,它的准确性直接影响后续处理的有效性,因此具有十分重要的意义.目前,许多算法被应用于图像分割问题,基于图论的图像分割方法就是其中之一.Shi和Malik将图像分割转化为图的划分问题,提出了归一化割准则,这种分割方法没有把局部特征和一致性度量作为解决问题的关键,而是着重于提取整幅图像的特征,因此取得了较好的分割结果.归一化割准则不仅度量了不同分组之间的总体不相似性,同时度量了各个组之内的总体相似性.本文具体研究了该算法,并将它应用于医学图像分割中,取得了较好的结果。

摘要： 医学图像分割是一种重要的医学图像处理技术,它的准确性直接影响后续处理的有效性,因此具有十分重要的意义.目前,许多算法被应用于图像分割问题,基于图论的图像分割方法就是其中之一.Shi和Malik将图像分割转化为图的划分问题,提出了归一化割准则,这种分割方法没有把局部特征和一致性度量作为解决问题的关键,而是着重于提取整幅图像的特征,因此取得了较好的分割结果.归一化割准则不仅度量了不同分组之间的总体不相似性,同时度量了各个组之内的总体相似性.本文具体研究了该算法,并将它应用于医学图像分割中,取得了较好的结果。

摘要： 医学图像分割是一种重要的医学图像处理技术,它的准确性直接影响后续处理的有效性,因此具有十分重要的意义.目前,许多算法被应用于图像分割问题,基于图论的图像分割方法就是其中之一.Shi和Malik将图像分割转化为图的划分问题,提出了归一化割准则,这种分割方法没有把局部特征和一致性度量作为解决问题的关键,而是着重于提取整幅图像的特征,因此取得了较好的分割结果.归一化割准则不仅度量了不同分组之间的总体不相似性,同时度量了各个组之内的总体相似性.本文具体研究了该算法,并将它应用于医学图像分割中,取得了较好的结果。

摘要： 本发明公开了一种基于非均匀图子带划分的语音图自适应谱减法，在原有图谱减法的基础上，根据语音的图频率域特性对图频率进行非均匀图频率域划分，形成所谓的图子带信号，使得不同图频率范围下的图子带宽度不同。然后，根据图子带上的语音分布，对语音信号进行子带信噪比估计，以此为依据进行图子带筛选，对不同的图子带采取自适应的谱减策略，以提高算法的语音增强性能。本发明的噪声性能较图谱减法以及子带谱减法均有明显的提升。

摘要： 本发明涉及一种基于业务需求数据流图的云计算微服务划分方法和系统，方法包括：获取数据流图，将该数据流图对应的底层数据流图合并，构成一个整体的全连通数据流图，消除该全连通数据流图中的存储节点；将全连通数据流图中的有向边均改为无向边，然后进行图的广度优先遍历，得到若干连通子图集合；将消除的存储节点和有向边加入各个连通子图集合中，然后在各个连通子图集合中搜索成环路径，得到数据路径集合；根据数据路径集合划分微服务，得到候选微服务集合，用于微服务的划分。与现有技术相比，本发明保证了划分结果微服务的业务内聚性，同时不会出现粒度过大的微服务，且能尽量减少功能在微服务中的重复实现，划分质量较高。

摘要： 本发明公开了一种基于内视点划分墙面的施工索引图生成方法及计算机可读存储介质，将墙面按照内视点划分为四个组别，使得分组的效果达到能够合适的展示在施工索引图上，即不会产生施工误解，也能合理使用图纸布局。并且基于四个墙面图纸和两个地面图纸计算缩放比，使得最终呈现在施工索引图上的图纸既能够最大程度铺满绘图区域，又不会造成图纸相互重叠，以呈现出最佳的视觉效果。

摘要： 本发明提供了一种室内功能区域划分图的构建方法，包括：获取室内平面图的数据，对室内平面图的数据进行处理以划分得到各个房间区域的数据；分别获取各个房间区域对应的室内环境的图像，利用室内定位技术记录获取室内环境的图像时的三维坐标和时间，根据室内环境的图像以及与室内环境的图像对应的三维坐标和时间对室内环境的图像进行功能目标检测识别；根据功能目标检测识别的识别结果对各个房间区域进行对应功能标识，以得到室内功能区域划分图。通过本发明提供的技术方案，能够解决现有技术中的可移动机器人不便于对室内环境进行功能区域划分的技术问题。

摘要： 针对现有图分割方法对大规模图计算进行图分割划分时开销过大的技术问题，本发明提供了一种用于分布式图计算的图分割划分方法，基于开源框架PowerLyra，首先作为输入的图数据按照目标点哈希将边分散到各个节点，然后各节点在分布式框架上同步并行处理分布到其节点上的边，根据需要执行相应的分布式算法。本发明提出了“包”的概念，包是指局部性较高的部分边的集合，其最大值是可修改的，通过包将数据局部性特性引入图划分的计量标准，使划分的子图具有局部性，充分利用数据局部性原理，有效减少顶点的镜像顶点的数目，同时也保证了节点间的负载均衡，减少了分布式系统中的通信开销，提高大规模图相关应用的处理效率，提高分布式图计算的性能。

摘要： 本发明涉及移动互联技术领域，且公开了基于图划分算法和图嵌入算法的相似金融社区网络发掘算法，首先是构图；其次是图切分社区；然后再基于图嵌入得到每个社区中节点的表示。该基于图划分算法和图嵌入算法的相似金融社区网络发掘算法，通过知识图谱技术，并采用图划分和图嵌入技术，实现整图的金融社群划分，以及将网络中的所有节点嵌入低维的向量空间，再通过以划分社群为基础，基于相似度算法，在全域图谱网络中挖掘具有相似图结构特征、且未被发现的金融社群网络，从而充分考虑到社会经济活动的网络关系特性，基于知识图谱网络，挖掘分析经济紧密社群和高危风险社群，达到社会经济组织挖掘和群体风险防控的效果。

摘要： 本发明提供一种基于动态K个中心点图划分与简化的图直径算法，包括步骤S1：选取当前图中未覆盖顶点近似中心性最高的K个顶点加入到簇集中心点集合；步骤S2：根据所述簇集中心点集合按照第一扩张参数，得到第一簇集；步骤S3：对所述第一簇集中当前未覆盖的顶点数量与已覆盖的顶点数量进行判断，若所述第一簇集中当前未覆盖的顶点大于已覆盖的顶点数，更新第一扩张参数并执行步骤S2；若所述第一簇集中当前未覆盖的顶点小于等于已覆盖的顶点数，则将已覆盖顶点的边转移并合并到距离其最近的中心点，然后从图中删除该已覆盖顶点，并执行步骤S4；若未覆盖的顶点数量小于等于预设阈值，则进行构建商图操作。

摘要： 本发明提出了一种面向大图计算高效图划分方法与系统，该方法将图数据划分成多个顶点，并将顶点随机排序转为队列；按照队列顺序对第一个顶点进行分区分配，即分配到处理单元，分配完后以该顶点的分区信息作为值，此顶点的邻点作为键，以字典条目的形式存储于DRAM或者NVM中；后续顶点，先判断DRAM或NVM中是否有以此顶点为键的条目，如存在，直接将此顶点的分区信息追加到DRAM或者NVM中对应的条目；如果不存在，则将该点分配到负载最小的处理单元。将每个分配完的顶点的分区信息作为值，此顶点的邻点作为键，以字典条目的形式存储于对应的缓存中。该方法每次可直接根据当前定点查找对应的以此点为键的条目，效率得到了提升。

摘要： 针对现有图分割方法对大规模图计算进行图分割划分时开销过大的技术问题，本发明提供了一种用于分布式图计算的图分割划分方法，基于开源框架PowerLyra，首先作为输入的图数据按照目标点哈希将边分散到各个节点，然后各节点在分布式框架上同步并行处理分布到其节点上的边，根据需要执行相应的分布式算法。本发明提出了“包”的概念，包是指局部性较高的部分边的集合，其最大值是可修改的，通过包将数据局部性特性引入图划分的计量标准，使划分的子图具有局部性，充分利用数据局部性原理，有效减少顶点的镜像顶点的数目，同时也保证了节点间的负载均衡，减少了分布式系统中的通信开销，提高大规模图相关应用的处理效率，提高分布式图计算的性能。

摘要： 本发明公开了一种多无人机巡线的网络图划分方法及系统，所述方法包括：生成无人机巡视的任务网络图；通过第一算法对所述任务网络图进行划分，得到第一划分集合；通过第二算法对所述第一划分集合进行筛选，得到可行解集；对所述可行解集进行计算，得到所述无人机巡线的网络图划分方案。本发明采用基本割集原理进行网络图的划分，实用性强，生成的划分方案质量高。