Digraph decompositions and monotonicity in digraph searching

Graph decompositions such as tree-decompositions and associated width measures have been the focus of much attention in structural and algorithmic graph theory. In particular, it has been found that many otherwise intractable problems become tractable on graph classes of bounded tree-width.More recently, proposals have been made to define a similar notion to tree-width for directed graphs. Several proposals have appeared so far, supported by algorithmic applications.In this paper we explore the limits of algorithmic applicability of digraph decompositions and show that various natural candidates for problems, which potentially could benefit from digraphs having small “directed width”, remain NP-complete even on almost acyclic graphs.Closely related to graph and digraph decompositions are graph searching games. An important property of graph searching games is monotonicity and a large number of papers addresses the question whether particular variants of these games are monotone. However, so far for two natural types of graph searching games-underlying DAG- and Kelly-decompositions-the question whether they are monotone was still open.We settle this issue by showing that both variants, the visible and the inert invisible graph searching games on directed graphs, are non-monotone.     

Breaking symmetries in graph search with canonizing sets

There are many complex combinatorial problems which involve searching for an undirected graph satisfying given constraints. Such problems are often highly challenging because of the large number of isomorphic representations of their solutions. This paper introduces effective and compact, complete symmetry breaking constraints for small graph search. Enumerating with these symmetry breaks generates all and only non-isomorphic solutions. For small search problems, with up to 10 vertices, we compute instance independent symmetry breaking constraints. For small search problems with a larger number of vertices we demonstrate the computation of instance dependent constraints which are complete. We illustrate the application of complete symmetry breaking constraints to extend two known sequences from the OEIS related to graph enumeration. We also demonstrate the application of a generalization of our approach to fully-interchangeable matrix search problems.     

基于RDF图结构切分的高效子图匹配方法

针对在SPARQL查询处理中,随着查询图结构逐渐复杂而导致基于图的查询效率愈发低下的问题,通过分析几种资源描述框架（RDF）图的基本结构,提出了一种基于查询图结构切分的子图匹配方法——RSM。首先,将查询图切分为若干结构简单的查询子图,并通过相邻谓词结构索引来定义查询图节点的搜索空间;然后,通过相邻子图结构来缩小搜索空间范围,在数据图中根据搜索空间中的搜索范围找到符合的子图结构;最后,将得到的子图进行连接并作为查询结果输出。将RSM与RDF-3X、R3F、GraSS等主流查询方法作比较,对比了各方法在不同数据集上对于复杂程度不同的查询图的查询响应时间。实验结果充分表明,与其他3种方法相比,在处理结构复杂的查询图时,RSM的查询响应时间更短,具有更高的查询效率。     

Monotonicity of non-deterministic graph searching

In graph searching, a team of searchers are aiming at capturing a fugitive moving in a graph. In the initial variant, called invisible graph searching, the searchers do not know the position of the fugitive until they catch it. In another variant, the searchers permanently know the position of the fugitive, i.e. the fugitive is visible. This latter variant is called visible graph searching. A search strategy that catches any fugitive in such a way that the part of the graph reachable by the fugitive never grows is called monotone. A priori, monotone strategies may require more searchers than general strategies to catch any fugitive. This is however not the case for visible and invisible graph searching. Two important consequences of the monotonicity of visible and invisible graph searching are: (1) the decision problem corresponding to the computation of the smallest number of searchers required to clear a graph is in NP, and (2) computing optimal search strategies is simplified by taking into account that there exist some that never backtrack.

Fomin et al. [F.V. Fomin, P. Fraigniaud, N. Nisse, Nondeterministic graph searching: From pathwidth to treewidth, in: Proceedings of the 30th International Symposium on Mathematical Foundations of Computer Science, MFCS’05, 2005, pp. 364–375] introduced an important graph searching variant, called non-deterministic graph searching, that unifies visible and invisible graph searching. In this variant, the fugitive is invisible, and the searchers can query an oracle that permanently knows the current position of the fugitive. The question of the monotonicity of non-deterministic graph searching was however left open.

In this paper, we prove that non-deterministic graph searching is monotone. In particular, this result is a unified proof of monotonicity for visible and invisible graph searching. As a consequence, the decision problem corresponding to non-deterministic graph searching belongs to NP. Moreover, the exact algorithms designed by Fomin et al. do compute optimal non-deterministic search strategies.     

A note on minimal d-separation trees for structural learning

Structural learning of a Bayesian network is often decomposed into problems related to its subgraphs, although many approaches without decomposition were proposed. In 2006, Xie, Geng and Zhao proposed using a d-separation tree to improve the power of conditional independence tests and the efficiency of structural learning. In our research note, we study a minimal d-separation tree under a partial ordering, by which the maximal efficiency can be obtained. Our results demonstrate that a minimal d-separation tree of a directed acyclic graph (DAG) can be constructed by searching for the clique tree of a minimal triangulation of the moral graph for the DAG.     

Graph Searching, Elimination Trees, and a Generalization of Bandwidth

The bandwidth minimization problem has a long history and a number of practical applications. In this paper we introduce a natural extension of bandwidth to partially ordered layouts. We consider this extension from three main viewpoints: graph searching, tree decompositions, and elimination orderings. The three graph parameters pathwidth, profile, and bandwidth related to linear layouts can be defined by variants of graph searching using a standard fugitive. Switching to an inert fugitive, the two former parameters are extended to treewidth and fill-in, and our first viewpoint considers the analogous tree-like extension that arises from the bandwidth variant. Bandwidth also has a definition in terms of ordered path decompositions, and our second viewpoint extends this in a natural way to ordered tree decompositions. In showing that both extensions are equivalent we employ the third viewpoint of elimination trees, as used in the field of sparse matrix computations. We call the resulting parameter the treespan of a graph and prove some of its combinatorial and algorithmic properties.     

Graph Searching, Elimination Trees, and a Generalization of Bandwidth

The bandwidth minimization problem has a long history and a number of practical applications. In this paper we introduce a natural extension of bandwidth to partially ordered layouts. We consider this extension from three main viewpoints: graph searching, tree decompositions, and elimination orderings. The three graph parameters pathwidth, profile, and bandwidth related to linear layouts can be defined by variants of graph searching using a standard fugitive. Switching to an inert fugitive, the two former parameters are extended to treewidth and fill-in, and our first viewpoint considers the analogous tree-like extension that arises from the bandwidth variant. Bandwidth also has a definition in terms of ordered path decompositions, and our second viewpoint extends this in a natural way to ordered tree decompositions. In showing that both extensions are equivalent we employ the third viewpoint of elimination trees, as used in the field of sparse matrix computations. We call the resulting parameter the treespan of a graph and prove some of its combinatorial and algorithmic properties.     

面向用户行为的页面质量评估

页面质量评估在搜索引擎系统中具有极其关键的作用,传统的方法是基于页面链接关系进行页面质量评估。但由于当前Web环境的复杂性,传统方法已经难以适应当前的Web环境,近年来,用户行为被用来弥补完全依赖链接关系方法的不足。用户行为可以分为两类:浏览行为和搜索行为。利用浏览行为构造了用户浏览图;提出了一种利用用户搜索行为的新方法,此方法构造了用户搜索图;合并用户浏览图和用户搜索图得到用户浏览搜索图。实验表明用户浏览搜索图的性能比较接近用户浏览图的性能,并超过全网的性能,同时用户浏览搜索图能够评价的页面数要大于用户浏览图。     

一种面向攻击图的即时验证方法

攻击图将原本孤立的攻击行为关联起来,描述潜在攻击路径,是一种网络脆弱性分析技术.现有方法通常从攻击目标节点开始进行反向搜索,找出所有可能的攻击路径,从而对网络进行安全分析.本文在攻击图的基础上,提出了一种基于正向搜索的即时验证方法.该方法快速搜索网络中的一条完整攻击路径,通常只需构造网络系统的部分状态空间,从而减轻了内存不足和状态爆炸等问题,可作为已有方法的补充.实验表明本文方法具备良好的性能和可扩展性.     

Tradeoffs in process strategy games with application in the WDM reconfiguration problem

We consider a variant of the graph searching games that models the routing reconfiguration problem in WDM networks. In the digraph processing game, a team of agents aims at processing, or clearing, the vertices of a digraph D. We are interested in two different measures: (1) the total number of agents used, and (2) the total number of vertices occupied by an agent during the processing of D. These measures, respectively, correspond to the maximum number of simultaneous connections interrupted and to the total number of interruptions during a routing reconfiguration in a WDM network.Previous works have studied the problem of independently minimizing each of these parameters. In particular, the corresponding minimization problems are APX-hard, and the first one is known not to be in APX. In this paper, we give several complexity results and study tradeoffs between these conflicting objectives. In particular, we show that minimizing one of these parameters while the other is constrained is NP-complete. Then, we prove that there exist some digraphs for which minimizing one of these objectives arbitrarily impairs the quality of the solution for the other one. We show that such bad tradeoffs may happen even for a basic class of digraphs. On the other hand, we exhibit classes of graphs for which good tradeoffs can be achieved. We finally detail the relationship between this game and the routing reconfiguration problem. In particular, we prove that any instance of the processing game, i.e. any digraph, corresponds to an instance of the routing reconfiguration problem.     

贝叶斯网结构学习搜索空间分析

贝叶斯网结构学习是一个NP难题,提高学习效率是重要研究问题之一。贝叶斯网结构空间的规模随节点(随机变量)数呈指数增加,选择适当的结构空间可以提高学习效率。本文对贝叶斯网结构空间进行定性和定量分析,对比有向图空间、贝叶斯网空间和马尔科夫等价类空间的规模和特点。通过实验数据分析先验结构空间约束对降低结构空间规模的效率,给出约束参数的选择区间。为贝叶斯网结构学习选择搜索空间和确定约束参数提供理论支持,从而提高学习效率。     

基于幂图的离群子空间搜索算法*

通过分析子空间搜索算法的研究现状以及存在的问题,提出基于幂图的离群子空间搜索算法。该方法主要讨论离群点产生的原因,能够找出单个对象的离群子空间,并根据离群子空间对离群点进行分类。在对幂图扩展的基础上进行剪枝,减少了存储量和计算量,算法性能得到很大的提高。采用实例说明了该算法,并通过实验证明了该算法的可行性和高效性。     

Black-white pebbles and graph separation

Summary We exhibit a close relationship between two topics in computational complexity. One topic is the analysis of storage requirements for nondeterministic computations. The corresponding mathematical model is a well known black-white pebble game on directed acyclic graphs. The other topic is the search for small separators of undirected graphs. We model a dynamic version of the concept of a separator with a vertex separator game. This game is closely related to graph layout and searching problems. We show that instances of the black-white pebble game and the vertex separator game can easily be transformed into each other. As an application of this result both games are shown to be NP-complete.     

Asymmetry in search

Most of the work on search in artificial intelligence (AI) deals with one search direction only-mostly forward search-although it is known that a structural asymmetry of the search graph causes differences in the efficiency of searching in the forward or the backward direction, respectively. In the case of symmetrical graph structure, however, current theory would not predict such differences in efficiency. In several classes of job sequencing problems, we observed a phenomenon of asymmetry in search that relates to the distribution of the are costs in the search graph. This phenomenon can be utilized for improving the search efficiency by a new algorithm that automatically selects the search direction. We demonstrate fur a class of job sequencing problems that, through the utilization of this phenomenon, much more difficult problems can be solved-according to our best knowledge-than by the best published approach, and on the same problems, the running time is much reduced. As a consequence, we propose to check given problems for asymmetrical distribution of are costs that may cause asymmetry in search.     

遗传算法求解邮递员问题的探讨

邮递员问题是目前一个尚未完全解决的图论问题,而遗传算法则是一个比较好的全局搜索算法,本文提出了一种换方法,以此为基础,用遗传算法实现了对有向图邮递员问题的求解,较传统方法更加容易实现,在求解大规模复杂网络时,其效率更高。     

基于基因搜索的模糊图象解释方法

图象解决是计算机视觉的重要组成部分，它涉及图象处理，分类器设计和逻辑推理等许多领域。针对目前图象解释系统要面对的严重噪声、模糊性和不确定性问题。重点研究了一种基于基因搜索的双向推理技术，该算法分为如下两步：首先通过基于分割区域统计/几何特征的模式分类器来得到初始的分类模糊隶属度，并根据经验（或统计）得到的先验空间位置关系模糊规则来构造一种有效表达图象解释信息的模糊图。然后通过基因搜索算法融合上面的两类信息来得到图象的最佳解释，实验结果表明，该方法对具有单一对象或多个对象的区域均有很好的效果，也是对基于概率、证据和模糊推理等单向推理机制图象解释方法的提高。     

Datalog程序的正规变换及其实现

文中提出了Ｄａｔａｌｏｇ程序的正规变换，并构造了Ｄａｔａｌｏｇ程序的约束模型图，从而把正规变换的求解转化为对约束模式图的搜索。约束模式图搜索算法与经典的ＡＯ＾＊搜索算法及相关文献中的算法相比具有更高的效率。     

基于路径映射的相似子图匹配算法

迄今为止,相关的图相似性匹配方法通常不考虑节点关系以及边权重的实际意义。提出一种基于路径映射 的相似子图匹配方法,用以更精确地查找具有相似拓扑结构的加权图。其创新之处在于充分利用标签信息,综合考虑 拓扑结构特征,克服了忽略节点结构关系和边权重的意义去分析图相似性的弊端。因此,该方法在很大程度上提高了 图相似性匹配的应用范围和匹配精度。实验表明本方法具有较高的查询质量和效率。     

回溯算法的形式模型

讨论了回溯算法的形式模型,提出了刻画回溯的一些数学概念,以隐式搜索教育界背景提出了状态空间概念,给出了分别以邻接方阵和邻接表形式表示的有向图所对应的状态空间,从而说明显式搜索是隐式搜索的特例,通过展开空间概念揭示了问题求解的不同要求所对应的不同数据结构,提出了通用回溯算法,并以N皇后问题、稳定婚姻问题,点着色问题、子集和数问题,跳马问题,最长路径问题和强连通分支问题等多种算法设计问题为例讨论了通用回溯 算法的应用,该文结果有助于扩大回溯算法的使用范围,提高回溯算法实现的正确性和效率。     

知识图谱嵌入研究综述

随着互联网技术和应用模式的迅猛发展,表达方式丰富直观的知识图谱得到了大量关注,在知识表示学习方面积累了丰富研究成果,这些研究已在垂直搜索、智能问答等应用领域发挥了重要作用.在总结现有知识图谱嵌入研究基础之上,以面向的知识图谱数量为依据,将知识图谱嵌入模型分为面向单个知识图谱的链接预测模型和面向多个知识图谱的实体对齐模型...