一种基于极大完全子图的最大频繁项集并行挖掘算法

提出一种基于极大完全子图的最大频繁项集并行挖掘算法PMFIM,通过遍历由频繁2-项集构成的用邻-接矩阵表示的图,寻找图的极大完全子图,从而由极大完全子图顶点序列实现对项集的划分,即挖掘子任务的划分.在同类算法中,将找到的最大频繁项划分为局部最大频繁项集LMFI、可能最大频繁项集PMFI和邻接项集的最大频繁项集的超集SMFI,减少了该类算法合并最大频繁项集的开销,并对算法进行了实现和优化.     

一种基于图立方体的移动对象网络压缩算法

针对大规模移动对象网络在构建图立方体的过程中产生的大量浓缩图,引入了图压缩的思想,提出了进一步压缩浓缩图的算法MC-compress,用来合并浓缩图中顶点和相应的边.通过将图中相邻的两个顶点进行合并,再比较两条边合并后权重的最大差异度,从而找出最优的合并顶点对,最终产生构建压缩图的超级顶点和超级边.通过压缩图结构,加快了在图立方体上查询图结构的显示过程,减少了构建图立方体过程中存储大量浓缩图的空间.     

基于有界增长图的无线传感器网络虚拟骨干形成算法

提出了基于有界增长图的虚拟骨干近似形成算法(VBF).算法采用网络划分机制构建极大独立集,使用染色过程形成簇图;以2分离集合子集递归计算(1 ε)近似局部最小支配集,合并局部最优解构造全局最优解:然后调整簇头传输范围直接以全局最优解形成最小近似连通支配集,无须加入网关节点,降低计算开销.构造的连通支配集具有常量扩展因子和常量度,并且算法运行时节点仅需直接邻域信息.理论分析和仿真比较证明了算法的正确性和有效性.     

DisHAP:基于层次亲和聚类的分布式大图划分算法

平衡图划分是改善并行图计算性能的关键.一个良好的划分算法应保证划分后的子图在负载均衡的前提下,减少子图之间的交互边(切割边)规模,从而减少网络通信.对此,本文设计一种基于层次亲和聚类的分布式大图划分算法(DisHAP).该算法采用亲和聚类的思想,将图初始划分为规模相等的k个子图;再将结果映射成顶点序列,以线性嵌入顺序处理节点,通过局部交换策略优化割边率;最后将DisHAP应用在MapReduce框架中,使用多种真实及理论图数据,与现有的大图划分算法做比较分析.以Twitter图为例,划分2,4,8,16,32个子区,相较于现有的大图划分算法(LDG,BLP,Spinner,Fennel,ParMetis及PSA-MIR算法),割边率减少1.7％～30.2％,说明了该算法的优越性.同时该算法具有良好的可扩展性,划分的子区数量及图的规模对划分时间具有较低的影响.     

基于图割的单水平集迭代终止算法

针对C-V模型中变分水平集优化方法存在的最佳迭代次数难于确定,且容易陷入局部最优等不足,借鉴图割算法在较短时间内能得到全局最优的优势,提出一种基于图割的单水平集迭代终止算法.首先在目标区域设定一条初始轮廓线,采用无须重新初始化的C-V模型对轮廓线进行迭代,当轮廓线内部面积变化值小于预先给定的阈值时终止迭代,然后将此轮廓线作为图割算法的初始轮廓线进行图像分割.实验结果表明,该方法较原始C-V模型大大缩短了迭代时间,稳健性更高,具有较好的图像分割效果.     

求二部图的最大匹配图的一种算法

 一个图的最大匹配图是以这个图的最大匹配集作为顶点集,两个顶点相邻当且仅当这两个最大匹配恰有一条边不同.本文首先对Gallai Edmonds结构定理中的三部分顶点在二部图中进行了详细刻画.然后讨论了构造最大匹配图问题的计算复杂性.最后深入研究了二部图最大匹配图的结构性质并给出了构造二部图的最大匹配图的一种算法.     

一种基于图割的全变差图像去噪算法

本文提出一种基于图割的全变差(TV)图像去噪算法.该算法将全变差去噪模型的能量函数最小化问题转化为图的最小割问题,然后采用图割技术(最大流/最小割算法)求得能量函数的全局最优解.并给出了去噪模型中,均衡系数的自适应设定方案.实验结果及分析表明,该算法能有效抑制以往最小化方法产生的阶梯效应,具有较优的复原效果.     

基于FPGA的图着色问题求解

图着色问题是在满足相邻顶点不能分配相同颜色且颜色数最少的约束条件下,将图的顶点划分为不相交的集合,且每个集合中的顶点分配相同的颜色。由于图着色问题属于NP-完全问题,求解图着色问题的算法复杂度会随顶点个数的增加呈指数级增长。当顶点个数非常大时,通用处理器求解图着色问题的性能将会显著下降。因此,该文基于现场可编程逻辑门阵列(FPGA)实现求解图着色算法的专用硬件加速器。首先依据FPGA模块化的设计思路提出并实现了基于回溯法的图着色问题求解的硬件架构;其次分析了FPGA内部消耗资源与图着色顶点数之间的关系;最后利用通用异步收发传输器协议实现了通用处理器与FPGA的通信。实验结果表明,相比于在通用处理器上利用软件实现图着色算法,基于FPGA所实现的图着色算法运行时间减少了一个数量级。除此之外,FPGA内部消耗资源数与顶点个数呈线性关系,且每次迭代时FPGA运算所消耗的时间与顶点个数无关。     

基于DNA折纸术求解图的顶点着色问题的方法

该文基于DNA折纸术,设计了一个通过DNA折纸结构的自组装求解图的顶点着色问题的方法.利用DNA折纸术可以构建出具有特定形状的DNA折纸结构.这些结构可以用来编码图的顶点和边,由于这些结构具有粘性末端,因此可以通过特异的分子杂交组装成为代表了不同的图的顶点着色方案的高级结构.利用DNA-纳米颗粒共聚体的属性和电泳等实验方法,可以筛选出正确的符合条件的图的顶点着色方案.该方法是一种高度并行的方法,可以极大地降低求解图的顶点着色问题的复杂度.     

一种基于图论的RFID防冲突建模与优化方法

针对RFID系统的超高频段、多读写器的静态拓扑结构,研究了读写器冲突问题,并提出了一种图论的图着色算法与遗传算法相结合的防冲突干扰方法.该静态预定义算法对读写器冲突建立图论模型,将读写器时隙分配问题转化为图论模型的K-顶点着色问题,优化遗传算法并用于求解图的K-顶点着色问题,求得最小时隙数和最优时隙分配方案.最后将算法应用于算例.实验结果表明该方法可行、实用,能够有效地防止读写器冲突干扰.     

基于图卷积网络的手指静脉识别方法研究

针对传统手指静脉识别方法往往存在识别率低或者计算量大等问题，本文提出一种基于轻量型图卷积网络的手指静脉识别方法。首先用一个加权图描述一张手指静脉图像，图的顶点特征和加权边集分别由指静脉图像的局部方向能量特征和特征间相关性确定。图数据作为输入，经过基于切比雪夫多项式的图卷积层和由图粗化协助的快速池化层，然后全连接层进行特征整合，再进行分类识别。实验结果显示，该方法识别效率远高于传统算法，并在实验室自制手指静脉数据库达到96.80%的识别率，在不同数据库有较好的普适性。      

加权T图的几种化简运算

本文首先给出加权Ｔ图的几种化简运算，然后证明这几种运算于网的某些结构性质保持不变，从而为加权Ｔ图的化简及综合提供了有效途径。     

由Signless Laplacian谱确定的一类奇单圈图

为了探讨一类奇单圈图的Signless Laplacian谱惟一的的问题,利用图与其线图之间的关系,图与其多项系数之间的关系以及图与其同谱图之间的关系,证明了Signless Laplacian同谱图的一个重要的的结构,即:恰含一个奇单圈图的Signless Laplacian同谱图也是一个连通奇单圈图。在此基础上证明了一类奇单圈图的Signless Laplacian谱惟一性,确定了此类奇单圈图的结构。     

基于图论的人脸图像数据降维方法综述

近几年基于图论的降维方法越来越得到人们的关注,本文针对人脸识别中的核心问题即对高维数据进行降维的目的,首先介绍了有关图论的基本概念,通过总结各种人脸图像降维的方法,将这些方法统一到图嵌入框架中。然后结合线性与非线性的角度分析了各种算法的优缺点,得出了非线性图嵌入算法在挖掘人脸图像中的非线性特征以及在数据降维方面均优于传统的方法。最后针对现有的构图方式所存在的问题对今后的研究与发展方向进行了讨论。     

有向图上k步可达查询处理

给定一个有向图,一个k步可达查询u→?kv用来回答在该图中是否存在一条从顶点u到顶点v且长度不大于k的有向路径。k步可达查询是一种基本的图操作并在过去十年间被广泛地研究。已有的k步可达查询算法仍存在许多弊端,例如不可达查询效率低,索引规模大和索引构建时间长等。本文针对上述问题提出了2种优化方法,分别是基于互逆拓扑序号以及基于等价顶点的图压缩方法.前者提高了不可达查询的效率,后者减少了索引规模和索引构建时间。实验结果表明,本文提出的方法可以有效地处理k步可达查询,并支持大规模数据的处理。     

图嵌入方法与应用:研究综述

图模型越来越广泛地应用于数据管理、知识发现和信息服务等问题中,图嵌入作为图分析和应用的重要技术手段,成为了人工智能领域研究的热点之一.本文从图嵌入研究中面临的挑战出发,主要介绍了基于矩阵分解、基于随机游走和基于深度学习的图嵌入方法.接着,介绍了图嵌入方法常用的测试数据集、评测标准和典型应用.最后,总结了图嵌入未来研究的趋势和方向.     

图表示下的知识约简

 知识约简主要有代数表示下的知识约简和信息表示下的知识约简.本文提出图表示下的知识约简,给出图表示下求最小约简的完备递归算法.借鉴人工智能理论中的图搜索技术,提出旋转剪枝和回溯剪枝两个搜索算子求最小约简,并证明了在这种表示下求最小约简的完备性,理论分析和实验结果表明,在图表示下求最小约简是有效可行的.     

论图的坚韧度（Ⅰ）——基本理论

本文首先指出坚韧度是可以用来刻划图的连通性，因而能广泛地应用于通讯网络可靠性等有关领域的研究，进而，研究了坚韧度的自身特性，诸如取值范围、存在性问题、计数问题以及计算问题等。     

Research of RFID anti collision algorithm based on

针对射频识别技术（R．FID）存在多个阅读器同时传输数据容易产生冲突的问题,提出了一种基于图染色理论的防止冲突的算法。该算法利用图的染色算法将可能存在冲突的阅读器染成不同的颜色,使得每种不相同的颜色不能同时获得相同的时隙,降低了多个阅读器同时传输数据产生冲突的可能性。分析表明：采用该算法明显地降低了阅读器之间的冲突率,同时得到最小的时隙数,提高了信道利用率,为R-FID防冲突算法提供了一种新的解决方案,同时为基于TDMA的广播调度模式也提供了一种新的时隙分配方式。