Abstract
Measuring agreement among multiple rankings is critical in fields ranging from information retrieval to group decision-making. Traditional metrics often fail to handle partial rankings, ties, or position-dependent importance. This paper introduces a novel framework that represents rankings as Directed Acyclic Graphs (DAGs). By leveraging matrix operations, the authors derive a flexible consensus measure ($\kappa$) that incorporates sensitivity weights for item positions and gaps. Experimental results on clustering validation and search engine results demonstrate the framework's efficiency and its ability to capture nuanced global agreement.
Introduction
In many real-world applications, we encounter sets of rankings from various experts or algorithms. Determining the degree of consensus among these lists is essential for evaluating performance and aggregating results. However, standard measures like Kendall’s $\tau$ or Spearman’s $\rho$ are primarily designed for pairwise comparisons of full rankings. They lack the flexibility to handle "top-k" importance—where differences at the head of a list are more significant than at the tail—and they struggle with partial rankings where items may not appear in every list.
A Graph-Based Consensus Framework
The core of the proposed method is the representation of a set of rankings as a Directed Acyclic Graph (DAG). Each item is a vertex, and a directed edge exists between two items if their relative order is consistent across the entire set.
Matrix Representation and Efficiency
The consensus is quantified by the number of common subsequences ($\kappa$) shared by the rankings. The authors represent the graph using a strictly lower triangular matrix $L$. A key contribution is the "matrix trick": the total number of common patterns $\kappa(R)$ can be computed efficiently in linear time $O(n + |E|)$ using the matrix inversion $(I - L)^{-1}$. This bypasses the need for expensive combinatorial counting and makes the approach scalable to large datasets.
Incorporating Sensitivity Weights
To address the limitations of unweighted metrics, the model introduces two weighting functions that allow for a more granular analysis of agreement:
- Position Weight ($\theta$): Penalizes items that exhibit high variance in their rank positions across different lists.
- Gap Weight ($\psi$): Penalizes pairs of items that are separated by large distances, distinguishing between "tight" consensus (items consistently adjacent) and "loose" consensus.
Experimental Evaluation
The framework was tested on two distinct datasets: clustering algorithm rankings evaluated against validation measures, and real-world search engine results from Google and Bing.
Rank Aggregation Algorithms
The authors compared two aggregation methods: a Genetic Algorithm (GA) and a Cross-Entropy (CE) approach. The consensus measure revealed that while both algorithms perform similarly, they exhibit different sensitivities to weighting parameters.
As shown in the evaluation plots, the CE approach tends to be more sensitive to position deviations, whereas the GA is more influenced by the gaps between items. This distinction allows researchers to choose an aggregation method that aligns with their specific consensus priorities.
Search Engine Consensus
In a comparison of Google and Bing search results for James Bond-related queries, the framework found that Google consistently maintained a higher consensus score. Interestingly, even when Bing shared more common links across queries, its consensus score was lower due to higher variance in the positions of those links. This demonstrates the effectiveness of the position-based weighting scheme in capturing true agreement beyond simple link counting.
Conclusion
This graph-based framework provides a scalable and flexible solution for measuring consensus in complex ranking scenarios. By reducing combinatorial counting to linear algebra, it enables the analysis of large-scale datasets with nuanced weighting. Future work will explore using this measure as an objective function for developing "elastic" rank aggregation algorithms that can automatically adapt to varying data characteristics.
Summary updated