SIHC:一种高效的时态图上k-core查询算法

许多实体之间的关系可以建模为时态图,其中每条边都与表示其发生的时间相关联,k-core是捕获密集子图的基本模型,在近些年得到了广泛研究.给定时间区间I=[s,e]和k值,时态图G上的k-core子图查询从区间I对应的快照图GI中返回相应的k-core子图.针对时态图中的k-core子图查询问题,现有方法是基于PHC索引(Pruned Historical Core-Index)的算法.对任意可能的k值,PHC索引维护了所有可能出现在某个时间区间的k-core子图中的顶点集Sk,且为集合中每个顶点存储了一组时间区间,用于判定该点是否属于给定时间区间的k-core子图.基于PHC索引查询k-core子图时,需要访问Sk集合中的所有顶点,并判断每个顶点的可满足性.由于Sk集合对应于最大区间快照图的k-core子图里的所有顶点,且实际中用户查询区间对应的快照图往往比最大区间快照图小得多,基于PHC索引的查询算法存在许多无效判断,需要对大量不在结果集中的顶点进行检测,且无效检测次数随着查询区间的缩短而增多,从而导致算法效率较低.针对该问题,本文提出一种新的索引,即最短区间历史核索引SIHC(Shortest Interval Historical Core Index).SIHC索引的基本思想是通过维护最短k核区间到顶点的倒排表,查询处理时,可基于用户给定的时间区间定位到SIHC索引中满足条件的区间,进而直接得到满足条件的k-core子图中的顶点,从而避免了基于PHC索引进行查询时所需的大量无效判断.我们从理论上证明了基于SIHC索引处理时态图上k-core子图查询的正确性,并设计了高效的索引构建算法.最后,基于真实世界的时态图进行了实验,实验结果表明本文提出的算法比现有算法快1~2个数量级.

基于可控制性度量的图神经网络门级硬件木马检测方法

随着全球化的不断深入,第三方知识产权(IP)核应用越来越广泛。随着硬件木马攻击技术逐渐成熟,使得在芯片设计阶段植入硬件木马成为可能。因此,在芯片设计过程中面临IP核被植入木马的严重威胁,现有研究所提的硬件木马检测方法具有依赖黄金参考电路、需要完备的测试向量、大量的样本进行学习等特征。面向IP核的硬件木马检测需求,提出一种基于可控制性度量的图神经网络检测方法。该方法以门级网表作为输入,首先以可控制性值为指导,得到可疑的门节点,用于缩小搜索范围;然后利用可疑门节点生成对应的子图,利用图卷积神经网络从子图中提取特征,实现对子图的分类和检测,最终识别硬件木马。实验结果表明,该方法无须测试激励和黄金模型,利用硬件木马的隐蔽特性与结构特征相结合的方法提升硬件木马的检测准确率,平均真阳率为100%,假阳率为0.75%,在保证较高真阳率的同时可有效降低假阳率,达到较好的检测效果。

基于邻域k-核的社区模型与查询算法

现实生活中的网络通常存在社区结构,社区查询是图数据挖掘的基本任务.现有研究工作提出了多种模型来识别网络中的社区,如基于k-核的模型和基于k-truss的模型.然而,这些模型通常只限制社区内节点或边的邻居数量,忽略了邻居之间的关系,即节点的邻域结构,从而导致社区内节点的局部稠密性较低.针对这一问题,将节点的邻域结构信息融入k-核稠密子图中,提出一种基于邻域连通k-核的社区模型,并定义了社区的稠密度.基于这一新模型,研究了最稠密单社区查询问题,即返回包含查询节点集且具有最高稠密度的社区.在现实生活图数据中,一组查询节点可能会分布在多个不相交的社区中.为此,进一步研究了基于稠密度阈值的多社区查询问题,即返回包含查询节点集的多个社区,且每个社区的稠密度不低于用户指定的阈值.针对最稠密单社区查询和基于稠密度阈值的多社区查询问题,首先定义了边稠密度的概念,并提出了基于边稠密度的基线算法.为了提高查询效率,设计了索引树和改进索引树结构,能够支持在多项式时间内输出结果.通过与基线算法在多组数据集上的对比,验证了基于邻域连通k-核的社区模型的有效性和所提出查询算法的效率.

基于子图同构的vEPC虚拟网络分层协同映射算法

5G及未来移动通信网络虚拟化的场景下,资源的管理与编排是实现虚拟化演进分组核心网(v EPC)业务高效部署的关键问题。v EPC中业务功能的载体是服务功能链(SFC),不同服务功能链的控制信令与多媒体数据流呈现负载差异化特点。该文针对传统算法资源定比分配所导致的负载不均问题,提出服务功能链的控制层和转发层解耦的映射模型,解耦后不同层的服务链可以独立地扩容和缩容,实现资源精准按需切片。拓扑映射阶段引入图相似理论,提出一种基于子图同构的虚拟网络映射算法VF2-H,依据节点的全局资源度优选映射子网,通过图特征分析设置剪枝条件,采用回溯机制进行启发式搜索。仿真结果表明,该算法在租户请求接收率、长期收益开销比等方面均具有良好的性能。

基于贪婪策略的紧密k核子图查询

k核查询是一种社团查询,由于其可以在线性时间内被有效计算,因此在社团检测中具有较广泛的应用。图中边的权值在很多场景下具有较强的语义关系,但现有研究较少考虑图中边的权值。为提升k核查询的效率,在k核的基础上定义加权图中的紧密k核子图查询(CRKSQ)问题,并使用归约方法证明该问题是NP-难的。基于贪婪策略设计启发式算法CRK-G,通过迭代删除节点为CRKSQ问题找到一个近似解。在此基础上,从降低图规模和减少迭代次数两方面研究CRK-G算法的优化策略,分别提出使用图压缩策略的算法CRK-C及使用单次多节点删除策略的算法CRK-F。在Bio-GRID、Email-Enron、DBLP 3个数据集上的实验结果表明,相对于CRK-G算法,CRK-C、CRK-F算法在查询速度上有较大的提升,且平均误差均在8%以内。

异构属性网络中统计显著密集子图发现算法研究

密集子图体现了大图中的稠密部分,它是图中具有最高密度的子图,这使得它在事件检测,生物分析和社区发现等方面具有广泛应用和实用价值.现有的密集子图发现方法所使用的图模型描述不够详细,并且发现的密集子图缺乏统计显著性.为了解决以上问题,本文提出了异构属性网络这一新模型,然后在异构属性网络上通过非参数扫描统计和基于(k,Ψ)-核的方法发现高Steiner连通度的统计显著密集子图.首先构建异构属性网络,其包括类型、实体、关系和带有时序关系的属性信息;其次通过历史属性信息计算异构属性网络中每个实体的统计值,形成统计权重网络;然后利用非参数扫描统计方法测量统计权重网络中子图的统计显著性;最后由于此问题是NP-难的,于是提出了基于(k,Ψ)-核的局部扩展的近似统计显著密集子图发现算法.大量基于真实异构属性网络数据的实验结果证明了本文所提出算法的有效性和高效性.

基于VF2算法的vEPC网络高效部署策略

聚焦虚拟演进分组核心网(vEPC)相关技术,针对虚拟网络功能(VNF)部署问题,提出一种基于VF2算法的改进算法。通过资源约束判断与网络拓扑分析,推算VNF的所有可部署区域,借助所设计的物理网络资源的综合效用值,优选虚拟网络部署的最终方案。在开始部署区域搜索前,引入连通子图发现过程(CCDP),寻找物理网络中的连通区域,提升算法效率。仿真结果表明,该算法可使物理网络资源合理分配,减少资源碎片,提高用户请求接受率。

面向大规模时态图的紧密子图维护算法

大规模图数据中的重要顶点与层级结构对于挖掘复杂网络(如社交网络、交通网络等)中有价值的信息具有重要意义.提出一种自顶向下的大规模时态图(k,h)-维护算法,对时态图中紧密度最高的前n层(k,h)-核,或满足自定义k,h值约束条件的核进行维护.首先提出识别(k,h)-最大层的方法 .当时态图中出现新的边时,为了定位当前时刻可能因新加入边导致核值需要更新的顶点的范围,提出候选插入子图与部分(k,h)-核的概念及相应的识别算法.针对加边情况,提出自顶向下的时态图(k,h)-核维护加边算法,根据部分(k,h)-核识别核值受加边影响的顶点并对其核值进行更新.针对当前时刻有已经存在的边被删除的情况,提出自顶向下的时态图(k,h)-核维护删边算法,对上一时刻的(k,h)-核做最小调整以得到当前时刻的核值.从理论上证明了算法的正确性,还在真实的时态图上设计了一系列对比实验.实验结果表明,在维护层数较少时下添加边,提出的核维护算法与其他对比算法相比,加速比可达几十倍;删边时,加速比也在1~2倍.提出的算法有良好的扩展性,对于增删不同数量的边和不同的(k,h)设置,都能保持较高的效率.

基于概率推理的知识图谱中实体间关联度计算

针对知识图谱中实体间的关联关系存在不确定性、实体间关联度计算复杂度高等问题,提出一种基于贝叶斯网的实体间关联度的计算方法。针对知识图谱做预处理,利用剪枝后获取的核心子图构建贝叶斯网,提出基于知识图谱的贝叶斯网构建方法;利用贝叶斯网作为知识图谱中实体之间关联关系的量化和推理框架,基于贝叶斯网的概率推理,提出知识图谱中实体间关联度的定量计算方法。建立在真实数据之上的实验结果验证了方法的有效性。

一种新的犯罪团伙挖掘算法

为了利用图模式挖掘犯罪情报网络中的核心团伙和核心人物,提高犯罪网络威胁预测和识别的效率,提出一种新的核心团伙挖掘算法(Core Gang Mining Algorithm,CGMA).对海量的犯罪情报网络数据集建立相应的无向简单图模型,通过改进图挖掘方式,构建候选核心团伙集的数据结构,并提出由k-团伙通过连接和扩展2种操作得到(k+1)-团伙,从各个不同的图数据中统计其频度,最后在模拟数据集和真实数据集上验证算法CGMA的准确性和时间复杂度.该算法避免了传统的图模式挖掘中的子图同构问题,同时也优于其他常用的犯罪团伙挖掘算法.试验结果表明:该算法能对犯罪核心团伙信息进行有效预测.