Supporting ontology adaptation and versioning based on a graph of relevance

Ontologies recently have become a topic of interest in computer science since they are seen as a semantic support to explicit and enrich data-models as well as to ensure interoperability of data. Moreover, supporting ontology adaptation becomes essential and extremely important, mainly when using ontologies in changing environments. An important issue when dealing with ontology adaptation is the management of several versions. Ontology versioning is a complex and multifaceted problem as it should take into account change management, versions storage and access, consistency issues, etc. The purpose of this paper is to propose an approach and tool for ontology adaptation and versioning. A series of techniques are proposed to ‘safely’ evolve a given ontology and produce a new consistent version. The ontology versions are ordered in a graph according to their relevance. The relevance is computed based on four criteria: conceptualisation, usage frequency, abstraction and completeness. The techniques to carry out the versioning process are implemented in the Consistology tool, which has been developed to assist users in expressing adaptation requirements and managing ontology versions.     

A cognitive pedestrian behavior model for exploratory navigation: Visibility graph based heuristics approach

Navigation is a complex issue in simulating pedestrian dynamics. Many existing studies have investigated how pedestrians navigate from an origin to a specific destination, i.e., traveling to familiar or novel destinations. However, pedestrians’ navigation through built environment without specific destinations still remains as an open issue. This exploratory navigation usually involves more spatial cognitive behaviors and perceptual considerations. To represent realistic route choice and natural movement of theses pedestrians, this paper presents a cognitive pedestrian behavior model with a focus on the space visibility and individual characteristics. Then the sensitivity of model parameters is analyzed, indicating that regional target, memory of visiting records and individual crowd tendency can have varied influences on pedestrians’ navigation decisions and movement patterns. As a case study, the proposed model is implemented using the pedestrian movement data collected from an observational study of Tate Gallery Museum. The simulation results show good consistency with the actual data at the aggregate level and those obtained individually, indicating that our proposed model is credible and can benefit real applications such as master planning of a museum.     

A distributed command governor based on graph colorability theory

In this paper, a distributed command governor (CG) strategy is introduced that, by the use of graph colorability theory, improves the scalability property and the performance of recently introduced distributed noncooperative sequential CG strategies. The latter are characterized by the fact that only 1 agent at a decision time is allowed to update its command, whereas all the others keep applying their previously computed commands. The scalability of these early CG distributed schemes and their performance are limited because the structure of the constraints is not taken into account in their implementation. Here, by exploiting the idea that agents that are not directly coupled by the constraints can simultaneously update their control actions, the agents in the network are grouped into particular subsets (turns). At each time instant, on the basis of a round‐robin policy, all agents belonging to a turn are allowed to update simultaneously their commands, whereas agents in other turns keep applying their previous commands. Then, a turn‐based distributed CG strategy is proposed and its main properties are analyzed. Graph colorability theory is used to determine the minimal number of turns and to distribute each agent in at least a turn. A novel graph colorability problem that allows one to maximize the frequency at which agents can update their commands is proposed and discussed. A final example is presented to illustrate the effectiveness of the proposed strategy.     

A fundamental approach to debugging

We examine the costs and psychology of debugging. We propose a fundamental approach to debugging. We suggest that industry's outlook is perhaps not thorough.     

基于多色图的宗地信息历史回溯模型及实现

为解决宗地信息历史回溯问题,基于多色图理论,建立了宗地信息历史回溯模型,将宗地抽象为多色图中的节点,宗地间的变更关系抽象为多色图中的边,用节点和边的不同颜色分别表示宗地的不同状态及宗地间不同的变更关系;提出了回溯矩阵的赋值算法及历史回溯算法;设计了宗地变更业务相关数据结构,分析了计算机后台处理程序,开发了宗地变更业务的原型系统,表明了该模型和算法的可行性.     

基于图论求解多选择背包问题

多选择背包问题涉及的约束条件种类最多,在背包问题的各种变形中最为复杂.使用动态规划的思想,巧妙地把这个组合优化领域的问题转化成图论上求最短路径的问题.因为标准的Dijkstra算法只能找出两个节点间的一条最短路径,为了克服这个问题,对该算法进行了改进.对案例的测试表明,该算法能成功地算出多选择背包问题的全部最优解.首次把动态规划、图论算法共同应用到多选择背包问题,既能发挥动态规划的理论优势来大大减少计算量,又能充分利用图论的已有成果.     

A graph grammar‐based approach for graph layout

As a two‐dimensional formal tool, graph grammars are capable of handling the layout problems of visual programming languages. Based on an edge‐based graph grammar (EGG), this paper proposes a novel layout approach that uses the unique features of EGG and overcomes the weakness of existing layout approaches. In order to make the approach rigorous yet concise, the graph grammar mechanisms with layout constraints and quantitative analysis techniques are combined together as an integrity. First, the basic notions of EGG are briefly introduced; second, the layout approach is presented that consists of two phases, ie, bottom‐up parsing and top‐down derivation. Finally, a case study is given by taking the standard flowchart as an example to demonstrate the working process of the proposed approach.     

The DenK-architecture: A fundamental approach to user-interfaces

In this paper we present the basic principles underlying the DenK-system, a generic cooperative interface combining linguistic and visual interaction. The system integrates results from fundamental research in knowledge representation, communication, natural language semantics and pragmatics, and object-oriented animation. Our design incorporates a cooperative and knowledgeable electronic assistant that communicates with a user in natural language, and an application domain, which is presented visually. The assistant, that we call thecooperator, has an information state that is represented in a rich form of Type Theory, a formalism that enables us to model the inherent cognitive dynamics of a dialogue participant. Pragmatic issues in man-machine interaction, concerning the use of natural language and knowledge in cooperative communication, are central to our approach.Authors' addresses: R. M. C. Ahn and H. C. Bunt, Institute for Language Technology and Artificial Intelligence (ITK), Tilburg University, P.O. Box 90153, 5000 LE Tilburg, The Netherlands, e-mail: r.m.c.ahn@kub.nl, h.c.bunt@kub.nl; R. J. Beun, Institute for Perception Research (IPO), P.O. Box 513, 5600 MB Eindhoven, The Netherlands, e-mail: rjbeun@prl.philips.nl; T. Borghuis and C. W. A. M. van Overveld, Eindhoven University of Technology, Den Dolech 2, Eindhoven, The Netherlands, e-mail: tijn@win.tue.nl, wsinkvo@info.win.tue.nl.     

一种基于有向图的工作流测试方法

已有工作流测试方法在测试完备性和充分性方面存在不足。针对此问题文章对有向图工作流模型进行扩展,提出了一种新的工作流测试方法,设计并实现了其算法。该方法能够自动生成完备且充分的测试路径和测试用例。实例验证该方法有效。     

一种基于图论的聚类算法NeiMu

提出一种新的基于图论的聚类算法NeiMu。该算法首先分析数据中的对象,寻找每个对象的k近邻,根据k近邻关系构造k近邻有向图,然后通过k近邻有向图中的k-互邻居关系构造k-聚类图,发现数据中的自然聚类。算法的特点是根据数据之间的互为k近邻关系确定数据中的自然簇,而不必引入其他方法来划分小簇,从而能够保证对象不会被错误聚类,仅会与其他小簇一起融合到一个大簇中。这一优点可以有效保证NeiMu算法的聚类质量。而且,NeiMu算法给出的这种类似自底向上的层次聚类结果还有利于用户根据渐变的结果确定最佳的k值。实验结果表明,该算法对密度变化大的数据、大小相差大的数据、任意分布形状的数据均具有很好的聚类质量,对孤立点也很健壮。     

一种基于图割理论的快速立体匹配算法

针对传统的立体匹配算法中存在的低纹理区域和遮挡区域匹配精度低、实时性不好等问题,提出了一种基于图割理论的立体匹配算法.把图像分割成色彩单一的不同区域;计算初始视差图,利用可靠点求取各分割区域的平面模板参数,对模板参数相同的相邻区域进行融合;构造全局能量函数,采用图割算法求取全局能量最小的视差最优分配.实验结果表明,该算法对低纹理区域和遮挡区域均有较好的匹配结果,能够满足高精度、高实时性的要求.     

基于图论的边缘提取方法

针对传统边缘方法提取的边缘具有不连续、不完整、倾斜、抖动和缺口等问题,提出基于图论的边缘提取方法。该方法视像素为节点,在水平或垂直方向上连接两个相邻的节点构成一个边,从而将图像看作无向图。它包括三个阶段：在像素相似性计算阶段,无向图的边上被赋予权值,权值代表了像素间的相似性;在阈值确定阶段,将所有权值的均值（整幅图像的相似度）确定为阈值;在边缘确定阶段,只保留权值小于阈值的水平边的左边节点与垂直边的上边节点,从而获得了图像的边缘。实验表明,该方法适用于具有明显目标与背景的图像的边缘提取,能够克服不连续、不完整、倾斜、抖动和缺口等缺陷,并且对Speckle噪声和高斯噪声具有抗噪性能。     

A Riemannian approach to graph embedding

In this paper, we make use of the relationship between the Laplace-Beltrami operator and the graph Laplacian, for the purposes of embedding a graph onto a Riemannian manifold. To embark on this study, we review some of the basics of Riemannian geometry and explain the relationship between the Laplace-Beltrami operator and the graph Laplacian. Using the properties of Jacobi fields, we show how to compute an edge-weight matrix in which the elements reflect the sectional curvatures associated with the geodesic paths on the manifold between nodes. For the particular case of a constant sectional curvature surface, we use the Kruskal coordinates to compute edge weights that are proportional to the geodesic distance between points. We use the resulting edge-weight matrix to embed the nodes of the graph onto a Riemannian manifold. To do this, we develop a method that can be used to perform double centring on the Laplacian matrix computed from the edge-weights. The embedding coordinates are given by the eigenvectors of the centred Laplacian. With the set of embedding coordinates at hand, a number of graph manipulation tasks can be performed. In this paper, we are primarily interested in graph-matching. We recast the graph-matching problem as that of aligning pairs of manifolds subject to a geometric transformation. We show that this transformation is Pro-crustean in nature. We illustrate the utility of the method on image matching using the COIL database.     

融合BTM和图论的微博检索模型

微博数据量庞大且微博文本的字符数少、特征稀疏,为提高检索精度,提出一种融合BTM和图论的微博检索模型,通过词汇语义相关度计算微博文本中带有标签的特征相关度,构建bi-term主题模型,用JSD距离计算映射到该模型中短文本的词对相关度,抽取CN-DBpedia中实体及图结构,再使用SimRank算法计算图结构中实体间的相关度。综上3种相关度为该模型最终相关度。最后使用新浪微博数据集进行检索实验,实验结果表明:对比于融合隐含狄利克雷分布算法与图论的检索模型和基于开放数据关联和图论方法系统模型,新模型在MAP、准确率和召回率上性能有明显提高,说明该模型具有较优的检索性能。     

一种基于二部图谱划分的聚类集成方法

将二部图模型引入聚类集成问题中,使用二部图模型同时建模对象集和超边集,充分挖掘潜藏在对象之间的相似度信息和超边提供的属性信息.设计正则化谱聚类算法解决二部图划分问题,在低维嵌入空间运行K-means++算法划分对象集,获得最终的聚类结果.在多组基准数据集上进行实验,实验结果表明所提出方法不仅能获得优越的结果,而且具有较高的运行效率.     

A tabu search based approach for graph layout

This paper describes an automated tabu search based method for drawing general graph layouts with straight lines. To our knowledge, this is the first time tabu methods have been applied to graph drawing. We formulated the task as a multi-criteria optimization problem with a number of metrics which are used in a weighted fitness function to measure the aesthetic quality of the graph layout. The main goal of this work is to speed up the graph layout process without sacrificing layout quality. To achieve this, we use a tabu search based method that goes through a predefined number of iterations to minimize the value of the fitness function. Tabu search always chooses the best solution in the neighbourhood. This may lead to cycling, so a tabu list is used to store moves that are not permitted, meaning that the algorithm does not choose previous solutions for a set period of time. We evaluate the method according to the time spent to draw a graph and the quality of the drawn graphs. We give experimental results applied on random graphs and we provide statistical evidence that our method outperforms a fast search-based drawing method (hill climbing) in execution time while it produces comparably good graph layouts. We also demonstrate the method on real world graph datasets to show that we can reproduce similar results in a real world setting.     

CALPHAD aqueous solution model based on the BET approach: General theory

The Brunauer–Emmett–Teller (BET) model for adsorption has found extensive use in modelling of adsorption, surfaces and concentrated solutions. We present here a Gibbs energy minimiser based application of a BET and related GAB model, implemented using the ChemApp program library via ChemSheet. The basic model is constructed using solely ideal mixture phases. The use of a free energy minimiser readily enables various extensions, such as multicomponent adsorption and interactions between lattice sites. While the method presented is applicable to BET model problems in general, the emphasis in this work is on applications related to concentrated aqueous solutions.     

基于高斯扩散模型的化工危险品泄露区域计算及其实现

化工危险品在生产储运过程中会引发泄漏扩散事故,对它的泄露扩散进行模拟,可以及时、准确、有效、直观地对事故过程的危险区域做出预测,并以此为依据制定相应的应急措施。以高斯扩散模型为核心,结合化工危险品数据库、地理信息系统GIS等现代计算机辅助技术对化工危险品扩散的短时间接触容许浓度范围、半致死浓度范围等指标进行科学的量化计算以及对泄漏事故进行技术模拟预测,并且成功的应用于实际项目中。