有向无环图

摘要： 为加快推进区块链应用场景向纵深发展,释放区块链技术潜在价值,本文对区块链技术落地存在的点对点网络实现困难、并发处理能力不足、数据存储能力不强、跨链互通困难等技术性因素进行分析,同时对监管不到位、隐私保护存在隐患等非技术性因素进行总结,提出推动区块链技术应用进一步深化的策略。

摘要： 图模型是一种分析网络结构的有效方法,其中有向无环图由于可表示因果关系而受到广泛关注。而大量真实网络中节点的度服从幂律分布,即具有无标度特征。因此,研究了在无标度先验下,节点序已知的有向无环图结构学习问题。通过引入网络中节点度的信息和边的稀疏先验,提出罚项为Log型与lq(0

摘要： 区块链技术已广泛应用于金融、公共服务、物联网、网络安全、供应链等多个领域,但传统单链结构的区块链在吞吐量、交易确认速度和可扩展性方面存在不足,导致其在一些短时高并发量数据场景中难以落地应用。基于有向无环图(DAG)的区块链技术因其具有交易并发确认功能、吞吐量高、可扩展性强等优势受到研究者广泛关注。通过分析研究现有DAG区块链的发展和演化过程、评估方法、优化方向以及应用场景,探索DAG区块链在落地应用中的可行性。阐述主流DAG区块链的研究现状,比较传统区块链与DAG区块链的优势与不足,并分析现有区块链属性评估方法,总结DAG区块链评估结果。在此基础上,从交易确认速度、系统吞吐量、系统安全性、存储结构等方面对比现有DAG区块链的优化方法,介绍DAG区块链在数据管理、基于边缘计算和联邦学习的数据共享以及面向访问控制和隐私保护的数据安全等场景中的应用情况,并指出当前研究中存在的主要问题和挑战,对未来的研究方向进行展望。

摘要： 异构多处理器的高效性和可靠性能够满足日趋复杂的信号处理任务需求,因此分层异构系统已成为信号处理平台的发展趋势。为提高平台强实时性并解决高吞吐量的问题,文中对分层异构信号处理平台的软硬件模块及架构进行了研究,并采用有向无环图对组件任务及硬件资源进行建模。将已提出的调度算法按照任务类型、调度目标、调度过程和研究方法进行分类,并根据任务调度最新的研究进展提出组合优化算法的概念。文中对经典启发式算法、智能搜索算法、机器学习算法以及组合优化算法的性能进行对比和分析,发现组合优化算法能够满足平台任务调度的需求。

摘要： 针对异质信息网络中的影响力最大化(IM)问题,提出了一种基于有向无环图(DAG)的影响力最大化算法(DAGIM)。首先基于DAG结构度量节点的影响力,然后采用边际增益策略选择影响力最大的节点。DAG结构表达力强,不仅描述了不同类型节点之间的显性关系,也刻画了节点之间的隐性关系,较完整地保留了网络的异质信息。在三个真实数据集上的实验结果验证所提DAGIM的性能优于Degree、PageRank、局部有向无环图(LDAG)以及基于元路径的信息熵(MPIE)算法。

摘要： 在多标记学习(MLL)问题中,每个示例都与一组标记相关联.为了实现对未见示例的高效预测,挖掘和利用标记之间的关系是至关重要的.大多数已有的研究都将关系简化为标记之间的相关性,而相关性又通常基于标记的共现性.揭示了因果关系对于描述一个标记在学习过程中如何帮助另一个标记更为重要.基于这一观察,提出了两种策略来从标记因果有向无环图(DAG)中生成标记的因果顺序,同时使得生成的因果顺序都遵循因标记应该在果标记之前的准则.第1种策略的主要思想是对随机顺序进行排序,使其满足DAG中的因果关系.而第2种策略的主要思想是根据DAG的结构,将标记放入许多不相交的拓扑层次中,再通过它们的拓扑结构进行排序.进一步,通过将因果顺序纳入到分类器链(CC)模型中,提出了一种有效的MLL方法,从而从更加本质的角度来利用标记关系.在多个数据集上的实验结果验证了该方法确实能够挖掘出有效的标记因果顺序,并帮助提升学习性能.

摘要： 车联网通过实现车与车、车与路边单元的互联互通,共享驾驶信息和交通消息,为司机与乘客提供一个方便、安全的驾驶环境,但是虚假消息会对驾驶安全造成威胁,车辆消息可信度问题亟待解决.针对此问题提出一种车联网信誉值模型.该模型设计了一种根据车辆消息计算车辆信誉值的方法;然后基于有向无环图的分布式账本提出了一种车辆信誉的共识机制,通过动态调整共识难度,使信誉高的车辆更容易获得记账权,从而可以保证车联网中消息的可信度.通过分析发现,该机制可有效解决车联网中车辆消息的可信度问题,并且能够抵御常见的车联网攻击,相较于传统区块链,该共识机制具有更高的共识效率和更低的能量消耗,适用于计算和存储资源受限的车联网环境.

摘要： 针对区块链应用于建筑物联网场景时存在的吞吐量严重不足和响应时延高的问题,提出一种基于哈希图的建筑物联网数据管理方法。该方法使用有向无环图(DAG)存储数据,从而利用图式结构的高并发特性提高区块链的吞吐量性能;引入哈希图算法对存储在DAG内的数据达成共识,从而减少共识所需时间;设计智能合约实现访问权限控制,以防止未授权用户对数据的操作。使用区块链性能测试工具Caliper进行的性能测试的结果表明:在由32个节点构成的中等规模仿真环境下,与现有边缘计算方法和跨链方法相比,所提方法的吞吐量为每秒处理1063.1笔交易,分别为对比方法吞吐量的6倍和3倍;该方法的数据存储时延和控制时延分别为4.57 s和4.92 s,响应速度优于对比方法;该方法在尖峰冲击测试中的交易成功率为87.4%;同时基于该方法的原型系统在稳定性测试中可以平稳运行120 h。可见,所提方法可以有效提高区块链的交易吞吐量和响应速度,满足建筑物联网场景的实际使用需求。

摘要： 区块链具有去中心化、数据不可篡改、分布式账本的特性,在未来众多行业中有着广泛的应用前景.但在高校联盟链场景中会遇到交易高并发的问题,本文提出使用具有高并发特性的有向无环图DAG(Directed Acyclic Graph)数据存储结构,修改单元结构,加入消息积分、实名验证和投票三种消息类型,实现节点信用积分和实名认证.通过模拟实验证明系统具有较高安全性,能够抵御常见的双花攻击、伪造交易信息和伪造共识节点网络攻击,适用于高校联盟链场景.

摘要： 随着任务类型多样化和任务节点数目增多,传统调度算法以及一些改进算法得到的调度结果使系统整体运行时间延长,导致系统实时性下降。针对这一问题,提出一种面向异构处理平台的任务调度算法。首先,针对不同类型任务采用不同的排序策略,得到任务优先级列表;其次,充分考虑任务间的依赖关系,引入任务上行序值和下行序值权重因子,确定关键路径任务集合和关键处理器;最后,按照最早完成时间原则,结合空闲时隙插入策略和任务复制思想进行处理器分配。仿真结果表明,所提算法在同样的任务图中,能够降低任务调度中的通信开销,调度长度平均减少15%,调度加速比平均提高10%。

摘要： 本文采用有向无环图技术(DAG)和基于DAG的预测方差分解方法探讨了我国货币因素、生猪供给、消费需求对猪肉价格波动的影响.研究结果表明,我国猪肉价格的剧烈波动主要源于自身惯性的推动;货币流动性对猪肉价格的波动短期效应不明显,但从长期来看能解释30％左右的猪肉价格波动;生猪供给和消费需求对猪肉价格波动的解释程度较小,分别为8％和4％.因此为了有效调控猪肉价格,可以从控制货币流动性和稳定生猪供给着手,实施稳健的货币政策和创新猪肉目标价格保险政策,从而稳定猪肉价格波动.

摘要： 具有长度约束的简单路径(Simple Paths with Length Constraint,SPLC)问题是指求解图中任意两点间路径长度为m的简单路径数,是κ-path问题的一种特殊情况该文基于网树数据结构提出了在有向无环图中求解SPLC问题的算法(Nettree for SPLC in Directed Acyclic Graphs,NSPLCDAG)网树是一种多树根多双亲的数据结构NSPLCDAG算法将该问题转化为一棵网树后,利用树根路径数这一性质对其进行求解对NSPLCDAG算法进行改造,可以求解有向无环图中最长路径问题并形成网树求解最长路径算法(Nettree for the Longest Path in DAGs,NLPDAG),NLPDAG算法可找到所有最长路径,对NLPDAG算法做进一步改进形成改进的NLPDAG算法,改进的NLPDAG算法可在线性时间复杂度内给出有向无环图中的一条最长路径实验结果验证了NSPLCDAG和改进的NLPDAG算法的正确性与有效性.

摘要： 本文以结构自回归模型为基础，结合有向无环图方法和方差分解技术对我国金融发展和贸易开放的关系进行了考察，结果表明：经济货币化程度与贸易开放互为同期因果关系，证券市场发展是贸易开放的单向同期原因，而金融机构信贷与贸易开放之间不存在同期因果关系；经济货币化、金融中介信贷、经济证券化与贸易开放相互影响，但对于对方波动的解释能力存在显著的差异。

摘要： 本文从模式识别的角度,将路网交通状态判别转化为状态信息归类问题.首先,运用AdaBoost方法和SVM方法作为路网交通状态分类器的训练学习方法,提高了AdaBoost方法和SVM方法的多分类性能.随后,借助有向无环图(DAG)搭建路网交通状态判别器.通过训练和判别两个阶段,实现对城市交通状态信息的有效判别,为治理交通拥堵提供可靠信息.

摘要： 在真实环境中,服务的执行时间可能由于网络、CPU、磁盘I/O及负载变动而产生波动,从而影响组合服务的实际完工时间.研究组合服务的实际完工时间的分布规律与影响因素对于保证组合服务的性能至关重要.本文采用有向无环图描述组合服务,提出了一种组合服务的时序鲁棒性指标,以评估组合服务的完工时间的波动程度.通过理论分析给出了该指标的界限;通过仿真分析,探索了服务的执行时间的分布与波动情况、组合服务中简单服务的个数等因素对该指标的影响.为分析鲁棒服务组合的必要性和设计鲁棒服务组合方法奠定了基础.

摘要： 给定有向无环图G,G的传递归约是和G有相同传递闭包的最小唯一子图针对已有传递归约算法不能有效适应实际应用中图规模不断膨胀的问题,首先提出一种空间复杂度为O(n)的算法BUTR,其中n为G的顶点数BUTR首先计算G的路径分解,并以自底向上的方式处理每条路径中的顶点其特点体现在处理每条路径p时,可以利用p中顶点间的父子关系来避免对部分顶点和边的重复访问,并保证在处理完p的所有顶点后,所有涉及到的边仅被访问一次其次提出无需路径分解的优化算法—TDTR.TDTR通过栈来缓存已处理顶点并标记其逆向传递闭包,从而尽可能早的利用不同路径中顶点间的父子关系来避免BUTR算法存在的冗余计算问题最后在26个不同规模的真实数据集和10个大规模人工数据集上,通过实验从不同角度对算法的性能进行了深入比较和分析实验结果显示,文本提出的BUTR和TDTR算法具有良好的时间和空间扩展性.

摘要： 异构分布式系统性能得到大幅度提升的同时,却造成故障率大增,以有向无环图(Directed Acyclic Graph,DAG)任务模型研究异构分布式系统的容错调度成为当前的研究热点.广泛采用的基于任务复制的容错算法存在以下问题:(1)DAG任务可靠性需求与DAG可靠性需求的约束存在缺陷且缺乏严谨的理论证明;(2)每个任务仅有一个副版任务,不足以应对任务潜在的多次发生的故障;(3)盲目地使每个任务拥有ε+l个副版来容忍可能的ε个故障,虽然提高了系统的可靠性但易造成系统冗余度过高,并付出昂贵的计算资源.文中首先分析DAG图中任务依赖关系,确定DAG任务的可靠性概率模型,并建立DAG可靠性模型;接着提出满足可靠性目标的任务复制下限值算法、经济的任务复制策略算法和贪婪的任务复制策略算法,精确量化各个任务需要复制的次数,最后在上述算法的基础上提出可选策略的DAG容错算法OPDFT(Optional Policy on DAG Fault-Tolerant).实验表明,OPDFT算法的经济复制策略和贪婪复制策略的可靠性代价分别是盲目策略算法可靠性代价的60％和70％左右.

摘要： 对于典型的NP难度问题——二维矩形Packing问题,经典完备算法的计算复杂度不仅与待放块的数目相关,也与矩形框的宽和高相关.通过观察二维矩形Packing问题的合法布局的特点,将其与一对有向无环图相对应,并基于Prüfer码进行编码,提出了一种计算复杂度仅与待放块数相关的复杂度较低的完备算法.

摘要： 针对模拟电路的故障诊断问题,讨论了一种基于有向无环图支持向量机分类器(DAGSVC)的故障字典新方法,并提出一种评估支持向量机分类器的测试复杂度指标。首先,对电路施加一定的测试激励,利用可测节点采集电路响应;其次,对采集的电路响应进行特征提取形成训练样本,并建立“l-v-l”SVMs进行训练,训练完毕并构建故障字典;最后,建立DAGSVC结构对未知样本加以测试.通过对一个模拟滤波器的实际测试和验证表明,本文方法性能要优于“l-v-r”SVC、“l-v-l”SVC和神经网络,适合模拟电路的故障分类和诊断.

摘要： 供应链管理网络是种有向无环图,在实际应用中不可避免的具有多种不确定性,这些不确定性可用概率进行表示.贝叶斯网是种应用较广的概率图模型,它也是有向无环图.对供应链管理网络中的不确定信息与贝叶斯网进行研究,对使用贝叶斯网络研究供应链管理的可行性进行了论证.由于贝叶斯网是概率分布与图表示的完美结合,根据供应链管理中的不确定信息,可建立合适的贝叶斯网,通过联合概率分布进行决策,使得供应链中的各方达到共同获利的目的.由于贝叶斯网在-般情况下的学习与推理问题都是NP难问题,对用于供应链管理贝叶斯网在仿真中可能遇到的情况进行了分析.研究表明,将贝叶斯网应用到供应链管理中的不确定信息仿真是切实可行的.

摘要： 本申请公开了一种基于有向无环图的任务调度方法、系统、设备及存储介质，所述基于有向无环图的任务调度方法包括：将一项总任务划分为若干可独立执行的最小单元作为任务节点；基于有向无环图确定各任务节点的依赖关系，并根据依赖关系确定各任务节点对应的执行次序，以便基于所述执行次序为各任务节点分配工作线程；本申请具有提高存在大量数据依赖时多线程计算的效率的效果。

摘要： 本申请涉及有向无环图技术领域，公开一种用于验证有向无环图的环的方法，通过获取有向无环图中未入栈的多个节点，从中选取一个节点为起始节点，并对起始节点对应的多条路径依次进行遍历，对待遍历路径执行第一预设操作，即从待遍历路径中的第一个待遍历节点开始依次对待遍历路径中的节点执行第二预设操作，在各节点均执行完第二预设操作且未确定出有向无环图存在闭环的情况下，将待遍历路径中的待遍历节点均出栈；在各路径均执行完第一预设操作且未确定出有向无环图存在闭环的情况下，确定有向无环图不存在闭环。这样，能够提高判断有向无环图是否存在闭环的效率。本申请还公开一种用于验证有向无环图的环的装置、电子设备、存储介质。

摘要： 本申请实施例属于大数据领域，涉及一种基于有向无环图的任务调度方法，包括根据业务类型对多个任务进行分类；对每类所述任务进行拆分形成多个子任务，将每类所述任务中的子任务形成子任务集；将子任务集中所述子任务按照执行逻辑顺序进行编排，以每个所述子任务为节点、以所述子任务之间的逻辑关系为边组成有向无环图的数据结构；触发引用所述任务的事件，在所述有向无环图的数据结构中执行任务。本申请还提供一种基于有向无环图的任务调度装置、设备及介质。本申请可以将所有任务组成一个有向无环图的数据结构，根据有向无环图的遍历算法进行调度，确保了各个任务之间的有序执行，便于任务的维护。

摘要： 本发明提供了一种基于有向无环图的系统构建策略生成方法，通过将待构建系统抽象为一个有向无环图，优化了系统构建数据存储方法，便于系统构建状态更新和维护，通过动态生成构建策略，避免了频繁遍历系统构建目标导致的性能开销，提高了系统构建的稳定性和拓展性。

摘要： 本发明公开了一种有向无环图生成方法，包括获取目标网络的数据信息；网络节点将自身邻居关系告知其他节点；构造初始图；删除初始图中只能单向传输的边得到第一初始图；检查第一初始图中每个节点并删除不合格节点后得到第二初始图；根据第二初始图对应的邻接矩阵进行节点拓扑顺序的列举；根据节点拓扑顺序确认各个节点的上下游关系；输出最终构建的目标网络的有向无环图。本发明还公开了包括所述有向无环图生成方法的网络编码方法，以及包括所述有向无环图生成方法和网络编码方法的网络通信方法。本发明方法能够实现有向无环图的分布式构建，而且可靠性高，实用性好。

摘要： 本发明公开涉及一种基于有向无环图的数据传输方法、装置及电子设备，该方法包括：根据数据传输指令在有向无环图中确定起始节点、终止节点和最先到达路径；将待传输的数据沿该最先到达路径进行传输；若接收到问题节点发送的未接收到数据的反馈信息，确定向该问题节点发送数据的上级节点并删除该上级节点和问题节点之间的数据传输通道；重复执行上述步骤，直至该终止节点接收到该数据，以完成该数据传输指令中指示的数据传输过程。能够通过在有向无环图结构中确定数据的最先到达路径以及根据数据是否传输至每个节点实时对最先到达路径进行调整，形成一套完整的异常检测，异常节点确定以及异常解决的完整机制，提高数据传输的效率。

摘要： 本发明公开拜占庭容错(BFT，byzantine fault tolerance)确定性共识方式的有向无环图‑账户智慧交易链(DAG(directed acyclic graph)‑AWTC(account‑wise transaction chain))总账系统。有向无环图‑账户智慧交易链(DAG‑AWTC)总账系统包括共识对象交易设置模块，上述共识对象交易设置模块选择并实时设置所要对有向无环图‑账户智慧交易链(DAG(directed acyclic graph)‑AWTC(account‑wise trans action chain))的交易(transaction)执行拜占庭容错(BFT，byzantine fault tolerance)共识的共识对象交易，将实时设置的共识对象交易输出到拜占庭容错共识执行模块。根据上述拜占庭容错(BFT)确定性共识方式的有向无环图‑账户智慧交易链(DAG‑AWTC)总账系统，通过配置成在并行型结构的有向无环图(DAG)总账结构中应用作为确定性共识方式的拜占庭容错(BFT)共识方式，具有可以确保交易的快速处理、迅速验证及信息完整性的效果。更加具体地，通过以充分扩散以执行拜占庭容错确定性共识为前提的时间设置，具有可以允许并行地分别执行拜占庭容错确定性共识以及交易处理的效果。即，通过配置成在进行处理交易的同时执行拜占庭容错确定性共识作为单独的后台处理，可以实现拜占庭容错确定性共识，而不破坏有向无环图‑账户智慧交易链总账结构所具有的交易的快速处理速度。

摘要： 本公开提供了“克隆有向无环图的自动同步”。公开一种用于同步克隆有向无环图的方法。所述方法可以包括识别有向无环图(“DAG”)，所述DAG包括经由多个边以成对关系链接的多个顶点。可以创建至少一个克隆DAG，所述至少一个克隆DAG可以与所述DAG的至少一部分相同。可以针对所述DAG的所述顶点中的每一个从所述至少一个克隆DAG的所述克隆顶点中识别对应克隆顶点。可以基于来自所述DAG中所述克隆顶点中的每一个及其对应顶点的梯度数据计算聚合梯度数据，并且可以基于所述聚合梯度数据更新所述DAG和所述至少一个克隆DAG的至少一个权重。

摘要： 本发明公开了一种基于有向无环图的区块链系统中区块的定序方法，确定并记录该纪元内所有区块的引用计数，引用计数表示的是一个区块在其所属纪元内被其它区块引用的次数；建立队列，并将引用计数为0的定序区块送入队列中，随后建立栈，并使得栈初始状态为空；从队列中出列第一个区块，获取该区块的引用列表，然后将该区块送入栈中；对于步骤3中的引用列表，对引用列表中引用的每一个区块，如果该区块也在这个纪元中，那么该区块引用计数减1。本发明法体现了DAG结构引用即见证的特性，并且在定序区块还未出现时，不容被恶意节点操纵区块顺序。

摘要： 本发明公开了一种基于有向无环图业务流程恢复的方法及装置，包括：在业务流程异常时，确定异常步骤；将业务流程中与异常步骤的深度信息相同的步骤确定为待重新执行步骤；其中，各步骤的深度信息是根据各步骤在依据业务流程构建的有向无环图中的位置确定的；有向无环图是以业务流程的各步骤为节点，各步骤之间的执行依赖关系为有向边建立的；针对任一待重新执行步骤，根据待重新执行步骤的步骤记录生成待重新执行步骤的执行上下文实例；待重新执行步骤的步骤记录用于存储待重新执行步骤在执行时所需要的数据信息；通过执行上下文实例对业务流程进行恢复执行处理。从而提升对业务流程中各步骤的管理能力，提升业务流程的执行效率。