二部图形式的Erd\H{O}s-S\'{o}s猜想

二部图形式的Erd\H{O}s-S\''{o}s猜想     

五边形图的标准化的拉普拉斯谱及其应用

一个图的标准化的拉普拉斯特征值对图在结构性质和一些相关的动力学方面提供了信息,尤其在相关的随机过程方面. 在这篇文章中,我们给出了由一个简单连通图迭代生成的五边形图的标准化的拉普拉斯谱.在应用方面,我们得到了关于倍增度基尔霍夫指数,凯梅尼常数和生成树的个数的重要公式.     

Near-optimal Nonlinear Regression Trees

We propose Near-optimal Nonlinear Regression Trees with hyperplane splits (NNRTs) that use a polynomial prediction function in the leaf nodes, which we solve by stochastic gradient methods. On synthetic data, we show experimentally that the algorithm converges to the global optimal. We compare NNRTs, ORT-LH, Multivariate Adaptive Regression Splines (MARS), Random Forests (RF) and XGBoost on 40 real-world datasets and show that overall NNRTs have a performance edge over all other methods.     

最小成本生成树对策上Shapley值的新刻画及其应用

2002年,Kar利用有效性、无交叉补贴性、群独立性和等处理性四个公理对最小成本生成树对策上的Shapley值进行了刻画。本文提出了“群有效性”这一公理,利用这一公理和“等处理性”两个公理,给出了最小成本生成树对策上Shapley值的一种新的公理化刻画。最后,运用最小成本生成树对策的Shapley值,对网络服务的费用分摊问题进行了分析。     

基于IERT的非线性全光谱复杂水体定量分析算法研究

水是一种有限的资源,对农业、工业乃至人类的生存都是必不可少的,良好的水环境是可持续发展的重要保障。对水质信息的科学监测,是实现水资源优化配置与高效利用的基础。联合国环境署（UNEP）与世界卫生组织（WHO）指出,应当加强发展中国家的水质监测网络,包括数据质量的保证和分析能力的提高。光谱法作为一种新兴的水质分析方法,相比传统的化学水质监测方法,具有“响应速度快、多参数同步、绿色无污染”的特点。传统单波长、多波长的线性模型依赖于水体对特定波长的吸收特征,不适用于多组分混合溶液且普适性较差。因此,提出了一种基于IERT的非线性全光谱定量分析算法,建立适用于多组分混合溶液浓度预测模型,达到利用全光谱信息来预测浓度信息的目的。利用实验室配置的COD,BOD₅和TOC多组分混合溶液与NO₃-N、浊度、色度多组分混合溶液作为实验样本,使用光谱仪采集样本的光谱曲线,通过全光谱数据进行浓度预测实验,结果显示,对于COD,BOD₅和TOC多组分混合溶液,本算法对于三种组分的决定系数（R2）分别为0.999 3,0.991 4和0.999 3,均方根误差（RMSE）分别为0.024 4,0.057 7和0.000 4;对于NO₃-N、浊度、色度多组分混合溶液,决定系数（R2）分别为0.983 4,0.868 4和0.981 0,均方根误差（RMSE）分别为0.100 5,0.326 4和0.120 2。通过对比本算法与偏最小二乘（PLS）、支持向量机回归（SVR）、决策树（DT）、极端随机树（ERT）对于同一组数据的实验结果,表明：在两组多组分混合溶液的实验中,本算法对于其中各组分的决定系数（R2）均为最优,相比于其他对比算法均方根误差（RMSE）均有大幅减少。本算法可利用光谱信息对多组分混合溶液进行定量分析,在计算时间相当的情况下,可有效的提高浓度预测精度,减少定量分析的均方根误差,可为光谱法水质监测提供一种新的有效途径。     

Construction and studies of a new class of reciprocal trees: interknitting of the Pascal's triangle

A method of construction of a new class of trees with reciprocal pairs of eigenvalues (λ, 1/λ) has been developed. They are derived from star graphs and can be symbolized as K _{1, n ?1} + n(p) + mK ₂ (1 ≤ m ≤ n ? 1 except for n = 1). The trees are minimally Kekulenoid and hence contain reciprocal pairs of eigenvalues in their eigenspectra. The characteristic polynomial coefficients of these trees with given values of n and m are shown to be obtainable by appropriate use of the Pascal's triangle. A general formula for this purpose has been developed. An analytical formula for the Wiener indices of such trees in terms of m and n has been derived and some consequences of this formula are presented. The relevance of these trees to real molecular structures is discussed. The trees have been shown to be useful in observing the subspectrallity of two series of IPR fullerenes of formulae C_{50+10 n} and C_{60+12 n} (n is a positive integer).     

Random field Ising model and community structure in complex networks

We propose a method to determine the community structure of a complex network. In this method the ground state problem of a ferromagnetic random field Ising model is considered on the network with the magnetic field B_s = +∞, B_t = -∞, and B_i≠s,t=0 for a node pair s and t. The ground state problem is equivalent to the so-called maximum flow problem, which can be solved exactly numerically with the help of a combinatorial optimization algorithm. The community structure is then identified from the ground state Ising spin domains for all pairs of s and t. Our method provides a criterion for the existence of the community structure, and is applicable equally well to unweighted and weighted networks. We demonstrate the performance of the method by applying it to the Barabási-Albert network, Zachary karate club network, the scientific collaboration network, and the stock price correlation network. (Ising, Potts, etc.)     

Random pseudofractal scale-free networks with small-world effect

A random pseudofractal network (RPN) is generated by a recursive growing rule. The RPN is of the scale-free feature and small-world effect. We obtain the theoretical results of power-law exponent γ=3, clustering coefficient C=3π²-19≈ 0.74, and a proof that the mean distance increases no faster than ln N, where N is the network size. These results agree with the numerical simulation very well. In particular, we explain the property of growth and preferential attachment in RPNs. And the properties of a class of general RPNs are discussed in the end.     

Efficiency of the Incomplete Enumeration Algorithm for Monte-Carlo Simulation of Linear and Branched Polymers

We study the efficiency of the incomplete enumeration algorithm for linear and branched polymers. There is a qualitative difference in the efficiency in these two cases. The average time to generate an independent sample of configuration of polymer with n monomers varies as n ² for linear polymers for large n, but as exp(cn ^α) for branched (undirected and directed) polymers, where 0<α<1. On the binary tree, our numerical studies for n of order 10⁴ gives α = 0.333±0.005. We argue that α =1/3 exactly in this case. An erratum to this article can be found at .     

A visual proof of a result of Knuth on spanning trees of Aztec diamonds in the case of odd order

The even Aztec diamond AD_n is known to have precisely four times more spanning trees than the odd Aztec diamond OD_n—this was conjectured by Stanley and first proved by Knuth. We present a short combinatorial proof of this fact in the case of odd n. Our proof works also for the more general case of odd-by-odd Aztec rectangles.