基于摘要图的不确定社会网络Top-k子图查询算法

针对不确定W eb社会网络的Top-k子图查询问题,以无向、顶点带标签及边赋权重的简单图为基本模型,设计了用来简洁描述社会网络并编码原始图信息的摘要图,提出了Top-k子图同构查询算法。针对真实和虚拟网络数据进行了大量实验,结果表明:基于摘要图的Top-k子图查询算法较VF2算法运算时间缩短;由于构建摘要图时的主要依据是顶点的标号,因此查询图的标号分布对查询性能有较大影响;顶点标号数目增加时该算法的查询性能呈类似指数形式提高,而VF2算法的查询性能没有受到较大影响;当数据图的顶点数量增大时,该算法与VF2算法相比,消耗时间的增长更缓慢;该算法在处理Top-k查询时体现出了稳定高效的性能。     

新型建筑智能化平台节点拓扑匹配算法研究

针对新型建筑智能化平台中空间拓扑与节点拓扑一致性问题,提出了一种拓扑匹配算法.在拓扑匹配过程中,通过提取AutoCAD建筑平面图的B-rep信息,将其表示为以空间单元为节点的属性邻接图.建筑平面图空间拓扑被表示为大图,平台中智能节点交互形成的拓扑被表示为小图,一致性问题被转化为大图中查询同构小图问题.该算法与传统的子图同构算法相比,首先利用顶点度优化匹配顺序,其次增加顶点的邻域信息作为剪枝条件,对候选集匹配项进行筛选,最后采用非递归-回溯思想对数据节点进行验证,并在真实的数据集上验证了算法的适用性与高效性.     

URSI:高效的子图同构查询算法

子图同构查询用于返回数据图中与给定查询图匹配的子图,是图数据管理中的核心问题。如果匹配策略不当、查询结点和数据结点之间大量的冗余枚举以及剪枝策略不当,都会引起查询中的冗余计算问题。本文首先将查询图转化为邻居等价类树并使用过滤条件生成候选区域;其次,通过对候选区域探测将区域中的结点进行排列组合得到结点匹配顺序,并对数据结点进行验证,得到查询图在数据图中的所有匹配的子图;最后给出了基于上述策略的URSI算法,并在真实的数据集上通过实验验证了所提算法的高效性。     

具有结果多样性的近似子图查询算法

针对大型图中的各种top-k近似子图查询算法存在的顶点重叠度高、无法满足多样性匹配结果输出等问题,提出具有最大顶点覆盖集的多样性近似子图查询算法.该算法建立基于近邻关系和基于区域划分的双重索引,并为相互关系紧密的同标号顶点建立簇索引.在图查询过程中,利用近邻特征为查询图中的每个顶点快速筛选出满足局部匹配要求的候选顶点集,并从不同区域找到多个满足要求的近似匹配子图,避免了查询结果间的高重复率.同时,基于区域和同标号近邻簇的划分,优先查找属于不同划分或不同簇顶点的匹配,减少了不同区域划分间的交互,提高了查询的效率.在大量数据集上的实验结果验证了该算法在查询效率和结果多样性等方面的有效性.     

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

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

逐步最佑扩展的频繁子图挖掘算法

gSpan算法是一种高效的频繁子图挖掘算法,它通过最右扩展图的标准编码得到图集中的所有频繁子图,但它需要通过子图同构判断来计算支持度,由于子图同构问题是NP完全问题,其计算比较复杂.针对上述问题提出一种优化的算法IgSpan,通过改进的ADI++存储结构将图的最右扩展和支持度的计算相结合,避免直接的子图同构判断,经实验...     

一种高效的生物网络概率模体发现算法

针对概率模体发现算法中非树形子图的挖掘和在得分函数最大化的过程中得分函数值计算的2个难点.首先提出基于划分的非树形子图的搜索算法,其次将子图同构应用于最小错配的求解以缩小智能优化算法对得分函数求解的解空间,最后将基于模拟退火算法和遗传算法的混合算法应用于得分函数的求解过程.在大肠杆菌基因调控网络中的实验结果表明,与其他算法相比,混合智能算法可以大大减少非树形子图的搜索时间,并以相对较快的收敛速度收敛到一个较优的解,因此所提出的方法有效地提高了概率模体发现的效率.     

一种基于悬挂顶点关联索引的最短路径查询算法

最短路径查询是图数据查询中的热点问题。针对现有的"索引+查询"方法存在的查询效率低下且扩展性差等问题,本文提出了悬挂顶点关联索引策略,即先对度为1的顶点构建顶点关联索引,再对其他顶点构建2-hop标签索引,并依此提出了相应的最短路径查询算法。本文提出的索引策略降低了索引规模,减少了构建索引时间,使得最短路径查询算法的效率和扩展性得到了改善。最后,通过对11个真实的数据集进行实验,从索引构建时间、索引规模大小、查询时间等方面验证了本文方法的高效性。     

无向图同构的快速算法

规范标记算法和顶点划分算法是判断无向图同构的两种重要途径,其缺点是要么无法对图进行规范标记,从而不能进行判断；要么必须进行不断地回溯和试探,从而造成指数阶时间开销.对于任何两个同构的无向图,各自新增一个顶点和若干条关联边,可获得父图.当且仅当新增顶点的邻接点在原同构图中保持同构关系时,父图同构.根据这个充要条件,文中使...     

并行环境下基于图着色理论的空间数据部署

在面向计算部署到数据节点端执行的分布式并行环境下,提出一种基于图着色理论的适用于矢量空间数据的部署方法,将空间数据粒度的部署问题转化为图顶点着色的过程,提高了任意空间区域的信息查询效率.给出基于图着色理论的数据部署方法,并通过节点的任务量进一步改进算法,使得该算法可实现海量空间数据粒度的离散化部署,提高了空间数据检索和查询的并行化程度,充分利用了并行计算资源.