进化图数据挖掘算法及其在信息学科建设中的应用

为了克服当前主流的图数据挖掘算法常采用的贪婪式查找带来的易于陷入局部最优这一问题,提出了一种基于进化算法的图数据挖掘算法,以增强算法的全局查找能力。定义了基于图的交叉和变异算子。考虑到进化算法局部搜索能力弱的特点,本文在变异算子的设计中还融入了爬山算法的思想,以进一步提高解的质量。应用该算法于信息与计算科学的学科建设之中。首先,将网上收集的有关各个院校信息学科专业建设的信息转化为图表示方式,然后用该算法从这些图数据中挖掘出信科专业建设的典型模式。该模式为我校的信息科学专业建设和教学改革提供了理论依据,具有重要的参考价值。

电信大规模社交关系网络图数据挖掘研究

电信技术的发展使得通话网络几乎覆盖了整个社会,对电信运营商来说,这个庞大的社会网络蕴藏着巨大的商机。尤其在日益激烈的市场竞争中,客户关系的维护、客户潜在价值的挖掘以及有针对性地对客户进行营销等对电信图数据的挖掘,受到了强烈关注。通过对比,研究了当前针对类似电信网络的大规模社交关系网络图数据进行挖掘的分布式和单机图计算工具和框架,并对单机图计算工具Graphchi的单机处理数据能力进行了可行性和可用性测试,同时采用单机Graphchi对电信社交关系网络的数据进行了图挖掘研究和应用。

图数据挖掘在社交网络的应用研究

社交网络数据的复杂性为数据挖掘带来严峻的考验,对于数据的复杂性,在社交网络中使用具有针对性的处理方法显得尤为重要。图数据挖掘依据图数据关系,可以很好地利用其本有的优势来开发和分析这类互相联系紧密的实体联系的复杂数据。该文根据图数据挖掘的特性和图数据挖掘的处理方式,首先介绍了图数据挖掘方面的若干定义、计算模型以及在图数据挖掘方面的处理系统;然后介绍了图数据挖掘的应用,主要包括图数据库的相关内容以及图数据算法等;最后,从整体上简要介绍了社交网络的发展情况以及图数据挖掘与社交网络的的不同模型不同的结合过程和处理方法。

大规模时序图数据的查询处理与挖掘技术综述

时序图作为一种带有时间维度的图结构,在图数据的查询处理与挖掘工作中扮演着越来越重要的角色.与传统的静态图不同,时序图的结构会随时间序列发生改变,即时序图的边由时间激活.而且由于时序图上每条边都有记录时间的标签,所以时序图包含的信息量相较于静态图也更为庞大,这使得现有的数据查询处理方法不能很好地应用于时序图中.因此如何解决时序图上的数据查询处理与挖掘问题得到研究者们的关注.对现有的时序图上的查询处理与挖掘方法进行了综述,详细介绍了时序图的应用背景和基本定义,梳理了现有的时序图模型,并从图查询处理方法、图挖掘方法和时序图管理系统3个方面对时序图上现有的工作进行了详细的介绍和分析.最后对时序图上可能的研究方向进行了展望,为相关研究提供参考.

面向复杂网络图的环路挖掘算法研究进展

环路作为一种特殊的模体,在揭示图的结构特征方面发挥着不可或缺的作用,能够帮助人们深入理解图的结构特点,得出更有价值的结论和科学预测。因此,环路挖掘一直是图研究领域中的热点问题之一。文章紧扣环路挖掘问题的研究脉络,从静态图和动态图两个维度,对图上的环路挖掘算法进行了全面细致的梳理,同时选取其中部分经典算法以更直观的方式展开进一步对比分析,并列出了相关研究所涉及的数据集与其对应的下载链接,便于读者能够更便捷地获取所需资源,展开进一步的探索与研究。

不完整多视图聚类综述

多视图聚类是近年来图数据挖掘领域的研究热点。由于数据采集技术的限制或人为因素等原因常导致视图或样本缺失问题。降低多视图的不完整性对聚类效果的影响是多视图聚类目前面临的重大挑战。因此,综合研究不完整多视图聚类(IMC)近年的发展具有重要的理论意义和实践价值。首先,归纳分析不完整多视图数据缺失类型;其次,详细比较基于多核学习(MKL)、矩阵分解(MF)学习、深度学习和图学习这4类IMC方法,分析代表性方法的技术特点和区别;再次,从数据集类型、视图和类别数量、应用领域等角度总结22个公开不完整多视图数据集;继次,总结评价指标,并系统分析现有不完整多视图聚类方法在同构和异构数据集上的性能表现;最后,归纳分析不完整多视图聚类目前存在的问题、未来的发展方向和现有应用领域。

基于Motif的图采样算法

图采样通过对图数据进行约简操作,获得比原图的规模更小的图结构,进而服务于图谱分析、图可视化等下游任务.现有的图采样算法侧重于保留图中显著的结构特征而忽略了节点属性,导致采样图在许多下游任务如频繁模式挖掘等,难以取得预期效果.为此,提出基于Motif的节点有偏采样算法(Motif-Based Node Biased Sampling,MNBS),利用频繁Motif结构重新定义图中节点的重要性,随后进行有偏节点采样,实现融合节点属性与结构特征的采样.为了快速识别频繁Motif模式,设计了具有“提前终止”特性的Motif模式快速发现算法(Fast Motif-Pattern Discovery,FMPD),能高效且准确地发现Motif模式以支持图采样.实验表明,MNBS采样算法在多项指标上优于其他基线算法,其对数归一化累积组相关性指标平均降低0.54,使用包含“提前终止”特性策略的FMPD算法的时间消耗和内存消耗比基线算法分别降低56.1%和29.8%.

基于图神经网络的线上学习资源推荐模型设计

图神经网络(Graph Neural Networks,GNN)作为一种强大的机器学习模型,已经在图数据挖掘领域取得了显著的研究进展。GNN可以对学习资源构建出图结构,并通过学习节点和边的表示进行推荐,这为解决线上学习资源推荐问题提供了新的思路和方法。本文提出了一种基于图神经网络(GNN)的线上学习资源推荐模型,该模型利用图神经网络对用户偏好进行建模,并根据用户历史行为数据在已有信息上进行挖掘,从而实现对用户需求的智能分析和推荐。结果表明,该模型具有较高的性能表现,能够较好地解决在线学习资源推荐问题。

面向图的异常检测研究综述

近年来,随着Web 2.0的普及,使用图挖掘技术进行异常检测受到人们越来越多的关注.图异常检测在欺诈检测、入侵检测、虚假投票、僵尸粉丝分析等领域发挥着重要作用.在广泛调研国内外大量文献以及最新科研成果的基础上,按照数据表示形式将面向图的异常检测划分成静态图上的异常检测与动态图上的异常检测两大类,进一步按照异常类型将静态图上的异常分为孤立个体异常和群组异常检测两种类别,动态图上的异常分为孤立个体异常、群体异常以及事件异常这3种类型.对每一类异常检测方法当前的研究进展加以介绍,对每种异常检测算法的基本思想、优缺点进行分析、对比,总结面向图的异常检测的关键技术、常用框架、应用领域、常用数据集以及性能评估方法,并对未来可能的发展趋势进行展望.

检测最大密度子图的局部广度优先扩张与收缩方法

最大密度子图检测是一个重要的图挖掘问题,目前已经应用在诸如互联网、生物科学及图像处理等多个领域.在传统的最大密度子图检测算法基础上,提出一种新的基于局部广度优先扩张与收缩算法.首先,选定图中的最优结点,并从该结点出发做广度优先扩张;其次,对上面所得到的扩张结点集合进行收缩,从而得到当前迭代过程的局部最大密度子图;最后,在该局部最大密度子图相对于原图的补图上不断进行上述迭代,每次记录当前平均密度最大的子图,直至补图为空.该算法利用局部邻域优势,有效地提升了最大密度子图的平均密度.通过实验结果表明,与同类算法相比,利用该算法所得到的最大密度子图的平均密度更大.此外,通过实验表明,该算法与同类算法相比还具有更好的稳定性和适应性.

基于个体协同的子图结构发现混合进化算法

将进化算法与爬山算法的混合进化算法引入图数据挖掘,以克服贪婪式查找易陷入局部极值的问题.针对子图结构发现问题中实例易丢失的特点,提出了一种新的遗传操作——个体协同算子,使得代表同一子结构的不同个体能够以协同的方式进行查找.另外,还提出了一种基于年龄段和个体生成方式的多样性保持方案,以从种群的组成和个体的生成两个方面保持和提高种群的多样性,同时还有助于个体协同算子的执行.在进化过程中随时以新生成的单边子结构替换当前种群中没有潜力的个体的机制在缩小查找空间的同时还使得进化过程成为一个更为完全的查找过程.实验结果表明,以上措施增强了算法的寻优能力,能够获得更优的解.

双网络中影响力凝聚子图发现算法

双网络由物理图和概念图构成,其中物理图和概念图共享网络结点集合而具有不同边集合.物理图中边表示结点间实际存在的关系;概念图中边表示结点间的相似程度,通常由计算得出.最近,从双网络中发现凝聚子图,即物理图中连通且概念图中稠密的子图受到研究者的广泛关注,在研讨会筹备、商品推荐和致病基因发现等真实场景中具有广泛应用.但现有研究鲜有考虑双网络中凝聚子图的影响力.为此:1)提出一种基于最小边权重定义的影响力凝聚子图,即影响力k-连通truss(k-ICT)子图模型.k-ICT子图模型能够有效刻画子图在双网络中的重要性且对低影响力边鲁棒.2)由证明可知,发现影响力最大的k-ICT子图是NP-难的,因此提出一种基于概念图边等价类划分的CT索引结构.利用索引的概要图,能够根据不同的k值,快速发现包含所有k-ICT子图的候选子图.3)提出了基于全局枚举删除和局部子图扩展的精确算法Exact-G kICT和Exact-LkICT,用于发现top-r具有最大影响力的k-ICT子图.通过大量在真实数据集上的实验,验证算法的高效性和有效性.

基于深度学习的属性图异常检测综述

异常检测一直以来都是数据挖掘领域的研究热点之一,其任务是在海量数据中识别罕见的观测对象。随着图数据挖掘的发展,属性图异常检测在各个领域广受关注。然而,属性图因其复杂的拓扑结构和丰富的属性信息成为异常检测一大难点。深度学习方法在捕捉属性图复杂的信息中展现出优越性能,已被证实是解决属性图异常检测问题非常有效的方法。对普通图异常检测和属性图异常检测以及表示学习相关方法进行简要概述;其次从静态属性图和动态属性图两方面对最新深度学习异常检测方法进行介绍与分类;对常见数据集上的实验结果进行了对比、分析;对属性图异常检测的应用场景、存在的问题以及面临的挑战进行讨论,展望了未来的研究方向。

基于简单Petri网和gSpan算法的业务流程频繁结构挖掘

针对业务流程的结构特性,提出了将图结构数据挖掘算法应用于业务流程模型的思想,具体将gSpan算法应用于简单Petri网模型,提出简单Petri网有向图化和d-gSpan算法的可实践方法,实现了业务流程频繁子结构挖掘。论文最后以某列车入段检修业务流程进行实验。

满足强连通性的有向团枚举算法研究

有向图的有向边可以表示关系的指向或者数据的传递,在稠密子图的挖掘中引入连通性的约束可以增加顶点之间的联系。为此,结合极大团与强连通分量的定义,底图是完全子图且顶点之间满足强连通性的子图结构被称为有向团。已有工作给出了枚举极大有向团的输出敏感算法,然而其存在大量重复枚举和判重操作复杂等不足之处。为了解决这些问题,基于深度优先搜索的思想和有向团的扩展性质,提出一种新颖的递归枚举算法。算法对于出边邻居和入边邻居分别划分候选集与排除集,维护完全子图结构的同时,不断尝试扩展有向团并保证满足强连通性,并且引入基于共同邻居的支撑点剪枝策略,在稠密图上获得上千倍的效率优化。算法还针对搜索空间给出两种优化设计:一是添加了分割子图的预处理,限制递归调用的搜索范围;二是基于位向量压缩表示顶点集合,提高集合运算的效率。在真实图数据上的实验结果表明,相比现有工作中的输出敏感算法,提出的算法具有50倍以上的加速比。

基于XGBoost与拓扑结构信息的蛋白质复合物识别算法

蛋白质相互作用(PPI)网络中存在大量不确定性及已知蛋白质复合物数据的不完整性,单独地根据结构信息进行搜索或对已知复合物进行监督学习的方法在识别蛋白质复合物的准确性上存在不足。对此,提出一种XGBoost模型与复合物拓扑结构信息相结合的搜索方法(XGBP)。首先,根据复合物拓扑结构信息进行特征提取;然后,把所提取的特征用XGBoost模型进行训练;最后,将拓扑结构信息与监督学习方法相结合,建立特征与复合物之间的映射关系以提高蛋白质复合物预测的准确性。该算法分别与目前流行的马尔可夫聚类算法(MCL)、极大团聚类方法(CMC)、基于核心-附属结构算法(COACH)、快速层级聚类算法(HC-PIN)、基于重叠邻居的扩展聚类(ClusterONE)、分子复合物检测算法(MCODE)、基于不确定图模型的蛋白质复合物检测方法(DCU)和加权核心-附属算法(WCOACH)这八种非监督学习算法和三种监督学习方法贝叶斯网络(BN)、支持向量机(SVM)、回归模型(RM)进行比较,所提方法在精准度、敏感度、F-measure方面显示出良好的性能。

基于带状态回溯个体进化的子结构发现

将进化算法引入图数据挖掘,以克服贪婪式查找易陷入局部极值的问题。针对图数据挖掘中经常遇到的子图同构问题,提出了带状态回溯个体的概念,从而使遗传算子的设计更为合理。另外,还提出了一种新的多样性保持方案,从种群的组成和个体的生成两个方面提高了种群的多样性。在进化过程中随时去掉当前种群中没有潜力的个体的机制使查找空间缩小了一半。实验结果表明,以上措施增强了算法的寻优能力,提高了算法的效率和解的质量。

快速的混合进化子结构发现算法

将混合进化算法引入图数据挖掘,避免了陷入局部极值问题,提高了解的质量。在此基础上提出了一种基于单标签扩展的子结构扩展方法,该方法可以减少进化过程中图同构操作执行的次数。在典型数据集上的仿真实验和理论证明表明了该方法的高效性和正确性。

进化子结构发现在区域经济研究中的应用

提出了一种基于进化算法的子结构发现算法,并将爬山算法的思想融合于交叉和变异算子的设计之中,该算法可有效地跳出局部极值,取得较好的实验结果。将该算法应用于我国区域经济研究,挖掘结果反映了我国经济目前发展的趋势及存在的问题。

一种基于混杂EA的子结构发现算法

将混杂进化算法引入图数据挖掘,定义了基于图的染色体表示与加边变异和减边变异算子。针对子图同构问题,采用了SUBDUE提出的带实例的子结构的概念并提出了个体的潜力和带历史的个体两个概念,前者用以衡量一个个体生成新子结构的能力,后者用来保存进化过程中有潜力的个体,从而使减边变异成为可能,在一定程度上克服了子图同构问题。实验结果表明,以上措施增强了算法的寻优能力,提高了算法的效率和解的质量。