基于图分析的OFDM频谱感知

随着OFDM信号被广泛应用到现代无线通信系统中,认知无线电中OFDM信号的检测具有重要意义。引入基于图的离散信号处理理论,提出了一种基于图分析的OFDM信号频谱感知方法,详细分析了其检测原理及判决门限的设定,并最后通过蒙特卡洛仿真实验,验证了这种方法的可行性并分析了检测性能,仿真结果表明,在较低信噪比下,这种方法仍具有良好的检测性能。     

适用于小样本的双邻接图判别分析算法

作为一种常用的降维方法,适用于小样本的监督化拉普拉斯判别分析方法通过使用图嵌入的判别近邻分析得到了很好的降维效果。但该方法在构建近邻图时,在K近邻中寻找同类和异类样本点存在数据不平衡问题;此外,在优化该方法的目标函数时,没有全面考虑到类间信息,从而会在一定程度上降低该方法的性能。针对以上两个问题,本文提出了适用于小样本的双邻接图判别分析方法。首先该方法分别在同类和异类样本中找出K个近邻点,然后使用这K个类内近邻点和K个类间近邻点来构造双邻接图,这样可以确保邻接图中既有同类样本点也有异类样本点,且数目相同。然后该方法在目标函数的推导结果中加入了类间拉普拉斯散度矩阵,从而使优化得到的投影矩阵融入更多的类间信息。在Yale和ORL人脸数据集上进行实验,并与同类方法相比,结果表明本文提出的适用于小样本的双邻接图判别分析方法能够得到更好的降维效果。     

用遗传算法实现四色图问题

遗传算法是模拟生物进化过程的算法,任何问题只要能用一组合适的编码来表示其中的一个可行解,那么这个可行解就可以看做是一个生物个体,若干个可行解就可以看做是一个生物种群。将问题的若干个可行解利用生物进化的特点,最终就可以简单快速地得到问题的一个最优解。利用遗传算法和四色图问题的这一特点,通过遗传算法实现了四色图问题的求解。实验证明,用遗传算法实现类似的四色图问题,思想简单,收敛速度快。     

图数据压缩技术综述

应用合适的压缩技术对包含上亿个节点和边的图数据进行紧凑准确的表示和存储是对大规模图数据进行分析和操作的前提。紧凑的图数据表示不仅可以降低图数据的存储空间,而且还可以支持在图数据上的高效操作。从图数据的存储角度出发对图数据管理中关于图数据压缩技术的研究进展进行综述,将重点介绍以下3种压缩技术:基于邻接矩阵的图数据压缩技术、基于邻接表的图数据压缩技术和基于形式化方法的图数据压缩技术,以及相关的代表性算法、适用范围和优缺点。最后对图数据压缩技术的现状和面临的问题进行了总结,并给出了未来图数据压缩技术的发展趋势。     

基于邻接矩阵的网络拓扑辨识算法

电力网络拓扑辨识是电网管理系统高级应用软件的重要组成部分,是电力系统各种分析计算的基础。针对矩阵法计算量大、计算速度慢的缺点,提出了一种加快网络拓扑辨识的新方法。该方法用节点—支路关联矩阵表示网络的基本拓扑结构,通过定义矩阵的"或"、"与"运算和开关状态矢量,利用对称消去法降低邻接矩阵的阶数,并把对称性应用于求连通矩阵的过程中,从而实现网络的动态拓扑。与传统算法相比,该方法减少了计算量,加快了计算的速度,适用于复杂的网络拓扑辨识。     

图的谱半径的一些下界

利用矩阵的相似变换,研究了简单连通图的谱半径的可达下界,得到一个新的下界ρ（G）≥δ1＋t-s＋√（s＋t-δ1）2＋4s（δ2-t）/2,等号成立当且仅当G=~G1 G2,其中G1为n-i阶（δ1-s）-正则图,G2为i阶t-正则图。     

一种基于邻接表的改进FP—growth算法

提出了改进的FP—tree树及FP—growth算法,不需要递归的生成条件模式基和条件模式树,改进的FP—tree结构类似于邻接表,保留了FP—tree中的项头表,舍弃了繁琐的树结构,采用单向链表结构来压缩结点信息,链表中各结点按照支持度降序排列。在挖掘频繁项目集部分相对FP—growth算法在运行时间上有显著提高,且算法的运行速度也明显优于FP—growth算法。     

局部平衡的判别近邻嵌入算法

判别近邻嵌入算法（discriminant neighborhood embedding,DNE）通过构造邻接图,使得在投影子空间中能够保持原始数据的局部结构,能有效地发现最佳判别方向。但是它有两方面的不足：一方面不能标识样本点的近邻样本点位置信息,从而不能更好地保持邻域结构;另一方面当数据不均衡时,不能实现子空间中类内聚合或者类间分离的目的,这不利于分类。为此提出了一种新的有监督子空间学习算法--局部平衡的判别近邻嵌入算法（locality-balanced DNE,LBDNE）。在构建邻接图时,局部平衡的判别近邻嵌入算法分别建立同类邻接图和异类邻接图,并通过引入一个控制参数,有效地平衡了类内与类间的关系。该算法与其他经典算法相比,在人脸识别问题上具有较高的识别率,充分说明了局部平衡的判别近邻嵌入算法能够有效地处理识别问题。     

基于邻接表的非结构网格快速生成算法

目的 优化Delaunay方法,提高网格生成效率并通过拉普拉斯光顺化提高网格质量.方法 用图这种数据结构来表示三角形网格并用邻接表存储以优化存储方式.结果 该数据结构同传统结构数组算法相比时间大大缩短、提高了网格生成效率.从网格生成的算例看出,该算法不仅提高了网格生成的速度,而且生成的网格质量较好,便于局部加密.结论 通过用图表示三角形网格并用邻接表优化储存,提高了网格生成效率.将生成的网格进行拉普拉斯光顺化,可使网格质量得到进一步的提高.     

Using eigenvectors of perturbed and collapsed adjacency matrices to explore bowtie structures in directed networks

The bowtie structure can illustrate not only the accessibility of the World Wide Web, but also the reachability of other directed networks. In this paper, we use the principal eigenvectors of the adjacency matrix with the unique largest eigenvalue to identify the strongly connected component of a directed network and fit the network into the bowtie structure. To ensure that the largest eigenvalue is unique, we add a little perturbation to the matrix before the eigen analysis. After the revelation of the bowtie structure centered on the strongly connected component with the largest unique eigenvalue, a directed network may have other bowtie structures centered on strongly connected components with smaller eigenvalues. To reveal other bowtie structures, we collapse the perturbed matrix by aggregating nodes of the strongly connected component with the largest eigenvalue into a supernode. Hence, the principal eigenvectors of the perturbed and collapsed matrix can be used to reveal the bowtie structure centered on the strongly connected component with the second largest eigenvalue. Furthermore, repeating the process of collapsing a strongly connected component and finding principal eigenvectors of the perturbed and collapsed matrix, we can reveal all the bowtie structures of a directed network.