多路复用网络中的模体检测算法

多路复用网络可以形象地描述复杂系统中个体之间的相互作用关系,模体作为一种高阶结构在网络中频繁出现。与单层模体相比,多重模体具有数量多、种类繁、结构杂的特点。鉴于目前缺少针对多重模体的完整检测算法,提出一种适用于多路复用网络的快速多重模体检测算法(FAMMD)。首先,通过改进ESU(Enumerate SUbgraphs)算法进行多重子图枚举;其次,使用层标记和二进制字符串相结合的方法加速同构检测的过程,并且构造了保持度序列和层间依赖性不变的零模型进行多重子图测试;最后,在两层真实网络上进行了模体检测,多重模体表现出紧密相连的三联模式,且在社交网络中更加同质,在交通网络中则更加互补。实验结果表明,所提方法可以准确、快速地检测出反映网络结构特性和符合实际情况的多重模体。

HashESU:一种生物网络模体识别高效方法

通过模体识别可以获得生物网络结构和功能,生物网络模体识别过程涉及到子图枚举和子图同构的问题,计算量非常大.提出一种高效的网络模体识别算法Hash ESU,它使用经典算法ESU枚举子图,采用Hash表结构保存生成的子图,利用每个新增结点与已经确定的结点之间的关系,生成子图标识关键字SIK并映射到Hash表中,每个SIK只在第一次生成时才需要调用同构计算,以大大减少调用NAUTY算法进行同构检测的次数、更快地进行查找和插入子图操作,进而加快模体识别的速度.实验结果表明,在模体识别结果质量相同的前提下,Hash ESU算法的运行效率明显优于著名的ESU算法和使用四分树结构存储子图的Quate Xelero算法.

基于预处理-枚举的子图匹配算法

子图匹配是从与查询图格式相同的数据图中找到所有嵌入。目前常用的算法主要通过基于查询图在数据图上生成树结构索引来工作,对树中的顶点根到叶的路径进行排序,并按照匹配顺序枚举嵌入。但是这种处理方式由于没有考虑路径中邻接点之间的影响,其基于路径的排序和基于树结构的枚举在本质上限制了算法的性能。为了解决这个问题,提出了一种基于预处理-枚举的子图匹配算法。先通过查询顶点的前向邻居生成候选集,再通过后向邻居对候选集进行精化得到更小的候选集。同时,根据查询顶点的候选数量和度生成匹配顺序,进一步消除了基于路径的排序带来的限制。针对真实数据集的模拟实验结果表明,所提出的算法与现有的算法相比具有更好的候选集过滤效果和更快的匹配速度。

五面体平图中的生成树的构造与计数

首先给出了生成子图的定义,生成子图与生成树、含圈的生成子图的关系S(G)=C(G)+T(G);其次对于任意连通图,以p=4,q=6的完全图K4为例给出了生成子图个数的计算公式,同样以p=4,q=6完全图K4为例给出了生成树的构造定理和计数定理,提出了图S(G)生成树的计数方法和构造方法;最后,介绍了五面体平图生成子图个数的计算和各生成子图的构造,并验证了所给公式的正确性,从而解决了任意平图G(p,q)生成树的构造问题。

计数一阶相关免疫布尔函数

基于列平衡矩阵的概念,利用组合数学中的容斥原理和图论中的子图概念,给出了在流密码学中有重要应用的一阶相关免疫布尔函数的一般计数公式。

一种高效的凸连通子图枚举算法

在可配置处理器的定制指令设计过程中，需要提取热点代码数据流图的凸连通子图．为实现子图的快速枚举，对有向无环图内的凸子图特性进行了研究．根据凸子图特性和节点邻接关系，提出了一种AS（adjacent search）算法用于枚举有向无环图内满足I／O端口约束的凸连通子图．实验数据显示，AS算法比现有算法具有更高的效率，加速比可达10～1000X．当现有算法因数据流图规模较大而失效时，应用AS算法仍能成功完成子图枚举．

特殊子图的计数

计数问题是图论研究的一个课题,图的一些特殊子图的计数确定了图的着色性;在这里使用组合数学的方法,估计了二部图K(u,v)-A和三部图K(n+a1,n+a2,n+a3)-A的三角形子图和没有弦的四边形子图的计数,在三部图中比较了这些特殊子图的计数。

两棵树的公共子树查找算法综述

本文通过对基于两棵树中的公共子树查找问题在有根、带标记、有序树中的主要算法及相关历史的回顾,结合算法思想将公共子树查找问题分为主要3类。本文深入探讨了每类算法中的代表算法,其中根据数据挖掘中枚举树相关技术提出了一种可能的公共子树查找算法的思想。最后比较了文中主要算法的效率,同时较为深入地分析和讨论了公共子树的相关研究及未来可能的研究发展方向。

应用子图划分策略的不确定图极大团枚举算法

为了更加高效地枚举出不确定图极大团,通过对现有确定图和不确定图极大团枚举算法进行研究,结合在相同图结构下确定图极大团与不确定图极大团之间的关系,提出了一种基于相同图结构确定图极大团子图划分的高效不确定图极大团枚举算法D-MULE-D。通过在不同的真实数据集上进行实验测试,对比D-MULE-D算法和MULE算法的运行时间,验证D-MULE-D算法的可行性和高效性。

面向高层次综合的自定义指令自动识别方法

针对在高层次综合(HLS)过程中性能提升、功耗降低困难等问题,提出了一种面向高层次综合的自定义指令自动识别方法。在高层次综合过程之前实现对自定义指令的枚举和选择,从而为高层次综合提供通用的自定义指令识别方法。首先,将高层次源代码转换为控制数据流图(CDFG),实现了对源代码的预处理;其次,基于控制数据流图内的数据流图(DFG),采用子图枚举算法以自底而上的方式枚举出所有连通凸子图,有效提高了用户可灵活修改约束条件的能力;然后,分别从面积、性能和代码量三个角度考虑,利用子图选择算法选择部分最佳子图作为最终的自定义指令;最后,用所选的自定义指令重新生成新代码作为高层次综合工具的输入。与传统高层次综合相比,采用基于出现频率的模式选择可平均减少19.1%的面积,采用基于关键路径的子图选择可平均减少22.3%的时延。此外,与TD算法相比,所提算法的枚举效率平均提升70.8%。实验结果表明,自定义指令自动识别方法使高层次综合在电路设计中能够显著地提升性能,减少面积和代码量。

生物复杂网络motif发现的并行算法

生物复杂网络motif发现是一种研究生物网络的重要方法,它基于复杂网络的理论研究,以新的视角来研究生命现象和生命机制,但是在处理较大的网络规模或者需挖掘较大的motif时计算效率低。针对这个问题,在现有串行网络motif发现算法ESU的基础上,提出一种基于消息传递接口(MPI)的并行化ESU算法。该方法在ESU计算过程中优化了节点值以解决节点值依赖问题,并以ESU算法的子图发现策略统计各节点子图数,利用动态规划策略寻找最佳节点分配策略以解决负载不均衡问题。模拟网络数据和真实生物网络数据的实验结果表明,并行化ESU算法优化了节点值依赖问题,实现了基于动态规划的负载均衡策略,其运行时间比串行算法缩短了90%,并且该并行算法对不同类型不同规模的网络都具有较强的适用性,有效地提高了网络motif发现问题的计算效率。

Graphlet Degree Vector方法的优化与并行

Graphlet Degree Vector(GDV)是一种研究生物网络的重要方法,能揭示生物网络中各节点与其局部网络结构的相关性,但随着需要挖掘的自同构轨道数量的增加以及生物网络规模的增大,GDV方法的时间复杂度会呈指数级增长。针对这个问题,在现有串行GDV方法的基础上,实现了基于消息传递接口(MPI)的GDV方法并行化;此外又将GDV方法进行了改进并将改进后的方法实现了并行优化,改进后的方法在寻找不同节点自同构轨道的过程中优化了计算过程以解决重复计算的问题,同时结合负载均衡策略合理分配任务。模拟网络数据和真实生物网络数据上的实验结果表明,并行化的GDV方法与改进后的并行化GDV方法都具有较好的并行性能,并且对不同类型不同规模的网络都具有较强的适用性,扩展性强,可有效地保持寻找网络中自同构轨道的高效率。