基于不确定使用边的间接依赖过滤方法

起源过滤是通过改造起源图中的节点、边或间接依赖关系,隐藏起源图中的敏感信息,实现起源安全发布的新兴技术.针对现有起源过滤研究主要关注节点和边的过滤,较少研究间接依赖的过滤问题.扩展现有"删除+修复"的间接依赖过滤策略,提出了一种起源间接依赖过滤方法.形式地定义不确定的使用边,并阐明引入不确定的使用边修复被误断的间接依赖...     

时态函数依赖多值依赖混合集的成员籍问题研究

对于TFD和TMVD混合集约束的时态模式来说，由于多时间粒度的使用使成员籍问题的解决变得更加复杂．由于成员籍问题的解决对设计有效的模式分解算法必不可少，由此定义了时态类型集的强封闭集、属性集的有限闭包、属性集在给定时态类型上的有限依赖基、属性集的有限依赖基及特殊有限依赖基等概念，给出了求属性集的有限闭包、有限依赖基和特殊有限依赖基、时态混合集成员籍问题的算法，并对算法的可终止性、正确性进行了证明，对时间复杂性进行了分析，     

强偏序时态模式中混合依赖集的成员籍问题

有效的模式分解算法设计中应着重考虑和解决成员籍问题,时态类型间偏序关系在强偏序时态模式中的存在给解决成员籍问题带来了困难。为了有效解决强偏序时态模式中混合依赖集的成员籍问题,提出了给定时态类型上的偏序混合依赖基、强偏序模式混合依赖基、偏序时态函数依赖和偏序时态多值依赖的混合集闭包、强偏序模式混合闭包等概念,给出了求混合依赖集中属性的依赖基、属性集的闭包的算法,并在此基础上给出了强偏序模式混合依赖集成员籍问题的算法,证明了其正确性及可终止性,对该算法的时间复杂度进行了分析。应用实例表明相关理论和算法能解决强偏序混合依赖集中成员籍问题的判定问题,为解决强偏序时态模式规范化问题以及时态数据库设计提供了理论基础。     

强全序时态模式中混合依赖集成员籍问题的研究

对于TFD和RTMVD混合依赖集约束的强全序时态模式来说,成员籍问题的解决对设计有效的模式分解算法必不可少.由于强全序时态模式中多时间粒度的使用,使其成员籍问题的解决变得更加复杂.为此定义了强全序时态模式下的属性集在给定时态类型上的混合闭包、属性集的混合闭包、属性集在给定时态类型上的混合依赖基、属性集的混合依赖基等概念,给出了求强全序时态模式下属性集的混合闭包、属性集的混合依赖基以及TFD和RTMVD混合依赖集成员籍问题的算法,并对算法的可终止性、正确性进行了证明,对时间复杂性进行了分析.     

一种基于权值的大规模分布式系统结构脆弱性分析算法

结构脆弱性是大规模分布式系统的典型脆弱性类型之一.针对大规模分布式系统实体间复杂的依赖关系和冗余备份机制,构建了实体拓扑模型.该模型采用简单有向图描述实体间依赖关系,采用故障容忍机制刻画节点间的冗余关系,并引入权值刻画节点或边失效对于业务流程的影响.在此基础上,提出了基于权值的大规模分布式系统结构脆弱性分析算法,该算法通过权值计算和基于故障传递的剪枝方法发现并验证结构脆弱性.通过算法分析和实现充分验证了算法的有效性.     

构造基于构件依赖关系矩阵的元数据模型

构件集成到应用环境中实施集成测试时,会与其它构件产生相应的依赖关系.本文在对这些依赖关系进行概述的基础上,给出了构件直接依赖图、构件间接依赖图和构件依赖图的定义,并依据这些定义,提出了构件依赖矩阵(CmDM)的概念,用以描述构件Cm与构件系统中其它构件之间的依赖关系,接着进一步定义了复杂依赖关系矩阵(CmDDM),用以对依赖关系矩阵(CmDM)进行更为详细的描述.对依赖矩阵方法在回归测试、构件变更处理和软件重用的应用方法进行了形式化的描述,进一步将基于依赖关系矩阵的方法应用于学校内部开发的构件RegisterStuGrade 中,并另外选取了三个与之有关的构件,对其依赖关系进行分析,建立相应的构件依赖关系矩阵和复杂依赖关系矩阵,并与Orso方法、Spec方法(基于规范说明的方法)所生成的测试用例对于构件RegisterStuGrade源代码的覆盖情况进行了对比,从而证明了本方法的有效性.     

基于容差关系的扩展粗集模型中的知识依赖

论文在基于容差关系的扩展粗集模型中,考虑了条件属性子集与决策属性子集间知识依赖和条件属性子集间的知识依赖两种情况,分别给出了这两种情况下知识依赖和部分知识依赖以及依赖度等概念的定义,证明了与这些概念的定义相关的一些重要定理结论,并给出了一些例子加以验证。     

基于时态数据库的极小子结构逻辑系统

逻辑是知识表达的重要方法,但由于时序性知识与时间属性知识交叉应用的复杂性,其对时态数据库支撑一直不尽如人意.目前时态数据运算体系不完备,时态关系演算缺乏系统和有力的逻辑与代数理论支持.为此,文中从子结构逻辑出发,针对时态数据库及其信息处理中关键的知识推理、时态操作与函数依赖等内容,构建了一个极小的(最小的)子结构逻辑系统TDLrmin,其恰好等价于传统的数据库函数依赖Armstrong规则.TDLmin系统能在逻辑语义模型中对时序性、时间属性进行表达,而在句法逻辑系统将时间剥离,从而既表达了时态知识,对时态操作进行处理,又降低了逻辑系统的复杂度,使得逻辑系统的时间复杂度为P-time (O(n2)).而该逻辑系统还可与传统的Allen方法进行对接,使得相关时态查询所需的时间代价为传统非时态查询的时间加上一个复杂度仅为O(n)的线性时间,从而使得系统具有更强的普适性和应用前景.     

一个多时间粒度下时态函数依赖的有限属性闭包算法

为了有效地进行时态数据库设计,支持多时间粒度的时态函数依赖(TFDs)被用于时态模式的规范化．时态模式规范化所要解决的一个关键问题是求解时态函数依赖的有限属性闭包问题．由于多时间粒度的使用,使得有限属性闭包问题变得非常复杂．实际上,TFDs与传统的函数依赖(FDs)之间存在着密切的联系．通过分析这些联系和封闭时态类型集的特性,利用传统FDs的相关算法提出一个有效的求解有限属性闭包的算法．通过分析和与相关算法的实验比较,该算法更加有效．     

具有多时间粒度的强全序时态模式中多值依赖问题研究

在时态数据库中存在着与时态多值依赖相关的存储冗余、更新异常等问题.但由于时态多值依赖的复杂性,使得根据时态多值依赖所进行的范式分解并不能总保持无损联接,为此对强全序时态模式中时态多值依赖与无损分解的相关性进行了深入研究,给出了规则的时态多值依赖(RTMVD)和属性集的时间粒度等概念,并给出了RTMVD的一套有效的推理规则,针对强全序时态模式中时态多值依赖与无损分解的相关性给出了相关定理,解决了规则的时态多值依赖环境下时态模式在多粒度上的无损分解问题,为规则时态多值依赖环境下时态模式的进一步规范化奠定了基础.     

Minimal communication cost software construction in the Internet environment

This paper investigates the issue of building software in the Internet environment, where local area network (LAN) based systems are interconnected by links with different bandwidth and do not share file systems. The software is modeled as a directed acyclic graph. Each node in the graph represents a logical step in processing the software while the edges describe the order of execution. The problem is to construct the software at a particular LAN with minimum Internet communication cost. An optimal polynomial algorithm, SOFTCON, with time complexity is presented, where and are the number of nodes and edges in the graph describing the software respectively, is the number of LANs in the Internet environment, and is the time complexity of the network flow algorithm on the flow network with nodes and edges transformed from the directed acyclic graph of the software. Received: 6 December 1995 / 1 May 1996     

Minimal functional routes in directed graphs with dependent edges

Graphs are mathematical structures used to model a set of objects and the relations between them. One of the basic concepts of graph theory, the path, has wide real‐world applications. In classic graph models, edges ending at a node are assumed to be independent. However, many real graphs/networks can only be correctly described by considering a dependency among nodes or edges. Paths in such graphs may not be functional if the conditional dependency is ignored. In this study, we investigate the routing problem in directed graphs with dependent edges represented by general graph models as alternatives to hypergraphs. We define a minimal functional route (MFR) as a minimal set of nodes and edges that can independently perform information transfer between two given nodes, and formulate the determination of MFRs as a graph search problem. A depth‐first‐search (DFS) top‐down algorithm, an iterative integer linear programming (ILP) bottom‐up algorithm, and a subgraph‐growing bottom‐up algorithm are devised subsequently to solve this problem. Numerical experiments verify the effectiveness of the algorithms. The defined MFR problem and the proposed algorithms are expected to find many practical applications.     

基于时序模体注意力图卷积的动态网络链路预测算法

时序网络中的动态链路预测旨在基于历史连边信息预测未来会产生的连边,是网络分析的重要组成部分,具有极大的理论研究价值和广阔的应用场景.针对现有的动态链路预测算法大多基于一阶连边关系预测未来连边,忽略了对高阶的拓扑信息和时序通联信息的挖掘和利用问题,提出一种基于时序模体注意力图卷积的动态链路预测算法.首先,提出一种时序模体邻接矩阵构建算法,利用时序模体抽取节点间的高阶拓扑和时序关系信息;然后利用隐式调节过程对网络演化过程进行建模,并使用时序模体邻接矩阵作为传输矩阵的图卷积神经网络学习节点的低维向量表示并进行迭代更新;最后以节点间表示向量作为输入,通过计算连边发生的条件密度函数值作为依据完成动态链路预测.在多个真实时序网络数据集上的实验结果表明,所提算法可有效挖掘节点间的高阶拓扑和时序信息,提高动态链路预测效果.     

大规模软件网络节点中生代指数解法研究

将大规模软件结构看作一个有向网络图,类看作是网络中的一个节点,类间关系看作是一条连接节点的边。定义了网络节点的家族指数和中生代指数。一个节点的中生代指数反映了此节点和软件网络中其它节点联系的紧密程度。根据定义提出了中生代指数的一般求解算法APSA。基于dijkstra算法提出了快速求解算法ADDA。用两种算法对不同节点数的十种大规模软件进行中生代指数计算,结果表明节点越大,ADDA算法的时间性能越好。最后阐述了中生代指数对于软件开发的指导意义。     

基于评论文本图表示学习的推荐算法

基于卷积或循环神经网络的推荐系统主要捕捉评论文本中相邻词之间的局部和连续依赖关系,对长期、全局、非连续的依赖关系的捕捉能力有限。针对该问题,提出一种基于评论文本图表示学习的推荐算法RGP。将每个用户或项目的评论文本表示成图,图的节点为评论文本的词,图的边为词与词的连接关系。针对图中的每个节点,使用基于连接关系的图注意力网络加权融合其邻点信息,利用基于交互关系的注意力机制对节点重新赋权,并加权融合图中所有节点的表征从而得到整个图的表征。在此基础上,将基于用户和项目ID的嵌入表征及其评论图表征耦合输入并采用因子分解机进行评分预测,以得到最终的推荐结果。实验结果表明,与NARRE、DAML等算法相比,RGP算法可有效提高推荐精度。     

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.     

基于图神经网络的方面级情感分析

目前基于循环神经网络和注意力机制的方面级情感分析模型缺乏解释相关句法约束和远程单词依赖关系.针对该问题提出结合句子依存树和单词序列信息建立句子关系图模型.首先将句子表示为图,单词作为图的节点,依存句法树的边和单词序列作为图的边;然后提出邻接矩阵标记方案对句子关系图进行标记;最后利用图神经网络实现节点和边的分类任务.该模型在SemEval2014任务中的restaurant和laptop两个数据集上进行实验,在两个数据集上F1值提升了5％左右.实验结果表明,将句子转换成图利用图神经网络对句子进行方面级情感分析是有益的.     

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

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

基于语义依存分析的图网络文本分类模型

针对目前已有的文本分类方法未考虑文本内部词之间的语义依存信息而需要大量训练数据的问题,提出基于语义依存分析的图网络文本分类模型TextSGN。首先对文本进行语义依存分析,对语义依存关系图中的节点（单个词）和边（依存关系）进行词嵌入和one-hot编码;在此基础上,为了对语义依存关系进行快速挖掘,提出一个SGN网络块,通过从结构层面定义信息传递的方式来对图中的节点和边进行更新,从而快速地挖掘语义依存信息,使得网络更快地收敛。在多组公开数据集上训练分类模型并进行分类测试,结果表明,TextSGN模型在短文本分类上的准确率达到95.2%,较次优分类法效果提升了3.6%。     

Apex graph grammars and attribute grammars

Summary Apex graph grammars are a particular type of directed node-label controlled (DNLC) graph grammars: the embedding edges are established between terminal nodes only. Apex graph grammars, slightly generalized, can generate the sets of dependency graphs of attribute grammars. The other way around, every apex graph language can be obtained from such a dependency graph language by a graph replacement (which is an operation analogous to a string homomorphism).