一种基于邻居信息的最大派系过滤算法

最大派系问题(Maximal Clique Problem, MCP)是组合优化中经典而重要的问题之一,在信息抽取、信号传输、计算机视觉、社会网络及生物信息学等众多领域有着重要的应用。学者们根据不同的思想策略,提出了许多方法求解最大派系问题,如分支定界、遗传算法、模拟退火、交又嫡及DNA方法等。现根据派系的部居信息提出一种基于派系邻接顶点和邻接边的派系过滤算法。算法从一个已知派系(初始为一个单独顶点)出发,每次考察派系的部接顶点,并以派系的邻接边为基础,扩展已有派系而得到更大的派系。用两个大规模的科学家合作网络对提出的算法进行了分析,并讨论了大规模社会网络中的派系分布情况。实验表明,提出的算法可有效地抽取网络中的最大派系。     

一种求解集合覆盖问题的启发式算法

集合覆盖问题是运筹学研究中的一个基本的组合优化问题,它通常描述成如下的一个覆盖问题:从一个m行、n列的0-1矩阵(aij)m×n中选出若干列盖住所有的行,使得付出的代价最小.集合覆盖问题被广泛应用到航空人员行程安排、电路设计、运输的车辆路线安排等领域.对这一问题,国内外学者提出了诸如遗传算法、模拟退火算法、蚁群算法、人工神经网络算法等求解算法.本文以贪心算法为基础,利用人类的智慧和经验,提出了一种求解集合覆盖问题的启发式算法.算法的主要思想为:从某个解出发,随机移除一定比例的列,再用贪心策略加入若干列.用本文提出的算法,对Beasley提出的45个测试实例进行了实算测试,所得结果和最优解的平均相对差值为0.44%,并且得到了其中33个实例的最优解,实算结果表明,本文提出的算法对求解集合覆盖问题是行之有效的.     

基于特征工程的重要节点挖掘方法

复杂网络中重要节点的挖掘对分析和治理现实复杂系统有着重要的指导意义。设计能反映节点重要性的有效计算方法,是高效准确挖掘重要节点的关键。该文基于节点的邻居信息,采用特征工程中的特征提取、特征重构等方法提取能有效反映节点局部结构的特征向量。利用局部特征向量,通过回归模型建立节点局部结构和重要性的关系模型。在13个真实网络上的实验结果表明,相比于已有的重要节点挖掘基准方法,该方法具有更优的性能。     

一种基于社会网络分析的P2P僵尸网络反制策略

设计并实现了一种基于社会网络分析的P2P僵尸网络反制策略.该策略包括两个方面:第一,挖掘网络中的关键节点和桥梁节点,重点防护这两类节点;第二,挖掘网络中的社区结构,重点监控社区间的关键通讯.模拟实验表明,该策略能准确挖掘网络中的关键节点、桥梁节点和关键通讯边,挖掘桥梁节点和关键边的准确率分别达到了95%和93%.使用提出的策略可有效控制僵尸网络病毒和黑客攻击指令的传播,从而达到反制P2P僵尸网络的目的.     

一种求解集装箱装载问题的启发式算法

所谓集装箱装载问题,就是将若干大小不同的长方体盒子装进一个大小已知的长方体容器,其目标是最大化容器的积裁率.对这一问题,国内外学者利用不同的哲学思想,提出了诸如遗传算法、模拟退火算法等求解算法.本文提出一种求解此问题的基于最大穴度优先原则的启发式算法.算法中使用了两个重要的策略:最大穴度原则和最小边度原则.用一些公开的算例对算法性能进行了实算测试,测试结果表明:算法所得结果的容器积载率高,是求解集装箱装载问题的有效算法.     

改进的势能曲面变平法在二维非格点模型中的应用

蛋白质结构预测问题是生物信息学中的一个重要问题.缺少一种有效的全局寻优方法是阻碍这一问题解决的关键.势能曲面变平(ELP)法是一种启发式的全局优化方法,是一种推广的Monte Carlo方法,已成功地应用于许多优化问题.在ELP法的基础上,提出了改进的势能曲面变平(ELP )算法.将ELP 算法应用于二维非格点的蛋白质AB模型,预测和发现四条链长分剐为13,21,34和55的氨基酸序列的蛋白质结构.数值实验表明,ELP 算法是一种预测蛋白质结构的有效算法.     

网络科学中相对重要节点挖掘方法综述

网络科学中相对重要节点的挖掘具有重要的实际应用价值。设计衡量节点相对重要程度的指标和方法，是准确有效地识别复杂网络中相对重要节点的关键。本文对近二十多年来网络科学领域中提出的相对重要节点衡量指标和方法进行了系统性地综述，利用数值模拟方法对这些衡量指标和方法的准确度进行了分析和比较，并讨论了相对重要节点挖掘的一些开放问题和发展趋势。     

重叠社区发现的两段策略

复杂网络中的社区特别是重叠社区在信息传播与推荐、舆情控制、商业营销等领域中具有重要作用。在实际的网络中,由于有些节点天然地属于多个功能团体,重叠社区的挖掘越来越受到重视。提出了一种重叠社区挖掘的两段策略算法:初始社区抽取与社区合并。在社区抽取阶段,选择网络中最大度节点及其紧密的邻居节点作为初始社区,将与此初始社区联系紧密的节点也一并加入;在社区合并阶段,如果两个社区合并之后使得模块度增加,则合并这两个社区。用包括大规模网络在内的3个实际网络对所提算法进行了测试,结果表明,该算法可有效挖掘网络中的重叠社区。     

时序阵发性对信息传播的影响

近年来,传播动力学是网络研究的一个热门话题,传统的信息传播都是在静态网络上进行研究的,但现实生活中许多网络是有时序的。到目前为止,已有很多学者针对时序阵发性对信息传播影响做了研究,结果表明对不同的数据集、不同的节点感染方式,阵发性对信息传播呈现的作用是不同的。针对此现象,通过构建DCW空模型消除原数据的阵发性特征,分析信息在原数据和空模型数据上的传播情况,以找到阵发性对传播呈现不同影响的原因。     

基于多尺度标签传播的小样本图像分类

在小样本条件下,由于低数据问题,即标记数据较少且难以收集,采用传统的深度学习很难训练出一个好的分类器.最近的研究中,基于低维局部信息度量方法和标签传播网络(transductive propagation network, TPN)算法取得了较好的分类效果,并且局部信息可以很好地度量特征与特征之间的关系,但是低数据问题依然存在.为了解决低数据问题,提出基于多尺度的标签传播网络(multi-scale label propagation network, MSLPN)方法,其核心思想在于利用多尺度生成器生成多个尺度的图像特征,通过关系度量模块获得多个不同尺度特征下的样本相似性得分,并通过集成不同尺度的相似性得分获得分类结果,具体地,方法首先通过多尺度生成器生成不同尺度的图像特征,然后利用多尺度信息的相似性得分进行标签传播,最后通过多尺度标签传播结果计算获得分类结果.与TPN相比,在数据集miniImageNet上,5-way 1-shot和5-way 5-shot设置中的分类准确率分别提高了2.77%和4.02%;在数据集tieredImageNet上,5-way 1-shot和5-wa...