图数据分析系统计算模型综述

随着大数据时代的到来,图作为一种表示和分析大数据的有效方法,正成为学术界和工业界广泛关注的焦点.图数据具有规模巨大、耦合性强、动态变化等特点,需要新的计算模型支持高效的图计算系统对大规模图数据进行处理.对图计算系统计算模型的研究现状进行了调研和综述,首先介绍图计算系统的产生和发展,然后将主流图计算系统中的计算模型按照计算对象分为:结点中心计算模型、边中心计算模型、路径中心计算模型和子图计算模型四类,重点介绍结点中心模型的应用和性能,最后对图计算模型的发展过程进行总结,并展望图计算模型未来发展方向.     

大规模图例的最大团问题算法分析

最大团问题是一个经典的组合优化问题,在蛋白质功能推测、竞胜标确定、视频对象分割等领域有广泛的应用。随着图例规模的增大,最大团问题求解难度增加,常规图例最大团求解算法已逐渐被大规模图例最大团求解算法取代。介绍求解大规模图例最大团问题的技术支撑点,重点总结基于大规模图例的最大团问题算法,并在大数据计算背景下对融合单层图划分方法和多层图划分方法的MapReduce框架和Spark框架进行优缺点分析。此外,比较k-core方法与k-community方法的应用场景,从算法分类的角度总结不同类型算法的优缺点,对求解大规模图例最大团问题的确定型算法进行梳理,并对代表性的求解算法在公开数据集中的表现进行对比分析。基于分析结果,指出不同算法在求解大规模图例最大团问题时需要重点关注的方面,并展望了智能优化算法、分层式深度强化学习方法、图结构相变分析技术的未来研究方向。     

基于图分割的求解最大流加速方法研究

随着科技的不断发展,交通、信息服务、电信等领域产生的数据都在飞速增长,通常这些数据都是以大规模图的形式呈现出来,城市交通最大车流量、双十一用户的交易信息传输、承载能力等很多实际问题都可以转化为最大流问题,大规模图中的最大流问题已经成为图论体系中的重要研究方向。现有的网络最大流问题,经过人们多年来的努力,建立的理论已趋于完善,但是大规模图的求解最大流的效率较低,依然无法满足目前很多应用场景的需求。为解决上述问题提出了利用割点构造原图覆盖图,确定从源点到汇点在覆盖图上对应的唯一路径后,将该路径上的节点对应的子图提交到GraphChi平台并行计算最大流。保证了每个子图最大流计算的独立性,可快速求解大规模图的最大流的。     

基于锚点的快速无监督图嵌入

图嵌入降维算法由于其有效性被广泛应用.传统图嵌入算法构造K-Nearest Neighbors(K-NN)图的计算复杂度至少为O(n2 d),其中n为样本数,d为样本维度.在数据量大的情况下,构造K-NN图将非常耗时,因为其计算复杂度与样本数的平方成正比,这将限制图嵌入算法在大规模数据集上的应用.为降低构图过程的计算复...     

基于并行图计算的社区划分方法

以图计算形式研究社交网络由来已久,但对于如何提升图计算应用于大规模社交网络的计算速度和扩展性,一直是研究的难点。谱图论的应用为社交网络在图计算方面的研究带来新的研究热点,谱图分割为社交网络社区划分带来基于结构的支撑。为了解决谱图论在处理大规模社交网络时存在计算缓慢、内存溢出等问题,本文提出了谱聚类改进算法结合矩阵方式在并行环境下的处理方法。首先,利用Spark对网络数据进行并行化预处理,将社交网络以图结构表示,再将图转化为Spark分布式稀疏矩阵。然后,将谱聚类改进算法在Spark环境下,实现并行化社交网络社区快速划分,并以分布式方式持久化存储源数据、中间计算数据和计算结果,提高图计算在社交网络中的可靠性。最后,通过实验证明并行化图计算方法能有效提高计算速度和扩展性,支持大规模社交网络的挖掘分析,实现并行算法下高并发、高吞吐的特点。     

一种基于GAS模型的k-Truss分解算法

在大规模网络中发现稠密子图具有极其广泛的应用,如社区发现、垃圾邮件检测等。为了在大规模网络数据中快速、有效地发现稠密子图,本文提出一种基于GAS (Gather-Apply-Scatter)编程模型的分布式k-Truss算法—GASTruss。该算法采用GAS的模式完成数据同步和算法迭代,有效的克服了传统并行算法重复性计算及不能有效处理依赖关系大的数据等问题。本实验选择在GraphLab平台上进行,结果表明：与串行k-Truss算法以及基于MapReduce的GPTruss算法性能相比,GASTruss算法对数据规模具有良好的拓展性,在保持算法效果的同时能有效降低时间复杂度。     

面向大规模工控网络的关键路径分析方法

针对大规模工控网络攻击图的量化计算耗时高、消耗资源大的问题,提出了一种大规模工控网络的关键路径分析方法。首先利用割集思想结合工控网络中的原子攻击收益,计算贝叶斯攻击图关键节点集合,解决目前割集算法只考虑图结构中节点关键性的问题。其次,提出一种只更新关键节点攻击概率的贝叶斯攻击图动态更新策略,高效计算全图攻击概率,分析攻击图关键路径。实验结果表明,所提方法在大规模工控攻击图的计算中,不仅可以保证计算结果的可靠性,而且能够大幅度降低方法耗时,显著提升计算效率。     

大规模图数据匹配技术综述

在大数据时代海量的多源异构数据间存在着紧密的关联性,图作为表示数据之间关系的基本结构在社交网络分析、社会安全分析、生物数据分析等领域有着广泛应用.在大规模图数据上进行高效地查询、匹配是大数据分析处理的基础问题.从应用角度对用于图查询的图数据匹配技术的研究进展进行综述,根据图数据的不同特征以及应用的不同需求对图匹配问题分类进行介绍.同时,将重点介绍精确图匹配,包括无索引的匹配和基于索引的匹配,以及相关的关键技术、主要算法、性能评价等进行了介绍、测试和分析.最后对图匹配技术的应用现状和面临的问题进行了总结,并对该技术的未来发展趋势进行了展望.     

基于影响力剪枝的图神经网络快速计算图精简

计算图精简是提升图神经网络(Graph Neural Network, GNN)模型训练速度的一种优化技术,它利用节点间存在共同邻居的特性,通过消除聚合阶段的冗余计算,来加速图神经网络模型的训练。但是,在处理大规模图数据时,已有的计算图精简技术存在计算效率低的问题,影响了计算图精简技术在大规模图神经网络中的应用。文中详细分析了当前的计算图精简技术,统计了包括搜索和重构两阶段处理的时间开销,并总结了现有方法的不足。在此基础上,提出了基于影响力剪枝的图神经网络快速计算图精简算法。该算法应用影响力模型刻画各个节点对计算图精简的贡献,并基于影响力对共同邻居的搜索空间进行剪枝,极大地提升了搜索阶段的效率。此外,详细分析了算法复杂度,从理论上证明了该技术期望的加速效果。最后,为验证所提算法的有效性,将所提算法应用到两种主流的计算图精简技术上,选取常见的图神经网络模型在多个数据集上进行测试,实验结果表明所提算法在保证一定冗余计算去除量的前提下,能够显著地提升计算图精简的效率。相比基线计算图精简技术,所提技术在PPI数据集上搜索阶段的加速效果最高提升了3.4倍,全过程最高提升了1.6倍;在Reddit...     

异构计算环境中图划分算法的研究

复杂网络的研究已经广泛地应用到生物、计算机等各个学科领域.如今,网络规模十分巨大,如何对这些大规模图数据进行有效率的挖掘计算,是研究复杂网络的首要任务.并行计算技术是现在最成熟、应用最广、最可行的计算加速技术之一.而图划分技术是提高并行计算性能的有效手段.图划分问题的研究是随着实际应用的需求而驱动.针对异构计算环境下的...     

面向模式图变化的增量图模式匹配

在大数据时代,数据图的规模急剧增长,增量图模式匹配算法能够在数据图或模式图发生变化时避免重新在整个数据图上进行匹配、减少响应时间,因此成为了研究的热点.针对实际应用中数据图不变而模式图发生变化的情况,提出了一种面向模式图变化的增量图模式匹配算法PGC_IncGPM,在模式图匹配的过程中记录适当的中间结果作为索引,用于后续的模式匹配.提出了增强的图模式匹配算法GPMS,用于首次整个数据图上的模式匹配.该算法一方面能够建立后续增量匹配所需的索引,另一方面减少了整个数据图匹配的执行时间.设计实现了面向模式图增边和减边的两个核心子算法,通过子算法的组合,能够支持在模式图发生各种变化时进行增量图模式匹配.在真实数据集和合成数据集上进行实验,结果表明:与重新在整个数据图上进行匹配的ReComputing算法相比,当模式图中变化的边的数目不超过不变的边的数目时,PGC_IncGPM算法能够有效减少图模式匹配的执行时间;随着数据图规模的增大,PGC_IncGPM算法相对于ReComputing算法的执行时间的减少程度更加明显,对于大规模数据图具有更好的适用性.     

图依赖研究与应用综述

图依赖是用于解决图数据的数据一致性问题的数据质量规则。基于图依赖提升数据一致性的过程通常分为图依赖定义与形式化、图依赖自动挖掘、基于图依赖的数据一致性提升三步。介绍了针对数据一致性的图依赖理论,并根据拓展类型将图依赖分为基于结构约束拓展、基于语义约束拓展和基于外部约束拓展的图依赖;综述并对比了从图数据中自动挖掘图依赖及其拓展的算法;分析了应用图依赖提高数据一致性的研究现状;总结了当前研究中仍存在的问题,并依据问题展望了图依赖在数据质量领域的应用前景。     

图数据压缩技术综述

应用合适的压缩技术对包含上亿个节点和边的图数据进行紧凑准确的表示和存储是对大规模图数据进行分析和操作的前提。紧凑的图数据表示不仅可以降低图数据的存储空间,而且还可以支持在图数据上的高效操作。从图数据的存储角度出发对图数据管理中关于图数据压缩技术的研究进展进行综述,将重点介绍以下3种压缩技术:基于邻接矩阵的图数据压缩技术、基于邻接表的图数据压缩技术和基于形式化方法的图数据压缩技术,以及相关的代表性算法、适用范围和优缺点。最后对图数据压缩技术的现状和面临的问题进行了总结,并给出了未来图数据压缩技术的发展趋势。     

A partition index for XML and semi-structured data

XML and other semi-structured data can be represented by a graph model. The paths in a data graph are used as a basic constructor of a query. Especially, by using patterns on paths, a user can formulate more expressive queries. Patterns in a path enlarge the search space of a data graph and current research for indexing semi-structured data focuses on reducing the search space. However, the existing indexes cannot reduce the search space when a data graph has some references.

In this paper, we introduce a partitioning technique for all paths in a data graph and an index graph which can effectively find appropriate path partitions for a path query with patterns.     

半监督图核降维方法

基于图结构的数据表示和分析,在机器学习领域正得到越来越广泛的关注。以往研究主要集中在为图数据定义一个度量其相似性关系的核函数即图核,一旦定义出图核,就可以用标准的支持向量机(SVM)来对图数据进行分类。将图核方法进行扩充,先利用核主成分分析(kPCA)对图核诱导的高维特征空间中的数据进行降维,得到与原始图数据相对应的低维向量表示的数据,然后对这些新得到的数据用传统机器学习方法进行分析;通过在kPCA中利用图数据中的成对约束形式的监督信息,得到基于图核的半监督降维方法。在MUTAG和PTC等标准图数据集上的实验结果验证了所提方法的有效性。     

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

社交网络数据的高度复杂性给数据挖掘研究带来了巨大的挑战,而社交网络数据挖掘更注重实体之间相互关联的特点,使得图数据挖掘技术的研究与应用逐渐成为该领域的热点。传统数据挖掘,如聚类、分类、频繁模式挖掘等技术逐渐拓展到图数据挖掘领域。文中首先介绍了现阶段图数据挖掘算法（其中包括图查询、图聚类、图分类和图的频繁子图挖掘）的研究内容和存在的问题;其次介绍了图形数据库研究现状,以及对比了主流图形数据库管理系统的优劣;最后介绍了图挖掘技术在社交网络中的应用。     

大图分布式存储关键技术浅析

大图的存储方式直接影响大图的访问效率以及查询与挖掘的效率。随着大图应用的不断发展,大图分布式存储技术所面临的挑战更加严峻,需要解决的问题日益迫切。首先阐述大图产生的背景以及大图分布式存储所面临的主要挑战,然后分析大图分布式存储技术的国内外研究现状,最后总结现有研究存在的问题并指明未来可能的研究方向。     

A fuzzy graph matching approach in intelligence analysis and maintenance of continuous situational awareness

In intelligence analysis a situation of interest is commonly obscured by the more voluminous amount of unimportant data. This data can be broadly divided into two categories, hard or physical sensor data and soft or human observed data. Soft intelligence data is collected by humans through human interaction, or human intelligence (HUMINT). The value and difficulty in manual processing of these observations due to the volume of available data and cognitive limitations of intelligence analysts necessitate an information fusion approach toward their understanding. The data representation utilized in this work is an attributed graphical format. The uncertainties, size and complexity of the connections within this graph make accurate assessments difficult for the intelligence analyst. While this graphical form is easier to consider for an intelligence analyst than disconnected multi-source human and sensor reports, manual traversal for the purpose of obtaining situation awareness and accurately answering priority information requests (PIRs) is still infeasible. To overcome this difficulty an automated stochastic graph matching approach is developed. This approach consists of three main processes: uncertainty alignment, graph matching result initialization and graph matching result maintenance. Uncertainty alignment associates with raw incoming observations a bias adjusted uncertainty representation representing the true value containing spread of the observation. The graph matching initialization step provides template graph to data graph matches for a newly initialized situation of interest (template graph). Finally, the graph matching result maintenance algorithm continuously updates graph matching results as incoming observations augment the cumulative data graph. Throughout these processes the uncertainties present in the original observations and the template to data graph matches are preserved, ultimately providing an indication of the uncertainties present in the current situation assessment. In addition to providing the technical details of this approach, this paper also provides an extensive numerical testing section which indicates a significant performance improvement of the proposed algorithm over a leading commercial solver.     

基于环境信息融合的知识图谱构建方法

针对多源异构的环境数据难以利用的问题, 在通用知识图谱的基础上, 融合各类环境数据构建环境知识图谱. 首先利用网络爬虫等获取环境数据, 并进行数据预处理; 进而利用结构化数据转化、文本抽提以及数据融合等技术, 研究基于环境信息融合的知识图谱构建方法; 最后将生成的知识图谱存入图谱数据库,并搭建知识图谱应用平台, 提供递归查询功能, 实现环境知识图谱的可视化, 以期为相关人员提供有益参考.     

关于主动学习下的知识图谱补全研究

知识图谱补全任务研究如何补全知识图谱中的缺失关系。知识图谱补全任务有许多广泛的应用,例如可以应用到轨道交通运维知识库中以支撑轨道交通的系统设计、运维优化。现有的算法在用于现实的大规模知识图谱时时间开销巨大,并且无法很好地利用知识图谱外部的数据信息。针对以上两点局限性,提出了一种基于主动学习的知识图谱补全框架。该框架结合主动学习的思想,利用链接预测预先筛选缺失知识图谱中最有可能产生链接的前k对实体对,然后充分考虑知识图谱内部信息和外部信息,采用内外部数据相结合的方式实现知识图谱的缺失补全。基于Freebase和DBpedia数据集,针对已有的工作进行了对比实验,实验结果表明提出的增强链接预测算法(ELP)效果更好,并且具有主动学习能力;提出的内部数据和外部数据相结合的关系验证方法能更有效地验证三元组。