Letter-Value Plots: Boxplots for Large Data

Boxplots are useful displays that convey rough information about the distribution of a variable. Boxplots were designed to be drawn by hand and work best for small datasets, where detailed estimates of tail behavior beyond the quartiles may not be trustworthy. Larger datasets afford more precise estimates of tail behavior, but boxplots do not take advantage of this precision, instead presenting large numbers of extreme, though not unexpected, observations. Letter-value plots address this problem by including more detailed information about the tails using “letter values,” an order statistic defined by Tukey. Boxplots display the first two letter values (the median and quartiles); letter-value plots display further letter values so far as they are reliable estimates of their corresponding quantiles. We illustrate letter-value plots with real data that demonstrate their usefulness for large datasets. All graphics are created using the R package lvplot, and code and data are available in the supplementary materials.     

求最短路径的“改进标号法”

本给出了求赋权图中两顶点之间最短路径的“改进标号法”,该方法在效率上优于Ｄｉｊｋｓｔｒａ的标号法,并在确定最短路径的长度的同时,也确定了相应的最短路径。     

关于图的结合数的一个猜想

本文对图论中的Woodall关于结合数的一个猜想作了研究,证明了:若图G的结合数,则图G包含三角形,从而较好地改进了文献[1]中的一个结果.     

A Sharp Upper Bound for the Number of Spanning Trees of a Graph

Let G = (V,E) be a simple graph with n vertices, e edges and d₁ be the highest degree. Further let λ_i, i = 1,2,...,n be the non-increasing eigenvalues of the Laplacian matrix of the graph G. In this paper, we obtain the following result: For connected graph G, λ₂ = λ₃ = ... =  λ_n-1 if and only if G is a complete graph or a star graph or a (d₁,d₁) complete bipartite graph. Also we establish the following upper bound for the number of spanning trees of G on n, e and d₁ only:

A Survey on the Relation Between Transitivity and Dense Periodicity for Graph Maps

This paper is an outline of the relation between the transitivity, the dense periodicity and the topological entropy of graph maps.     

A fast method for discovering critical edge sequences in e-commerce catalogs

Web sites allow the collection of vast amounts of navigational data – clickstreams of user traversals through the site. These massive data stores offer the tantalizing possibility of uncovering interesting patterns within the dataset. For e-businesses, always looking for an edge in the hyper-competitive online marketplace, the discovery of critical edge sequences (CESs), which denote frequently traversed sequences in the catalog, is of significant interest. CESs can be used to improve site performance and site management, increase the effectiveness of advertising on the site, and gather additional knowledge of customer behavior patterns on the site.     

A New Method for Estimating the Distribution of Scan Statistics for a Two-Dimensional Poisson Process

A method for estimating the distribution of scan statistics with high precisìon was introduced in Haiman (2000). Using that method sharp bounds for the errors were also established. This paper is concerned with the application of the method in Haiman (2000) to a two-dimensional Poisson process. The method involves the estimation by simulation of the conditional (fixed number of points) distribution of scan statistics for the particular rectangle sets of size 2 × 2, 2 × 3, 3 × 3, where the unit is the (1 × 1) dimension of the squared scanning window. In order to perform these particular estimations, we develop and test a perfect simulation algorithm. We then perform several numerical applications and compare our results with results obtained by other authors.     

一种基于二部图的试题知识点标注方法

针对在线教育中试题知识点自动标注问题,本文提出了一种基于二部图的试题知识点标注方法。首先,为了合理划分知识点粒度,本文构建了知识点知识图谱来融合知识点;其次,基于教材等语料抽取知识点与特征词二部图和试题与特征词二部图,并利用TF-IDF公式计算知识点与特征词、试题与特征词之间的边权,以构建试题-知识点二部图模型;再次,提出词频加权的相似性度量方法计算试题和知识点之间的相似度,将相似度最高的知识点作为试题知识点标签。最后,以某在线教育平台提供的高中历史试题为实验数据集进行数值实验,实验结果表明该方法的效果显著优于朴素贝叶斯、K最近邻、随机森林以及支持向量机。     

ARIES: A Visual Path in the Investigation of Statistical Data

Abstract

The massive flood of numbers in ongoing large-scale periodic economic and social surveys commonly leaves little time for anything but a cursory examination of the quality of the data, and few techniques exist for giving an overview of data activity. At the U.S. Bureau of Labor Statistics, a graphical and query-based solution to these problems has recently been adopted for data review in the Current Employment Statistics survey. Chief among the motivations for creating the new system were: (1) Reduce or eliminate the arduous paper review of thousands of sample reports by review analysts; (2) allow the review analysts a more global view of sample activity and at the same time make outlier detection less of a strain; and (3) present global views of estimates over time and among groups of subestimates. The specific graphics approaches used in the new system were designed to quickly portray both time series and cross-sectional aspects of the data, as these are both critical elements in the review process. The described system allows the data analysts to track down suspicious sample members by first graphically pinpointing questionable estimates, and then pinpointing questionable sample data used to produce those estimates. Query methods are used for cross-checking relationships among different sample data elements. Although designed for outlier detection and estimation, the data-representation methods employed in the system have opened up new possibilities for further statistical and economic uses of the data. The authors were torn between the desire for a completely automatic system of data review and the practical demands of an actual survey operating under imperfect conditions, and thus viewed the new system as an evolutionary advance, not as an ideal final solution. Possibilities opened up by the new system prompted some further thinking on finding an ideal state.     

A Note on Observables for Counting Trails and Paths in Graphs

We point out that the total number of trails and the total number of paths of given length, between two vertices of a simple undirected graph, are obtained as expectation values of specifically engineered quantum mechanical observables. Such observables are contextual with some background independent theories of gravity and emergent geometry. Thus, we point out yet another situation in which the mathematical formalism of a physical theory has some computational aspects involving intractable problems.     

基于理想关联度的不确定多属性决策方法

针对只有部分属性权重信息且属性值以区间数形式给出的不确定多属性决策问题,提出了一种逼近理想关联度的决策分析方法。首先改进了文[4]给出的区间数决策矩阵的规范化方法;然后提出了利用期望-方差区间数排序方法求解理想最优方案;最后依据关联系数矩阵给出了属性权重信息不完全的区间数多属性决策问题的求解方法,其核心是求解线型规划得到属性权重,进而根据各个方案与理想最优方案的综合关联度大小进行排序。特别地,给出了属性权重完全未知的简洁方法,文后的实例验证了方法的可行性和有效性。     

对DEA中有效单元排序的一种新方法

文章对数据包络分析(DEA)的强有效性问题提出了一种新的研究方法.利用有效值和负有效值来构造复合输入和输出这种方法可以实现有效决策单元的完全排序.文章还给出了新方法中模型的一些性质.最后,用两个例子来检验此方法并和其他模型的计算结果进行了比较.     

一种基于Dijkstra算法的机器人避障问题路径规划

移动机器人的避障问题是移动机器人控制领域的研究热点.针对给定的移动机器人避障问题,探讨了最短路径及最短时间路径的路径规划问题.对于最短路径问题,建立了简化的路径网格模型,将其抽象为由节点及边构成的两维图,再使用经典的Dijkstra算法获得可行的最短路径.对于最短时间路径问题,通过分析移动机器人弯道运行的速度曲线,基于几何方法得出了移动时间与过渡圆弧圆心之间严格的数学关系,此后借助MATLAB优化函数获得最佳的移动路径.算法可为类似机器人避障问题的解决提供借鉴.     

一种快速计算Zpk上码字深度的算法

开始定义了环Zpk上码字的深度,给出了一种快速计算环Zpk上码字的深度的算法.     

A competitive algorithm in searching for many edges in a hypergraph

We give a competitive algorithm to identify all d defective edges in a hypergraph with d unknown. Damaschke did the d=1 case for 2-graphs, Triesch extended the d=1 case to r-graphs, and Johann did the general d case for 2-graphs. So ours is the first attempt to solve the searching for defective edges problem in its full generality. Further, all the above three papers assumed d known. We give a competitive algorithm where d is unknown.     

A dual ascent approach for steiner tree problems on a directed graph

The Steiner tree problem on a directed graph (STDG) is to find a directed subtree that connects a root node to every node in a designated node setV. We give a dual ascent procedure for obtaining lower bounds to the optimal solution value. The ascent information is also used in a heuristic procedure for obtaining feasible solutions to the STDG. Computational results indicate that the two procedures are very effective in solving a class of STDG's containing up to 60 nodes and 240 directed/120 undirected arcs. The directed spanning tree and uncapacitated plant location problems are special cases of the STDG. Using these relationships, we show that our ascent procedure can be viewed as a generalization ofboth the Chu-Liu-Edmonds directed spanning tree algorithm and the Bilde-Krarup-Erlenkotter ascent algorithm for the plant location problem. The former comparison yields a dual ascent interpretation of the steps of the directed spanning tree algorithm.     

A note on testing for constant hazard against a change-point alternative

Summary The problem of testing for constant hazard against a change-point alternative is considered. It is shown that this problem is related to another one in quality control. Based on this relationship, a test is proposed. The main advantages of this test are its computational simplicity and the ready availability of small and large sample distribution theory.     

A note on the Estrada-Hatano communicability algorithm for detecting community structure in complex networks

Recently Estrada and Hatano proposed an algorithm for the detection of community structure in complex networks using the concept of network communicability. Here we amend this algorithm by eliminating the subjectivity of choosing degree of overlapping and including an additional check of the fitness of detected communities. We show that this amendment can detect some communities which remain undetected by Estrada and Hatano’s algorithm. For instance, let G(p, q) be a graph obtained from two cliques, K_p and K_q(p ? q ? 3), joined by a single edge. It is apparent that this graph contains two communities, namely the two cliques. However, Estrada and Hatano’s algorithm detects only K_q as a community when p is sufficiently larger than q. Our algorithm correctly detects both communities. Also, our method also finds the correct community structure in one of the classic benchmark networks, the Zachary karate club.