A unified network performance measure with importance identification and the ranking of network components

In this paper, we propose the first network performance measure that can be used to assess the efficiency of a network in the case of either fixed or elastic demands. Such a measure is needed for many different applications since only when the performance of a network can be quantifiably measured can the network be appropriately managed. Moreover, as we demonstrate, the proposed performance measure, which captures flow information and behavior, allows one to determine the criticality of various nodes (as well as links) through the identification of their importance and ranking. We present specific networks for which the performance/efficiency is computed along with the importance rankings of the nodes and links. The new measure can be applied to transportation networks, supply chains, financial networks, electric power generation and distribution networks as well as to the Internet and can be used to assess the vulnerability of a network to disruptions.     

A combinatorial ranking problem

An algorithm is presented for finding annth-best spanning tree of an edge-weighted graphG. In sharp contrast to related ranking algorithms, the number of steps is a linear function of the parametern. The results apply as well to ranking the bases of an abstract matroid.     

Inversions in ranking data

In this note we prove a conjecture of P. McCullagh that inversions provide a basis for subset effects in ranking data.     

Edge ranking of weighted trees

In this paper we consider the edge ranking problem of weighted trees. We prove that a special instance of this problem, namely edge ranking of multitrees is NP-hard already for multitrees with diameter at most 10. Note that the same problem but for trees is linearly solvable. We give an O(logn)-approximation polynomial time algorithm for edge ranking of weighted trees.     

Robust ranking and portfolio optimization

The portfolio optimization problem has attracted researchers from many disciplines to resolve the issue of poor out-of-sample performance due to estimation errors in the expected returns. A practical method for portfolio construction is to use assets’ ordering information, expressed in the form of preferences over the stocks, instead of the exact expected returns. Due to the fact that the ranking itself is often described with uncertainty, we introduce a generic robust ranking model and apply it to portfolio optimization. In this problem, there are n objects whose ranking is in a discrete uncertainty set. We want to find a weight vector that maximizes some generic objective function for the worst realization of the ranking. This robust ranking problem is a mixed integer minimax problem and is very difficult to solve in general. To solve this robust ranking problem, we apply the constraint generation method, where constraints are efficiently generated by solving a network flow problem. For empirical tests, we use post-earnings-announcement drifts to obtain ranking uncertainty sets for the stocks in the DJIA index. We demonstrate that our robust portfolios produce smaller risk compared to their non-robust counterparts.     

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.     

One-dimensional identification problem and ranking parameters

The problem of identifying points of two sets in ImuRⁿ{mathop{{rm I}mskip-2.0mu{rm R}}^{n}} is considered. This problem is of interest by itself and has numerous practical applications. One of such applications—namely, to the ranking of parameters—is also mentioned in the paper. Two identification procedures are discussed: by means of a linear identifier (the separation method) and by means of isolation of one of the sets by an interval.     

Preference ranking of discrete multiattribute instances

This paper presents a procedure for preference ranking of discrete multiattribute instances based on the observations that (1) a difficult question could be answered in terms of answers to a sequence of easier ones, (2) in general, the decision maker's preferences can easily be expressed only relative to pairs of instances that differ over one attribute, and (3) the decision maker is able and willing to express his uncertainty regarding a quantity via a subjective probability distribution. The procedure is illustrated through a hypothetical situation.     

Weighted distance-based trees for ranking data

Advances in Data Analysis and Classification - Within the framework of preference rankings, the interest can lie in finding which predictors and which interactions are able to explain the observed...     

On correct selection for a ranking problem

Givenk populations which belong to the exponential class, and having specified two positive constants (δ ^*,P ^*), an experimenter wishes to selectt populations which (a) exclude all those populations with a parameter value not greater than thetth largest parameter value minusδ ^*, and (b) include all those populations with a parameter value not smaller than the (t+1)th largest parameter value plusδ ^*. This paper shows that the probability of successfully making such a selection, called aδ ^*-correct selection, is at leastP ^* if the basic sequential procedure,P _B ^* , of Bechhofer, et al. [3] is used. This result includes the corresponding old result of their book (p. 129) as a particular case.     

Tests of perfect judgment ranking using pseudo-samples

Ranked set sampling (RSS) is a sampling approach that can produce improved statistical inference when the ranking process is perfect. While some inferential RSS methods are robust to imperfect rankings, other methods may fail entirely or provide less efficiency. We develop a nonparametric procedure to assess whether the rankings of a given RSS are perfect. We generate pseudo-samples with a known ranking and use them to compare with the ranking of the given RSS sample. This is a general approach that can accommodate any type of raking, including perfect ranking. To generate pseudo-samples, we consider the given sample as the population and generate a perfect RSS. The test statistics can easily be implemented for balanced and unbalanced RSS. The proposed tests are compared using Monte Carlo simulation under different distributions and applied to a real data set.     

Continuous ranking of zeros of special functions

We reexamine and continue the work of J. Vosmansky [J. Vosmanský, Zeros of solutions of linear differential equations as continuous functions of the parameter k, in: J. Wiener, J.K. Hale (Eds.), Partial Differential Equations, Proceedings of Conference, Edinburg, TX, 1991, in: Pitman Res. Notes Math. Ser., vol. 273, 1992, pp. 253-257] on the concept of continuous ranking of zeros of certain special functions from the point of view of the transformation theory of second-order linear differential equations. This leads to results on higher monotonicity of such zeros with respect to the rank and to the evaluation of some definite integrals. The applications are to Airy, Bessel and Hermite functions.     

Decision theory and strict ranking of probabilities

This paper is concerned with the derivation of guides to decision making in a set of circumstances intermediate between the classic extremes of pure risk and pure uncertainty. It is assumed that the decision maker can specify a subjective strict ranking of the probabilities of states of nature, in which case, given knowledge of the payoffs of a strategy, it is possible to find in a straightforward fashion, maximum and minimum expected payoffs for the strategy. If the information contained in the strict ranking is available to the decision maker, then to fail to take it into account must adversely affect the quality of decision making. The paper discusses both the interpretation and the possible practical uses of extreme expected values in decision making and includes a numerical example, based on an investment decision problem, to demonstrate the ease of use of the results obtained.