Is more always better? Measuring the quality of ranking data through information entropy

As a classic position-based approach, Borda’s method is a conceptually simple and highly influential rank aggregation method (de Borda, 1781; Neveling & Rothe, 2021). Given m rankings R₁, R₂, …, R_m, for each object o_j∈ R_j, this method first assigns a score B_i(o_j) to object o_j based on the number of objects ranked below it. Then, the Borda count for object o_j is the total score of m rankings, denoted as ∑i=1mBi(oj)\sum\limits_{i = 1}^m {{B_i}} \left( {{o_j}} \right) Finally, the objects are ranked in descending order of their Borda counts to produce an aggregated ranking.

Dowdall method is another typical position-based rank aggregation method and can be regarded as a variant of the BM (Reilly, 2002). Given m rankings R₁, R₂, …, R_m, for each object o_j ∈R_j this method first assigns a score D_i(o_j) to object o_j, which is defined as the reciprocal of the rank assigned to it in R_i. Then, the total score for object o_j is given by the sum across all m rankings, denoted as ∑i=1mDi(oj)\sum\nolimits_{i = 1}^m {{D_i}\left( {{o_j}} \right)} . As a result, an aggregated ranking of objects can be generated by sorting the objects in descending order of their total scores.

A variant of Borda’s method uses extension sets to manage unobserved information, specifically by accounting for the possible ranking positions of objects absent from the given rankings to address the uncertainty associated with these objects (Aledo et al., 2016). Given a partial ranking R_i, the method defines a permutation σ, which is consistent with R_i if one of the two following conditions holds for all objects o_s, o_t ranked in R_i:

• o_s and o_t share the same rank in R_i,

• If o_s is ranked above o_t in R_i, then o_s must be ranked above o_t in σ, and vice versa.

Moreover, σ will be said to be restricted consistent with R_i if the following two conditions hold for all objects o_s, o_t in R_i:

• σ is consistent with R_i,

• ∀o_k non-ranked in R_i, o_k cannot be ranked between o_s and o_t which share the same ranking position in R_i.

Therefore, the extension set of a partial ranking R_i is denoted by E^r(R_i)={σ|σ is restricted consistent with R_i}.

Next, the restricted precedence extension value Vstr(Ri)V_{st}^r\left( {{R_i}} \right) of R_i between o_s and o_t is defined as follows: 2Vstr(Ri)=1| Er(Ri) |∑σ∈Er(Ri)1(osis ranked aboveot)V_{st}^r\left( {{R_i}} \right) = {1 \over {\left| {{E^r}\left( {{R_i}} \right)} \right|}}\sum\limits_{\sigma \in {E^r}\left( {{R_i}} \right)} 1 \left( {{o_s}{\rm{ }}is ranked above{\rm{ }}{o_t}} \right)

Then, given m rankings R₁, R₂, …, R_m, the research define the restrict precedence extension matrix by M^r = [M_st]_s,t=1:n by 3Mstr=1m∑i=1mVstr(Ri)M_{st}^r = {1 \over m}\sum\limits_{i = 1}^m {V_{st}^r} \left( {{R_i}} \right)

Finally, Borda’s method is used to obtain a consensus ranking by sorting the column sums of M^r in ascendingorder.

The competition graph method is an efficient approach for aggregating high-dimensional and partial rankings (Xiao et al., 2021). Given m rankings R₁, R₂, …, R_m with respect to n objects, this method first represents objects as nodes and employs directed weighted edges to represent pairwise comparison relationships between objects from the given rankings. Specifically, for a pair of nodes, the weight of an outgoing edge represents the number of rankings in which one node ranks above the other, while the weight of an incoming edge reflects the reverse. Based on this, the total weights of outgoing and incoming edges for each node are defined as its out-degree di+d_i^ + and indegree di−d_i^ - , respectively. Then, the “ratio of out- and in-degrees” (ROID) of each object is calculated as follows: 4si=di++1di−+1{s_i} = {{d_i^ + + 1} \over {d_i^ - + 1}}

Finally, the objects are ranked in descending order of ROIDs to obtain an aggregated ranking.

As a typical optimization method, the minimum violations ranking method aims to find a consensus ranking that minimizes violations of input rankings (Ali et al., 1986; Chartier et al., 2010; Pedings et al., 2012). To solve this problem, researchers often formulate it as a binary integer linear program (BILP). Specifically, Given m rankings R₁, R₂, …, R_m of n objects, this method first defines the decision variable x_ij and the constant c_ij. Let 5xij={ 1,if objectoiis ranked aboveoj0,otherwise,{x_{ij}} = \left\{ {\matrix{ {1,} & {{\rm{ }}if object{\rm{ }}{o_i}{\rm{ }}is ranked above{\rm{ }}{o_j}} \cr {0,} & {{\rm{ }}otherwise,} \cr } } \right. and 6cij=| { Rk:0<rki<rkj } |−| { Rk:0<rkj<rki } |{c_{ij}} = \left| {\left\{ {{R_k}:0 < {r_{ki}} < {r_{kj}}} \right\}} \right| - \left| {\left\{ {{R_k}:0 < {r_{kj}} < {r_{ki}}} \right\}} \right| where R_k ∈ R. Note that the optimal value of the decision variable x_ij corresponds to the aggregated ranking, while the constants c_ij are related to the input rankings. Then, the MVR problem can be presented as the following BILP formulation. max∑i=1n∑j=1ncijxijmax\sum\limits_{i = 1}^n {\sum\limits_{j = 1}^n {{c_{ij}}} } {x_{ij}}

7s.t.{ xij+xji=1for alli≠jxij+xjk+xki≤2for alli≠j≠kxij∈{0,1}s.t.{\rm{ }}\left\{ {\matrix{ {{x_{ij}} + {x_{ji}} = 1\quad {\rm{ }}for all{\rm{ }}i \ne j} \cr {{x_{ij}} + {x_{jk}} + {x_{ki}} \le 2\quad {\rm{ }}for all{\rm{ }}i \ne j \ne k} \cr {{x_{ij}} \in \{ 0,1\} } \cr } } \right.

Finally, a “branch and bound” algorithm based on linear programming (LP) is commonly used to solve BILP problems to obtain a minimum violation consensus ranking.

Kendall’s tau measures the correlation between two rankings by evaluating the consistency of pairwise ordering. Mathematically, given two complete rankings R₁ and R₂ of length n, Kendall’s tau is defined as: 8τ=2(Nc−Nd)n(n−1)\tau = {{2\left( {{N_c} - {N_d}} \right)} \over {n(n - 1)}} in which N_c and N_d respectively denote the number of object pairs whose orders are concordant and discordant in R₁ and R₂. It is obvious that the more consistent the two rankings are, the larger the value of Kendall’s tau. There are two extreme cases: τ = -1 indicates that the two lists are completely opposite, while τ = 1 signifies complete concordance.

The above definition has a flaw when dealing with rankings that include ties. Therefore, the researcher extended the Kendall’s tau to a distance metric applicable to rankings with ties in subsequent studies (Kendall, 1945). In cases where one or both rankings contain ties, Kendall’s tau-b is defined as: 9τb=Nc−Nd(Nc+Nd+Tx)(Nc+Nd+Ty){\tau _b} = {{{N_c} - {N_d}} \over {\sqrt {\left( {{N_c} + {N_d} + {T_x}} \right)\left( {{N_c} + {N_d} + {T_y}} \right)} }} where T_x and T_y represent the numbers of tied pairs in R₁ and R₂, respectively.

Spearman’s rho quantifies the correlation between two rankings by assessing how consistently the ranks of each object change across the two lists. Mathematically, given two complete rankings R₁ and R₂ of length n, Spearman’s rho is defined as: 10ρ=1−6∑i=1n(r1i−r2i)2n(n2−1)\rho = 1 - {{6\sum\nolimits_{i = 1}^n {{{\left( {{r_{1i}} - {r_{2i}}} \right)}^2}} } \over {n\left( {{n^2} - 1} \right)}} where r_1i and r_2i are the ranks of object o_i in R₁ and R₂, respectively.

Spearman’s rho is a simple and intuitive measure: the larger its value, the higher the correlation between the two rankings and the stronger the ranking consistency; when the two rankings are identical, ρ reaches its maximum value of 1, and when they are completely opposite, ρ reaches its minimum value of -1.

For ranking data, we aimed for each object to be compared with as many other objects as possible. In the corresponding ranking network, the degree of a node reflects the number of other objects with which it has comparisons. When the degree distribution is uniform, most objects have comparisons with a similar number of other objects, indicating that the ranking information is widely covered and evenly distributed. Conversely, when the degree distribution is highly concentrated, most comparisons involve only a few objects, suggesting that the ranking information is unevenly distributed. Degree entropy can be used to quantify the uniformity of this distribution: higher degree entropy indicates a more balanced distribution of ranking information, while lower degree entropy indicates that the information is concentrated on a small subset of objects.

For a network containing N nodes, let k_i denote the degree of the i-th node. Then the relative proportion of each node’s degree in the network is defined as: 11pi=ki∑j=1Nkj{p_i} = {{{k_i}} \over {\sum\nolimits_{j = 1}^N {{k_j}} }}

Building on this, the degree entropy H_d can be computed using the Shannon entropy formula: 12Hd=−∑i=1Npilogpi{H_d} = - \sum\limits_{i = 1}^N {{p_i}} log{p_i}

We used degree entropy to quantitatively assess the quality of the two sets of ranking data mentioned in the above section, with the results shown in Figure 3. It is clearly observed that when the overall distribution of ranking information is relatively concentrated, the coverage of comparisons among nodes is limited, resulting in lower degree entropy values. Conversely, when the ranking information is more evenly distributed, the degree entropy values are higher. This trend indicates that lower degree entropy corresponds to poorer data quality, as the information is concentrated among a few objects and cannot comprehensively reflect the relative ordering of all objects. In contrast, higher degree entropy indicates broader coverage and a more balanced distribution of information, reflecting higher data quality.

Figure 3.

A measurement of input ranking information quality based on degree entropy (H_d): the more evenly the information is distributed, the higher H_d; the more concentrated the information, the lower H_d.

The degree entropy method primarily examines the degree of network nodes to capture the global distribution characteristics of information. However, as this method fails to reflect the differences in edge weights, another approach is introduced, shifting the focus to the weights of network edges. Specifically, for an undirected weighted network derived from rankings, if the input ranking information is concentrated on a few objects, the edge weights between the corresponding nodes will be relatively large, resulting in an uneven distribution of edge weights across the network. Therefore, we can use edge weight entropy to quantify this unevenness, thereby reflecting the quality of the input ranking data.

For m input rankings, since the comparison information between any two objects o_i and o_j can appear at most once in each ranking, the corresponding edge weight w_ij takes values ranging from 0 to m. Therefore, the probability p_ij that a ranking contains the comparison information between o_i and o_j is given by: 13pij=wijm{p_{ij}} = {{{w_{ij}}} \over m}

Then, we can calculate the edge-weighted entropy based on the probability corresponding to the edge weight between each pair of nodes in the network, thereby obtaining a quantitative measure of the information distribution recorded in the m rankings. The edge-weighted entropy H_w is defined as: 14Hw=−∑(i,j)∈Epijlogpij{H_w} = - \sum\limits_{(i,j) \in E} {{p_{ij}}} log{p_{ij}}

In Figure 4, we calculated the H_w of input ranking information with different distribution characteristics based on the aforementioned example. The results similarly show that as the ranking information becomes more concentrated, the accuracy of the aggregated results decreases, and the H_w correspondingly declines, thereby reflecting lower data quality.

Figure 4.

A measurement of input ranking information quality based on edge-weighted entropy (Hw): the more evenly the information is distributed, the higher H_w; the more concentrated the information, the lower H_w.

We downloaded a dataset from the website http://www.dublincountyreturningofficer.com, containing the complete voting records of two independent elections held in Dublin, covering the northern and western areas of the Irish capital, as well as Meath County. In our experiments, we selected the voting dataset ED-00001-00000002. soi from western Dublin for empirical analysis. This dataset contains 29,988 incomplete rankings of varying lengths for nine candidates. Upon detailed examination of the original data, we found that many rankings included only a single candidate. Such rankings are essentially meaningless for ranking aggregation, as they provide no information about comparisons or outcomes between candidates. Therefore, we removed these single-item rankings. After this preprocessing, the dataset contained 28,245 candidate rankings.

We selected a course evaluation dataset from AGH University of Science and Technology in Krakow, obtained from PrefLib: A Library for Preferences, which records students’ course preferences. In this study, we used the dataset ED-00009-00000001.soc for empirical analysis. The dataset contains 146 course rankings of length 9, all of which are complete rankings. Since our experiments required incomplete rankings, we randomly removed 0 to 7 items from each ranking to create partial rankings.

The Mallows model is a distance-based conditional model over rankings, applicable to a wide range of tasks due to its compatibility with various ranking distance metrics (Mallows, 1957; Qin et al., 2010). Given a distance d over rankings, the model can generate a ranking R_i based on: 15pR0,θ(Ri)=1ϕ(θ)e−θd(Ri,R0){p_{{R_0},\theta }}\left( {{R_i}} \right) = {1 \over {\phi (\theta )}}{e^{ - \theta d\left( {{R_i},{R_0}} \right)}} where R₀ and θ are the parameters of the model, representing the location and the dispersion parameters, and ϕ(θ)=∑Rie−θd(Ri,R0)\phi (\theta ) = \sum\limits_{{R_i}} {{e^{ - \theta d\left( {{R_i},{R_0}} \right)}}} is a normalization constant. Specifically, we chose the Kendall tau distance as the metric for measuring the distance between rankings.

In the Mallows model, the parameter θ (θ ≥ 0) controls the concentration of the distribution of rankings around the central ranking R₀. When θ = 0, the distribution is uniform; as θ increases, the distribution becomes increasingly peaked.

To generate input ranking information with varying distribution characteristics, we introduce a distribution parameter α, which takes values in [0, ∞]. Each object is assigned an index from 1 to n, and the probability that the j-th object is selected by a voter is proportional to j^−α. After generating m complete rankings, we randomly select L₀ objects from each complete ranking according to this probability distribution, and reorder them according to their positions in the original ranking to construct m partial rankings. By adjusting the value of α, we can control the frequency with which each object appears in the partial rankings. Specifically, when α = 0, all objects have an equal probability of being selected, resulting in ranking information that is evenly distributed across all objects. As α increases, the probability of selecting certain objects rises significantly, leading to a more skewed distribution of the ranking data, where a few objects are ranked frequently while others appear only rarely.

The Plackett-Luce model is another classic probabilistic model for rankings (Luce, 1959; Plackett, 1975). Given n objects, this model first assigns a parameter s_oi to item o_j, which can be interpreted as the importance of item o_j. Then, a ranking R_k=[r_k1, r_k2,…, r_kn] is given as 16ps(Rk)=∏i=1nSorki∑j=1nSorkj{p_s}\left( {{R_k}} \right) = \prod\limits_{i = 1}^n {{{{S_{{o_{{r_{ki}}}}}}} \over {\sum\nolimits_{j = 1}^n {{S_{{o_{{r_{kj}}}}}}} }}} where s_orki <0, items with larger values of s_orki are more likely to appear earlier in the ranking.

The consensus in this model becomes stronger as the s_oi values decrease more rapidly (Ali & Meilă, 2012). In our experiments we assign s_oi to each object using an exponential decay form defined as: 17soi=smax×ri−1{s_{{o_i}}} = {s_{max}} \times {r^{i - 1}} where s_max is the maximum importance value, r ∈ (0,1) is the decay ratio.

We adopted the same approach as in the Mallows model to obtain ranking information with varying distribution characteristics. By introducing the distribution parameter α, we define the probability distribution for selecting objects by each voter. After generating m complete rankings, we randomly select L₀ objects from each ranking and reorder them based on their positions in the original ranking to construct partial rankings.

Xiao et al. (2017) proposed a ranking data generation method based on the inherent ability values of objects. The model first assume that each object o_j has an inherent ability ω_j, which follows a uniform distribution over [0,1]. Let R₀=[r₀₁, r₀₂,…, r_0n] be the ground truth ranking of these objects, and let r_i be the true ranking position of object o_j based on ω_j. Intuitively, a greater ω_j corresponds to a higher ranking position for o_j.

Then, this model introduces the displayed inherent ability ω˜ij{{\tilde \omega }_{ij}} to represent the estimate of ω_j by voter v_i. Since voter v_i may not accurately estimate ω_j of object o_j for various reasons, the model assumes that ω˜ij{{\tilde \omega }_{ij}} is a random variable uniformly distributed in the interval [ω_j – ω_j(1 – β_ij), ω_j + (1 – ω_j)(1 – β_ij)], where β_ij∈[0,1] denotes the strength of random error. A larger β_ij indicates voter v_i ranks object o_j more accurately based on ω_j. Thus, a ranking R_i = [r_i1, r_i2,…, r_in] is generated by voter v_i based on the estimated values ω˜ij{{\tilde \omega }_{ij}} of each object o_j. In this study, we assume that all voters have the same level of estimation accuracy β_ij meaning that β_ij=β for all i ∈ [1, m] and j∈ [1, n]. Moreover, we assume that all rankings have the same length, that is, L_i = L₀ ∈ (0, n], where i = 1,2,…, m.

Finally, we also introduce the distribution parameter α to control the distribution characteristics of the generated ranking information. Unlike the previous two models, this model allows us to generate partial rankings directly based on the specified probability distribution for selecting objects, without the need to first generate complete rankings.

To comprehensively analyze the advantages and limitations of different methods, we employed four approaches, Kendall’s tau, Spearman’s rho, degree entropy, and edge-weighted entropy, to assess the quality of data generated by three ranking data generation models with different distribution characteristics. Since the generated rankings are all incomplete, when calculating Kendall’s tau or Spearman’s rho for any pair of rankings, we consider only their common elements and finally take the average of all computed values to obtain the correlation coefficient for the dataset. The experimental results are presented in Tables 2, 3, 4, and 5, with the parameter settings as follows: n = 50, m = 1,000, θ = 0.1, S_max = 100, r =0.9, β =0.8, and L₀ = 10.

Subsequently, we aggregated the generated ranking data using five rank aggregation methods and computed the Kendall’s tau-b between the aggregated rankings and the ground-truth rankings, with the results shown in Figure 7. It can be seen that as α increases, the consistency between the aggregated results and the ground-truth rankings for the data generated by the three ranking data generation models under the five aggregation methods gradually decreases, indicating that data quality declines as the input ranking information becomes more unevenly distributed among the objects. Therefore, the effectiveness of the four data quality measures can be evaluated by examining their measurement results on the data under different values of α.

Figure 7.

The Kendall’s tau-b (τ_b) under different distribution parameters (α), where n = 50, m = 1,000, and L₀ = 10. The results are averaged over 100 independent trials.

For the two classical ranking consistency measures, Tables 2 and 3 show that their results fluctuate non-monotonically as α increases, indicating that these methods cannot effectively capture the changes in data quality caused by variations in the distribution characteristics of the ranking data. For degree entropy, as shown in Table 4, when α increases slightly, its value changes little; as α increases further and the unevenness of the data distribution becomes more pronounced, the degree entropy decreases steadily, indicating that it can reflect the quality differences caused by variations in the distribution characteristics of the ranking data, particularly when the data distribution is highly uneven. Finally, as shown in Table 5, edge-weighted entropy decreases gradually as α increases; compared to degree entropy, it is more sensitive to changes in α and can more effectively reflect the quality differences caused by variations in the distribution characteristics of the ranking data.

We further conducted experiments to evaluate the performance of the two entropy-based methods on datasets of different scales. Specifically, using three data generation models, we generated varying numbers of rankings under four conditions m = 50, m = 500, m = 5,000 and m = 50,000. The quality of each dataset was then assessed using degree entropy and edge-weighted entropy. The experimental results are shown in Figure 8 and Figure 9, where n=50, θ=0.1, S_max = 100, r = 0.9, β = 0.8, and L₀ = 10.

Figure 8.

Degree entropy (H_d) under different distribution parameters (α) and numbers of rankings (m), where n = 50 and L₀ = 10. The results are averaged over 100 independent trials.

As shown in Figure 8, for degree entropy, when the dataset is relatively small (i.e. m=50), degree entropy gradually decreases as α increases. However, as the dataset size grows, the change of degree entropy with increasing α initially remains stable and then gradually declines, and the initial stable phase becomes more pronounced with larger dataset sizes. This indicates that when the dataset is large and the unevenness of the data distribution is relatively low, degree entropy has limited capability to effectively measure data quality.

For edge-weighted entropy, as shown in Figure 9, it exhibits a decreasing trend with increasing α across datasets of all sizes. This indicates that edge-weighted entropy can effectively capture variations in data distribution, and its applicability is broader than that of degree entropy regardless of dataset size.

Figure 9.

Edge-weighted entropy (H_w) under different distribution parameters (α) and numbers of rankings (m), where n=50 and L₀=10. The results are averaged over 100 independent trials.