子图同构

摘要： 随着全军顶层设计工作的开展和推进,在使用Inf-ProA框架及其配套的工具开展军事领域的架构设计工作中逐步积累并形成了一定数量的架构设计模型资产。在架构师进行模型设计时,存在着广泛地参考已有相似模型的需求。然而,现有的架构方法和工具还无法对有参考价值的相似模型进行度量和推荐。本文基于信息活动模型(IAV-1a)的基本架构设计要素,通过对可扩展语言文档以及统一建模语言模型相似性度量的研究,提出一种可用于衡量Inf-ProA信息活动过程模型相似度的方法。对信息活动过程模型的内容和结构方面进行相似性的衡量,并考虑接近模型最终设计结果上的设计相似性,利用架构设计实践经验,使得到的相似性度量结果更具有合理性。该相似性度量的结果可以用于对正在设计的模型提供一个最大化的相似匹配,对推荐给架构师来完成辅助设计具有重要意义。实验结果表明,本文提出的方法可以有效地对信息活动过程模型的相似性进行度量。

摘要： 子图同构问题是非确定多项式(NP)完全问题,而轴心子图同构是一种特殊的子图同构问题。针对现在已经有许多高效的子图同构算法,然而对于轴心子图同构问题目前并没有基于GPU的搜索算法,且通过改造已有的子图同构算法来解决轴心子图匹配问题会产生大量不必要的中间结果这一问题,提出了一种基于GPU的轴心子图同构算法。首先,通过一种新颖的多编码树方式,利用节点的标签、度以及节点邻居的结构特征的组合对节点进行编码,并在GPU上对查询图节点并行地进行剪枝,从而明显地减小数据图候选节点所生成的搜索空间树的尺寸;然后,逐层访问查询图节点的候选节点,过滤掉不满足的节点;最后,验证得到的子图是否是查询图的同构子图,从而高效地完成轴心子图同构搜索。实验结果表明,与GPU友好子图匹配(GpSM)算法相比,所提算法的执行时间降低了二分之一,且该算法能够高效地执行轴心子图同构搜索并且具有可扩展性。所提轴心子图同构算法可以减少解决轴心子图同构问题所需的时间,同时降低了GPU内存消耗,提升了算法的性能。

摘要： 在对工业互联网设备私有工控协议进行安全分析时,溯源其采用的工控网络协议标准十分困难。文章提出一种基于状态机子图同构匹配的私有工控协议溯源方法,可快速匹配私有工控协议所采用的工控网络协议标准。该方法首先对私有工控协议流量数据进行逆向解析,通过聚类算法提取消息格式和关键字段,根据关键字段构造增广前缀树(Augmented Prefix Tree Acceptor,APTA),推断出协议状态机图;然后采用子图同构匹配算法将该状态机图与工控协议标准状态机图进行子图匹配,解决流量数据有限导致生成状态机图不完整的问题。实验结果表明,该方法溯源准确率在95%以上,可快速定位私有协议采用的工控网络协议标准,从而为进一步的安全分析提供帮助。

摘要： 子图匹配是图数据分析中的基础问题,具有重要的研究意义。针对子图匹配求解算法存在大量冗余搜索的问题,提出了一种基于图神经网络的子图匹配符号算法。该算法利用图神经网络技术聚合节点的邻域信息,得到包含图局部属性和结构的特征向量,以该向量作为过滤条件得到查询图的节点候选集C。此外,优化匹配顺序并利用符号ADD操作在数据图中构建C的各个候选区域,减少了子图枚举验证过程中的冗余搜索。实验结果表明,与VF3算法相比,该算法有效地提高了子图匹配的求解效率。

摘要： Hive现有的审计功能不能对数据操作目的进行合规判断。针对以上问题,该文提出一种基于子图同构的Hive数据操作合规分析方法。首先,提出基于图的Hive数据操作和合规规则的建模方法,形成数据溯源图和合规规则图;然后,将数据操作合规判断建模为溯源图和合规图的匹配问题,并提出基于子图同构的求解算法。最后,在数据治理平台Apache Atlas及Hive中进行了实验验证,实验结果表明,相比于基于集合、VF2以及Ullmann的合规验证,该文方法具有更高的合规验证效率。

摘要： 图匹配在现实中被广泛运用,而子图同构匹配是其中的研究热点,具有重要的科学意义与实践价值.现有子图同构匹配算法大多基于邻居关系来构建约束条件,而忽略了节点的局部邻域信息.对此,提出了一种基于邻居信息聚合的子图同构匹配算法.首先,将图的属性和结构导入到改进的图卷积神经网络中进行特征向量的表示学习,从而得到聚合后的节点局部邻域信息;然后,根据图的标签、度等特征对匹配顺序进行优化,以提高算法的效率;最后,将得到的特征向量和优化的匹配顺序与搜索算法相结合,建立子图同构的约束满足问题(CSP)模型,并结合CSP回溯算法对模型进行求解.实验结果表明,与经典的树搜索算法和约束求解算法相比,该算法可以有效地提高子图同构的求解效率.

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

摘要： 针对子图同构中索引构建方法效率低、内存占用大而影响查询效率的问题,本文提出基于2次排序查找等价顶点的数据图索引构建算法.该算法采用不同邻接链表表示类别不同的语法等价顶点的邻居集合,并依此设计2次排序的方法快速查找数据图中两两互连和两两互不相连的等价顶点,然后依据语法等价和语法包含关系为数据图构建索引来提高子图同构查询的效率.最后,基于不同规模的数据集,通过实验验证了本文提出索引构建算法的高效性和可扩展性.

摘要： Android现有的恶意代码检测机制主要是针对bytecode层代码,这意味着嵌入Native层的恶意代码不能被检测,最新研究表明86％的热门Android应用都包含Native层代码.为了解决该问题,本文提出一种基于Native层的Android恶意代码检测机制,将smali代码和so文件转换为汇编代码,生成控制流图并对其进行优化,通过子图同构方法与恶意软件库进行对比,计算相似度值,并且与给定阈值进行比较,以此来判断待测软件是否包含恶意代码.实验结果表明,跟其他方法相比,该方法可以检测出Native层恶意代码而且具有较高的正确率和检测率.

摘要： 设计模式能够在较大程度上反映软件系统的设计思路.准确地挖掘并理解软件源码中所使用的设计模式实例,能够帮助开发和维护人员理解软件系统的设计和实现,从而促进对软件系统的维护、升级、二次开发和文档化等工作.目前已存在多种挖掘结构型设计模式实例的方法,其中部分方法将软件系统源码和设计模式转化为图的形式,并通过寻找同构子图的方式挖掘设计模式实例.然而,由于挖掘同构子图是一个NP完全问题,这些方法的效率普遍不太理想.针对这一问题,本文提出一种高效的基于有向圈子图同构的结构型设计模式挖掘方法.该方法根据设计模式的图表示形式生成一个快速搜索序列,在挖掘同构有向子图(或设计模式实例)时根据该快速搜索序列可以大大减少搜索空间,从而显著提高挖掘过程的效率.本文通过对3个开源软件源码的实验分析验证了本文方法的有效性和效率.

摘要： 本文提出了一种基于子图同构的子电路识别启发式算法。该算法启发式地确定识别的起始点,并对电路图中各个结点进行权值计算,通过权值比较,过滤掉不可能匹配的结点,得到可有效匹配的侯选结点集,避免了大量无效的识别过程,提高了识别的效率。

摘要： 超大规模集成电路设计中的故障检测问题的实质是子图同构问题，目前还没有通用的解决方法。针对这一问题的研究，研究人员对其中一个较好的电路匹配算法进行了三点改进，使算法的效率有了明显提高，并消除了可能的重复解。该文详细介绍了改进的具体方法，并给出了实验对比数据。

摘要： 本发明公开了一种基于子图同构的电网故障建模方法及系统，方法包括以下步骤：对电力系统的网络拓扑进行识别；获取典型故障的特征，包括网络模式、动作模式以及时序模式；根据所述网络模式在所述电力系统中搜索所有的潜在故障子图，形成潜在故障子图集合；根据所述动作模式和所述时序模式为所述潜在故障子图集合中的每个潜在故障子图分配动作和时序。本发明的目的在于提供一种基于子图同构的电网故障建模方法及系统，根据现有电网的拓扑结构，可实现常见故障的自动建模，避免因电网拓扑结构以及运行方式的改变导致人员的大量故障人工建模、维护工作，提高电力系统稳定分析的自动化水平。

摘要： 一种基于子图同构的web数据自动可视化方法，包括以下步骤：第一步：构建服务数据可视化建模与匹配方法的架构；第二步：定义元数据树MDT；第三步：读取调用的REST API所返回的JSON数据，将JSON数据集ds作为建模算法的输入，对ds进行树形结构建模；第四步：通过剪枝的方法，保留基本的数据结构信息；第五步：对可视化图形进行分类；第六步：先用降维方法对MDT进行降维操作，生成元结构树MST，再进行匹配查询，调用基于子图同构的匹配方法查找MST中与VT的各个StructModel匹配的片段，并根据Mapping信息进行数据映射生成可视化图形。本发明将模型进行自动化匹配，以实现数据的自动可视化。

摘要： 本发明公开一种基于对称破坏的子图同构约束求解方法，其采用约束满足问题CSP的模型，首先分析模式图和目标图的节点、边等信息构建子图同构问题的约束满足问题的模型，添加破坏对称约束，再根据约束满足问题的求解方法，对所建立的模型进行求解。破坏对称技术包括检测自同构节点和通过Schreier‑Sims算法生成对称破坏约束两步。由于对称破坏技术用于解决CSP中的对称性，通过施赖埃尔一西姆斯算法对置换群的操作生成破坏对称约束，能够避免对称子树的二次搜索，降低组合复杂性。因此算法执行过程中，有效缩减了搜索空间，提高问题的求解效率，具有良好的实用性。

摘要： 本发明公开了一种支持数据库动态更新的隐私保护子图同构查询方法，包括：获取待查询图形的第一图形特征与图数据库的第二图形特征，基于所述第二图形特征建立树状索引，利用安全特征向量匹配方法对所述树状索引进行加密，获得密文下的匹配查询。本发明通过采用树状索引，显著提高了过滤阶段的速度；采用Hash映射的方式决定特征在特征向量上的位置，更加充分的利用了特征向量的每一位，提高了过滤效果。本文所提出的查询方法可以支持数据库频繁更新，加密索引可以随着数据库的更新快速更新。

摘要： 本发明公开了一种基于协议状态机子图同构匹配的私有协议分类方法，该方法包括私有协议状态机生成阶段和状态机匹配分类阶段。在私有协议状态机生成阶段，首先对捕获的设备网络流量进行解析提取出协议应用层的二进制序列，接着采用对齐算法从二进制序列中解析出协议字段内容，进一步利用聚类算法实现相似字段归并得到私有协议消息类型和消息格式，最后采用增广前缀树结构从设备交互消息中进行状态合并生成协议状态机；在状态机匹配分类阶段，采用子图同构匹配算法将该状态机图与已知标准协议状态机进行匹配，实现私有协议的快速分类。本发明可以帮助设备协议分析人员快速定位网络设备厂商自行定义的私有协议设计时所参考的标准协议。

摘要： 本发明提出一种结合子图同构的量子线路程序通用变换方法，将量子线路表示成顶点为单量子门或双量子门、边为弧尾结点依赖的量子比特信息的DAG；并在这种DAG上提出子图同构的QVF算法解决线路的模式匹配问题，并基于线路匹配信息设计子图替换算法。本发明还引入量子线路等价关系的模式描述格式，并定义通用模式和合并模式两种具体模式类别及其描述格式，使得重写方法能够处理诸如线路优化、线路转换等重写问题。在IBM和ScaffCC提供的量子测试程序集上的实验表明，本发明的方法实现的连续单量子门优化能够对量子程序规模提供10％的优化率。

摘要： 本发明公开了一种基于子图同构的电网故障建模方法及系统，方法包括以下步骤：对电力系统的网络拓扑进行识别；获取典型故障的特征，包括网络模式、动作模式以及时序模式；根据所述网络模式在所述电力系统中搜索所有的潜在故障子图，形成潜在故障子图集合；根据所述动作模式和所述时序模式为所述潜在故障子图集合中的每个潜在故障子图分配动作和时序。本发明的目的在于提供一种基于子图同构的电网故障建模方法及系统，根据现有电网的拓扑结构，可实现常见故障的自动建模，避免因电网拓扑结构以及运行方式的改变导致人员的大量故障人工建模、维护工作，提高电力系统稳定分析的自动化水平。

摘要： 本发明涉及一种基于子图同构的FPGA软件可疑电路检测方法，属于技术领域。本发明提供的一种基于子图同构的FPGA软件可疑电路检测方法，可实现对FPGA软件设计阶段代码中存在的可疑电路的快速和低成本检测。

摘要： 一种基于子图同构的社交网络中意见领袖角色识别方法及其存储介质，包括从网络媒体获取的用户活动信息，提取用户之间的活动关系，将具体用户抽象为网络节点，进行社交网络的构建；读取社交网络模型，选取网络节点的多个多维度图指标属性，依据所计算的多种图属性指标，对三种指标进行多目标决策计算，给出核心用户列表；进行查询图构建，判断每个核心用户节点是否满足领导‑下级模式或传播者模式，并生成最终结果。本发明可以发现社交网络中的高影响力用户的角色信息，帮助相关人员对暗网中的犯罪分子密谋策划犯罪活动进行分析，对社交网络中的谣言传播者进行发现，对网络空间治理人员给予有力的数据支撑。

摘要： 本发明公开了一种基于图节点信息聚合的子图同构约束求解方法，包括如下步骤：1）获取模式图和目标图；2）聚合邻居信息；3）生成约束；4）建立路径约束；5）要求匹配模式图与目标图的路径数；6）建立子图同构的CSP求解模型；7）求解子图同构的CSP求解模型。这种方法提高了子图同构的匹配效率，节约了子图同构匹配的时间。