rap_greedy_alg: Greedy Algorithm for Rank Aggregation

Description

Greedy Algorithm is a heuristic method that hunts for improved rankings by moving one object at a time (up or down). In case an object’s movement results in an improved ranking, the next object is moved with respect to this improved ranking. The process is repeated until all objects are considered once.

Usage

rap_greedy_alg(
  seed_rkg,
  input_rkgs,
  search_radius = 0,
  objNames = c(),
  wt = c()
)

Value

A list containing the consensus ranking (expressed as ordering), total Kemeny distance, and average tau correlation coefficient corresponding to the consensus ranking.

Arguments

seed_rkg: an initial ranking to begin the algorithm. The algorithm is often used in conjunction with Subiterative Convergence.
input_rkgs: a n by k matrix of k rankings of n objects, where each column is a complete ranking.
search_radius: a positive integer for the maximum change in the rank of each object. The default value of 0 considers all possible rank changes for each object. Recommended value of search radius is less than or equal to \(\min(30, \lfloor \mbox{n}/2 \rfloor)\).
objNames: a n-length vector containing object names. An optional parameter.
wt: a k-length vector containing weights for each judge or attribute. An optional parameter.

References

Badal, P. S., & Das, A. (2018). Efficient algorithms using subiterative convergence for Kemeny ranking problem. Computers & Operations Research, 98, 198-210. tools:::Rd_expr_doi("10.1016/j.cor.2018.06.007")

Examples

Run this code

## Four input rankings of five objects
input_rkgs <- matrix(c(3, 2, 5, 4, 1, 2, 3, 1, 5, 4, 5, 1, 3, 4, 2, 1, 2, 4, 5, 3),
    byrow = FALSE, ncol = 4)
mean_seed_rkg <- mean_seed(t(input_rkgs))
rap_greedy_alg(mean_seed_rkg, input_rkgs, search_radius = 0) # Determined the consensus ranking,
                                                             # total Kemeny distance, and average
                                                             # tau correlation coefficient

## Five input rankings with five objects 
## 2nd ranking == 3rd ranking, so if a third object is weighted as zero,
## we should get the same answer as the first examples
input_rkgs <- matrix(c(3, 2, 5, 4, 1, 2, 3, 1, 5, 4, 2, 3, 1, 5, 4, 5, 1, 3, 4, 2, 1, 
                       2, 4, 5, 3),byrow = FALSE, ncol = 5)
wt = c(1,1,0,1,1)
mean_seed_rkg <- mean_seed(t(input_rkgs),wt=wt)
rap_greedy_alg(mean_seed_rkg, input_rkgs, search_radius = 0,wt=wt) # Determined the
#consensus ranking,  total Kemeny distance, and average tau correlation coefficient


## Using five input rankings with five objects with prepare_data to 
## automatically prepare the weight vector
input_rkgs <- matrix(c(3, 2, 5, 4, 1, 2, 3, 1, 5, 4, 2, 3, 1, 5, 4, 5, 1, 3, 4, 2, 1, 
                       2, 4, 5, 3),byrow = FALSE, ncol = 5)
out = prepare_data(input_rkgs) 
input_rkgs = out$input_rkgs
wt = out$wt
mean_seed_rkg <- mean_seed(t(input_rkgs),wt=wt)
rap_greedy_alg(mean_seed_rkg, input_rkgs, search_radius = 0,wt=wt) # Determined the
#consensus ranking,  total Kemeny distance, and average tau correlation coefficient

## Included dataset of 15 input rankings of 50 objects
data(data50x15)
input_rkgs <- as.matrix(data50x15[, -1])
mean_seed_rkg <- mean_seed(t(input_rkgs)) # Use the mean seed ranking as the seed ranking
rap_greedy_alg(mean_seed_rkg, input_rkgs, search_radius = 1)