迭代拉普拉斯半监督学习本体算法

本体相似度计算和本体映射是知识表示和信息处理的核心研究内容。利用迭代拉普拉斯半监督学习方法将本体图中每个顶点映射成一个实数,通过比较顶点对应实数间的差值得到本体相似度计算算法和本体映射策略。通过两个实验表明,该方法对特定的应用领域是有效的。     

一种新的AOV网络拓扑排序算法

通过表达每个顶点在图中相对其他顶点的位置，提出的后序集的概念。基于此将图用二维数组存储，构造出一种新的基于后序集的AOV网拓扑排序算法，给出了算法的思路和实现步骤，采用一个装配生产线作业顺序规划问题为实例，验证了算法的正确性和可行性。     

本体算法中相似度矩阵的学习

本体图中顶点之间的相似度计算是各类本体算法的本质所在.本体图中各个顶点对的相似度组成本体相似度矩阵,因此得到一个最优相似度矩阵是本体应用的实质.本文提出一种通过计算距离矩阵来得到本体相似度矩阵的方法,该方法着眼于降维过程的稀疏化和解的光滑性.从样本集得到相似顶点对集合S和不相似度顶点对集合D,由此得到三元组Γ.将Γ的信息融入到计算模型中,进而使得距离矩阵保持了原本体图中顶点间的距离结构特征.借鉴凸最小最大优化模型的光滑逼近法,得到距离矩阵计算模型的求解策略.最后,通过两个具体实验表明,本文所给的相似度矩阵计算方法对于特定应用领域中的本体相似度计算和不同本体间建立本体映射具有较高的效率.     

基于谱图理论的本体相似度计算

概念的语义相似度研究,是知识表示以及信息检索领域中的一个重要内容。将与某概念相关的信息表示为一个向量,建立原本体图的伴随图。用ε-领域方法定义边,用高斯核函数定义边的权值。通过计算图拉普拉斯矩阵的次小特征值对应的特征向量得到本体相似度计算函数。实验结果表明该算法是有效的。     

Supervised and Transductive Ranking Algorithms with Relational Objects

在信息检索和机器学习领域,大部分排序学习方法假设查询中的各个对象均满足独立同分布.虽然该假设简化了排序问题,却未能利用目标对象之闻隐藏的相关性信息.在全监督排序和直推式排序2个问题中分别提出了新的方法,充分地利用了对象间的关系.在全监督排序问题中,将对象相关性映射为RBF Kernel,作为约束项加入优化目标,使得优化过程中越相似的对象打分越接近,即全局一致性思想.在直推式排序问题中,利用对象相关性将每个查询映射为图结构,设计了新的基于图结构的查询相似度度量,使得优化过程中越相似的查询,该查询内的对象对预测查询的影响越大.实验结果表明,加入对象之间的相关性提升了全监督排序算法和直推式排序算法的性能.     

基于对象相关性的全监督和直推式排序算法

在信息检索和机器学习领域,大部分排序学习方法假设查询中的各个对象均满足独立同分布.虽然该假设简化了排序问题,却未能利用目标对象之间隐藏的相关性信息.在全监督排序和直推式排序2个问题中分别提出了新的方法,充分地利用了对象间的关系.在全监督排序问题中,将对象相关性映射为RBF Kernel,作为约束项加入优化目标,使得优化过程中越相似的对象打分越接近,即全局一致性思想.在直推式排序问题中,利用对象相关性将每个查询映射为图结构,设计了新的基于图结构的查询相似度度量,使得优化过程中越相似的查询,该查询内的对象对预测查询的影响越大.实验结果表明,加入对象之间的相关性提升了全监督排序算法和直推式排序算法的性能.     

一种新的散列排序算法

根据大多数统计数据服从正态分布的特性 ,在排序时不需要用传统的比较排序算法 ,而是根据分布函数构造出一个序号函数 ,运用该函数可以很快计算出每个数据所排的位置。其排序速度大大快于 QUIKSORT等比较排序 ,排序时间的平均特性仅为 O(n)     

基于查询聚类的排序学习算法

排序学习算法作为信息检索与机器学习的一个交叉领域,越来越受到人们的重视。然而,几乎没有排序学习算法考虑到查询差异的存在。文中查询被建模为多元高斯分布,KL距离被用来度量查询之间的距离,利用谱聚类方法对查询进行聚类,为每个聚类类别训练一个排序函数。实验结果表明经过聚类得到的排序函数需要较少的训练样例,但是它的性能却和没有经过聚类得到的排序函数具有可比性,甚至优于后者。     

一种比QUICKSORT更快的排序算法

本文根据大多数统计数据服从正态分布的特性,在排序时不需要用传统的比较排序算法,而是根据分布函数构造出一个序号函数,运用该函数可以很快地计算出每个数据所排的位置。其排序速度大大快于QUICKSORT等比较排序,排序时间的平均特性仅为0（n）。     

基于概率分布的排序算法(1)

该文根据大多数统计数据都服从某一概率分布的特性,在排序时不需要用传统的比较排序算法,而是根据其密度函数构造出一个序号函数,运用该函数可以很快计算出每个数据所排的位置。其排序速度大大快于QUIKSORT等比较排序算法,时间和空间的耗费真正达到了O(n)。     

Greedy rankings and arank numbers

A ranking on a graph is an assignment of positive integers to its vertices such that any path between two vertices of the same rank contains a vertex of strictly larger rank. A ranking is locally minimal if reducing the rank of any single vertex produces a non-ranking. A ranking is globally minimal if reducing the ranks of any set of vertices produces a non-ranking. A ranking is greedy if, for some ordering of the vertices, it is the ranking produced by assigning ranks in that order, always selecting the smallest possible rank. We will show that these three notions are equivalent. If a ranking satisfies one property it satisfies all three. As a consequence of this and known results on arank numbers of paths we improve known upper bounds for on-line ranking of paths and cycles.     

利用相互增强关系迭代计算本体中概念与关系的重要性

通过排序本体中概念重要性和关系权重的方式评价本体,能够辅助领域专家改进本体设计,辅助语义Web搜索引擎实现.现有链接分析技术不能直接应用于对概念的排序,而且缺乏有效方法对关系赋予权重.文中提出依据本体的图结构特点,以Hub值代替Authority值作为概念重要性,并利用本体中概念和关系相互增强的迭代方式计算概念重要性和关系权重.证明该迭代过程收敛于迭代方程组的不动点.实验初步表明,该方法具有与PageRank接近的收敛速度,并能得到合理的概念重要性与关系权重的排序结果.     

On vertex ranking of a starlike graph

A vertex coloring c:V→{1,2,…,t} of a graph G=(V,E) is a vertex t-ranking if for any two vertices of the same color every path between them contains a vertex of larger color. The vertex ranking number χ_r(G) is the smallest value of t such that G has a vertex t-ranking. A χ_r(G)-ranking of G is said to be an optimal vertex ranking. In this paper, we present an O(|V|+|E|) time algorithm for finding an optimal vertex ranking of a starlike graph G=(V,E). Our result implies that an optimal vertex ranking of a split graph can be computed in linear time.     

A Generalization of AT-Free Graphs and a Generic Algorithm for Solving Triangulation Problems

Abstract. A subset A of the vertices of a graph G is an asteroidal set if for each vertex a ∈ A a connected component of G-N[a] exists containing A\backslash{a} . An asteroidal set of cardinality three is called asteriodal triple and graphs without an asteriodal triple are called AT-free . The maximum cardinality of an asteroidal set of G , denoted by \an(G) , is said to be the asteriodal number of G . We present a scheme for designing algorithms for triangulation problems on graphs. As a consequence, we obtain algorithms to compute graph parameters such as treewidth, minimum fill-in and vertex ranking number. The running time of these algorithms is a polynomial (of degree asteriodal number plus a small constant) in the number of vertices and the number of minimal separators of the input graph.     

特殊模糊数集上的一种新的排序函数

针对模糊数的排序问题,给出几条自然的排序准则并提出了一种新的特殊模糊数的排序函数。该函数基于格论中的字典序,依次通过模糊数中心、模糊数与x轴所围图形面积以及模糊数图形的重心位置三个指标综合确定模糊数的排序;克服了现有方法的某些缺陷,具有一定的优越性和启发性。     

一种保持结点可达性的高效社会网络图匿名算法

为了保护社会网络隐私信息,提出了多种社会网络图匿名化技术.图匿名化目的在于通过图修改操作来防止隐私泄露,同时保证匿名图在社会网络分析和图查询方面的数据可用性.可达性查询是一种基本图查询操作,可达性查询精度是衡量图数据可用性的一项重要指标.然而,当前研究忽略了图匿名对结点可达性的影响,导致较大的可达性信息损失.为了保持匿名图中结点的可达性,提出了可达性保持图匿名化（reachability preserving anonymization,简称RPA）算法,其基本思想是将结点进行分组并采取贪心策略进行匿名,从而减少匿名过程中的可达性信息损失.为了保证RPA算法的实用性,针对其执行效率进行优化,首先提出采用可达区间来高效地评估边添加操作所导致的匿名损失;其次,通过采用候选邻居索引,进一步加速RPA算法对每个结点的匿名过程.基于真实社会网络数据的实验结果表明了RPA算法的高执行效率,同时验证了生成匿名图在可达性查询方面的高精度.     

C-Rank:一种Deep Web数据记录可信度评估方法

针对Web信息可信度问题,提出了一种为Deep Web数据记录计算可信度的有效方法C-Rank。该方法为每一条记录构造一个S-R可信度网络,包含两种类型顶点及三种类型边。首先基于可信度传播的思想,利用顶点出度为每一个顶点计算其局部可信度值;再利用Record顶点入度及相邻Site顶点的可信度值,为该Record顶点计算权值;继而求得整个S-R网络的全局可信度值。实验证明,C-Rank方法能够合理而有效地评价数据记录的可信度,从而达到甄别虚假信息,为用户推荐可信数据记录的目的。该方法普遍适用于Deep Web的各个领域。     

An Efficient Algorithm for Finding All Hinge Vertices on Trapezoid Graphs

The distance between at least two vertices becomes longer after the removal of a hinge vertex. Thus a faulty hinge vertex will increase the overall communication cost in a network. Therefore, finding the set of all hinge vertices in a graph can be used to identify critical nodes in a real network. An O(n log n) time algorithm has been proposed here to find all hinge vertices of a trapezoid graph with n vertices.     

Constructing a minimum height elimination tree of a tree in linear time

Given a graph, finding an optimal vertex ranking and constructing a minimum height elimination tree are two related problems. However, an optimal vertex ranking does not by itself provide enough information to construct an elimination tree of minimum height. On the other hand, an optimal vertex ranking can readily be found directly from an elimination tree of minimum height. On n-vertex trees, the optimal vertex ranking problem already has a linear-time algorithm in the literature. However, there is no linear-time algorithm for the problem of finding a minimum height elimination tree. A naive algorithm for this problem requires O(nlogn) time. In this paper, we propose a linear-time algorithm for constructing a minimum height elimination tree of a tree.     

基于多模态概念关联图的视频检索

为了有效地提高基于概念的视频检索的检索性能,提出一种新颖的基于多模态概念关联图的视频检索方法.首先通过分析查询与概念之间的组织关系得到网状关系模型描述,并基于该模型构建概念关联图;然后提出查询与概念的多模态映射结构,将多模态查询融入概念关联图,增强概念扩展的针对性;之后使用流形排序动态地扩展索引概念集;全局稳态后采用正交的概念融合方法计算视频索引值,用于视频检索.与多种典型的基于概念的视频检索方法相比,文中方法的平均检索精度增幅达14.6%～86.2%.此外,实验结果表明,该方法在实际的交互式视频检索系统中也具有良好的适用性.