基于权限提升矩阵的攻击图生成方法

目前的攻击图生成算法的复杂度较高,难以应用于大规模网络环境的攻击图生成.本文对攻击图构建过程进行了研究,在攻击模式库和目标环境描述模型的基础上,提出了基于权限提升矩阵的攻击图生成方法,以矩阵描述攻击过程中攻击者的权限提升过程,能够以较低的算法复杂度生成攻击图.搭建实验网络,验证了本文算法的攻击图生成过程.      

信息可视化研究综述

信息可视化是可视化技术在非空间数据领域的应用,可以增强数据呈现效果,让用户以直观交互的方式实现对数据的观察和浏览,从而发现数据中隐藏的特征、关系和模式。可视化应用非常广泛,主要涉及领域:数据挖掘可视化、网络数据可视化、社交可视化、交通可视化、文本可视化、生物医药可视化等等。根据CARD可视化模型可以将信息可视化的过程分为以下几个阶段:数据预处理;绘制;显示和交互。根据SHNEIDERMAN的分类,信息可视化的数据分为以下几类:一维数据、二维数据、三维数据、多维数据、时态数据、层次数据和网络数据。其中针对后4种数据的可视化是当前研究的热点。多维数据可视化方法主要包括基于几何的方法、图标方法和动画方法等。基于几何的可视化方式中最经典的就是"平行坐标系"方法。平行坐标系(parallel coordinates)使用平行的竖直轴线来代表维度,通过在轴上刻划多维数据的数值并用折线相连某一数据项在所有轴上的坐标点展示多维数据。平行坐标系方法能够简洁、快速地展示多维数据,发展出很多改进技术。但是当数据集的规模变得非常大时,密集的折线会引起"视觉混淆"(visual clutter),处理方法包括维度重排、交互方法、聚类、过滤、动画等。其他基于几何的方法包括Radviz方法使用圆形坐标系展示可视化结果;散点图矩阵(scatter plot matrix)将多维数据中的各个维度两两组合绘制成一系列的按规律排列的散点图。基于图标的可视化方法用具备可视特征的几何形状如大小、长度、形状、颜色等刻划数据,代表性的方法包括星绘法和Chernoff面法等。动画方法用于可视化中可被用来提高交互性和理解程度,其缺点包括可能分散注意力、引起用户的误解、产生"图表垃圾"等。时间序列数据是指具有时间属性的数据集,针对时间序列数据的可视化方法如下:线形图、堆积图、动画、地平线图、时间线。层次数据具有等级或层级关系。层次数据的可视化方法主要包括节点链接图和树图2种方式。其中树图(treemap)由一系列的嵌套环、块来展示层次数据。为了能展示更多的节点内容,一些基于"焦点+上下文"技术的交互方法被开发出来。包括"鱼眼"技术、几何变形、语义缩放、远离焦点的节点聚类技术等。网络数据具有网状结构。自动布局算法是网络数据可视化的核心,目前主要有以下3类:一是力导向布局(force-directed layout);二是分层布局(hierarchical layout);三是网格布局(grid layout)。当数据节点的连接很多时,容易产生边交叉现象,导致视觉混淆。解决边交叉现象的集束边(edge bundle)技术可以分为以下几类:力导向的集束边技术、层次集束边技术、基于几何的边聚类技术、多层凝聚集束边技术和基于网格的方法等。其他研究热点包括图形的视觉因素研究、自适应可视化研究、可视化效果的评估等。视觉因素对于可视化效果的影响,如位置、长度、面积、形状、色彩等影响已经引起很多研究者的注意。色彩是视觉因素的重要组成部分,研究主要集中在颜色选择的原则和交互系统中。这些原则基于数据类型、类的数量、认知约束等。自适应可视化可以提高信息可视化的适应性。研究成果分为以下几类:自适应可视化展示、自适应资源模型、自适应用户模型。自适应可视化展示是指根据用户的特征自动为用户提供多种展示类型,自动选择可视化内容及布局的形式,自动调整可视化的元素等。自适应资源模型反映了对硬件和软件的利用以提高可视化性能。自适应用户模型通过显示用户模型的内容并让用户能够编辑,从而让用户能够控制模型的内容。当前关于信息可视化评价的研究较少,少量研究也没有提出直接和通用的可视化的评估方式,需要对信息可视化评价的理论基础、方法和应用做深入的研究。可视化技术与应用还应该继续向以下4个方面努力:直观化、关联化、艺术化、交互化。信息可视化技术的发展方向是协同(collaboration)、分析过程(analytics)、计算(computational)和意会(sense-making)。未来研究方向可以包括以下几个内容。信息可视化和数据挖掘的紧密结合。为提高处理海量数据时的速度和效率和解决视觉混淆现象;必须运用数据挖掘的公式和算法,对数据分析的过程及结果进行可视化展现。协同可视化。协同可视化领域的研究方向可以包括可视化接口设计、基于Web的可视化协同平台开发、协同可视化工作的视图设计、协同可视化中的工作流管理及协同可视化技术的应用等。更多领域的应用技术开发。包括统计可视化:需要研究使用几何、动画、图像等工具对数据统计的过程和结果进行加工和处理的技术;新闻可视化:对新闻内容进行抓取、清洗和提取和可视化展示;社交网络可视化:可视化方式显示社交网络的数据,对社交网络中节点、关系及时空数据的集成展示。搜索日志可视化:针对在使用搜索引擎时产生的海量搜索日志,可视化的展现用户的搜索行为、关系和模式等。     

基于正则约束的分层仿射图神经网络文本分类模型

文本分类是自然语言处理中一个重要的研究课题。近年来，图神经网络（graph neural network，GNN）在这一典型任务中取得了良好的效果。目前基于图结构的文本分类方法存在边噪声和节点噪声干扰、缺乏文本层次信息和位置信息等问题。为了解决这些问题，提出了一种基于正则约束的分层仿射图神经网络文本分类模型Text-HARC，该模型融合了图注意力网络（graph attention network，GAT）与门控图神经网络（gated graph neural network，GGNN），引入正则约束过滤节点与边噪声，分别使用仿射模块与相对位置编码补充词语表示。通过实验，该方法在TREC、SST1、SST2、R8四个基准数据集上的准确率提升明显，消融实验结果也验证了该方法的有效性。     

大规模软件网络类节点中介度分析

将大规模软件结构看做一个有向网络图,类看做是网络中的一个节点,类间关系看做是一条连接节点的边,并给出了水电仿真软件的软件网络图.给出了网络节点中介度定义和实例计算.提出了求解节点中介度的BTS算法,给出了10种软件的计算时间.以大型水电仿真系统为例,说明了节点中介度的大小可以反映该节点在网络中的重要程度,并能为软件开发提供指导意义.发现节点的中介度同出度和入度乘积之间具有递增相关性,并以最小二乘法拟合软件中此相关性而得出其直线斜率.     

基于观点传播的改进相似性计算评分预测方法

通过研究网络结构上的观点传播与协同过滤算法,基于对观点传播算法的优化,提出了基于用户相似和物品相似推荐系统评分预测算法.设计的算法修正了现有相似研究中在目标比较相似时,相似性结果为零的问题,将用户(或物品)的相似度定义为用户(或物品)间的观点数目和差异在相应复杂网络中的传播结果,并提出了相应的推荐算法.在MovieLens数据集上的实验结果证明,提出的算法与几种典型的现有方法相比较,具有更高的准确性,并且优于观点传播算法.     

多元数据的多点表示模型

提出了多元数据的多点表示模型.该模型采用多个平面矢量来表示多元数据的各个属性变量.每个平面矢量用一个复变函数来描述,整个数据集表达为一个复变函数矩阵.该模型可以统一描述多种常用的图表示方法,如平行坐标、雷达图、星座图等.该表示模型的参数可以利用机器学习算法进行优化,从而有效地揭示,数据结构并进行可视化模式识别.     

图类算法可重用设计及其实现

为了提高图算法生成效率和可靠性,该文提出一种将领域特征模型与构件组装技术相结合的可重用的图类算法开发方法.首先,通过对一族图算法的深入分析,揭示出图类算法领域的共性特征和可变特征,建立领域特征模型;然后,分析特征之间的交互过程,设计图类算法的可重用构件,并对构件依赖关系做出描述;最后,借助高可靠平台对算法构件进行开发,建立高可靠可重用构件库,进一步由构件组装出多种图算法,提高了图算法的开发效率和可靠性.实验表明开发出的图算法可重用构件库具有一定的实用性.     

基于用户相似度的随机游走社交网络事件推荐算法

针对基于社交网络的事件推荐覆盖性和准确性不够高的问题,提出了基于用户相似度Si-user Walker算法.该算法利用基于事件的社交网络特征,将线上用户群组数据抽象为图,以重启随机游走算法为基础,改变了传统的完全基于图的拓扑结构进行随机游走的策略.根据地理位置划分事件类型,提出了新的用户相似度计算方法,然后根据用户相似度矩阵作为随机游走的转移概率,既保留了图的传递性,又保证了图节点游走的真实性.与其他推荐算法在真实的数据集上实验表明,该算法在均方根误差、准确率及覆盖率上均得到提升.     

SA算法为什么能克服计算量的指数爆炸

在树（或图）的搜索中，多数启发式搜索算法只利用了节点的局部信息。统计启发式搜索算法，利用了子树的全局性信息，从而使搜索效率有显著的提高。本文着重讨论从局部信息提取全局信息的问题，并从另外的角度进一步讨论关于ＳＡ算法假设条件的可实现性。最后与Ａ＊算法进行了比较。     

图像边缘检测研究进展

 图像边缘是图像的最基本和最重要的特征之一,它包含了位置、轮廓等许多有用的信息,为人们描述或识别目标及解释图像提供了一个重要的特征参数。边缘检测是图像处理、图像分析和计算机视觉领域中最经典的研究内容之一,是进行模式识别和信息提取的基本手段。已有的图像边缘检测方法很多,但每种方法都尚有不足之处,在某些情况下仍不能检测到目标物体的最佳边缘,未形成一种普遍适用的边缘检测方法。因此边缘检测一直是图像处理与分析技术中的研究热点,其新理论、新方法不断涌现。对已有方法进行改进,或是按照具体要求设计新方法,是目前边缘检测领域研究的主导方向。本文阐述了边缘检测的研究意义,总结了图像边缘检测的基本思想和检测出的边缘的一般要求,回顾了边缘检测的各种方法,分析了这些方法的优点和存在的不足,总结了边缘检测的最新发展方向。最后分析了现有的边缘评价方法的特点,为边缘检测进一步的研究和应用提供参考。     

基于酒店特征信息和在线评价信息的酒店选择

为辅助游客通过旅游网站进行酒店选择,提出了一种基于旅游网站提供的备选酒店特征信息和在线评价信息的酒店选择方法.首先,基于酒店特征信息和在线评价信息构建备选酒店有向加权图,依据备选酒店特征信息,基于离差最大化法对酒店特征进行客观赋权,并采用简单加权法确定有向加权图结点权重,依据备选酒店间在线评价信息的比较关系确定有向加权图的有向边及有向边权重;然后,基于PageRank算法原理给出备选酒店排序值求解算法;最后,以基于缤客网站提供的酒店特征信息和在线评价信息进行酒店选择.结果说明了提出方法的有效性和可行性.     

图搜索问题算法推导及形式化证明

用非形式化方法解决图搜索问题规模受限,对于一些复杂问题难以保证其正确性.传统的形式化方法推导图搜索问题难以理解且不易于形式化证明,现有形式化方法对这类问题的解决方案较少,在保证可靠性和正确性方面有欠缺.该文通过对图搜索问题的深入研究,开发出一种针对解决图搜索算法的新方法.首先刻画问题的规约,利用循环不变式的递归定义技术给出了开发图搜索问题循环不变式的新策略,在此基础上得到Apla抽象算法程序,并对该算法程序进行了形式化证明,再将已验证的Apla算法程序自动生成C++可执行程序,实现了从抽象的形式规约推演出具体的面向计算机的程序代码的程序精化完整过程.以拓扑排序和广度优先遍历为例对所提方法进行实验,实验结果验证了所提方法的有效性,不仅可以推导和证明已知算法,而且对未知算法的推导也有指导性作用.     

基于图注意力网络的安卓恶意软件检测

安卓恶意软件的爆发式增长对恶意软件检测方法提出了更高效、准确的要求.早年的检测方法主要是基于权限、opcode序列等特征,然而这些方法并未充分挖掘程序的结构信息.基于API调用图的方法是目前主流方法之一,它重在捕获结构信息,可准确地预测应用程序可能的行为.本文提出一种基于图注意力网络的安卓恶意软件检测方法,该方法通过静态分析构建API调用图来初步表征APK,然后引入SDNE图嵌入算法从API调用图中学习结构特征和内容特征,再通过注意力网络充分融合邻居节点特征向量,进而构成图嵌入进行检测任务.在AMD数据集上的实验结果表明,本文提出的方法可以有效检测恶意软件,准确率为97.87%,F1分数为97.40%.     

基于子图特征的科学家合作网络链路预测

提出了多种基于子图结构特征的新特征,构建了基于节点重要性、基于节点共同邻居、基于边共同邻居、基于邻居子图和基于边子图五类特征,并将这五类特征中的多种特征分别作为特征输入,运用机器学习的方法,实现科学家合作网未来合作关系的预测。研究中发现,基于边子图特征的链路预测准确率最好。此外,研究中运用基于模型的特征排序和最大信息系数特征选择方法分析类内特征的影响力以及相互关系,通过机器学习算法的分类模型进行链路预测。该方法能够有效地揭示网络类内特征在预测中的重要性和相关性,有利于发现影响力大的特征和冗余特征。     

Design Pattern Mining Using Graph Matching

The identification of design pattern instances is important for program understanding and software maintenance. Aiming at the mining of design patterns in existing systems, this paper proposes a subgraph isomorphism approach to discover several design patterns in a legacy system at a time. The attributed relational graph is used to describe design patterns and legacy systems. The sub-graph isomorphism approach consists of decomposition and composition process. During the decomposition process, graphs corresponding to the design patterns are decom-posed into subgraphs, some of which are graphs corresponding to the elemental design patterns. The composition process tries to get sub-graph isomorphism of the matched graph if sub-graph isomorphism of each subgraph is obtained. Due to the common structures between design patterns, the proposed approach can reduce the matching times of entities and relations. Compared with the existing methods, the proposed algorithm is not linearly dependent on the number of design pattern graphs.     

用遗传算法模拟复杂最优网络的自然涌现过程

为了模拟复杂最优网络从树演化到完备图的整个过程，解决现有邻接节点编码方法只适用于低密度网络，而传统的交叉变异方法又有大量不可行解的问题，提出了基于三角阵的变长基因编码方法和段间交叉、段内变异平衡的交叉变异方法．该编码方法只记录对称邻接矩阵中三角阵的信息，反映了无向网络的所有可能变化，因而编码串长度适中，网络边数不需限制，可以模拟网络从树到完备图的整个演化过程．段间交叉只交换节点一级近邻的连接方式，段内变异平衡对边进行重绕，这既符合遗传算法的要求，又保证了网络的连通性．模拟结果表明，与邻接节点编码和传统交叉变异方法相比，所提方法适用范围更广，收敛速度较快．     

Improved Approximate Minimum Degree Ordering Method and Its Application for Electrical Power Network Analysis and Computation

Electrical power network analysis and computation play an important role in the planning and operation of the power grid, and they are modeled mathematically as differential equations and network algebraic equations.The direct method based on Gaussian elimination theory can obtain analytical results. Two factors affect computing efficiency: the number of nonzero element fillings and the length of elimination tree. This article constructs mapping correspondence between eliminated tree nodes and quotient graph nodes through graph and quotient graph theories.The Approximate Minimum Degree(AMD) of quotient graph nodes and the length of the elimination tree nodes are composed to build an Approximate Minimum Degree and Minimum Length(AMDML) model. The quotient graph node with the minimum degree, which is also the minimum length of elimination tree node, is selected as the next ordering vector. Compared with AMD ordering method and other common methods, the proposed method further reduces the length of elimination tree without increasing the number of nonzero fillings; the length was decreased by about 10% compared with the AMD method. A testbed for experiment was built. The efficiency of the proposed method was evaluated based on different sizes of coefficient matrices of power flow cases.     

基于点云数据的杂乱场景分割算法研究

目前处理桌面上单个对象已经被解决,然而处理复杂的场景时由于杂乱和遮挡而引起相当多的问题。虽然当前最先进的方法在基准性能上继续逐渐提高,但是它们也变得越来越复杂。针对杂乱场景中多个物体的分割问题,提出了一种基于RGB-D点云数据的分割方法。该方法先将场景点云超体聚类分解为基于体素网格的邻接图,然后对邻接图的边缘进行分类创建凸度图,再通过区域生长合并具有凸关系的分块从而得到未知物体。此外,提出用欧几里得算法对区域生长进行改进,发现对于碗和杯子这类具有内部凹面的物体有较好地分割效果。我们在对象分割数据库和手动提取场景中的实验结果,表明该方法可以在杂乱的桌面场景中分割各种形状的对象。     

基于Optimized-AG的节点攻击路径预测方法

针对传统攻击图中因对节点分析考虑不全面而导致的攻击路径预测不准确问题, 提出一种基于攻击图攻击行为分析的攻击路径预测方法. 先通过节点攻击距离权重对传统的攻击图进行优化, 决策出可能的攻击路径, 并计算其路径的节点攻击行为成本, 然后基于估计函数判断出优先考虑的攻击路径. 实验结果表明, 该方法有效消除了攻击图路径冗余, 能筛选出可靠的攻击路径, 提高了攻击图攻击路径预测的准确性.     

基于Optimized AG的节点攻击路径预测方法

针对传统攻击图中因对节点分析考虑不全面而导致的攻击路径预测不准确问题, 提出一种基于攻击图攻击行为分析的攻击路径预测方法. 先通过节点攻击距离权重对传统的攻击图进行优化, 决策出可能的攻击路径, 并计算其路径的节点攻击行为成本, 然后基于估计函数判断出优先考虑的攻击路径. 实验结果表明, 该方法有效消除了攻击图路径冗余, 能筛选出可靠的攻击路径, 提高了攻击图攻击路径预测的准确性.