An Evolutionary Algorithm Coupled to an Outranking Method for the Multicriteria Shortest Paths Problem

In this article, we are interested in solving a combinatorial optimization problem, the shortest path problem in a multi-attribute graph, by the out-ranking methods. A multi-attribute graph has simultaneously qualitative and quantitative criteria. This situation gives rise to incomparable paths thus forming the Pareto front. Outranking methods in Multi-criteria Decision Making (MCDM) are the only methods that can take into account this situation (incomparability of actions). After presenting the categories of Multi-criteria Decision Making (MCDM) and the difficulties related to the problems of the shortest paths, we propose an evolutionary algorithm based on the outranking methods to solve the problem of finding “best” paths in a multi-attribute graph with non-additive criteria. Our approach is based on the exploration of induced subgraphs of the outranking graph. Properties have been established to serve as algorithmic basis. Numerical experiments have been carried out and the results presented in this article.

k阶采样和图注意力网络的知识图谱表示模型

知识图谱表示(KGE)旨在将知识图谱中的实体和关系映射到低维度向量空间而获得其向量表示。现有的KGE模型只考虑一阶近邻,这影响了知识图谱中推理和预测任务的准确性。为了解决这一问题,提出了一种基于k阶采样算法和图注意力网络的KGE模型。k阶采样算法通过聚集剪枝子图中的k阶邻域来获取中心实体的邻居特征。引入图注意力网络来学习中心实体邻居的注意力值,通过邻居特征加权和得到新的实体向量表示。利用ConvKB作为解码器来分析三元组的全局表示特征。在WN18RR、FB15k-237、NELL-995、Kinship数据集上的评价实验表明,该模型在链接预测任务上的性能明显优于最新的模型。此外,还讨论了阶数k和采样系数b的改变对模型命中率的影响。

基于子图采样的大规模图对抗性攻击方法

为提高对抗性攻击在大规模图上的攻击效率,提出了基于子图采样的对抗样本生成方法.该方法通过引入PageRank、余弦相似度及K跳子图等技术,提取与目标节点高度相关的子图,在大规模图上缓解了计算梯度效率较低的问题,在降低被攻击模型准确性的同时提升了攻击的隐蔽性.实验结果表明:所提出的对抗性攻击方法与基于梯度攻击的GradArgmax算法相比,在Cora数据集上提升了30.7%的攻击性能,且在Reddit大规模数据上能够计算GradArgmax算法无法计算的攻击扰动.

动态图模式匹配技术综述

随着大数据时代的到来,多源异构数据的快速增长已经成为开放性问题,数据之间的内在关联通常可以用图数据的形式来表现.然而在实际应用中,例如网络安全分析和社交网络舆情分析,描述实体对象之间关系的图数据的结构和内容往往不是固定不变的,图数据的结构以及节点和边的属性会随着时间的推移发生更新变化.因此,如何在动态更新的图数据中进行高效的查询、匹配,是目前研究的热点问题.从关键技术、代表性算法和性能评价方面概述动态图模式匹配技术的研究进展.最后,对动态图模式匹配技术的典型应用、面临的挑战问题和未来发展趋势进行了总结和展望.

基于蚁群算法的三维CAD模型检索

为了更好地实现CAD模型的重用,提出一种利用蚁群算法的三维CAD模型检索算法.通过提取CAD模型的B-rep信息,将模型用属性邻接图来表示;根据如果2个CAD模型存在相似的特征或局部结构,那么CAD模型对应的属性邻接图就应存在公共子图这一原理,利用蚁群算法来检测属性邻接图中的公共子图,从而得到2个CAD模型相似的局部细节特征;然后通过比较相似局部细节特征对CAD模型进行相似性评价.实验结果表明,该算法能较好地实现三维CAD模型检索,检索性能高于通用领域的检索算法,可以实现CAD模型设计和制造知识的重用.

小世界电力网络故障传播过程与抑制策略

为抑制小世界电力网络中的连锁故障的规模,根据电力网络的连锁故障传播模型,分析了故障在小世界电网中的传播特性,指出连锁故障是传播范围扩散与传播强度累积共同作用的结果,故障在高聚类区域的反复感染是引发雪崩现象的关键。提出了一种新的连锁故障抑制策略,综合考虑故障时刻电力网络的整体状态与初始故障的具体特征,通过切除少量低负荷的节点,减少高聚类区域的负荷波动,抑制故障传播强度的持续累积,降低连锁故障的规模。仿真实验结果证明,该方法可以降低系统的阀值条件,防止连锁故障的扩散。

现代物流系统中基于频繁子图的RFID路径挖掘算法

为研究射频识别物流挖掘中数据的存储方法,以及基于此类数据集的频繁路径的挖掘,提出基于图的联机分析处理架构,用图来表示物品流动的路径信息,在此基础上提出了基于射频识别数据的频繁子图挖掘算法,来对射频识别频繁路径数据进行挖掘。实验结果与算法分析都表明,基于射频识别数据的频繁子图挖掘算法能够快速有效地挖掘物流频繁子图集。

复杂网络中随机图模型研究

随着复杂网络研究的兴起,随机图成为一种重要复杂网络模型。基于完全图的生成子图的思想,得到了生成随机图的一种新算法,即用去边的方法生成随机图的算法,并用数值实验验证了加边和去边生成的随机图的统计特性(最大度、最小度、聚集系数、平均最短路径和平均度)是相近的,用去边的方法得到的图的度分布曲线在其平均度处达到峰值,随后呈指数下降,这与随机图的度分布是相同的。为了得到稀疏连通的随机图,又提出了一个不去割边的近似随机图生成算法,并从理论上说明了该算法生成的图是连通的,同时通过数值实验验证了图的连通性,并与加边随机图的统计特性进行了比较。

Tomato leaf curl Bangladesh病毒完整基因组上微卫星分布

为了展示Tomato leaf curl Bangladesh病毒完整基因组上的微卫星分布特性。借助MATLAB软件、应用最优完全子图算法,提取并展示NCBI数据库中Tomato leaf curl Bangladesh病毒完整基因组(AF_188481.1)上的微卫星分布特性,计算1-碱基组至6-碱基组在完整基因组序列上重复出现的次数和位置,展示它们的分布规律(指数函数)。结果表明:Tomato leaf curl Bangladesh病毒完整基因组(AF_188481.1)上各种N-碱基组(N取1至6)最大的重复出现次数,随N按指数函数数减少;笔者提取和展示Tomato leaf curl Bangladesh病毒完整基因组序列微卫星分布特性(特别是微卫星各种N-碱基组重复出现的位置和次数)的方法,可以系统地运用到其他病毒完整基因组序列微卫星分布特性的提取和展示中,从而为有效利用微卫星分布特性研究完整基因组的结构和功能、遗传和变异规律提供完备、仔细的数据支撑。

一种三维CAD模型局部匹配算法

针对现有的三维计算机辅助设计模型检索算法难以实现局部结构匹配的问题,提出一种利用蚁群算法来实现三维计算机辅助设计模型局部匹配的方法。提取模型的B-Rep信息,将局部结构和计算机辅助设计模型分别用属性邻接图来表示;利用蚁群算法实现局部结构和计算机辅助设计模型属性邻接图中的公共子图检测,并根据公共子图得到计算机辅助设计模型中包含的局部结构;通过比较欲检索的局部结构和计算机辅助设计模型所包含的局部结构,实现模型局部相似性评价。实验结果表明,该算法可以实现三维计算机辅助设计模型局部匹配,检索效率满足工程检索的要求。

基于双链遗传算法的复杂特征识别方法研究

子图匹配问题是典型的非多项式算法问题,但又是基于图的特征识别方法的基础,导致目前提出的基于图的特征识别方法很难实现交叉特征识别、包含凸边的特征识别等问题。针对特征识别的需求,提出了一种双链遗传算法。该算法采用双链结构描述特征识别问题的染色体,一条链描述面信息,另一条描述特征对于面的分割。同时根据双链的特点,定义了双链染色体的交叉、变异、选择、半表留复制等运算。实验证明双链遗传算法具有解决特征识别的可行性,且结果较其他特征识别方法识别特征范围更广和可以合并被分割的特征、识别包含凸边的特征等优点。

子图估算PageRank网页排序算法研究

针对传统PageRank算法难以高效处理Web图数据网页排序问题,文章在不牺牲准确度的前提下,提出一种在MapReduce平台上基于改进PageRank的加速算法:top K-Rank.为识别出排名为前k的网页,通过在迭代过程中裁剪掉不必要的节点及边的形式,动态构建子图,由子图迭代计算出PageRank值的上下限。理论分析和实验结果表明:该算法不仅可以保证结果的准确性,还可以更快地找到用户所需网页数。

从不确定图中发现K紧密子图

由蛋白质交互网络、社会网络及无线通信网络构成的图中存在许多不确定性。如何高效获取不确定图中有价值的信息,如蛋白质网络中关键的功能集团、社会网络中适于投放广告的团体及通信网络中应重点维护的区域等,具有重要的现实意义。从理论上证明了在不确定图中发现最紧密子图问题具有NP-Hard复杂性;基于树搜索策略提出了通过枚举解空间及剪枝获得最优解的算法TreeClose;针对树搜索算法TreeClose在处理大图时空间复杂度过高的问题,提出了基于贪心思想的2-近似算法GreedyClose。实验结果表明,通过上述算法可以高效快速地在不确定图中发现紧密子图,从而解决在实际应用中遇到的各种问题。

马铃薯X病毒完整基因组上微卫星分布

本文利用自编计算机程序提取并展示马铃薯X病毒完整基因组(NC_011620.1)上微卫星分布特性。借助MATLAB软件和借用最优完全子图算法,分析NCBI数据库中该基因组(NC_011620.1)微卫星分布特性。结果表明,计算出所有各种N-碱基组(N取1至6)在完整基因组序列上重复出现次数和出现位置,展示它们的分布规律(指数函数),马铃薯X病毒完整基因组(NC_011620.1)上各种N-碱基组最大的重复出现次数随N按指数函数数减少;且呈现出重复出现次数由少到多排序,重复出现次数随序号增加;本文使用的方法,可以系统地应用到其它病毒完整基因组序列微卫星分布特性分析,从而为有效利用微卫星分布特性研究完整基因组的结构和功能、遗传和变异规律提供完整的数据支撑。

一种新的频繁子图挖掘算法

传统Aprior频繁子图挖掘算法中存在大量冗余子图。针对该问题,提出一种新的频繁子图挖掘算法(GAI)。介绍一种三层MADI索引结构,用于存储图集的信息,以减少图集的扫描次数,通过扩展ETree树构造频繁子图,并用表来存储候选子图,避免扩展过程中冗余图的产生以及对整个数据库的扫描,从而简化支持度的计算,提高图/子图同构的查询效率。实验结果表明,与Aprior算法相比,GAI的挖掘效率更高。

图的最大公共连通子图问题研究

图像识别、恶意代码族群特征提取、人工智能中许多应用问题都可以规约为一类图的最大公共连通子图问题。提出了求解简单最大连通子图问题的矩阵方法,定义了图特征相关度和图度序列相关系数的概念,最后结合算例给出了一种求解一般最大公共连通子图问题的贪婪算法,能够快速有效地找到一个尽可能大的公共连通子图。

挖掘不确定频繁子图的改进算法的研究

鉴于图结构能简单方便地描绘复杂的数据以及实际应用中图数据的获得具有不确定性,不确定频繁子图挖掘算法得到广泛的研究。目前一个典型的图挖掘算法是MUSE,但MUSE算法存在期望支持度计算消耗大、时间效率不够高等问题。针对此问题提出了一种基于划分思想混合搜索策略的不确定子图挖掘算法EDFS,它用改进过的GSpan算法进行不确定的子图数据预处理,用裁剪子图模式的搜索空间裁剪不确定子图数据,用基于划分思想的混合策略进行频繁子图的挖掘。子图同构与边存在概率的实验结果证明了EDFS算法能更高效地挖掘出不确定数据频繁子图。

基于子图同构的子电路提取算法

从门级到功能模块级的子电路提取问题在大规模集成电路计算机辅助设计领域有广泛地应用,提出了基于子图同构的方法来解决该问题。针对子电路的特征,选择辐射路匹配和赋标号算法之一作为搜索的主算法。尽管子图同构问题是NP完全问题,算法对实际的电路是快速的,满足工程需要。

宽度优先的频繁子图高效挖掘新算法

频繁子图已成为数据挖掘领域研究的热点之一。在经典的Apriori算法的基础上,提出了一种图挖掘的新算法Apriori-Graph。首先给出了一种新的、用于计算图的邻接矩阵规范编码的结点排序策略,大大降低了求图规范编码的复杂度,并可加速子图规范编码序列匹配的速度。其次,对候选子图的生成进行了规范。最后,针对频繁性检验这一瓶颈过程,给出了若干性质,从而较大地降低了候选子图频繁性判断的代价。实验结果表明,Apriori-Graph算法具有较高的挖掘效率。

一种高效挖掘生物网络闭合频繁子图的算法

针对生物网络中频繁子图的挖掘问题,提出了一种基于FP-树结构的MaxFP算法。此算法以代谢路径作为研究对象,在适合于生物网络图简化模型的基础上,采用一种不产生候选集的改进FP-growth算法挖掘生物网络中的闭合频繁子图。此算法考虑了基于频繁项目集的算法应用于网络的缺陷,根据生物网络的特点对FP-growth算法进行了改进。实验证明,提出的MaxFP算法比基于Apriori的频繁模式挖掘算法运行速度快,不仅能挖掘出最大的频繁子图,且能找到更多具有生物意义的频繁子图。