2.5. Markov Chains methods

The Markov Chains methods constitute a well-established family of rank aggregation methods. Originally proposed by Dwork et al., (2001), they consider an aggregate list as a system that moves from one state to another with respect to a particular criterion. Dwork et al. (2001) introduced four such methods in the following article:

• C. Dwork, R. Kumar, M. Naor, D. Sivakumar, "Rank Aggregation Methods for the Web", In Proceedings of the 10th International Conference on World Wide Web, pp. 613-622, 2001.

In addition, DeConde et al. (2006) introduced MCT, a variant that constructs the transition matrix by considering the proportion of lists which prefer an element over another.

• R.P. DeConde, S. Hawley, S. Falcon, N. Clegg, B. Knudsen, R. Etzioni, "Combining results of microarray experiments: a rank aggregation approach", Statistical Applications in Genetics and Molecular Biology, vol. 5, no. 1, 2006.

The execution of all five methods takes place by passing the appropriate arguments to the MC exposed C function of FLAGR.

Function Definitions

void MC(const char inf[], const char relf[], const int evpts, const int ram,
     const char ranstr[], const char out[], const float ergodic_number, const float delta, const int iter)

and

__declspec(dllexport) void __cdecl MC(const char inf[], const char relf[], const int evpts, const int ram,
     const char ranstr[], const char out[], const float ergodic_number, const float delta, const int iter)

Implementation Files

• MC() function: cflagr.cpp and dllflagr.cpp.
• Markov Chains implementation: src/ram/MC.cpp.

Input arguments

• const char inf[]: The path of the input file that stores the preference lists to be aggregated.
• const char relf[]: The path of the input file that stores the element relevance judgments.
• const int evpts: the elements in the aggregate list on which the evaluation measures (i.e. Precision, and nDCG) will be computed.
• const int ram: The selected (Markov Chains-based) rank aggregation method (801, 802, 803, 804, or 805 - see the aggregation_method parameter in this document for a list of possible values).
• const char ranstr[]: A string that is embedded in the names of the output files. Used when FLAGR is compiled as a shared library.
• const char out[]: The file system location where the output file with the aggregate list will be stored.
• const float ergodic_number: The ergodic number, used during the computation of the ergodic transition matrix from the normalized transition matrix.
• const float delta: unused.
• const float iter: Controls the maximum number of iterations before convergence.

Description
The input parameters are parsed and stored in a special C structure called UserParams that is defined in src/InputParams.h. Then, UserParams is passed to the execution driver and the rank aggregation process starts.