Math: pyhasse.lpom

LPOM stands for Local Partial Order Model.

LPOM0 and LPOMext are approximations to calculate the average height, hav, of partially ordered sets (posets).

Background: „Average height as a ranking index“

The average height of an element x of a partially ordered set is the mean of all heights, element x takes within the set of linear extension. A linear extension is a linear order, which preserves all order relations of a poset. Let h(x,le(i)) the height of an element x in the ith linear extension, le(i), and LT the number of all linear extensions of a poset, then:

(1)

The number of LT can be very high. Therefore a direct evaluation of equation (1) is in most cases impossible. This is the reason why approximations are needed. One of the most important approximation is that of Bubley, Dyer (1999), which is a Markov chain path coupling technique based on the method of Karzanov and Khachiyan.

Although the method of Bubley-Dyer is among the best approximations available, it turns out that for screening analysis another approximation might be useful. Its central point is the estimation, what height any single element of the partially ordered set could get. Because the analysis is focused on the single elements of a poset, it is called a local method. Actually in PyHasse two approximations are applied: LPOM0 and LPOMext. LPOM0 is based on the check of the principal downset, generated by x and the set of elements incomparable with x. LPOMext is a refinement of LPOM0. For details, see Bruggemann R., et al.

References:

Bruggemann, R. and L. Carlsen. 2011. An Improved Estimation of Averaged Ranks of Partial Orders. MATCH Comm.Math.Comput.Chem. 65:383-414.

Brüggemann, R. and P. Annoni. 2014. Average heights in Partially Ordered Sets. MATCH Commun.Math.Comput.Chem. 71:101-126.

Bruggemann, R., P. B. Sørensen, D. Lerche, and L. Carlsen. 2004. Estimation of Averaged Ranks by a Local Partial Order Model. J.Chem.Inf.Comp.Sc. 44:618-625.

Bruggemann, R. and G. P. Patil. 2010. Multicriteria prioritization and partial order in environmental sciences. Environ.and Ecological Statistics 17:383-410.

Bruggemann, R. and G. P. Patil. 2011. Ranking and Prioritization for Multi-indicator Systems - Introduction to Partial Order Applications. Springer, New York.

Bubley, R. and M. Dyer. 1999. Faster random generation of linear extensions. Discr.Math. 201:81-88.