On Different Ranking Methods

Abstract

In this note we present a short overview of different ranking methods. We recall the ranking methods for directed graphs and focus on axiomatic characterizations of the ranking methods by outdegree, Copeland score, and the $\beta$-measure.

1 Related Literature on Ranking Methods

Ranking accompanies our everyday activities and is crucial in various situations, in particular, when facing competitive issues and having to choose from a set of alternatives. As a consequence, the investigation of appropriate ranking methods is particularly important. Which method should be used when one needs to rank, for instance, political candidates or parties in election, teams in sport competition, universities or institutes in excellence competition, scientific candidates for academic positions?

The literature on ranking methods and their applications is very rich and gets a lot of interest for many years; for some examples see, e.g., [16, 57, 67], for ranking scientific journals, web pages on the internet, and alternatives in social choice, respectively. There exists a vast literature on the classical problem of ranking objects, based on a binary relation between the objects (e.g., [8, 30, 49, 62]).

In this short overview, we will briefly recall some selected ranking methods. We will focus on ranking methods for directed graphs, where nodes have different interpretations, depending on the ranking subject and environment. A ranking method is then formally defined as a mapping which assigns to every directed graph a complete preorder on the set of nodes. Every node gets its ranking score, and a node is ranked higher, the higher is its score. In this stream of literature, usually axiomatic characterizations to ranking methods and ranking scores are provided.

One of the well-known ranking methods is based on Copeland score ([22]). When defining an outdegree (respectively, an indegree) of a node in a directed graph as the number of its outgoing (respectively, ingoing) arcs, the Copeland score of the node simply counts the difference between its outdegree and its indegree. In the literature, there exist several axiomatizations of the ranking by Copeland score; see e.g., [7, 41] (also [15] for a related method). Reference [62] provides an axiomatic characterization of the ranking by Copeland score on the class of tournaments, where the ranking coincides with the one by outdegree.

In order to measure domination in directed graphs, [18] characterize two relational power measures: the score measure and the $\beta$-measure; see also [42, 70], as well as [17] for the case of undirected graphs. Reference [19] characterize the ranking induced by the score measure (that they call the ranking by outdegree) for arbitrary directed graphs. The ranking induced by the $\beta$ measure (the $\beta$-ranking) is axiomatically characterized in [14]. A related idea underlies the ranking for chess players investigated earlier in [34], where defeating a strong opponent gives more points than defeating a weak one.

[21] introduce a ranking method based on the degree ratio of a node, which is its outdegree divided by its indegre, and a ranking method based on a modified degree ratio. The authors provide axiomatic characterizations of these two ranking methods as well as an alternative axiomatization of the Copeland score.

Some ranking methods have been also introduced for weighted directed graphs. The outflow as a relational power measure for weighted (and also non-weighted) directed graphs is axiomatically characterized by [18]. Also [20] deliver an axiomatic characterization of the outflow ranking method for weighted directed graphs.

There is a variety of other methods that are based on hyperlinks for ranking web pages or citations for ranking academic journals. Reference [58] presents an economic analysis of many ranking methods and the use of citations in the law. Ranking methods based on evaluations or citations consider a one-sided setting in which experts evaluate some items for ranking, and a peers’ setting when the experts coincide with the items.

The first citation index for articles published in journals is the Science Citation Index (SCI), which uses the counting method, based on counting the total number of citations received by a journal (see [35]). The Impact Factor ([36]) of an academic journal counts the average number of citations received by articles published on it; see also [37]. Reference [53] use an iteration (impact adjusted) method to examine the impact factors of economic journals.

The Markov-chain approach comes originally from [75] and [45]. Reference [57] introduce the influence measure which counts both direct and indirect citations. Google’s Page Rank ([16]) uses a similar recursive approach and is based on the invariant method. The axiomatic approach to the invariant method and several axiomatizations of eigencentrality (used in the eigenvalue centrality method) is presented, e.g., in [1, 47, 56, 69]; see also [2, 68]. [28] propose a “market” approach to ranking items in a network, e.g., ranking web pages connected by links or papers connected by citations. Their set of methods includes the eigencentrality method. Also the so-called mutual centrality method characterized in [27] is related to the eigenvalue centrality. Reference [26] introduces and axiomatically characterizes the handicap-based method, which assigns both scores to the items and weights to the experts. References [24, 25] investigates rankings in a dynamic setting.

The related contributions come also from the extremely vast literature on bibliometrics. We mention just few of them. Although the Impact Factors of journals are among the oldest bibliometric indices used for evaluating journals (see, e.g., [5, 38, 39] for surveys), many others have been introduced. The well-known h-index (the Hirsch index, [43]) widely examined from an axiomatic point of view (see e.g., [12, 54, 60, 77]) induces a ranking method that supports evaluations of researchers. [33] introduces another bibliometric index, the so-called g-index, axiomatically characterized, e.g., in [76]; see also [32, 55, 61, 78], as well as [4, 31, 44, 48] for some other bibliometric indices. Also [10] provide an axiomatic foundation of the ranking of journals based on Impact Factors and suggest alternative rankings that use some generalizations of Impact Factors.

Within this bibliometric literature, numerous works discuss in detail the importance of some properties (e.g., independence and consistency) for bibliometric rankings of authors and journals; see e.g., [9,10,11, 54, 55, 71, 74]. Some other properties might be subject to discussion, for instance, totality for ranking departments, saying that when two equal-size departments have the same citation distribution, they must be equivalent. For various works on ranking departments we also refer to, e.g., [6, 23, 29, 46, 59, 64].

An important issue in ranking is related to the fact that in some situations we are faced to compare authors, journals, departments belonging to different fields of research (e.g., [3, 63, 65, 66]). There exist several research directions on how to solve this normalization problem between different fields. One of the ideas lies on the fractional counting of citations, meaning that the value of a citation given by an article is inversely proportional to the total number of articles that it cites. Fractional counting of citations is proposed in [40, 50, 51]. [13] axiomatically characterize the ranking authors by using the fractional counting of citations. There exist also some empirical studies on this concept; see e.g., [52, 72, 73].

In the following two sections, we briefly present preliminaries and then recall several ranking methods for directed graphs that use outdegree (and indegree) of a node.

2 Notation and Basic Definitions

We introduce some basic notation and definitions, as in [19].

Directed graphs A directed graph (or digraph) is a pair (N, D), where $N =\{1, 2, \dots , n\}$ is a finite set of nodes and $D \subset N \times N$ is a set of arcs on N. We only consider digraphs (N, D) that are irreflexive, i.e., $(i,i) \notin D$ for every $i\in N$. Since the set of nodes N is fixed, a digraph (N, D) can be represented by its binary relation D. The collection of all digraphs on N is denoted by $\mathcal{D}$. For $i \in N$ and $D \in \mathcal{D}$, we define the set of successors of node $i \in N$ in digraph D by

$$S_{D}(i) = \{j \in N \mid (i,j) \in D\}$$

and the set of predecessors of i in D by

$$P_{D}(i) = \{j \in N \mid (j,i) \in D\}.$$

The cardinalities of $S_{D}(i)$ and $P_{D}(i)$ are called the outdegree $out_i(D)$ and the indegree $in_i(D)$ of node i in D, i.e.,

$$out_i(D) = \# S_{D}(i) \text{ and } in_i(D) = \# P_{D}(i).$$

Preorder A preorder on N is a binary relation $\mathcal{R} \subset N \times N$ that is reflexive (i.e., $(i,i)\in \mathcal{R}$ for all $i \in N$) and transitive (i.e., if $(i,j)\in \mathcal{R}$ and $(j,h)\in \mathcal{R}$, then $(i,h)\in \mathcal{R}$ for every $i,j,h \in N$). A preorder $\mathcal{R}$ on N is complete if $(i,j)\in \mathcal{R}$ or $(j,i)\in \mathcal{R}$ or both for every pair $i,j \in N$, $i \not = j$. We use the standard notation, i.e.,

$$i \succeq j\, \text { if and only if}\, (i,j) \in \mathcal{R}\, \text {(}i \,\text {is ranked at least as high as}\, j\text {)},$$

$$i \succ j\, \text {if and only if}\, [i \succeq j\, \text {and not}\, j \succeq i]\, \text {(}i \,\text {is ranked higher than}\, j\text {),}$$

$$i \sim j\, \text {if and only if}\, [i \succeq j\, \text {as well as}\, j \succeq i] \text {(}i\, \text {and}\, j\, \text {are ranked equally).}$$

We denote the collection of all complete preorders by $\mathcal{W}$.

Ranking methods A ranking method is a mapping $R :\mathcal{D} \rightarrow \mathcal{W}$ which assigns to every digraph $D\in \mathcal{D}$ on N a complete preorder $R(D) \in \mathcal{W}$. We use the notation

$$i \succeq _{D} j\, \text {if and only if}\, (i,j) \in R(D).$$

A digraph $D\in \mathcal{D}$ is a tournament on N if

$$\# \left[ \{(i,j),(j,i)\}\cap D \right] =1 \ \text {for all} \ i,j \in N, \ i \not = j.$$

Note that every tournament is a complete digraph, where by a complete digraph we mean $D \in \mathcal{D}$ such that $(i,j)\in D$ or $(j,i)\in D$ or both for every pair $i,j \in N$, $i \not = j$. Let $\mathcal{CD} \subset \mathcal{D}$ be the collection of all complete digraphs on N, and let $\mathcal{T} \subset \mathcal{CD} \subset \mathcal{D}$ denote the class of all tournaments on N.

The ranking method by outdegree is the ranking method $R^{out} :\mathcal{D} \rightarrow \mathcal{W}$ which assigns to every digraph $D\in \mathcal{D}$ on N a complete preorder $R^{out}(D) \in \mathcal{W}$ given by

$$(i,j) \in R^{out}(D)\, \text {if and only if}\, out_i (D) \ge out_j (D).$$

We use the notation

$$i \succeq _{D}^{out} j\, \text {if and only if}\, (i,j) \in R^{out}(D).$$

The Copeland score $cop_i (D)$ of node $i \in N$ in digraph D is defined by

$$ cop_i (D) = 2\# \left( S_{D}(i) \setminus P_{D}(i) \right) + \# \left( S_{D}(i) \cap P_{D}(i) \right) .$$

For $D \in \mathcal{CD}$, $\# S_{D}(i) + \# P_{D}(i) - \# \left( S_{D}(i) \cap P_{D}(i) \right) =n-1$. Hence, $2\# \left( S_{D}(i) \setminus P_{D}(i) \right) + \# \left( S_{D}(i) \cap P_{D}(i) \right) = 2\# S_{D}(i) - \# \left( S_{D}(i) \cap P_{D}(i) \right) = \# S_{D}(i) - \# P_{D}(i) + n-1$, and therefore

$$ cop_i (D) = 2\# \left( S_{D}(i) \setminus P_{D}(i) \right) + \# \left( S_{D}(i) \cap P_{D}(i) \right) = out_i (D) - in_i (D)+n-1. $$

The ranking method by Copeland score is the ranking method given by

$$ i \succeq ^{cop}_{D} j \ \text {if and only if} \ cop_i(D) \ge cop_j(D) \text{ for } \text{ all } i, j \in N. $$

Note that for tournaments the ranking by outdegree and the ranking by Copeland score are the same, since $S_{D}(i) \cap P_{D}(i) =\emptyset$ for all $i \in N$ and $D \in \mathcal{T}$.

However, these two ranking methods are different on $\mathcal{D}$.

For a digraph $D\in \mathcal{D}$ and a permutation $\pi :N \rightarrow N$, the permuted digraph $\pi D\in \mathcal{D}$ is given by $(\pi (i), \pi (j)) \in \pi D$ if and only if $(i,j) \in D$.

The $\beta$-measure on N (introduced in [18]) is the function $\beta :\mathcal{D} \rightarrow \mathbb {R}^N$ defined by

$$ \beta _i(D) = \sum _{j \in S_D (i)} \frac{1}{in_j (D)} \quad \text {for all} \ i \in N \ \text {and} \ D \in \mathcal{D}. $$

The $\beta$-measure equally distributes the domination power over a node $j\in N$ in a digraph D over all its predecessors.

The ranking method by the $\beta$-measure or the $\beta$-ranking is the ranking method given by

$$ i \succeq ^{\beta }_{D} j \ \text {if and only if} \ \beta _i(D) \ge \beta _j(D) \text{ for } \text{ all } i, j \in N. $$

3 Axiomatizations of the Ranking Methods

Rubinstein’s result on the ranking in a tournament On the class of tournaments $\mathcal{T}$, [62] provides an axiomatic characterization of the ranking by Copeland score (i.e., by outdegree, since for tournaments the rankings by outdegree and by Copeland score are the same).

The following three axioms (as formulated in [19]) are used for Rubinstein’s characterization:

• (i) Anonymity:

  Permuting the nodes in a digraph permutes accordingly the ranking, i.e.,

  $$\begin{aligned} { For}\, { every}\,&D\in \mathcal{D}\, { and}\, { permutation}\, \pi :N \rightarrow N\, { it}\, { holds}\, { that} \\&\quad i \succeq _{D} j\, { if}\, { any}\, { only}\, { if}\, \pi (i) \succeq _{\pi D} \pi (j). \end{aligned}$$

• (ii) Positive responsiveness:

  If i is ranked at least as high as j, then increasing the outdegree of i makes i being ranked higher than j, i.e.,

  $$\begin{aligned} { Let}\, D\in \mathcal{D} \, { and}\, i,j,h \in&N, i \not = j \, { be}\, { such}\, { that}\, \,(i,h) \notin D,\, { and}\, { let}\, D' = D \cup \{(i,h)\}. \\&\quad \,Then\, i \succeq _{D} j \, { implies}\, { that}\, i \succ _{D'} j. \end{aligned}$$

• (iii) Independence of irrelevant arcs:

  The order between two nodes does not change if changes only take place with respect to arcs on which they are neither the predecessor nor the successor, i.e.,

  $$\begin{aligned}&{ Let}\, D, D'\in \mathcal{D}\, { and}\, i,j \in N\, { be}\, { such}\, { that}\, S_D (i) = S_{D'} (i), S_D (j) = S_{D'} (j), \\&\quad P_D (i) = P_{D'} (i),\, { and}\, P_D (j) = P_{D'} (j). \,{ Then}\, i \succeq _{D} j \, { if}\, { and}\, { only}\, { if}\, i \succeq _{D'} j. \end{aligned}$$

Ranking by outdegree [19] generalize Rubinstein’s result by characterizing the ranking by outdegree for arbitrary digraphs. The first two axioms introduced in [62], i.e., anonymity and positive responsiveness are the same, while independence of irrelevant arcs is generalized in a straightforward way to independence of non-dominated arcs.

Formally, for a ranking method represented by $\{\succeq _{D} \ \mid D \in \mathcal {D}\} \subset \mathcal{W}$, we consider the following three axioms ([19]):

• (i) Anonymity:

  Permuting the nodes in a digraph permutes accordingly the ranking, i.e.,

  $$\begin{aligned} { For}\, { every}\,&D\in \mathcal{D}\, { and}\, { permutation}\, \pi :N \rightarrow N\, { it}\, { holds}\, { that} \\&\quad i \succeq _{D} j \, { if}\, { any}\, { only}\, { if}\, \pi (i) \succeq _{\pi D} \pi (j). \end{aligned}$$

• (ii) Positive responsiveness:

  If i is ranked at least as high as j, then increasing the outdegree of i makes i being ranked higher than j, i.e.,

  $$\begin{aligned} { Let}\, D\in \mathcal{D} \,{ and}\, i,j,h \in&N, i \not = j \,{ be}\, { such}\, { that}\, (i,h) \notin D, \,{ and}\, { let}\, D' = D \cup \{(i,h)\}.\\&\quad { Then}\, i \succeq _{D} j \,{ implies}\, { that}\, i \succ _{D'} j \end{aligned}$$

• (iii) Independence of non-dominated arcs:

  The order between two nodes does not change if changes only take place in arcs on which they are not the predecessors, i.e.,

  $$\begin{aligned} { Let}\, D, D'\in \mathcal{D} \,{ and}\, i,&j \in N \,{ be}\, { such}\, { that}\, S_D (i) = S_{D'} (i) \,{ and}\, S_D (j) = S_{D'} (j). \\&{ Then}\, i \succeq _{D} j \,{ if}\, { and}\, { only}\,{ if}\, i \succeq _{D'} j. \end{aligned}$$

Reference [19] prove (their Theorem 2.4) that a ranking method is equal to the ranking method by outdegree if and only if it satisfies anonymity, positive responsiveness, and independence of non-dominated arcs.

Ranking by Copeland score [7] presents an alternative generalization of Rubinstein’s result by providing an axiomatic characterization of the ranking by Copeland score for arbitrary digraphs.

More precisely, [7] characterizes the Copeland score by the following axioms (that we state by using the same notation borrowed from [19], the first two being the same as in [19]):

• (i) Anonymity:

  Permuting the nodes in a digraph permutes accordingly the ranking, i.e.,

  $$\begin{aligned} { For}\,{ every}\,&D\in \mathcal{D} \,{ and}\,{ permutation}\, \pi :N \rightarrow N \,{ it}\, { holds}\, { that} \\&\quad i \succeq _{D} j \,{ if}\, { any}\, { only}\,{ if}\, \pi (i) \succeq _{\pi D} \pi (j). \end{aligned}$$

• (ii) Positive responsiveness:

  If i is ranked at least as high as j, then increasing the outdegree of i makes i being ranked higher than j, i.e.,

  $$\begin{aligned} { Let}\, D\in \mathcal{D} \,{ and}\, i,j,h \in&N, i \not = j \,{ be}\,{ such}\,{ that}\, (i,h) \notin D, \,{ and}\,{ let}\, D' = D \cup \{(i,h)\}.\\&{ Then}\, i \succeq _{D} j \,{ implies}\,{ that}\, i \succ _{D'} j. \end{aligned}$$

• (iii) Independence of 2- or 3-cycles:

  Deleting or adding a cycle of length 2 or 3 to a digraph does not change the ranking of the nodes, i.e.,

  $$\begin{aligned} { Let}\, D, D'\in \mathcal{D} \,{ be}\,{ such}\,{ that}\, D' = D \cup \{(h,g),(g,h)\} \,{ for}\,{ some}\, h,g \in N \,\\{ with}\, \{(h,g),(g,h)\}\cap D = \emptyset , \,{ or}\, D' = D \cup \{(h,g),(g,f),(f,h)\} \,{ for}\, { some}\,\\ h,g,f \in N \,{ with}\, \{(h,g),(g,f),(f,h)\}\cap D = \emptyset . \,{ Then}\, i \succeq _{D} j \,{ if}\,{ and}\,{ only}\,\\{ if}\, i \succeq _{D'} j \,{ for}\,{ all}\, i,j \in N. \end{aligned}$$

• (iv) Negative responsiveness:

  If i is ranked at least as high as j, then increasing the indegree of j makes i being ranked higher than j, i.e.,

  $$\begin{aligned} { Let}\, D\in \mathcal{D} \,{ and}\, i,j,h \in&N, i \not = j \,{ be}\,{ such}\,{ that}\, (h,j) \notin D, \,{ and}\,{ let}\, D' = D \cup \{(h,j)\}.\\&\quad { Then}\, i \succeq _{D} j \,{ implies}\,{ that}\, i \succ _{D'} j. \end{aligned}$$

As mentioned in [19], the ranking by Copeland score does not satisfy independence of non-dominated arcs on $\mathcal{D}$. Moreover, the ranking by outdegree does not satisfy independence of 2- or 3-cycles nor negative responsiveness for arbitrary digraphs. Furthermore, note that while independence of non-dominated arcs generalizes independence of irrelevant arcs, independence of 2- or 3-cycles does not.

More precisely, [19] prove the following results (their Proposition 3.4) for a ranking method R on $\mathcal{D}$:

• If R satisfies independence of non-dominated arcs, then R satisfies independence of irrelevant arcs.

• R satisfies independence of non-dominated arcs on $\mathcal{T}$ if and only if R satisfies independence of irrelevant arcs on $\mathcal{T}$.

• On $\mathcal{D}$, independence of 2- or 3-cycles and independence of irrelevant arcs are two independent properties.

Reference [41] provides an axiomatic characterization of the ranking by Copeland score restricted to the class of complete 2-digraphs, which are modified digraphs such that there exist exactly two (possibly the same) arcs between every pair of nodes $i,j \in N$, $i \not = j$.

As emphasized in [19], the notions of 2-digraphs and “standard” digraphs recalled in Sect. 2 are different.

Reference [41] shows that for complete 2-digraphs the ranking by Copeland score is characterized by the following three properties:

• (i) Anonymity (stated for complete 2-digraphs);

• (ii) Positive responsiveness (stated for complete 2-digraphs);

• (iii) Independence of reversing cycles: Reversing a cycle in a complete 2-digraph does not change the ranking of the nodes.

Reference [19] point out that for complete 2-digraphs the ranking by Copeland score is the same as the ranking by outdegree with the outdegree defined for such graphs by $out_i (D) = \# \{(h,j)\in D \mid h=i\}$. Both ranking methods also satisfy independence of reversing cycles on $\mathcal{CD}$.

Ranking by the $\beta$-measure [14] characterize the $\beta$-ranking by using the following axioms:

• (i) Anonymity;

• (ii) Positive responsiveness;

• (iii) Independence of irrelevant arcs:

  Some arcs are irrelevant for comparing two nodes, i.e., arcs which do not “involve” the two nodes.

• (iv) Node addition:

  Adding nodes that are not linked to any other node has no influence on the ranking.

• (v) Independence of local density:

  Increasing the number of successors of a node and simultaneously increasing their number of predecessors, in the same proportion, does not change (improve or worsen) the position of that node.

When comparing the above conditions with the axioms stated in [19], the first two properties (anonymity, positive responsiveness) are the same, while independence of irrelevant arcs is strictly weaker than the independence of non-dominated arcs (as pointed out before). The last two properties (node addition, independence of local density) are not related to any of the conditions in [19].