基于改进GN算法的程序控制流图划分方法

针对控制流图规模过大导致的程序分析准确度和效率不够理想的问题,该文提出了一种用于控制流图划分的改进GN(Girvan-Newman)算法,在边介数计算中加入点权值作为参数,使划分所得各子图的规模更加平衡;通过动态控制子图的规模,在合适的时机提前终止算法执行,提高执行效率。利用angr工具对二进制程序进行分析所得到的控制流图,分别采用改进GN算法、K-means算法、谱聚类算法和朴素凝聚算法进行实验,比较不同算法对控制流图划分结果中的模块度以及均衡性等指标,证明改进GN算法具有最佳的划分结果和执行效率。     

求解最大完全子图的一种DNA算法

最大完全子图是图论中一个重要的问题。粘贴和删除模型是DNA计算的两个基本计算模型。利用改进的粘贴和删除模型给出求解最大完全子图的DNA算法。     

一种稳定的标签传播社区发现算法

网络中的社区发现是当前的一个研究热点。在众多社区发现算法中,标签传播算法因简单快速而被广泛应用。但标签传播算法也存在结果稳定性较差的问题。通过提取非重叠完全子图来避免社区重叠,提取最小极大团来避免巨型社区的出现,基于此,对标签传播算法的初始化过程进行改进,提出了一种稳定的标签传播社区发现算法,即非重叠最小极大团提取算法。在真实网络中的实验结果表明该算法可以大幅提高结果的稳定性。     

一种基于极大完全图扩展的社区挖掘算法

社区挖掘是复杂网络分析中一项重要工作.目前已有许多好的社区挖掘算法,但这些算法大多基于节点间的连接关系发现内聚的社会团体,而实际网络中节点大多具有不同的行为和影响力.基于此,充分考虑社区内节点相互连接紧密以及节点具有不同影响力的特性,提出一种基于极大完全图扩展的社区挖掘两阶段算法.第一阶段:从内聚的子团和度中心性节点的影响力出发,从网络中选取分散的k个内聚的且有影响力的极大完全图作为初始社区;第二阶段,基于局部社区模块度扩展方法,将重叠节点和初始社区外节点扩展到与其连接紧密的相应社区内.最后通过仿真实验验证了该算法的有效性.     

基于改进仿射传播聚类的多模型软测量建模及应用

对于多模型软测量建模,聚类效果、子模型的建模和融合方式对其模型精度有重要影响。对此,该文提出一种基于改进仿射传播聚类的多模型软测量建模方法。为提高聚类精度,在仿射传播聚类算法划分样本数据的基础上,采用人工鱼群算法对仿射传播聚类算法的偏向参数和阻尼系数寻优,同时针对距离较近类别边界处的样本再建立重叠类,采用支持向量机建立各类样本的回归子模型。分别用标准数据集仿真和工业双酚A生产装置的现场数据建模仿真,结果证明该方法是有效的。     

一种基于改进动态规划思路的众核软件映射算法

众核软件映射到处理器核心上,形成流水线执行,有利于挖掘软件任务模块的并行性,提高系统吞吐率.提出了一种基于改进的动态规划思路的软件映射算法,算法通过将图划分问题近似分解为多个子问题,通过寻求每个子问题的最优解进而获得全局最优解.动态规划思路的改进主要体现在实时更新可选任务节点和动态调整子图期望负载两方面,这有利于划分后的各子图负载更均衡.实验结果表明,算法在提高系统吞吐率方面均优于现有相关算法.     

一种基于改进的动态规划思路的众核软件映射算法

众核软件映射到处理器核心上,形成流水线执行,有利于挖掘软件任务模块的并行性,提高系统吞吐率.提出了一种基于改进的动态规划思路的软件映射算法,算法通过将图划分问题近似分解为多个子问题,通过寻求每个子问题的最优解进而获得全局最优解.动态规划思路的改进主要体现在实时更新可选任务节点和动态调整子图期望负载两方面,这有利于划分后的各子图负载更均衡.实验结果表明,算法在提高系统吞吐率方面均优于现有相关算法.     

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

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

基于复杂网络的社区发现算法

针对现有社区发现算法准确度较低的问题,该文提出了1种基于中心节点的社区发现算法。通过各节点度数及节点间相似度寻找社区的中心节点,然后利用局部模块度对各个社区进行优化,并根据节点吸引力将孤立节点和重叠社区节点尽量归入其社区,从而获得整个网络的社区划分。将该文算法分别与3种局部社区发现算法、4种全局社区发现算法相比较,实验结果表明,该算法可以提高社区发现的准确度,具有可行性。     

基于蚁群算法的子阵级自适应多波束形成

在大型阵列信号处理中,可以在子阵级进行数字波束扫描形成多波束,降低硬件成本和系统复杂度,其中子阵划分的优劣直接决定信号处理的性能.针对子阵级多波束形成的问题,提出了一种基于蚁群算法的子阵划分最优策略,该策略将蚂蚁的迁移路径作为子阵划分方案,以峰值旁瓣电平为优化目标进行迭代搜索,使得子阵级自适应形成多波束方向图的旁瓣性能...     

一种基于节点稳定性的社区发现算法

许多成功的社区发现算法已经被广泛应用于复杂网络社区发现任务中.随着数据复杂性的增加,网络中节点间的关系也呈现多样化的特点,因此提出一种基于信息熵的节点稳定性度量方法,衡量网络中节点在社区划分中的稳定性;并在此基础上提出一种基于节点稳定性的社区发现算法(Node Stability-based Algorithm,NSA).首先得到网络的t种社区划分,计算各节点的标签熵,选择熵小于一定阈值的节点作为网络的稳定节点集S;然后,利用所得到的稳定节点集S从原网络中抽取一个包含S的连通子图Gs,使Gs中节点的不稳定性尽可能低;在连通子图Gs上进行社区发现,得到初始聚类结果,再计算其他未聚类节点与初始类簇的距离,确定其社区归属,得到最终聚类结果 .在四个带标签真实网络数据集和八个不带标签的真实网络数据集上,与LPA,Infomap,Walktrap,BGLL,LPA-S等经典算法的比较实验表明,所提出的NSA算法能够较好地进行社区发现,在NMI和模块度等方面表现良好.     

Kv的完备匹配Mi的算法

给出了边矩阵的定义,提出了求解完备匹配Mi的2种算法.其中算法A是利用边矩阵K2n的△(G)一边着色求Mi,算法B是利用边矩阵K2n的2×2子矩阵划分及完全图Kn的n-1个完备匹配Mi的求解,再求Mi.介绍了用算法A构造循环赛图K(i)20的过程和用算法B构造循环赛图K(i)20的过程.     

基于gSpan算法的未知化合物毒性预测

gSpan算法是一种基于频繁图的挖掘算法。该算法基于无候选人产生的频繁子图,在图中建立字典序标号,将每个图映射为最小DFS code,再采用深度优先搜索策略挖掘频繁连接子图。与前人算法相比,该算法在生成候选子图时,冗余子图的产生量大大减少;在计算候选子图支持度时避免了大量重复扫描数据库,性能卓越。该文的贡献是将gSpan算法应用在挖掘与已知毒性化合物具有相同子结构的化合物研究工作中,进行未知化合物的毒性预测,对相关领域应用发展具有重要意义。     

基于结构近似度的社交网络聚类

针对基于结构近似度的聚类算法无法解决非对称网络聚类的问题,该文根据社交网络的特点,提出了基于结构近似度的有向社交网络聚类算法,通过将社交网络抽象为图结构,将网络聚类问题看成图论中的子图划分问题,实现了对社交网络的准确聚类分簇,且分簇复杂度较低。使用C++语言编程实现该算法,通过自定义有向网络数据集和标准数据集的测试表明,该算法对社交网络结构的划分较为准确,且能鉴别离群节点和枢纽节点。     

利用多级社区中心标签实现大规模图上距离查询

距离查询是图数据挖掘应用中的最基本的操作之一,但是目前的现存查询算法均无法高效处理大规模图数据.针对这个问题,提出建立多级社区中心的标签机制,即首先在原图中将结点按社区划分为多个集合,然后再将各集合中的中心结点建成带权查询子图,经过多次递归操作,最终为各结点建立一个基于社区中心的树状结构标签集,该标签集可以实现利用较短的创建时间和较小的存储代价大幅度提高距离查询的效率.从实验结果可以看出,该方法综合效率明显优于现存的高效算法.     

基于DCBM的马尔可夫谱聚类社区发现算法

谱聚类划分算法是经典社区发现算法之一,由于目前构造的相似图承载的社区结构信息较少,导致聚类效果与理想效果具有较大差距,因此,提出了基于DCBM的马尔可夫谱聚类社区发现算法MSCD.首先,基于DCBM模型提出了以节点间连接概率为元素的概率矩阵,并建立了概率矩阵与相似矩阵之间的映射关系;其次,利用马尔可夫链重构了谱聚类的相似图;最后,使用重构的相似图对网络进行社区划分.在人工合成网络和真实网络上与SC,MRW-KNN和FluidC三种典型算法进行了对比实验.实验结果表明,MSCD算法具有更加高效的聚类性能,能够揭示更加清晰的社区结构.     

有关完全图的算法及实现技术

讨论了求解极大完全子图算法的形式化，给出了带权的完全图中求最小权Ｈａｍｉｌｔｏｎ回路优化算法的软件实现。     

基于谱聚类带有节点特征的社区发现算法

提出一类基于谱聚类算法的带有节点特征的社区发现算法(SCSA),该算法首先将带有节点特征的网络图转化为加权图,其中边的权重用节点特征相似度度量,然后将谱聚类算法应用到加权图上进行社区检测.SCSA算法将带有节点特征的网络图分成K个社区,每个社区内节点不仅连接良好而且具有相似的特征属性.注意到不是所有节点的特征在社区划分过程中都是有用的,与划分无关的特征信息会降低社区发现算法的准确度.为此,提出了一类节点特征权重自调整机制嵌入到谱聚类中以提高社区检测质量.数值实验的结果验证了所提算法的有效性.     

考虑主题和时间的在线社交网络团体发现算法

如何准确、有效地发现虚拟社交网络中的社区或群体是复杂社交网络中的一个热点问题。本研究认为在线社交网络中用户之间显性的对话或彼此评论形成了一种网络结构,既包含社交网络底层的拓扑结构信息,又包含网络实体进行交互的确切时间,具有时效性。为了揭示虚拟社交网络中隐藏的动态现象,给出了一种同时考虑主题和时间的在线社交网络发现算法——多时间密集子图发现算法。首先,将在线社交网络中的对话或评论建模为一个交互网络,再利用拓扑结构将网络划分为属于不同主题(如热门新闻或话题)的社区,然后依据时间维度对每个主题下的社区挖掘稠密子图,最后在真实数据集上对所提算法进行了评估。与比较算法相比,本算法发现的团体内部间的交互在时间上更加密集,具有更高的时效性。     

基于矩阵填充的子阵重构二维波达方向估计算法

为提高稀疏阵列下二维波达方向(2D-DOA)估计的效率,提出1种基于加速近邻梯度矩阵填充的子阵重构旋转子空间(APG-SRESPRIT)算法。建立了基于矩阵填充的稀疏阵列DOA估计信号模型,并验证该信号模型满足零空间性质。通过加速近邻梯度算法将该信号模型恢复为完整信号,划分子阵并构建合并矩阵。对合并矩阵进行奇异值分解,在子阵重构后估计目标角度,且目标角度自动配对。仿真实验表明该文算法可减少70%的阵元数量,且在稀疏阵列下准确估计2D-DOA。