应用图论分析与最优化理论来数据挖掘大规模水牛普里昂蛋白结构数据（英文）

图论、最优化理论显然在蛋白质结构的研究中大有用场.首先,调查/回顾了研究蛋白质结构的所有图论模型.其后,建立了一个图论模型:让蛋白质的侧链来作为图的顶点,应用图论的诸如团、k-团、社群、枢纽、聚类等概念来建立图的边.然后,应用数学最优化的现代摩登数据挖掘算法/方法来分析水牛普里昂蛋白结构的大数据.成功与令人耳目一新的数值结果将展示给朋友们.     

基于哈密顿因子的蛋白质结构类研究

应用图论的哈密顿路模型研究了蛋白质结构类型,统计来自PDB的α型、β型、α+β型、α/β型单链蛋白质结构的哈密顿因子并进行方差分析,统计结果表明蛋白质结构不同类型的哈密顿因子存在显著差异,p值为0.0313.研究为蛋白质结构类研究提供了新的思路.     

关于图的因子分解

§1.引言 Petersen引入图的因子分解的概念,证明了一个图能2-因子分解的充分必要条件是该图为偶正则的,并由此给出了一类Diophanine方程的基础解。从此,图的因子理论一直为人们所重视,成为图论研究中最活跃的课题之一。著名匈牙利数学家Lovasz在提到图论中有些分枝的中心结构定理形成了图论研究的骨干时,把图因子和连通性作为两个这样的例子特别地提出来了。图的因子分解在研究图的结构性质中起重要作用,并且有重要的实际意义,在对策、组合设计,组合最优化以及生物等都有用处。图的同构是图论中的最基本的关系,有如拓扑学中的同胚,初等几何中的全同。然而同     

H图的充要条件和最小H回路的最优化模型

本文应用最优化方法,分别建立了无向(或有向)图是Hamilton图的充要条件、无向(或有向)赋权图最小总权Hamjlton回路等著名图论问题的整数规划模型,使上述著名难题能被借助于任一种求解整数规划的算法而得到解决。     

现代优化计算方法在蛋白质结构预测中的应用

现代优化计算方法在蛋白质结构预测中占有重要地位.简要地介绍了模拟退火算法,遗传算法,人工神经网络和图论算法在蛋白质结构预测中的应用.对国内外近年来应用这些算法,特别是在蛋白质构象搜索问题中,解决蛋白质结构预测的研究作了回顾,并分析、比较了这几种算法的效果和特点.     

广义太阳图的Felicitous性质

本文研究了广义太阳图的felicitous标号.利用广义太阳图的结构特征,获得了2类特殊广义太阳图的精确felicitous标号.并且,这些类图论模型在编码理论、通讯网络、物流等方面均有重要的应用.     

广义太阳图的Felicitous性质（英文）

本文研究了广义太阳图的felicitous标号.利用广义太阳图的结构特征,获得了2类特殊广义太阳图的精确felicitous标号.并且,这些类图论模型在编码理论、通讯网络、物流等方面均有重要的应用.     

p~2阶非正规Cayley图的核

图的核的研究是当前图论特别是代数图论中的一个前沿课题.一个图的核定义为与该图同态等价的最小阶的图.本文通过讨论p~2阶(p是素数)非正规Cayley图是否存在与其同态等价的诱导子图,研究该Cayley图与其诱导子图的色数、团数和独立数之间的关系,进而确定两个图之间是否存在同态等价.在此基础上确定出p~2阶非正规Cayley图的核.     

基于Hamilton路模型的蛋白质结构预测的研究

提出一种基于Hamilton路模型的新方法研究蛋白质结构预测问题,为使结构匹配序列,把已知蛋白质的3D结构信息转化为一个加权的完全图Kn,则求这个特定空间结构所匹配的氨基酸残基序列问题转化为求Kn图的最小H路问题.用此方法研究了72个单链蛋白质结构,结果表明Kn图的最小H路对应此蛋白质的序列,图的顶点数n与最小H路总长度成正比.     

最优消除顺序

本文从一个离散最优化问题的算法复杂性出发,提出了图论中一个新的而有趣的问题:图的节点最优消除顺序.这一问题不仅有实用价值,而且有理论意义.本文只得到该问题的部分结果,并提出了若干待解决的问题,供有兴趣的读者进行研究.     

选择最佳公交线路的数学模型

归纳影响乘客选择公交路线的诸多因素,以换乘次数少、时间短、费用低作为设计最佳路径的目标,利用数据结构和图论思想,建立了选择最佳公交线路的数学模型.     

Statistical ranking and combinatorial Hodge theory

We propose a technique that we call HodgeRank for ranking data that may be incomplete and imbalanced, characteristics common in modern datasets coming from e-commerce and internet applications. We are primarily interested in cardinal data based on scores or ratings though our methods also give specific insights on ordinal data. From raw ranking data, we construct pairwise rankings, represented as edge flows on an appropriate graph. Our statistical ranking method exploits the graph Helmholtzian, which is the graph theoretic analogue of the Helmholtz operator or vector Laplacian, in much the same way the graph Laplacian is an analogue of the Laplace operator or scalar Laplacian. We shall study the graph Helmholtzian using combinatorial Hodge theory, which provides a way to unravel ranking information from edge flows. In particular, we show that every edge flow representing pairwise ranking can be resolved into two orthogonal components, a gradient flow that represents the l ₂-optimal global ranking and a divergence-free flow (cyclic) that measures the validity of the global ranking obtained—if this is large, then it indicates that the data does not have a good global ranking. This divergence-free flow can be further decomposed orthogonally into a curl flow (locally cyclic) and a harmonic flow (locally acyclic but globally cyclic); these provides information on whether inconsistency in the ranking data arises locally or globally. When applied to statistical ranking problems, Hodge decomposition sheds light on whether a given dataset may be globally ranked in a meaningful way or if the data is inherently inconsistent and thus could not have any reasonable global ranking; in the latter case it provides information on the nature of the inconsistencies. An obvious advantage over the NP-hardness of Kemeny optimization is that HodgeRank may be easily computed via a linear least squares regression. We also discuss connections with well-known ordinal ranking techniques such as Kemeny optimization and Borda count from social choice theory.     

关于图论课教学的思考

在科学技术迅猛发展的今天，尤其是网络和信息产业的兴起，图论课越来越受到广泛的重视,本文总结了多年的图论课教学改革的一些经验．     

A sequential pattern mining algorithm using rough set theory

Sequential pattern mining is a crucial but challenging task in many applications, e.g., analyzing the behaviors of data in transactions and discovering frequent patterns in time series data. This task becomes difficult when valuable patterns are locally or implicitly involved in noisy data. In this paper, we propose a method for mining such local patterns from sequences. Using rough set theory, we describe an algorithm for generating decision rules that take into account local patterns for arriving at a particular decision. To apply sequential data to rough set theory, the size of local patterns is specified, allowing a set of sequences to be transformed into a sequential information system. We use the discernibility of decision classes to establish evaluation criteria for the decision rules in the sequential information system.     

CMARS and GAM & CQP—Modern optimization methods applied to international credit default prediction

In this paper, we apply newly developed methods called GAM & CQP and CMARS for country defaults. These are techniques refined by us using Conic Quadratic Programming. Moreover, we compare these new methods with common and regularly used classification tools, applied on 33 emerging markets’ data in the period of 1980-2005. We conclude that GAM & CQP and CMARS provide an efficient alternative in predictions. The aim of this study is to develop a model for predicting the countries’ default possibilities with the help of modern techniques of continuous optimization, especially conic quadratic programming. We want to show that the continuous optimization techniques used in data mining are also very successful in financial theory and application. By this paper we contribute to further benefits from model-based methods of applied mathematics in the financial sector. Herewith, we aim to help build up our nations.     

Optimal payoff under the generalized dual theory of choice

We consider portfolio optimization under a preference model in a single-period, complete market. This preference model includes Yaari’s dual theory of choice and quantile maximization as special cases. We characterize when the optimal solution exists and derive the optimal solution in closed form when it exists. The optimal portfolio yields an in-the-money payoff when the market is good and zero payoff otherwise. Finally, we extend our portfolio optimization problem by imposing a dependence structure with a given benchmark payoff.     

Computational Algorithms for Censored-Data Problems Using Intersection Graphs

This article presents methods for finding the nonparametric maximum likelihood estimate (NPMLE) of the distribution function of time-to-event data. The basic approach is to use graph theory (in particular intersection graphs) to simplify the problem. Censored data can be represented in terms of their intersection graph. Existing combinatorial algorithms can be used to find the important structures, namely the maximal cliques. When viewed in this framework there is no fundamental difference between right censoring, interval censoring, double censoring, or current status data and hence the algorithms apply to all types of data. These algorithms can be extended to deal with bivariate data and indeed there are no fundamental problems extending the methods to higher dimensional data. Finally this article shows how to obtain the NPMLE using convex optimization methods and methods for mixing distributions. The implementation of these methods is greatly simplified through the graph-theoretic representation of the data.     

基于可信性理论的均值-熵-偏度投资组合模型及其算法求解

本文考虑到证券市场的投资者往往面临着随机和模糊两种不确定性的情形,在模糊随机环境下把证券的收益率视作三角模糊变量,在可信性理论基础上建立了带融资约束条件的均值-熵-偏度三目标投资组合决策模型,拓展了基于可信性理论的投资组合决策模型的研究内容,同时通过对约束条件处理方法,外部档案维护方法等关键算子的改良,提出了一种新的约束多目标粒子群算法。本文运用该算法对模型进行求解,把得到的最优解与传统的多目标粒子群算法得到的最优解进行对比,结果表明新算法得到的最优解的质量会显著地优于传统的多目标粒子群算法的最优解,从而验证了算法的有效性和准确性。该算法可以在三维空间中得到一个分布性和逼近性较好的Pareto最优曲面,满足投资者对不同目标的差异需求,为投资者提供合理的投资组合决策方案。     

In and out forests on combinatorial landscapes

Fitness landscape theory is a mathematical framework for numerical analysis of search algorithms on combinatorial optimization problems. We study a representation of fitness landscape as a weighted directed graph. We consider out forest and in forest structures in this graph and establish important relationships among the forest structures of a directed graph, the spectral properties of the Laplacian matrices, and the numbers of local optima of the landscape. These relationships provide a new approach for computing the numbers of local optima for various problem instances and neighborhood structures.     

The theory of elementary landscapes

When joined to a stipulated neighborhood diagraph, an objective functin defined on the solution space of a real combinatorial optimization problem forms a landscape. Grover shows that landscapes satisfying a certain difference equation have properties favorable to local search.Studying only symmetric and regular neighborhood diagraphs, Stadler defines elementary landscapes as those which can be realized as an eigenvector of the Laplacian of the neighborhood diagraph, and shows that such landscapes satisfy Grover's difference equation.Recent developments in algebraic graph theory support a new definition of the graph Laplacian which we use to extend the notion of elementary landscapes to neighborhood diagraphs which may be neither regular nor symmetric. This paper uses the new definition to extend the notion of elementary landscapes so that they characterize landscapes satisfying Grover's wave equation.We extend some known results to these more general elementary landscapes and analyse the types which may occur.