.. _library_rank_centrality:

`rank_centrality`

Rank Centrality pairwise preference ranker. It uses the Rank Centrality transition rule where each observed opponent contributes an outgoing transition proportional to the empirical probability of beating the current item, scaled by the maximum comparison degree, and estimates the stationary distribution using deterministic power iteration.

The library implements the ranker_protocol defined in the ranking_protocols library. It provides predicates for learning a ranker from pairwise preferences, using it to order candidate items, and exporting it as a list of predicate clauses or to a file.

Datasets are represented as objects implementing the pairwise_ranking_dataset_protocol protocol from the ranking_protocols library. See the test_datasets directory for examples. The training dataset must declare each ranked item once, enumerate positive-weight pairwise preferences between distinct declared items, induce a connected undirected comparison graph, and induce a strongly connected directed transition graph so that the learned stationary distribution is unique.

API documentation

Open the `../../apis/library_index.html#rank_centrality <../../apis/library_index.html#rank_centrality>`__ link in a web browser.

Loading

To load this library, load the loader.lgt file:

| ?- logtalk_load(rank_centrality(loader)).

Testing

To test this library predicates, load the tester.lgt file:

| ?- logtalk_load(rank_centrality(tester)).

Features

Pairwise Preference Learning: Learns one stationary probability score per item from weighted head-to-head outcomes.
Original Rank Centrality Transition Rule: Builds the Markov chain from empirical pairwise win probabilities scaled by the maximum comparison degree, then estimates the stationary distribution by deterministic power iteration.
Deterministic Ranking: Orders candidate items by learned stationary probability with deterministic tie-breaking.
Strict Dataset Validation: Rejects duplicate items, undeclared items, self-preferences, non-positive weights, disconnected undirected comparison graphs, and pairwise datasets whose directed transition graph is not strongly connected.
Training Diagnostics: Learned rankers include convergence, iteration, maximum-degree, and dataset summary metadata that can be accessed using the diagnostics/2 predicate.
Ranker Export: Learned rankers can be exported as self-contained terms.
Sparse Transition Processing: Training aggregates observed pairwise comparisons into sparse incoming transition lists so each power-iteration step scales with observed matchups instead of a dense item cross-product.

Dataset requirements

This implementation requires more than undirected connectedness. In order to guarantee a unique stationary distribution, the directed transition graph induced by the aggregated pairwise outcomes must be strongly connected. Datasets that create one-way dominance sinks or other disconnected directed transition components are rejected instead of producing ambiguous stationary scores.

Usage

Learning a ranker ~~~~~~~~~~~~~~~~~

% Learn from a pairwise ranking dataset object | ?- rank_centrality::learn(my_dataset, Ranker). ...

% Learn with custom iteration and convergence options | ?- rank_centrality::learn(my_dataset, Ranker, [maximum_iterations(500), tolerance(1.0e-9)]). ...

Inspecting diagnostics ~~~~~~~~~~~~~~~~~~~~~~

% Inspect convergence and dataset summary metadata | ?- rank_centrality::learn(my_dataset, Ranker), rank_centrality::diagnostics(Ranker, Diagnostics). Diagnostics = [...] ...

Diagnostics syntax

The diagnostics/2 predicate returns a list of metadata terms with the form:

[ model(rank_centrality), options(Options), convergence(Status), iterations(Iterations), final_delta(FinalDelta), maximum_degree(MaximumDegree), dataset_summary(DatasetSummary) ]

Where:

model(rank_centrality) identifies the learning algorithm that produced the ranker.
options(Options) stores the effective learning options after merging the user options with the library defaults.
convergence(Status) records the training stop condition. The current values are converged and maximum_iterations_exhausted.
iterations(Iterations) stores the number of power-iteration steps that were executed.
final_delta(FinalDelta) stores the maximum absolute score update in the last iteration.
maximum_degree(MaximumDegree) stores the maximum number of observed opponents for any single item in the training dataset.
dataset_summary(DatasetSummary) stores a summary list describing the validated training dataset.
The current dataset_summary/1 payload has the form:

::

[ items(NumberOfItems), preferences(NumberOfPreferences), connected_components(NumberOfComponents), isolated_items(IsolatedItems) ]

Use the ranking_protocols diagnostic/2 and ranker_options/2 helper predicates when you only need a single metadata term or the effective options.

Ranking candidate items ~~~~~~~~~~~~~~~~~~~~~~~

::

% Rank a candidate set from most preferred to least preferred | ?- rank_centrality::learn(my_dataset, Ranker), rank_centrality::rank(Ranker, [item_a, item_b, item_c], Ranking). Ranking = [...] ...

Candidate lists must be proper lists of unique, ground items declared by the training dataset. Invalid ranker terms, duplicate candidates, and candidates containing variables are rejected with errors instead of being silently accepted.

Exporting the ranker ~~~~~~~~~~~~~~~~~~~~

Learned rankers can be exported as a list of clauses or to a file for later use.

::

% Export as predicate clauses | ?- rank_centrality::learn(my_dataset, Ranker), rank_centrality::export_to_clauses(my_dataset, Ranker, my_ranker, Clauses). Clauses = [my_ranker(rank_centrality_ranker(...))] ...

% Export to a file | ?- rank_centrality::learn(my_dataset, Ranker), rank_centrality::export_to_file(my_dataset, Ranker, my_ranker, 'ranker.pl'). ...

Options

The following options can be passed to the learn/3 predicate:

maximum_iterations(MaximumIterations): Positive integer iteration bound.
tolerance(Tolerance): Positive convergence tolerance.

Ranker representation

The learned ranker is represented by a compound term of the form:

rank_centrality_ranker(Items, Scores, Diagnostics)

Where:

Items: List of ranked items.
Scores: List of Item-Score pairs.
Diagnostics: List of metadata terms, including the effective options, convergence status, iteration count, final update delta, maximum degree, and dataset summary.
The Scores payload is expected to contain positive stationary probability values summing to 1.0. The ranker validation logic enforces this invariant when consuming serialized or exported ranker terms so that malformed payloads are rejected instead of silently accepted.

When exported using export_to_clauses/4 or export_to_file/4, this ranker term is serialized directly as the single argument of the generated predicate clause so that the exported model can be loaded and reused as-is.

References

Negahban, S., Oh, S., and Shah, D. (2012). Rank Centrality: Ranking from pairwise comparisons. Operations Research, 65(1), 266-287.