基于邻居向量的近似子图匹配

将近似子图匹配分成节点匹配和边匹配两个阶段。将数据图中所有节点的h-邻居节点表示成向量形式,采用一种启发式推理算法进行节点匹配得到节点对应关系,使用查询节点权重提高匹配相似度,使用节点过滤、索引技术和孤立候选节点提高运算效率;利用邻居向量索引得到匹配节点集合的扩展图,进行边匹配,得到匹配图。在真实数据上进行实验,实验结果表明,该算法效果较好,运算效率较高,可以应用于节点标签稀疏的情况和top-k近似匹配。     

基于三角形子图的复杂网络过滤压缩算法

为高效地挖掘和分析复杂网络,提出一种基于三角形子图的复杂网络过滤压缩算法NIIET。设计一种节点重要性排序算法NRSA选取高、低重要性节点并进行过滤,以降低计算规模并缩短压缩时间。列出边两端的节点及其共同节点集组成三角形子图集合,在此基础上,解析三角形子图集合完成复杂网络压缩。实验结果表明,NRSA算法的排序结果合理且可靠,相对Node_iterator算法,NIIET算法能够缩短压缩时间,提高压缩率,且能保留原网络的大部分结构和信息。     

图近似查询算法研究

从数据管理中的近似查询方向,对图数据的近似查询算法进行了研究.依据近似查询的类别,分别介绍了近似查询中的经典算法,并对这些算法进行了详细的分析和讨论,从索引单元以及索引机制比较了各种算法适用的范围以及应用领域.重点阐述和比较了各算法的特点及查询性能,分析了各个算法存在的优势和不足.对近似查询中现有算法的不足及未来的研究方向进行了讨论.     

基于图常量条件函数依赖的图修复规则发现

数据一致性是数据质量管理的一个重要内容。为了提升图数据一致性,大量关系型数据库中的数据依赖理论被引入到图数据库,包括图函数依赖、图关联规则等。图修复规则是最新提出的一种针对图数据的数据依赖规则,具有强大的修复能力,但目前尚无有效的挖掘算法。为了自动生成图修复规则并提高图数据修复的可靠性,提出一种将图常量条件函数依赖转化为图修复规则的方法(GenGRR)。通过图模式在图中匹配同构子图并映射成节点-属性二维表,从表中相应属性域中抽取错误模式把图常量条件函数依赖转化成图属性值修复规则;删去图模式中常量条件函数依赖RHS对应的节点与相连边生成图属性补充规则。基于最大公共同构子图筛选并验证生成图修复规则的一致性。在多个真实数据集上进行测试,验证相比图常量条件函数直接修复图数据,通过转化生成的图修复规则具有更好的修复效果。     

一种针对单快拍DOA估计的子空间搜索近似消息传递算法

压缩感知（Compressed sensing,CS）技术应用于单快拍波达方向（Direction of arrival,DOA）估计中可以实现相关信号的超分辨估计,但会遇到感知矩阵高相干性以及对噪声敏感的问题.本文提出一种基于近似消息传递的子空间搜索算法以解决上述问题.该算法首先通过近似消息传递算法得到一个粗解,随后利用该粗解划分子空间,最后在子空间中寻找精确解.仿真结果验证了所提算法的有效性.文章最后通过理论分析了该算法性能并讨论了算法在信号数未知时的扩展应用.     

基于双索引的近似子图匹配

越来越多的大型复杂网络使得图结构的研究变得日益重要,其中近似子图查询备受关注。为了提高查询效率,利用顶点的邻接关系特征为每个顶点建立索引,减少了匹配顶点的数量;并基于结构和标签对大型数据图进行划分,缩小了匹配时的搜索空间。利用离线时建立的双索引,查询时首先利用顶点间的近邻关系判定公式过滤掉大量不满足匹配关系的候选顶点,然后在一定的划分空间中进行边的匹配。真实数据集中的实验表明,与单纯的划分方法或近邻关系索引相比较,双索引机制对于查询的效率和准确率方面均有明显改善。     

基于核保持嵌入的子空间学习

子空间学习是特征提取领域中的一个重要研究方向,其通过一种线性或非线性的变换将原始数据映射到低维子空间中,并在该子空间中尽可能地保留原始数据的几何结构和有用信息.子空间学习的性能提升主要取决于相似性关系的衡量方式和特征嵌入的图构建手段.文中针对子空间学习中的相似性度量与图构建两大问题进行研究,提出了一种基于核保持嵌入的子空间学习算法(Kernel-preserving Embedding based Subspace Learning,KESL),该算法通过自表示技术自适应地学习数据间的相似性信息和基于核保持的构图.首先针对传统降维方法无法挖掘高维非线性数据的内部结构问题,引入核函数并最小化样本的重构误差来约束最优的表示系数,以期挖掘出有利于分类的数据结构关系.然后,针对现有基于图的子空间学习方法大都只考虑类内样本相似性信息的问题,利用学习到的相似性矩阵分别构建类内和类间图,使得在投影子空间中同类样本的核保持关系得到加强,不同类样本间的核保持关系被进一步抑制.最后,通过核保持矩阵与图嵌入的联合优化,动态地求解出最优表示下的子空间投影.在多个数据集上的实验结果表明,所提算法在分类任务中的性能优于主流的子空间学习算法.     

基于核保持嵌入的子空间学习

子空间学习是特征提取领域中的一个重要研究方向,其通过一种线性或非线性的变换将原始数据映射到低维子空间中,并在该子空间中尽可能地保留原始数据的几何结构和有用信息.子空间学习的性能提升主要取决于相似性关系的衡量方式和特征嵌入的图构建手段.文中针对子空间学习中的相似性度量与图构建两大问题进行研究,提出了一种基于核保持嵌入的子空间学习算法(Kernel-preserving Embedding based Subspace Learning,KESL),该算法通过自表示技术自适应地学习数据间的相似性信息和基于核保持的构图.首先针对传统降维方法无法挖掘高维非线性数据的内部结构问题,引入核函数并最小化样本的重构误差来约束最优的表示系数,以期挖掘出有利于分类的数据结构关系.然后,针对现有基于图的子空间学习方法大都只考虑类内样本相似性信息的问题,利用学习到的相似性矩阵分别构建类内和类间图,使得在投影子空间中同类样本的核保持关系得到加强,不同类样本间的核保持关系被进一步抑制.最后,通过核保持矩阵与图嵌入的联合优化,动态地求解出最优表示下的子空间投影.在多个数据集上的实验结果表明,所提算法在分类任务中的性能优于主流的子空间学习算法.     

基于子空间学习的图稀疏属性选择算法*

针对处理高维度属性的大数据的属性约减方法进行了研究。发现属性选择和子空间学习是属性约简的两种常见方法,其中属性选择具有很好的解释性,子空间学习的分类效果优于属性选择。而往往这两种方法是各自独立进行应用。为此,提出了综合这两种属性约简方法,设计出新的属性选择方法。即利用子空间学习的两种技术(即线性判别分析(LDA)和局部保持投影(LPP)),考虑数据的全局特性和局部特性,同时设置稀疏正则化因子实现属性选择。基于分类准确率、方差和变异系数等评价指标的实验结果比较,表明该算法相比其它对比算法,能更有效的选取判别属性,并能取得很好的分类效果。     

基于幂图的离群子空间搜索算法*

通过分析子空间搜索算法的研究现状以及存在的问题,提出基于幂图的离群子空间搜索算法。该方法主要讨论离群点产生的原因,能够找出单个对象的离群子空间,并根据离群子空间对离群点进行分类。在对幂图扩展的基础上进行剪枝,减少了存储量和计算量,算法性能得到很大的提高。采用实例说明了该算法,并通过实验证明了该算法的可行性和高效性。     

一种高效频繁子图挖掘算法

由于在频繁项集和频繁序列上取得的成功,数据挖掘技术正在着手解决结构化模式挖掘问题--频繁子图挖掘.诸如化学、生物学、计算机网络和WWW等应用技术都需要挖掘此类模式.提出了一种频繁子图挖掘的新算法.该算法通过对频繁子树的扩展,避免了图挖掘过程中高代价的计算过程.目前最好的频繁子图挖掘算法的时间复杂性是O(n³·2ⁿ),其中,n是图集中的频繁边数.提出算法的时间复杂性是O〔2ⁿ·n^2.5／logn〕,性能提高了O(√n·logn)倍.实验结果也证实了这一理论分析.     

一种频繁子图挖掘算法

为减少频繁子图规范化检测的时间复杂度,对规范化邻接矩阵的相关性质进行分析。给出相关定理并证明其正确性,从而减少冗余候选子图的产生。在此基础上,提出一种频繁子图挖掘算法——FSM_CAM。实验结果证明,与现有频繁子图挖掘算法FSubGraphM相比,FSM_CAM算法的效率较高。     

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

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

子图同构验证算法OES

提出一种新的子图同构验证算法OES,采用逐条边验证的方法寻找子图同构映射,以确定查询图是否为某个数据图的子图,通过调整边的验证顺序,提高算法的执行效率。给出一种为查询图的边打分的方法,每条边的得分越低,表明其剪枝效率越高,按照分数由低到高的边序验证可以取得较好的验证效率。     

频繁子图挖掘算法研究

图像能表达丰富语义,但增加了数据结构的复杂性和感兴趣子结构的挖掘难度。综合应用图论知识和数据挖掘的各种技术,对图像进行规范化编码,通过连接和扩展操作产生所有候选子图,引用嵌入集概念,计算候选子图的支持度和频繁度。提出频繁子图挖掘算法FSubgraphM,能从图数据库中挖掘频繁导出子图。     

基于出行模式子图的城市功能区域发现方法

城市的功能区域是指在城市的发展过程中逐渐形成的功能(如工业、商业、居住、教育等)相对固定的地理区域。这些区域间的位置结构影响着城市中居民的出行模式,与此同时,城市居民的出行模式也客观地反映了城市不同区域的真实的功能定位。文中以出租车运行轨迹数据为基础,研究城市居民的出行模式,并根据所得模式实现城市功能区域的自动化发现。主要思路及贡献包括:1)使用车辆轨迹及路网结构数据构造区域模式图(region pattern graph)结构,并提出区域模式图构建算法,采用图结构将城市的不同地理区域连接起来;2)提出自底而上的功能区域发现算法(Bottom-Up Functional Region Discovering,BUFRD)框架及基本实现思路,包括提出频繁出行模式子图挖掘算法,发现区域模式图中频繁出现的出行模式;3)提出功能区域聚类算法,聚类已获取的出行模式子图集,并最终实现城市功能区域的发现。实验结果表明,通过所提方法发现的城市功能区域较传统方法所得结果的功能纯度更高,其熵值比传统方法降低了至少10%。     

从不确定图中挖掘频繁子图模式

研究不确定图数据的挖掘,主要解决不确定图数据的频繁子图模式挖掘问题.介绍了一种数据模型来表示图的不确定性,以及一种期望支持度来评价子图模式的重要性.利用期望支持度的Apriori性质,给出了一种基于深度优先搜索策略的挖掘算法.该算法使用高效的期望支持度计算方法和搜索空间裁剪技术,使得计算子图模式的期望支持度所需的子图同构测试的数量从指数级降低到线性级.实验结果表明,该算法比简单的深度优先搜索算法快3～5个数量级,有很高的效率和可扩展性.     

FSMBUS：一种基于Spark的大规模频繁子图挖掘算法

随着社交网络用户数的快速增加,大规模单图上频繁子图挖掘的需求越来越强烈.单机算法对大规模图的运行效率较低,难以支撑支持度较低的频繁子图的挖掘;现有的分布式环境下单图的频繁子图挖掘算法不支持子图增长模式的挖掘,它们所使用的Hadoop框架也不适合运行迭代式算法.提出了一种基于Spark的大规模单图频繁子图挖掘算法FSMBUS,通过次优树构建并行计算的候选子图,在给定最小支持度时挖掘出所有的频繁子图,并利用非频繁检测和搜索顺序选择实现优化,还设计了一种名为Sorted-Greedy的轻量级数据划分方法.实验结果表明,FSMBUS的效率要比现有单图上最新的算法快一个数量级,并支持更低最小支持度阈值以及更大规模图数据的挖掘,同时FSMBUS比其Hadoop的移植版要快2~4倍.     

An Efficient Framework for Multiple Subgraph Pattern Matching Models

With the popularity of storing large data graph in cloud, the emergence of subgraph pattern matching on a remote cloud has been inspired. Typically, subgraph pattern matching is defined in terms of subgraph isomorphism, which is an NP-complete problem and sometimes too strict to find useful matches in certain applications. And how to protect the privacy of data graphs in subgraph pattern matching without undermining matching results is an important concern. Thus, we propose a novel framework to achieve the privacy-preserving subgraph pattern matching in cloud. In order to protect the structural privacy in data graphs, we firstly develop a k-automorphism model based method. Additionally, we use a cost-model based label generalization method to protect label privacy in both data graphs and pattern graphs. During the generation of the k-automorphic graph, a large number of noise edges or vertices might be introduced to the original data graph. Thus, we use the outsourced graph, which is only a subset of a k-automorphic graph, to answer the subgraph pattern matching. The efficiency of the pattern matching process can be greatly improved in this way. Extensive experiments on real-world datasets demonstrate the high efficiency of our framework.