基于局部有限搜索的无向图近似最大团快速求解算法

无向图最大团求解是一个著名的NP-完全问题,解决该问题的经典算法基本上都采用完全精确搜索策略。鉴于NP-完全问题本身所固有的复杂性,这些算法或许仅适用于某些特殊的小规模图,对于具有大规模顶点和边的复杂图还是显得无力,难以适用。针对完全精确搜索策略下的无向图最大团求解算法的大部分时间都用于对图进行额外而无效的查找的问题,采用分划递归技术将图划分为邻接子图和悬挂子图,然后对邻接子图进行递归求解,而对悬挂子图则通过设置搜索范围控制函数进行局部有限搜索。在DIMACS数据集上将所提算法与当前主要的最大团求解算法进行对比实验,结果表明,文中提出的局部有限搜索求解策略能在75%的基准数据上获得最大团,剩下不能得到最大团的数据实际上也可以获得接近于最大团的近似最大团,但算法的平均求解时间仅为目前最大团精确求解算法的20%左右。因此,在很多最大团非精确要求的场景中,所提算法具有极高的应用价值。     

基于蚁群算法求解最大团问题

最大团问题是一种典型的NP完全问题, 是图论中一个经典的组合优化问题.研究将蚁群算法应用于求解最大团问题,提出一种求解最大团问题蚁群算法.通过定义最大团问题蚁群算法中的各元素,并改进了蚂蚁搜索解的方法,有效地改善蚁群算法易于过早地收敛于局部最优解的缺陷.仿真实验表明,图中的顶点数较多时,也取得了较好的结果.     

最大团问题的改进蚁群算法求解

为了更好的解决最大团问题,提出一种改进的蚁群算法。通过提取图的顶点信息,将图用信息素模型来表示;根据最大团问题的约束条件利用蚁群构造极大团,并进行实时的全局信息素更新和局部信息素更新,直到找到最大团。实验结果表明,算法能较好的实现最大团问题,算法性能高于通用的蚁群算法。     

一种具有快速跟踪能力的改进RLS算法研究

为了改善固定遗忘因子递推最小二乘（RLS）算法在时变系统中的跟踪性能,提出一种改进的RLS算法。改进的可变遗忘因子RLS算法,不仅克服了固定遗忘因子RLS算法中跟踪速度和参数失调的矛盾,而且避免了当参数估值趋于参数真值时,卡尔曼增益趋于零,RLS算法失去对时变系统的跟踪能力的问题。最后,在MATLAB仿真平台下,对改进的RLS算法性能进行仿真验证。仿真结果表明,改进的算法能够获得快速的跟踪能力,也具有较快的收敛速度和较小的稳态误差。     

一种具有快速跟踪能力的改进RLS算法研究

为了改善固定遗忘因子BLS(Recursive least-square)算法在时变系统中的跟踪性能,提出了一种改进的BLS算法.改进的BLS算法结合了可变遗忘因子的BLS算法和自扰动BLS算法,既克服了固定遗忘因子RLS算法中跟踪速度和参数失调的矛盾,而且也避免了当参数估值趋向于参数真值时,卡尔曼增益趋于零,从而BLS算法失去对时变系统的跟踪能力的问题.最后,在MATLAB平台下,对改进后的RIS算法进行了仿真验证.仿真结果表明,算法具有较快的收敛速度和跟踪速度以及较小的稳态误差.     

稀疏编码的最近邻填充算法

针对K最近邻填充算法(K-nearest neighbor imputation,KNNI)的参数K值固定问题进行了研究,发现对缺失值填充时,参数K值固定很大程度上影响了填充效果.为此,提出了基于稀疏编码的最近邻填充算法来解决这一问题.该算法是用训练样本重构每一缺失样本,在重构过程中充分考虑了样本之间的相关性;并用e1范数来学习确保每个缺失样本用不同数目的训练样本填充,以此解决KNNI算法参数K值选取问题.基于数据性能分析指标RMSE和相关系数的实验比较结果表明,该算法比KNNI算法的效果要好.该算法能很好地避免了KNNI算法存在的缺陷,适用于数据预处理环节需要对缺失值进行填充的应用领域.     

基于改进的自适应局部保持投影算法的人脸识别

局部保持投影(LPP)通过构造近邻图来保持样本的局部结构,在构造近邻图的过程中,LPP会遇到两个参数K和σ的选择问题。近邻图的构建对算法的识别效果起着重要的作用,因而这两个参数的选择会在很大程度上影响LPP的识别率。为了避免参数的选择对识别率造成影响,提出了一种基于改进的自适应局部保持投影的人脸识别算法。首先,构造无参数的近邻图,其能够自适应地选取样本的近邻点并确定其相应的边权。其次,由于在计算过程中出现了矩阵维数过高的问题,因此采用QR分解进行降维处理。最后,利用共轭正交化使得投影轴具有统计不相关性,以降低特征矢量间的统计相关性,提高识别率。在ORL人脸库和YALE人脸库上进行了实验,结果表明改进的算法在识别率方面整体上好于LPP算法、DLPP算法、LMMC算法。     

基于多层图布局算法的不确定性网络可视化方法

由于越来越多的数据包含了不确定性,可视化不确定性网络最近几年成为了数据可视化领域中的一个热点。在现有的不确定性可视化研究中,基于概率图布局的方法取得了比较好的效果,通过一种固定采样图算法,可以很好地可视化不确定性网络,并反映出网络中的概率分布情况。针对基于概率图布局的方法存在运行时间过长、图布局不稳定等问题,提出了一种基于多层图布局的方法,改进了多层图布局算法并与固定采样图算法相结合,弥补基于概率图布局的不确定性网络可视化方法的缺陷。实验证明改进之后的算法与原来的方法相比具有更高的时间效率,而且生成的图结构更加稳定。     

一种高效的大规模网络k团挖掘算法

网络结构中的k团挖掘是各种基于网络的应用的基础问题之一。针对大规模网络k团挖掘效率低的问题,提出了一种高效的大规模网络k团挖掘算法。首先,将寻找最大密度的k团问题进一步转化为寻找超过给定密度值k团的问题。然后,以网络中的顶点和k－1团顶点为两类顶点构建二部图,并证明应用二部图可以在多项式时间内求解k团问题。在稀疏网络中,提出的算法的时间和空间复杂度分别为O(c²_k)和O(c_k)。实验表明,提出的算法与目前最优的算法相比能更准确地挖掘大规模网络中的k团,并且具有更高的运行效率。此外,提出的算法可应用于不完全网络中的k团挖掘。     

一类K1,3-free Hamiltonian图

1988年在美国Kalamazoo召开的＂第六届国际图论、组合及其应用会议＂上提出无爪图猜想：若3连通n≥3阶K1,3-free图G的不相邻的任两点x、y均有｜N（x）∪（N（y）｜≥（2n-6）/3,则G是哈密顿图.这里证明更深刻的结果：若3连通n≥3阶K1,3-free图G的满足1≤｜N（x）∩（N（y）｜≤α-1的不相邻的任两点x、y均有｜N（x）∪（N（y）｜≥（2n-6）/3,则G是哈密顿图.     

低度图的最大团求解算法

在图的最大团问题中,当图的顶点数不大于阈值m时,很容易求解其最大团问题,求解算法的时间复杂度为O(d)。给出一种求解低度图的最大团的确定性算法。该算法通过对图按顶点逐步分解实现分别计算,较好地解决低度图的最大团问题。算法时间复杂度为O(d•n3)。其中,n表示图的顶点数,图中顶点的最大度小于m或者图可以通过逐个删除度小于m的顶点而使所有顶点的度都小于m。     

New applications of clique separator decomposition for the Maximum Weight Stable Set problem

Graph decompositions such as decomposition by clique separators and modular decomposition are of crucial importance for designing efficient graph algorithms. Clique separators in graphs were used by Tarjan as a divide-and-conquer approach for solving various problems such as the Maximum Weight Stable Set (MWS) problem, Colouring and Minimum Fill-in. The basic tool is a decomposition tree of the graph whose leaves have no clique separator (so-called atoms), and the problem can be solved efficiently on the graph if it is efficiently solvable on its atoms. We give new examples where the clique separator decomposition works well for the MWS problem; our results improve and extend various recently published results. In particular, we describe the atom structure for some new classes of graphs whose atoms are P₅-free (the P₅ is the induced path with five vertices) and obtain new polynomial time results for the MWS problem. The complexity of this problem on the class of P₅-free graphs is still unknown.     

基于MapReduce的无线城市社团发现算法研究

对于无线城市数据中社团发现问题,针对已有的团搜索（CS）算法运行过程生成大量重复团、生成结果冗余、算法时间复杂度较高等问题,从优化边存储、预先进行边处理、搜索建团入手,用特殊的二叉树结构存储、权重[K]选择排序、深度优先遍历构建T-CS算法。针对海量数据溢出问题,结合MapReduce模型,提出了MP-T-CS算法。实验证明,MP-T-CS算法不仅可以解决运行过程大量重复团问题,时间代价大大降低,对海量数据的处理能力大大提升,生成团的代表性大大提高。     

无线城市数据中的社团发现方法

为了在缺失社交关系的无线城市接入日志中挖掘频繁共现的社团结构。提出了一种基于无向有权图的社团发现方法：团搜索（Clique Search）。该算法将日志数据映射到图空间,通过挖掘其中的团来对潜在的社团关系进行挖掘。相较于传统算法,该算法显著减小了运算时间复杂度与空间复杂度。实验结果表明,随着输入数据集规模的增长,该算法仍然能够在常数级别时间内完成计算。算法中的参数[δ]对结果社团中成员的联系紧密度影响比较明显,使用不同的[δ]值可以满足不同应用的需求。     

图卷积神经网络基础图结构影响研究

为进一步提高基于图卷积神经网络的半监督图节点分类的准确率,本文研究了基础图结构对图卷积神经网络的影响.通过对数据集(Cora、Citeseer及Pubmed)的图结构进行可视化,发现数据集(Cora、Citeseer)的图结构均为非连通图.通过研究非连通图中图拉普拉斯矩阵的"0"特征值和特征向量的特性,提出了通过对图拉普拉斯矩阵的"0"特征值对应的特征向量进行相关运算处理,获取非连通图最大连通分量的方法.该方法有效获取了数据集(Cora、Citeseer)图结构的最大连通分量,去除了非连通小分量.在该最大连通分量上利用3种先进的图卷积神经网络模型(GCN、GAT和GMNN)进行了实验验证,结果表明分类准确率提升了1%-4%,为其它包含小连通分量噪声的数据集更有效地利用图卷积神经网络模型训练提供了参考.     

基于KNN图的空间离群点挖掘算法

空间数据集中离群数据与正常数据之间的非空间属性值相差较大。针对该情况,提出一种基于K-最邻近(KNN)图的空间离群点挖掘算法。该算法通过所有对象的K近邻关系构造KNN图,将相邻对象非空间属性值的差作为2个对象点间的边权值,利用裁边策略去掉权值较高的边,从而识别出空间离群点和离群区域。实验结果表明,该算法的时间性能优于POD算法。     

求解最大团问题的并行多层图划分方法

在当今大数据环境下,针对图中节点的海量性和分析的复杂性对最大团问题的研究在速度和精度上都提出了更高要求的问题,提出求解最大团问题的并行多层图划分方法（PMGP_SMC）。首先,提出一种新的多层图划分（MGP）方法,在保持原有图的团结构不被破坏的情况下对大规模图例划分产生子图,并对规模较大的子图进行多层图划分,进一步缩小子图规模,并且应用GraphX图计算框架实现MGP,形成并行MGP（PMGP）方法;然后,依据划分后的子图规模,减少了惩罚值局部搜索算法（PBLS）的迭代次数,提出基于速度优化的PBLS（SPBLS）来求解划分后的各个子图的最大团;最后,将PMGP和SPBLS相结合形成PMGP_SMC。采用Stanford大规模数据集运行测试,实验结果表明,PMGP相比并行单层图划分方法（PSGP）,求得的最大子图规模能缩小至原来的1/100,平均子图规模能缩小至原来的1/2;PMGP_SMC相比求解最大团问题的PSGP（PSGP_SMC）,总体时间缩短至原来的1/100,并且PMGP_SMC求解最大团的精度和基于极大团枚举求解最大团问题的并行多层图划分方法（PMGP_MCE）一致。PMGP_SMC能够快速精准地求解大规模图例的最大团。     

一种简单的图的平面性判断算法的实现研究

Malgrange、Malgrange和Pertuiset三人合作提出O（n2）时间复杂度的平面性判断算法，尽管效率不是那么理想，却易于理解，并且算法结束时能够给出平面图的一种平面嵌入，另外算法仅涉及到割点的检测、图的计算机表示、图的分割、图的遍历等较为基础的问题。从而能够很好地适应教学及入门对直观性，可实现性的需要。尽管这个方法已经较为直观。但是由于图的平面嵌入在计算机中的表示较为困难等问题．其算法具体如何实现依然需要细心研究。     

网络攻击图逆向深度优先生成算法

大规模网络节点数量多,连接关系复杂,现有攻击图生成方法存在节点爆炸问题,针对大规模网络的这种特点,提出了一种逆向深度优先攻击图生成算法。首先对攻击图的相关概念进行了简要介绍,并分析了逆向生成算法流程。然后,鉴于生成攻击图过程中要对网络可达性进行测试,因此,同时提出了基于区间树的规则匹配算法,最后,对攻击图生成算法进行了实际环境测试,并对测试结果进行了验证分析。实验结果表明,该攻击图生成算法能以O（lgn）的时间复杂度高效检测网络可达性,优化网络攻击图生成结果。     

Dominating set is fixed parameter tractable in claw-free graphs

We show that the Dominating Set problem parameterized by solution size is fixed-parameter tractable (FPT) in graphs that do not contain the claw (K_1,3, the complete bipartite graph on four vertices where the two parts have one and three vertices, respectively) as an induced subgraph. We present an algorithm that uses 2^O(k2)n^O(1) time and polynomial space to decide whether a claw-free graph on n vertices has a dominating set of size at most k. Note that this parameterization of Dominating Set is W[2]-hard on the set of all graphs, and thus is unlikely to have an FPT algorithm for graphs in general.The most general class of graphs for which an FPT algorithm was previously known for this parameterization of Dominating Set is the class of K_i,j-free graphs, which exclude, for some fixed i,j∈N, the complete bipartite graph K_i,j as a subgraph. For i,j≥2, the class of claw-free graphs and any class of K_i,j-free graphs are not comparable with respect to set inclusion. We thus extend the range of graphs over which this parameterization of Dominating Set is known to be fixed-parameter tractable.We also show that, in some sense, it is the presence of the claw that makes this parameterization of the Dominating Set problem hard. More precisely, we show that for any t≥4, the Dominating Set problem parameterized by the solution size is W[2]-hard in graphs that exclude the t-claw K_1,t as an induced subgraph. Our arguments also imply that the related Connected Dominating Set and Dominating Clique problems are W[2]-hard in these graph classes.Finally, we show that for any t∈N, the Clique problem parameterized by solution size, which is W[1]-hard on general graphs, is FPT in t-claw-free graphs. Our results add to the small and growing collection of FPT results for graph classes defined by excluded subgraphs, rather than by excluded minors.