背包类问题的并行O(25n/6)时间-空间-处理机折衷

将串行动态二表算法应用于并行三表算法的设计中,提出一种求解背包、精确的可满足性和集覆盖等背包类NP完全问题的并行三表六子表算法.基于EREW-PRAM模型,该算法可使用O(2^n/8)的处理机在O(2^7n/16)的时间和O(2^13n/48)的空间求解n维背包类问题,其时间-空间-处理机折衷为O(2^5n/6).与现有文献的性能对比分析表明,该算法极大地提高了并行求解背包类问题的时间-空间-处理机折衷性能.由于该算法能够破解更高维数的背包类公钥和数字水印系统,其结论在密钥分析领域具有一定的理论和实际意义.     

确定任意多边形凸凹顶点的算法

本文提出一种确定任意多边形凸凹顶点的算法．该算法的时间复杂性为O(n²logn)次乘法和O(n²)次比较．     

背包问题的最优并行算法

利用分治策略,提出一种基于SIMD共享存储计算机模型的并行背包问题求解算法.算法允许使用O(2^n/4)^1-ε个并行处理机单元,0≤ε≤1,O(2^n/2)个存储单元,在O(2^n/4(2^n/4)^ε)时间内求解n维背包问题,算法的成本为O(2^n/2).将提出的算法与已有文献结论进行对比表明,该算法改进了已有文献的相应结果,是求解背包问题的成本最优并行算法.同时还指出了相关文献主要结论的错误.     

一类实际网络中的最小截算法

讨论了节点和边都有容量限制的无向平面网络中的两点间的最小截问题.传统方法是把节点和边都有容量的网络中的最小截问题转化为只有边有容量的问题,但该方法用在平面网络时不能保持网络的平面性,因此网络的平面性不能得到利用.使用传统方法的计算时间为O(n²logn)(其中n为网络的节点数).给出了可以充分利用网络平面性的方法.对源和汇共面的s-t平面网络,把最小截问题转化为平面图上两点间的最短路径问题,从而可以得到O(n)时间的算法;对一般的平面网络,给出了新的将节点和边都有容量的问题转化为仅边有容量问题的方法,这种转化方法不破坏网络的平面性,从而可以利用平面网络中仅边有容量问题的计算方法,使原问题在O(nlogn)时间内获得解决.     

模糊聚类计算的最佳算法

给出模糊关系传递闭包在对应模糊图上的几何意义,并提出一个基于图连通分支计算的模糊聚类最佳算法.对任给的n个样本,新算法最坏情况下的时间复杂性函数T(n)满足O(n)≤T(n)≤O(n²).与经典的基于模糊传递闭包计算的模糊聚类算法的O(n³logn)计算时间相比,新算法至少降低了O(n相似文献   

PRAM和LARPBS模型上有向序列翻转距离并行算法

分别在两种重要并行计算模型中给出计算有向基因组排列的反转距离新的并行算法.基于Hannenhalli和Pevzner理论,分3个主要部分设计并行算法:构建断点图、计算断点图中圈数、计算断点图中障碍的数目.在CREW-PRAM模型上,算法使用O(n²)处理器,时间复杂度为O(log²n);在基于流水光总线的可重构线性阵列系统(linear array with a reconfigurable pipelined bus system, LARPBS)模型上,算法使用O(n³)处理器,计算时间复杂度为O(logn).     

双向选择排序算法

为丰富O(n²)阶排序算法的种类,以更好地服务于教学科研和日常应用,提出了一种新的排序算法-双向选择排序算法.通过数学方法分析得知:该算法的时间复杂度为O(n²),空间复杂度为O(1).通过实验对比得知:在相同条件下,该算法的运行时间平均为冒泡排序的27%、简单选择排序的62%、直接插入排序的88%.     

一种高效频繁子图挖掘算法

由于在频繁项集和频繁序列上取得的成功,数据挖掘技术正在着手解决结构化模式挖掘问题--频繁子图挖掘.诸如化学、生物学、计算机网络和WWW等应用技术都需要挖掘此类模式.提出了一种频繁子图挖掘的新算法.该算法通过对频繁子树的扩展,避免了图挖掘过程中高代价的计算过程.目前最好的频繁子图挖掘算法的时间复杂性是O(n³·2ⁿ),其中,n是图集中的频繁边数.提出算法的时间复杂性是O〔2ⁿ·n^2.5／logn〕,性能提高了O(√n·logn)倍.实验结果也证实了这一理论分析.     

虫孔路由Mesh上的连通分量算法及其应用

用倍增技术在带有Wormhole路由技术的n×n二维网孔机器上提出了时间复杂度为O(log²n)的连通分量和传递闭包并行算法,并在此基础上提出了一个时间复杂度为O(log³n)的最小生成树并行算法.这些都改进了Store-and-Forward路由技术下的时间复杂度下界O(n).同其他运行在非总线连接分布式存储并行计算机上的算法相比,此连通分量和传递闭包算法的时间复杂度是最优的.     

RNA二级结构预测中动态规划的优化和有效并行

基于最小自由能模型的方法是计算生物学中RNA二级结构预测的主要方法,而计算最小自由能的动态规划算法需要O(n⁴)的时间,其中n是RNA序列的长度.目前有两种降低时间复杂度的策略:限制二级结构中内部环的大小不超过k,得到O(n²×k²)算法;Lyngso方法根据环的能量规则,不限制环的大小,在O(n3)的时间内获得近似最优解.通过使用额外的O(n)的空间,计算内部环中的冗余计算大为减少,从而在同样不限制环大小的情况下,在O(n³)的时间内能够获得最优解.然而,优化后的算法仍然非常耗时,通过有效的负载平衡方法,在机群系统上实现并行程序.实验结果表明,并行程序获得了很好的加速比.     

基于节点依赖度和相似社团融合的社团结构发现算法

社团结构作为复杂网络的拓扑特性之一具有重要的理论和实践意义。提出一种基于节点依赖度和相似社团融合的社团结构发现算法,首先根据依赖度和相似度的定义将整个网络划分成若干个平均集聚系数较大的局部网络,构成网络的基础骨架社团;然后根据连接度的定义不断将社团边缘的节点和小社团吸收到相应的骨架网络中去,直到所有节点都得到准确的社团划分。算法在Zachary空手道俱乐部网络和海豚社会网络中进行了社团划分实验,并与GN算法和Newman快速算法进行了比较,结果表明该算法可以有效地划分社团边缘的模糊节点,社团划分结果具有较高的准确度。     

基于网络嵌入与局部合力的复杂网络社区划分算法

社区划分可以揭示复杂网络中的内在结构和行为动态特点,是当前的研究热点。文中提出了一种基于网络嵌入和局部合力的社区划分算法。该算法将网络的拓扑空间转化成欧氏空间,把网络节点转换成向量表示的数据点,首先基于重力模型和网络拓扑结构,提出局部合力和局部合力余弦中心性指标(Local Resultant Force Cosine Centrality,LFC),通过节点的LFC和节点间的距离来确定各个初始小社区的中心节点,然后将网络中其他的非中心节点划入与其最近的中心节点所在的初始小社区内,最后通过优化模块度的方法来合并初始小社区并找到最优的网络社区结构。在6个现实世界网络和可调参数人工网络上与6种知名社区划分方法进行比较,比较结果表明了新算法良好的社区划分的性能。     

踪迹聚类下组织实体的重要度排序方法

针对简单套用交接网络等社会网络分析方式不能很好地反映踪迹聚类生成的一系列流程的组织实体的重要度的问题,提出了一种踪迹聚类下组织实体的重要度排序方法。首先,对于参与踪迹聚类生成的一系列流程的组织实体构建踪迹聚类与组织实体关系网络;其次,定义基于踪迹聚类与组织实体关系网络的节点重要度评估方法;最后,对踪迹聚类下的各个组织实体节点计算其在关系网络中的重要度评分并排序。实验结果表明,所提方法构建的关系网络相比踪迹聚类下的交接网络能够更准确地反映组织实体的实际重要度;与基于拓扑势的网络社区节点重要度排序算法相比,所提方法的节点重要度排序结果更符合实际业务流程,能更好地区分关系网络中重要度不同的节点。     

融合拓扑势的社交网络层次化社区发现算法

社交网络的社区结构呈现层次性。针对传统凝聚式层次化社区发现算法效率不高以及生成的层次谱图复杂的问题，提出一种融合拓扑势的层次化社区发现算法，利用拓扑势场呈现的自然峰谷结构揭示社交网络社区间的层次关系。该算法搜索局部极大势值节点，并根据局部极大势值节点完成社区的初始划分；根据局部极大势值节点间的距离对初始社区进行迭代合并，直到所有社区被合并为一个社区。在真实社交网络和人工网络上的实验结果表明，该算法能够高效地发现社区的层次结构，生成的层次谱图简单直观。     

基于拓扑特征的二分网络社团结构划分

目前社团结构划分算法只能划分1类节点并且依赖于额外参数。为此,在分析二分网络社团拓扑特征的基础上,利用社团核与外层的思想,提出一种新的社团结构划分算法。该算法完全依赖于原始网络本身的拓扑结构,并且允许社团间重叠。实验结果表明,该算法无需任何额外参数,即可比较准确地识别实际网络的社团个数,同时划分2类节点的社团结构。     

结合拓扑势与信任度调整的重叠社区发现算法

现实世界中的复杂系统可建模为复杂网络,探究复杂网络中的社区发现算法对于分析复杂网络的拓扑结构和层次结构具有重要作用。早期研究通常将网络中的节点局限在一个社区中,但随着研究的深入发现社区结构呈现重叠特性。针对现有重叠社区发现算法存在划分社区结构不稳定、忽略节点交互和属性等问题,提出一种基于网络拓扑势与信任度调整的重叠社区发现算法。融合节点的属性和结构特征计算节点的拓扑势,依据节点的拓扑势选取核心节点。从核心节点出发构建初始社区群,计算各个社区间的调整信任度,实现社区的合并与再调整,从而识别重叠社区。在多个人工模拟网络和真实网络数据集上的实验结果表明,与基于贪婪派系扩张、种子扩张等的重叠社区发现算法相比,该算法将扩展模块度最高提升至0.719,能有效识别社区结构及重叠节点,提升重叠社区检测性能。     

基于标签传播的拓扑势社区检测算法

基于拓扑势的社区检测通过节点的链接信息构造拓扑势域,在拓扑势域内进行社区划分.但实际划分过程存在大量孤立性社区.带节点属性信息的社区检测问题作为社区的重要组成,已成为社区检测的主要研究方向.本文提出了一种结合标签传播的拓扑势社区检测算法（TPCDLP）.首先,结合标签传播思想将属性信息转换为节点间的链接权值.其次,把链接权值加入到拓扑势中构造拓扑势域.再利用核心节点进行子群社区的划分.最后,利用子群社区间核心节点的距离进行社区划分.在3个含标签属性的数据集上,与6种算法对比,该算法在改进的模块度$Q_{ov}^E$、信息熵$Entropy$、社区重叠度$Overlap$和综合指标F上表现更优.在3个真实社区上应用了该算法,并与3种算法对比,实验结果显示该算法在标准化互信息指标$NMI$上表现良好,能够有效应用于实际问题.     

具有社会网络特性的P2P分层搜索机制

无结构P2P网络中基于泛洪法的搜索机制会给系统带来极大的网络负载,结构化P2P网络则需要较大的开销来维护其拓扑结构。针对该问题,给出一种具有社会网络特性的P2P分层搜索机制。根据社会网络的基本原理,将语义相似度高的节点分布在同一个虚拟社区,节点在虚拟社区内能动地建立搜索链接。实验结果证明,该搜索机制能有效地提高P2P网络的资源搜索效率。     

基于社区优化的深度网络嵌入方法

随着现代网络通信和社会媒体等技术的飞速发展,网络化的大数据由于缺少高效可用的节点表示而难以应用。将高维稀疏难于应用的网络数据转化为低维、紧凑、易于应用的节点表示的网络嵌入方法受到广泛关注。然而已有网络嵌入方法得到节点低维特征向量后,再将其作为其他应用（节点分类、社区发现、链接预测、可视化等）的输入来作进一步分析,没有针对具体应用构建模型,难以取得满意的结果。针对网络社区发现这一具体应用,提出结合社区结构优化进行节点低维特征表示的深度自编码聚类模型CADNE。首先基于深度自编码模型,通过保持网络局部及全局链接的拓扑特性来学习节点的低维表示,然后利用网络聚类结构对节点低维表示进一步优化。该方法同时学习节点的低维表示和节点所属社区的指示向量,使节点的低维表示不仅能保持原始网络结构中的拓扑结构特性,而且能保持节点的聚类特性。与已有的经典网络嵌入方法进行对比,结果显示CADNE模型在Citeseer和Cora上取得最优聚类结果,在20NewsGroup上准确率提升最高达0.525;分类性能在Blogcatalog、Citeseer数据集上取得最好结果,在Blogcatalog上训练比例20%时比基线方法提升最高达0.512;并且CADNE模型在可视化对比中能够得到类边界更加清晰的节点低维表示,验证了所提方法具有较好的节点低维表示能力。     

基于网络社区发现的标签传播聚类算法

高维数据的聚类特性通常难以直接观测. 将其构建为复杂网络, 节点间的拓扑结构可以反映样本之间的关系. 对网络中的节点进行社区发现, 可实现对数据更直观的聚类. 提出一种基于网络社区发现的低随机性标签传播聚类算法. 首先, 用半径和最近邻方法将数据集构建为稀疏的全连通网络. 之后, 根据节点相似度进行节点标签预处理, 使得相似的节点具有相同的标签. 用节点的影响力值改进标签传播过程, 降低标签选择的随机性. 最后, 基于内聚度进行社区的优化合并, 提高社区的质量. 在真实数据集和人工数据集上的实验结果表明, 该算法对各种类型的数据都具有较好的适应性.