基于邻接图的离群数据聚类算法

离群数据是数据中的小模式,因其固有的少数据与稀疏性等特征,使得基于距离或基于统计等常规聚类方式不适用于对离群数据的分类。该文根据离群对象关键域子空间的重合度,定义了离群共享属性集与离群相似度等概念,提出-离群簇分析技术。通过构建离群邻接图并将其稀疏化,将-离群簇搜索与相应的离群邻接图的最大完全子图搜索一一对应,给出一种基于邻接图的离群数据聚类算法。算例及实验结果表明,该方法具有较高的效率及良好的直观性。     

基于节点分值的攻击图量化评估算法

提出一种基于节点分值的攻击图量化评估算法NSBRank,用于对攻击图中所有节点的重要性进行量化计算。通过求解节点初始等级值,得到各节点的最终等级值,使各节点间的相对重要性更明确,从而提高网络安全事件的处理能力。实验结果证明,NSBRank计算得出的攻击图节点等级值更加客观准确。     

一个求无向图所有极大独立集的算法

图的极大独立集在计算机视觉、计算机网络、编码理论和资源配置等领域有着广泛的应用.本文利用图的分解方法给出了一个求简单无向图所有极大独立集的递归公式.定义了图的邻接矩阵的两个变换和点集合的一些运算.在此基础上,利用二分树给出了一个求无向图的所有极大独立集的有效算法.算法的时间复杂度是O(mn),其中m,n分别是图的所有极大独立集数和顶点个数.算法只需对网络的邻接矩阵进行处理,在计算机上实现起来非常方便.最后,通过实例验证了算法的有效性.     

基于不完备标签数据的半监督聚类算法

针对seeded-K-means和constrained-K-means算法要求标签数据类别完备的限制,本文提出了基于不完备标签数据的半监督K-means聚类算法,重点讨论了未标签类别初始聚类中心的选取问题.首先给出了未标签类别聚类中心最优候选集的定义,然后提出了一种新的朱标签类别初始聚类中心选取方法,即采用K-mea...     

近亲结点图编辑的Self-Training算法

Self-Training算法的性能很大程度上取决于高置信度样本的识别准确度。受DPC算法启发,利用密度峰值定义样本间的原型关系,并构造出近亲结点图这一新型数据结构。在此基础上,提出了一种近亲结点图编辑的Self-Training算法（self-training algorithm with editing direct relative node graph-DRNG）。DRNG采用假设检验的方法选择高置信度样本,将其加入有标签样本集进行迭代训练。因误分的高密度样本点对Self-Training算法的分类性能影响较大,所以,DRNG综合考虑距离和密度两个方面定义了近亲结点图中割边的非对称权重,增大了高密度点的割边权重,使其落在拒绝域外的概率增加,减小了因其误分类而产生的风险。为了验证DRNG的性能,在8个基准数据集上与类似算法进行对比实验,实验结果验证了DRNG的有效性。     

基于图收缩的半监督聚类算法

为了在只有少量已知标记的数据集中获得较好的聚类效果,提出了一种基于图收缩的半监督聚类算法。首先将整个样本空间中的数据表达为一个带权图,再根据给出的must-link约束,对图进行边收缩的修改,进而增强must-link约束。在此基础上引入图拉普拉斯算子,结合cannot-link约束将样本空间投影到一个特征子空间。最后在子空间上进行聚类分析。实验结果表明,该方法不仅提高了对复杂数据的聚类结果,而且在约束对数量较少时也能获得较好的结果。     

基于画图算法的WSN节点定位算法

针对无线传感器网络的节点定位问题,提出一种新的基于类Kamada Kawai画图算法的无线传感器网络节点定位算法,将无线传感器网络节点定位问题转化成画图问题,用经典的画图算法求得问题的最优解,从而实现对节点的定位。仿真实验结果表明,该算法收敛速度快、定位精度高、能够获得较好的效果。     

基于图模型的医学图像聚类算法

医学图像聚类算法的研究是面向特殊领域图像挖掘的重要组成部分,由于存在很多技术和特定领域方面的问题,使得这个方向的研究非常具有挑战性.已有的聚类算法对数据对象的形状和密度有要求,应用到医学图像聚类方面不能取得很好的结果.针对以上问题,在领域知识指导下,首先对图像进行了纹理检测,提出了面向纹理的T-LBP方法;然后对预处理之后的图像进行了空间划分,并对每个空间内的纹理求取LBP值,建立按空间序列排序的LBP直方图;最后,将以LBP直方图作为特征,提出了基于图模型的医学图像聚类算法.实验结果表明,该算法在时间复杂度和聚类结果方面具有良好的效果.     

基于完全图的能量高效可靠分簇算法

在采用多跳通信方式的分簇无线传感器网络中,接近sink点的簇头负担较重,容易过早耗尽能量而失效,引起大量簇重组。针对该问题,基于完全图理论提出一种能量高效可靠分簇算法以均衡簇间负载,设计动态簇头轮换机制来实现快速簇头选举和故障处理。仿真结果表明,该算法能延长网络生命周期、节约网络能耗、提高网络可靠性。     

基于图卷积的异质网络节点分类方法

图神经网络能够有效学习网络语义信息,在节点分类任务上取得了良好的效果.但仍面临挑战：如何充分利用异质网络丰富语义信息和全面结构信息使节点分类更精准.针对上述问题,提出了一种基于图卷积的异质网络节点分类框架(heterogeneous network node classification framework, HNNCF),包括异质网络约简和图卷积节点分类,解决异质网络节点分类问题.通过设计转换规则约简异质网络,将异质网络化简为语义化同质网络,利用节点间的关系表示保留异质网络多语义信息,降低网络结构建模复杂度;基于消息传递框架设计图卷积节点分类方法,在语义化同质网络上学习无1-sum约束的邻居权重等网络结构信息,深入挖掘关系语义特征,发现不同连接关系和邻居语义提取的差异性,生成节点的异质语义表示用于节点分类,识别节点类别标签.在3个公开的节点分类数据集上进行了实验,结果表明HNNCF能够充分利用异质网络多种语义信息,有效学习邻居节点权重等网络结构信息,提升节点分类效果.     

基于多节点社团意识系统的属性图聚类算法

属性图用属性向量描述节点,用边描述节点间的关系。为了把节点划分为具有紧密联系的社团,一种有效的方法是对属性图进行聚类。聚类方法有不同的标准,如节点连接度和属性相似度。虽然社团一般是围绕紧密的连边和相似的属性值的节点形成,但是目前的方法都只关注了这两种数据形式中的一种。通过给每个节点赋予一个自治域,提出一个准确且可延展的多节点系统用于提取属性图中的重叠社团。首先,引入带有可调带宽因子的核函数用于测度每个节点的影响力,具有最高局部影响力的节点可以被看作领导节点。其次,提出一种新颖的局部扩展策略,使每一个领导节点能够吸收属性图中相关性最强的跟随者。接着,设计了多节点社团意识系统,该系统为节点之间的充分沟通提供了必要的条件,从而能够得出最优的重叠社团结构。社团中的节点不仅互相联系紧密,而且也有相似的属性。该算法的计算复杂度在特定带宽条件下近似于连边数目的线性函数。最后,基于标准属性图和真实属性图的实验验证了该系统的有效性和高效性。     

无尺度图k-中心点聚类算法在文本挖掘中的应用

本文基于词的同现频率的方法对文本的特征进行提取,涉及了文档的语义。同时,引入了无尺度网络的理论,用无尺度图聚类算法对文本进行聚类。最后,我们使用错误分类度(MI)的均值和离差方法显示实验的结果。     

一种基于图形数据库的快速电力网络拓扑分析方法

提出了一种基于图形数据库的通用拓扑分析方法,将多状态设备映射为多节点,每个节点的父对象都为此设备,将设备连接抽象为连接电缆节点和连接关系,每种设备的电气属性都抽象为节点和关系的属性,在将网络的拓扑信息入库后,组合利用图形数据库中的多种图形分析算法,并结合电力网络应用开发出相连节点连通性分析和停电范围检测算法,基于此开发的电网停电范围监测系统和变电站智能开票操作票程序该方法具备高可用性和高性能,取得了良好的效果．     

基于DNA计算的层次图聚类算法

为解决使用DNA计算图聚类问题,提出一种基于DNA计算的层次图聚类算法。在分裂层次聚类中,使用DNA分子对图中顶点、边进行编码,在试管中并行产生最小生成树,根据给定阈值,通过切割树枝得到聚类结果。在凝聚聚类中使用DNA计算产生哈密尔顿路径,通过寻找最短哈密尔顿路径得到聚类结果。实验结果验证了该算法的可行性。     

基于持久性内存的属性图存储系统

属性图是一种流行的图数据模型, 在各种图系统中得到了广泛应用. 然而, 面向事务型负载的图数据库系统在执行图分析任务的场景下面临着高延迟等挑战. 传统的图分析系统往往是基于简单图模型, 而且大多不支持图的事务型负载. 因此, 迫切需要一个能够在属性图上高效处理事务型负载和图分析任务的图存储系统. 持久性内存的问世, 使得我们有机会重新设计图存储系统, 以充分发挥这种设备的特点. 为此, 本文提出了一种基于持久性内存的属性图存储系统, 名为TAG. TAG采用了一种新颖的混合架构的图存储方式, 以充分发挥持久性内存和主存的优势. 其次, 通过拓扑和索引结合的方式, 将图的拓扑嵌入到系统的索引中以加速图的拓扑查询. 最后, TAG通过基于标签的方式来组织图的属性数据, 进一步优化图的属性访问. 实验结果表明, TAG显著优于其他图数据库系统, 与图分析系统相比, TAG也有着相近的性能表现.     

基于CREW遍历图的一种并行算法

针对串行算法模型下基于顶点遍历图的情况,提出了一种在CREWPRAM并行模型下遍历无向图的算法。该算法是找出无向图的一棵最短路径生成树,由向上和向下两条有向边替换最短路径生成树的每条边形成欧拉回路,运用欧拉回路技术计算前缀和,前缀和所对应的顶点即为遍历无向图的顺序。得出了该算法时间复杂度为O（n＋logn）的结论。     

Node Embedding Research Over Temporal Graph

Compared with conventional graph data analysis methods, the graph embedding algorithm provides a new graph data analysis strategy. It aims to encode graph nodes into vectors to mine or analyze graph data more effectively using neural network related technologies. Some classic tasks have been improved significantly by graph embedding methods, such as node classification, link prediction, and traffic flow prediction. Although substantial breakthroughs have been made by former researchers in graph embedding, the nodes embedding problem over temporal graph has been seldom studied. In this study, we propose an adaptive temporal graph embedding (ATGED), attempting to encode temporal graph nodes into vectors by combining previous research and the information propagation characteristics. First, an adaptive cluster method is proposed by solving the situation that nodes active frequency varies types of graph. Then, a new node walk strategy is designed in order to store the time sequence between nodes, and also the walking list will be stored in a bidirectional multi-tree in the walking process to get complete walking lists fast. Last, based on the basic walking characteristics and graph topology, an important node sampling strategy is proposed to train the satisfied neural network as soon as possible. Sufficient experiments demonstrate that the proposed method surpasses existing embedding methods in terms of node clustering, reachability prediction, and node classification in temporal graphs.     

时序图节点嵌入策略的研究

相较于传统的图数据分析方法,图嵌入算法是一种面向图节点的新型图数据分析策略.其旨在通过将图节点向量化表达,进而在节点向量基础上,利用神经网络相关技术,更有效地进行图数据分析或挖掘工作,如在节点分类、链接预测及交通流预测等经典问题上效果显著.虽然研究者们在图嵌入方面已取得了诸多成果,但是面向时序图的节点嵌入问题却未被充分...     

一种基于符号关系图的快速符号数据聚类算法

由于在实际应用中有大量的符号数据生成,符号数据聚类成为了聚类分析的一个重要研究领域.目前,已有许多符号数据聚类算法被提出,但将它们应用于大数据环境时,仍然存在计算成本高、运行速度慢等问题.文中提出了一种基于符号关系图的快速符号数据聚类算法.该算法使用符号关系图替代原始数据,缩小数据集的规模,有效地解决了这一问题.大量的...     

基于图论的WSN节点定位路径规划

移动锚节点规划路径存在节点重复访问的问题,会影响定位精度的提高。为此,提出一种移动锚节点路径规划算法,引用图论知识,将传感器节点转化为图的顶点,并结合蚁群算法,利用图的遍历解决路径规划问题,寻找出一条路径。实验结果表明,该算法能够定位传感器节点,避免节点的重复访问,降低节点定位的误差。