基于图的数据挖掘算法研究

对图数据频繁模式的挖掘是近年的研究热点,而从图数据库中挖掘频繁模式的关键是子图测试和候选子图生成操作。与传统广泛研究的频繁项集、频繁序列、频繁子树挖掘相比较,频繁子图的挖掘更复杂、更有难度,因为图同构问题是一个NP-完全问题。因此,必须有个好的规范化编码和有效的算法来避免子图同构这个难题。     

ε≥（γ—1／2）—1的简单图的哈密顿分类

研究了γ阶（γ，γ－ｋ）图和Ｃｙ的包装问题，对边数ε≥γ－１／２）－１的简单图进行了哈密顿分类，得到了全部的非哈密顿图，由此推广了Ｏｒｅ和Ｂｏｎｄｙ关于此类问题的结果。     

基于快速图挖掘的网络拓扑局部调节区域算法

针对IP骨干网重新配置中繁重工作量的问题,提出一种快速图挖掘算法来解决网络拓扑的局部调节区域问题,解决了从网络拓扑中找到组件时子图同构的NP-hard问题,减少了网络重构的操作工作量.该文提出的启发式图挖掘算法顶点,称为顶点目标搜索(vertex targeting search,VTS)算法,通过考虑网络操作条件减少了搜索空间的大小.实验结果表明,该文方法可以快速得到搜索网络模式图,与其他方法比较,该文具有较少的搜索时间,说明该文方法具有可行性和有效性.     

基于标准编码的有向标记频繁子图挖掘算法

针对大部分频繁子图挖掘算法,基于无向图而不适用于更具有实际意义的有向图的挖掘的现状,通过对无向图挖掘算法gSpan中编码结构的扩展,采用改进的规范形式,使编码适用于有向图领域。并使用针对有向图的DADI++存储结构来存储图集,简化了数据访问操作的代价。另外在挖掘中使用Hash表存储同构图的Hash地址和支持度,避免对图集的重复扫描和直接的同构测试。在实际数据集上运行的实验结果表明提出的Dspan算法是正确的,并比FFSM算法效率更高。     

基于图Transformer网络的城市路网短时交通流预测模型

针对城市路网短时交通流预测问题,在考虑路网交通状态时空相关性基础上,提出一种基于图Transformer（graph transformer,Graformer）的预测方法。该方法将多条路段的交通状态预测问题转化为图节点状态预测问题,针对区分相同结构的空间路网结构图,本文将带有边的图同构网络（graph isomorphism network with edges,GINE）和Transformer网络相结合,对交通状态在路网层面的时空相关性进行建模,从而实现城市路网短时交通流预测。具体来说,Graformer模型首先利用长短期记忆网络（long short-term memory,LSTM）对交通数据的时序信息进行预处理,接着采用基于GINE与Transformer的全局注意力机制提取交通数据的空间特征,最后实现路网各路段交通流的同步预测。通过使用PeMS数据集进行实验验证,结果表明提出的Graformer模型在各项性能指标上均优于对比模型,证明了其作为一种可靠且高效的路网短时交通流预测方法的有效性。     

一种新的犯罪团伙挖掘算法

为了利用图模式挖掘犯罪情报网络中的核心团伙和核心人物,提高犯罪网络威胁预测和识别的效率,提出一种新的核心团伙挖掘算法(Core Gang Mining Algorithm, CGMA).对海量的犯罪情报网络数据集建立相应的无向简单图模型,通过改进图挖掘方式,构建候选核心团伙集的数据结构,并提出由k-团伙通过连接和扩展2种操作得到(k+1)-团伙,从各个不同的图数据中统计其频度,最后在模拟数据集和真实数据集上验证算法CGMA的准确性和时间复杂度.该算法避免了传统的图模式挖掘中的子图同构问题,同时也优于其他常用的犯罪团伙挖掘算法.试验结果表明：该算法能对犯罪核心团伙信息进行有效预测.     

统计网络Motif方法的研究与设计

在分析挖掘一个网络中的信息时,一个非常重要的信息就是统计Motif.现有算法是将原始网络在给定的条件下进行边与顶点转换,再从转换后的网络中找出所有子图,如果子图不满足Motif的要求则删除,存在时间复杂度过高的问题.针对这种情况,提出了一种自底向上的剪枝算法,在不需要经过网络转换的前提下,首先找到最小的符合要求的子图,再推导出更大的子图,而且所找到的每个子图均满足Motif的要求.并通过时间效率分析得出,对于该问题而言,提出的算法优于现有的算法,具有一定的理论研究价值.     

一种对称无向图的同构判定算法

文章在电路模拟法的基础上提出了一种对称无向图的同构判定算法。电路模拟法对随机图的同构判定问题非常有效,但是对于处理对称度较高的图,判定效率明显降低甚至失效。该文提出的算法针对对称无向图的特性,在电路模拟法的基础上结合Dijkstra算法,综合得到顶点属性和最短距离序列来搜索顶点之间的映射关系,能够有效判定这类图的同构问题。     

基于子图同构的前驱三维工序模型向二维工序图映射匹配算法

为满足企业对三维工序模型的迫切需求，解决前驱三维工序模型与工序图的映射匹配问题，提出一种基于子图同构的前驱三维工序模型向二维工序图的映射匹配算法．该方法首先对三维工序模型进行投影，获取其投影图；然后分别提取工序图与投影图中的图元信息，将其表示为以图元作为节点的属性邻接图．在映射匹配过程中，将投影图表示成“大图”，工序图表示成“子图”；将前驱三维工序模型向二维工序图的映射匹配问题转化为“大图”中寻找“子图”的问题．为提高匹配效率，对属性邻接图进行分割，并且充分利用图的顶点属性对图顶点进行有效细分．实验结果表明，该算法能够实现精确的匹配，并且匹配效率能满足实际应用要求．     

支持增量图数据的超图查询算法研究

当前大部分图查询算法都是针对静态图数据,不适用于现实应用中不断更新的图数据。针对这一问题,提出支持增量图数据的超图查询算法。该算法将数据图分解成直至单个顶点的子图,然后从单个顶点的子图开始求它到查询图的子图同构,直到求出数据图到查询图的子图同构结果,算法在数据图增加时只需将新加入的数据图进行分解即可,不必重新计算。通过分析证明,所提算法时间和空间复杂度不随数据图的增加而呈线性增长,节省了大量时间和空间代价。