顶点覆盖问题线性内核算法

参数复杂性作为算法研究的一个重要分支近10年在国际上受到了广泛的关注,线性内核问题作为参数复杂性研究的一类重要问题被广泛研究.主要给出了顶点覆盖问题的线性内核算法,在国内首次从理论上证明了顶点覆盖问题存在线性内核.算法首先通过顶点覆盖问题的2近似算法,将图的顶点集合分成两个顶点集合A,B,进而通过一系列规约将原始图的顶点覆盖问题转换到新图的顶点覆盖问题,然后证明了新图的顶点数目至多为2k,并且2k是这个问题的下界(k为参数具体定义见文章).     

一种增量式约简方法求解最小顶点覆盖问题

最小顶点覆盖问题是一个应用很广泛的NP难题,针对该问题给出一种增量式属性约简方法。首先将最小顶点覆盖问题转化为一个决策表的最小属性约简问题;利用增量式属性约简思想,随着图中边数的增多,提出一种更新最小顶点覆盖的增量式属性约简算法;该算法时间复杂度低于计算整个图的最小顶点覆盖的时间复杂度,同时针对大规模图问题,可随着边的增加动态更新最小顶点覆盖,因此降低了属性约简的方法求解最小顶点覆盖问题的运行时间;实验结果表明该算法的可行性和有效性。     

基于子图的随机图点覆盖2度点核化研究

点覆盖问题虽然可以在参数计算理论的架构内求精确解,但是目前在理论及应用上有一定的局限性.根据不同度的顶点之间及顶点与边的关系,提出随机图参数化点覆盖问题的d-核化可决策性及2度点三角形予图的计数方法;通过研究子图对顶点的共享关系,分析2度顶点核化过程中核及度分布演变的动态过程,得出随机图2度点核化强度与2度点概率关系及2度点核化可决策性的两个推论:2度点核化算法对2度点分布概率约为0.75的随机图的核化强度最高;对顶点度概率分布为φ(χ)的随机图的参数化点覆盖问题(G,k),当k小于某一与φ(х)有关的值时,它是2-核化可决策的.仿真结果证实,该理论能够把握2度点核化的内在机制,提供随机图上这一NP完全问题的求解方法,也为参数计算在已知度分布的一类不确定问题中的应用提供了可能.     

模糊环境下的最小权顶点覆盖问题*

最小权顶点覆盖问题在实际决策中应用广泛,但顶点上的权值在实际应用中通常代表费用、成本等,在很多情况下是不确定的。关注了最小权顶点覆盖问题中的模糊不确定性,对模糊环境下的最小权顶点覆盖问题进行了研究。引入了可信性理论以描述模糊不确定性,并根据不同的决策准则建立了求解模糊环境下最小权顶点覆盖问题的三个决策模型,结合模糊模拟和遗传算法设计了一种求解所建立模型的混合智能算法,并给出了数值实验。数值实验的结果验证了所提出的决策模型与算法的有效性。     

最小顶点覆盖问题的竞争决策算法

竞争决策算法是在分析大自然生物世界特别是人类的各种竞争机制和决策原理的基础上,利用竞争造就优化、决策左右结果的特性来达到优化目的的新型寻优算法。采用竞争决策算法原理,利用竞争决策算法的通用模型,求解图的最小顶点覆盖问题。     

随机图点覆盖1度顶点核化算法分析

将随机图引入参数计算领域,利用随机图统计和概率分布等特性,从全局和整体上研究参数化点覆盖问题1度点核化过程中问题的核及度分布演变的内在机制和变化规律,并得出关于随机图1度点核化强度与顶点平均度关系及随机图点覆盖问题的决策与度分布关系的两个重要推论.最后分别从MIPS和BIND提取数据进行1度核化实验和分析.初步结果表明,对随机图点覆盖问题的分析方法不仅具有理论上的意义,而且随着问题随机度的大小而对问题有不同程度的把握能力.     

一种基于随机化均匀设计点集的遗传算法用于求解MVCP

基于理想浓度模型的机理分析,利用随机化均匀设计的理论和方法,对遗传算法中的交叉操作进行重新设计,并在分析图最小顶点覆盖问题特点的基础上,结合扫描-修正和局部改进策略,给出一个解决图最小顶点覆盖问题的遗传算法,称之为基于随机化均匀设计点集的遗传算法。通过将该算法与简单遗传算法和佳点集遗传算法进行求解图最小顶点覆盖问题的仿真模拟比较,可看出该算法提高求解的质量、速度和精度。     

基于原始对偶方法求解网络流量监测集算法

考虑网络节点的流守恒特性,网络流量的有效监测问题可抽象为求给定图G(V,E)的最小弱顶点覆盖集的问题和基于流划分的最小弱顶点覆盖集的问题,这是NP难的问题.首先分析了弱顶点覆盖集的约束关系,并给出了问题的整数规划形式.然后利用原始对偶方法构造了求解最小弱顶点覆盖集的近似算法,并分析了算法的比界为2.进一步分析了求解基于最大流划分的最小弱顶点覆盖集的近似算法.     

图同构问题的决策神经网络模型

图的同构问题是研究两个图之间相互关系范畴.这对图表面上似乎不同,但本质上完全相同.由于图的同构问题在以系统建模、电路布线等众多问题中有直接的应用,因而,吸引了不少的学者从事这方面的研究.该文意在建立一种局域连接的、模拟人脑决策思维模式的、可用于优化信息处理的神经网络模型.该文在过去建立求解图的同构问题人工神经网络模型的基础上,拟应用人脑决策局域化的思想,提出了一种新的用于图的同构问题的人工神经网络模型.该模型中增加了一个自然的约束条件,加快了运算速度.     

图的最小顶点覆盖问题的DNA表面计算模型

基于生化反应原理的DNA计算具有强大的并行运算能力,DNA计算机在求解NP问题上存在着硅计算机无法比拟的先天的优越性。采用荧光标记的策略,给出了一种新的图的最小顶点覆盖问题的DNA表面计算模型。该模型首先将问题解空间的DNA分子固定在固体载体上,然后通过进行相应的生化反应来求得图的最小顶点覆盖问题的所有解。新算法利用荧光猝灭技术,通过观察荧光来排除非解,具有编码、解读简单和错误率低的特点。     

Finding Minimum Vertex Covering in Stochastic Graphs: A Learning Automata Approach

Structural and behavioral parameters of many real networks such as social networks are unpredictable, uncertain, and have time-varying parameters, and for these reasons, deterministic graphs for modeling such networks are too restrictive to solve most of the real-network problems. It seems that stochastic graphs, in which weights associated to the vertices are random variables, might be better graph models for real-world networks. Once we use a stochastic graph as the model for a network, every feature of the graph such as path, spanning tree, clique, dominating set, and cover set should be treated as a stochastic feature. For example, choosing a stochastic graph as a graph model of an online social network and defining community structure in terms of clique, the concept of a stochastic clique may be used to study community structures’ properties or define spreading of influence according to the coverage of influential users; the concept of stochastic vertex covering may be used to study spread of influence. In this article, minimum vertex covering in stochastic graphs is first defined, and then four learning, automata-based algorithms are proposed for solving a minimum vertex-covering problem in stochastic graphs where the probability distribution functions of the weights associated with the vertices of the graph are unknown. It is shown that through a proper choice of the parameters of the proposed algorithms, one can make the probability of finding minimum vertex cover in a stochastic graph as close to unity as possible. Experimental results on synthetic stochastic graphs reveal that at a certain confidence level the proposed algorithms significantly outperform the standard sampling method in terms of the number of samples needed to be taken from the vertices of the stochastic graph.     

基于不确定性的多元时间序列分类算法研究

多元时间序列(Multivariate time series, MTS)分类是许多领域中的重要问题,准确的分类结果可以有效地帮助决策.当前的MTS分类算法在个体的表征学习阶段难以自动建模多元变量之间复杂的交互关系,并且无法评估分类结果的可信度,这会导致模型性能受限,以及缺乏具备统计意义的可靠性解释.本文提出了一种基于不确定性的多元时间序列分类算法,变分贝叶斯共享图神经网络,即VBSGNN (Variational Bayes shared graph neural network).首先通过图神经网络(Graph neural network, GNN)提取多元变量之间的交互特征,然后利用贝叶斯神经网络(Bayesian neural network, BNN)为预测过程引入了不确定性.最后在10个公开MTS数据集上进行了算法实验,并与当前提出的7类算法进行了比较,结果表明VBSGNN可有效学习多元变量之间的交互关系,提升了分类效果,并使得模型具备一定的可靠性评估能力.     

Single-row mapping and transformation of connected graphs

In a dimensional problem, the transformation of a graph into its linear network can be viewed as a transition involving demand and supply. A connected graph represents the demand flows between the components in the graph while the network supporting it is the resource or capacity links for supporting the demand volumes. The transformation involves a mapping from the graph to its network to satisfy certain performance metrics. In this work, we propose a model for transforming a connected graph to its linear network model in the form of a single-row routing network. The main objective is to provide an optimum routing network that minimizes the congestion. In this technique, the given graph is first partitioned into several disjoint cliques using the Hopfield neural network using our model called AdCliq. From the cliques, a set of intervals derived from the zones are obtained through the matching nodes in the single-row axis. The intervals are then mapped into a network of non-crossing nets using our previously developed tool called ESSR. The network is optimal in terms of minimum street congestion and number of doglegs, and this provides a reasonably good step towards the overall solution to the demand-supply problem.     

面向时空图建模的图小波卷积神经网络模型

时空图建模是分析图形结构系统中各要素空间关系与时间趋势的一个基础工作.传统的时空图建模方法,主要基于图中节点与节点关系固定的显式结构进行空间关系挖掘,这严重限制了模型的灵活性.此外,未考虑节点间的时空依赖关系的传统建模方法不能捕获节点间的长时时空趋势.为了克服这些缺陷,研究并提出了一种新的用于时空图建模的图神经网络模型,即面向时空图建模的图小波卷积神经网络模型（Graph Wavelet Convolutional Neural Network for Spatiotemporal Graph Modeling,GWNN-STGM）,称为GWNN-STGM.在GWNN-STGM中设计了一个图小波卷积神经网络层,并在该网络层中设计并引入了自适应邻接矩阵进行节点嵌入学习,使得模型能够在不需要结构先验知识的情况下,从数据集中自动发现隐藏的结构信息.此外,GWNN-STGM还包含了一个堆叠的扩张因果卷积网络层,使模型的感受野能够随着卷积网络层数的增加呈指数增长,从而能够处理长时序列.GWNN-STGM成功将图小波卷积神经网络层和扩张因果卷积网络层两个模块进行有效集成.通过在公共交通网络数据集上试验发现,提出的GWNN-STGM的性能优于其他的基准模型,这表明设计的图小波卷积神经网络模型在从输入数据集中探索时空结构方面具有很大的潜力.     

基于注意力机制和图卷积的小样本分类网络

深度神经网络在有着大量标注数据的图像识别任务上已经占据了统治地位,但是在只有少量标注数据的数据集上训练一个好的网络仍然是一个据有挑战性的任务.如何从有限的标注数据中学习已经成为了一个有着很多应用场景的热点问题.目前有很多解决小样本分类任务的方法,但是仍然存在识别准确率低的问题,根本原因是在小样本学习中,神经网络只能接收少量有标签的数据,导致神经网络不能获取足够的用来识别的信息.因此,提出了一种基于注意力机制和图卷积网络的小样本分类模型.这个模型不仅能够更好地提取特征,而且能够充分利用提取的特征对目标图像进行分类.通过注意力机制,能够指导神经网络关注更有用的信息,而图卷积使得网络能够利用支撑集中其他类别的信息做出更准确的判断.经过大量的实验,证明了提出的模型在Omniglot数据集和mini-ImageNet数据集上的分类准确率都超过了基于传统神经网络的关系网络.     

图网络层级信息挖掘分类算法综述

深度学习作为人工智能的一个研究分支发展迅速,而研究数据主要是语音、图像和视频等,这些具有规则结构的数据通常在欧氏空间中表示。然而许多学习任务需要处理的数据是从非欧氏空间中生成,这些数据特征和其关系结构可以用图来定义。图卷积神经网络通过将卷积定理应用于图,完成节点之间的信息传播与聚合,成为建模图数据一种有效的方法。尽管图卷积神经网络取得了巨大成功,但针对图任务中的节点分类问题,由于深层图结构优化的特有难点——过平滑现象,现有的多数模型都只有两三层的浅层模型架构。在理论上,图卷积神经网络的深层结构可以获得更多节点表征信息,因此针对其层级信息进行研究,将层级结构算法迁移到图数据分析的核心在于图层级卷积算子构建和图层级间信息融合。本文对图网络层级信息挖掘算法进行综述,介绍图神经网络的发展背景、存在问题以及图卷积神经网络层级结构算法的发展,根据不同图卷积层级信息处理将现有算法分为正则化方法和架构调整方法。正则化方法通过重新构建图卷积算子更好地聚合邻域信息,而架构调整方法则融合层级信息丰富节点表征。图卷积神经网络层级特性实验表明,图结构中存在层级特性节点,现有图层级信息挖掘算法仍未对层级特性节点的图信息进行完全探索。最后,总结了图卷积神经网络层级信息挖掘模型的主要应用领域,并从计算效率、大规模数据、动态图和应用场景等方面提出进一步研究的方向。     

保留低阶和高阶关系的图表示深度学习集成算法

高质量学习图中节点的低维表示是当前的一个研究热点。现有浅模型的方法无法捕捉图结构的非线性关系,图神经网络技术中的图卷积模型会产生过平滑问题。同时,如何确定不同跳数关系在图表示学习中的作用亦是研究中尚需解决的问题。以解决上述问题为目的,提出一个基于T(T>1)个前馈神经网络的深度学习模型,该框架利用深度模型抽取图结构的非线性关系,T个子模型有效地捕获图的局部和全局(高阶)关系信息,并且它们在最终的向量表示中赋予了不同的作用、从而发挥不同跳数关系的优势。在顶点分类和链接预测任务中的实验结果表明,该框架比现有方法具有竞争力,对比基准算法可以获得20%左右的提升。     

基于异构动态图模型的社交网络节点分类方法

在机器学习领域,与传统的神经网络相比,图神经网络在社交推荐等任务中发挥着越来越重要的作用,但是目前工作中大多数都使用静态图.针对现有静态图神经网络方法难以考虑社交用户动态特性的问题,通过引入动态图模型提出了一种基于异构动态图模型的社交网络节点分类方法.该方法在动态图建模的基础上,通过基于点边交互的节点特征更新机制和基于循环神经网络的时序聚合方法,实现了高效的动态社交网络节点分类.在多个真实数据集上的实验结果表明,提出方法在动态社交网络数据的节点分类方面有较好的效果,对比静态图和动态图的基准方法有显著的提升.     

基于对话结构的多轮对话生成模型

目前,多轮对话生成研究大多使用基于RNN或Transformer的编码器-解码器架构.但这些序列模型都未能很好地考虑到对话结构对于下一轮对话生成的影响.针对此问题,在传统的编码器-解码器模型的基础上,使用图神经网络结构对对话结构信息进行建模,从而有效地刻画对话的上下文中的关联逻辑.针对对话设计了基于文本相似度的关联结构、基于话轮转换的关联结构和基于说话人的关联结构,利用图神经网络进行建模,从而实现对话上下文内的信息传递及迭代.基于DailyDialog数据集的实验结果表明,与其他基线模型相比,该模型在多个指标上有一定的提升.这说明使用图神经网络建立的模型能够有效地刻画对话中的多种关联结构,从而有利于神经网络生成高质量的对话回复.