Assessing Dual Approaches for Ranking Score Computation via Transitive Triads

Bowen Liu

Department of Mathematics, Shenzhen MSU-BIT University, Shenzhen, China.

DOI: 10.4236/jamp.2024.1211245                

Abstract

The possibility of developing a complete graph invariant computable in polynomial time remains an open question. Consequently, creating efficient algorithms to verify non-isomorphism, including heuristic approaches, is essential. Effective implementation of these heuristics necessitates both the adaptation of existing graph invariants and the invention of novel ones, which continues to be a relevant challenge. Numerous current invariants are capable of distinguishing a significant number of graphs rapidly in real-time scenarios. In this study, we present an invariant tailored for tournaments, a specific class of directed graphs. Tournaments are particularly intriguing because the count of distinct tournaments for a given number of vertices aligns with that of undirected graphs of the same size. The introduced invariant evaluates all possible tournament subsets derived from the original digraph that share the identical arc set. For each subset tournament, standard rankings are computed and aggregated to produce the final vertex scores, which serve as the new invariant. Our analysis indicates that this newly proposed invariant diverges from the most straightforward tournament invariant, which typically assigns scores to each participant. Preliminary computational tests demonstrate that the minimal correlation between the sequences generated by these two invariants occurs at a vertex count of 15.

Keywords

Graph Invariant, Directed Graphs, Tournament Theory, Transitive Triads

1. Introduction

Graph invariants are numerical values or ordered tuples that encapsulate essential structural properties of a graph, remaining unaffected by vertex labeling or ordering. Among the various graph invariants studied, the Graovac-Ghorbani ( ${\text{ABC}}_{\text{GG}}$ ) index [1] stands out as a topological descriptor with enhanced predictive capabilities compared to its counterparts. Extensive research has been conducted on tournaments [2] [3], with our current focus here is on the study of tournaments [4].

In our preceding work, titled “On an Invariant of Tournament Digraphs [5],” we introduced a potential invariant based on the consistency of relative ranking points of participants when evaluated through two different methods. Specifically, if differing ranking scores are derived using the first method, these differences persist and maintain their relative ordering when assessed using the second method. Building upon this foundation, the present paper delves deeper into this potential invariant. We examine how the interrelations among various ranking scores evolve as transitive triples within the same tournament digraph undergo sequential modifications. Additionally, we investigate the variation in the correlation coefficient between the two sets of ranking scores under these transformations.

2. Summary of “On an Invariant of Tournament Digraphs”

2.1. Introduction

Suppose there is a game and $\text{n}$ players participate in it. The rules of the game are as follows:

・ A two-on-two duel between the participating players;

・ The result of each duel is only the winner, there is no draw;

・ After each duel, the points of the winning player will increase by one point, and the points of the losing player will remain the same;

・ Every player has to fight against all players except himself;

Ranking Points Rule

After the game is over, there are two methods to calculate the ranking points for the players:

Standard Ranking Points Calculation:

・ The player with the most points will get $n$ ranking points;

・ The player who gets the second most points will get $n-1$ ranking points, and so on;

・ If there are two or more players with the same number of points, each player is given the average number of ranking points in their ranking range;

Alternative Ranking Points Calculation:

・ Think of the players in the entire game as a set, then any $\text{k}$ players in it form a subset;

・ For each possible subset (except for a subset that contains only one player or does not contain players), corresponding points are awarded according to the duel situation between the contestants in the subset (the duel situation comes from the complete competition), the points rules are the same as the previous points rules, and according to the newly obtained points, each participant is awarded the corresponding ranking points according to the previous rules for granting ranking points;

・ Add the ranking points obtained from each subset as new points to the corresponding players;

・ Finally, each player is given the ranking points obtained by processing the newly obtained points in the same way as the old ranking points.

2.2. Results and Discussion

We conducted computations on 1,000,000 different tournament graphs (with participants not exceeding 15) to calculate ranking points using two mentioned methods. In these results, it was observed that the relative ranking points of participants remain consistent when calculated using two different methods. Furthermore, the correlation coefficient can be zero when the number of participants is odd. This is because there exist tournament graphs where each participant wins an equal number of matches when the number of participants is an odd number.

Furthermore, we propose a theory to demonstrate that the relative ranking points of participants remain consistent when calculated using two different methods, thus establishing it as an invariant. The theory is formulated as follows: Suppose that in any duel of $\text{n}$ contestants, the person who gets the points $\text{K}$ (where $\text{K}>1$ ), on average, will have the new points at least $2^{\text{n}-2}$ points more than the new points of the person who gets the points $\text{K}-1$ .

Through these explorations, we believe that the consistency of relative ranking points of participants when calculated using two different methods represents a potential invariant. In this paper, I will further explore how this relationship changes when changing transitive triads and how the correlation between the ranking points calculated using the two mentioned methods changes, including identifying the minimum value.

3. Research Plan

In our previous study, my advisor Boris F. Melnikov and I explored a potential invariant: the relative ranking points of participants remain consistent when calculated using two different methods. We validated this invariant by randomly generating 1,000,000 Tournaments through a program and calculating the ranking points for each graph using these methods.

Now, we consider the role of transitive triads in this invariant. There are four ways to change a transitive triad:

・ Change the direction of the first edge, keeping other edges unchanged.

・ Change the direction of the second edge, keeping other edges unchanged.

・ Change the direction of the third edge, keeping other edges unchanged.

・ Change the direction of all edges.

Here, changing the direction of edges means altering the win-loss results of the participants’ duels. The uniqueness of the fourth change method lies in the fact that the total number of wins for each participant remains unchanged (i.e., the ranking points calculated using the first method do not change), but the ranking points calculated using the second method may change.

The reason is as follows:

When changing the direction of all edges in a transitive triad, even though the total number of wins for each participant remains unchanged, sub-tournament may appear that are affected when calculating ranking points using the second method. A sub-tournament refers to a sub-graph formed by selecting some nodes and their connecting edges from the entire Tournament. These sub-tournaments may affect the ranking points calculated using the second method.

Specifically, during the calculation of the second ranking method, there exist sub-tournament that only contain the two participants involved in the fourth change. In these sub-tournaments, the total number of wins for these participants changes, which alters their ranking points calculated by the first method. This change may not be compensated by other sub-tournament, as each ranking point and its corresponding number of wins are only correlated within the current sub-tournament graph, not equal. Therefore, this method may impact the overall ranking points.

After discussing this with my advisor, the following work was carried out by myself alone, as I am the sole author of the paper. Therefore, I plan to write a program that randomly generates numerous Tournaments, identifies all transitive triads in each graph, and performs the four mentioned transformations on each triad. After each transformation, we will check if the invariant (the relative ranking points of participants remain consistent when calculated using two different methods) holds. At the same time, we will calculate the modified Kendall correlation coefficient. This correlation coefficient effectively reflects the relationship I need to study in this paper.

The calculation method for the modified Kendall correlation coefficient is as follows:

・ Pair all participants, resulting in $\text{n}\left(\text{n}+1\right)/2$ pairs, each referred to as a pair.

・ Classify these pairs into three categories:

・ First category: One participant’s ranking points calculated by both methods are higher than the other participant’s corresponding ranking points.

・ Second category: One participant’s ranking points calculated by the first method are higher than the other participant’s ranking points, but the second method gives the opposite result.

・ Third category: Both participants have the same ranking points calculated by either method.

Let ${\text{n}}_1$ be the number of pairs in the first category, ${\text{n}}_2$ the number of pairs in the second category, and ${\text{n}}_3$ the number of pairs in the third category. The formula for the modified Kendall correlation coefficient is:

$\text{σ}=\frac{{\text{n}}_1-{\text{n}}_2+0.5\cdot n_3}{\text{n}\left(\text{n}+1\right)/2}$ . (1)

This correlation coefficient effectively reflects the relationship I need to study because it comprehensively considers the consistency and differences between the different ranking methods. The number of pairs in the first category ${\text{n}}_1$ and the number of pairs in the third category ${\text{n}}_3$ reflect the consistency of the ranking results calculated by both methods, while the number of pairs in the second category ${\text{n}}_2$ reflects the opposite results of the two methods. Therefore, the coefficient can comprehensively reflect the relationship between the two calculation methods.

Evidently, if the relationship is invariant, the minimum value of this coefficient will be 0.5, as ${\text{n}}_2$ equals 0. Moreover, when the number of participants is odd and each participant wins an equal number of duels, there exists a type of Tournament that will take this minimum value.

4. Research Method

To analyze the effect of the four transformations on transitive triads concerning the correlation coefficient and the potential invariant, I have enhanced the program used in my previous paper by incorporating three essential functions: a function to identify transitive triads, a function to perform the four transformations, and a function to compute the Modified Kendall Correlation Coefficient. Below, I provide a concise explanation of these functions.

4.1. Identifying Transitive Triads

The function in Figure 1. for identifying transitive triads employs three nested loops. Each loop is responsible for finding one edge of the triad. A crucial detail in this process is starting the second and third loops at the current vertex value of the first loop plus one. This approach is necessary because transitive triads can exist in two forms: small $\to$ medium $\to$ large $\to$ small and small $\to$ large $\to$ medium $\to$ small. To identify all transitive triads without repetition, the starting values of the second and third loops are adjusted accordingly.

Figure 1. Function to Identify Transitive Triads.

4.2. Performing the Four Transformations

The function in Figure 2 for performing the four transformations includes a parameter type that determines the specific transformation to execute. The transformations are defined as follows:

・ Change the direction of the first edge, keeping other edges unchanged.

・ Change the direction of the second edge, keeping other edges unchanged.

・ Change the direction of the third edge, keeping other edges unchanged.

・ Change the direction of all edges.

Figure 2. Function to perform the four transformations.

4.3. Computing the Modified Kendall Correlation Coefficient

The function in Figure 3 to compute the Modified Kendall Correlation Coefficient uses dynamic programming to generate all pairwise combinations of participants. For each pair, the function calculates the product of the differences in ranking points obtained by the two methods and determines the sign of the product. The sign categorizes the pairs into three classes, which are then used to update the numerator of the correlation coefficient formula. The final coefficient is derived by dividing the numerator by the denominator.

Figure 3. Function to compute the modified Kendall correlation coefficient.

Using these functions, I subsequently analyzed transitive triads in 10,000 randomly generated tournaments, each containing between 11 and 17 participants.

5. Results and Summary

This section presents the results obtained from analyzing 10,000 Tournaments. No examples violating the potential invariant (the relative ranking points of participants remain consistent when calculated using two different methods) were found. Additionally, examples with a correlation of 0.5 were found in Tournaments of sizes 11, 13, 15, and 17. Examples with a correlation near 0.57 were also found in Tournaments of sizes 12 and 14.

5.1. Examples with a Correlation of 0.5

Examples with a correlation of 0.5 were found in Tournaments of sizes 11, 13, 15, and 17. These examples show that the Modified Kendall Correlation Coefficient can indeed reach 0.5 under certain conditions.

The following Figures 4-7 and Table 1 show Tournaments of sizes 11, 13, 15,

Table 1. Triangle cycle and modified Kendall correlation coefficient for tournament. Here, i, j, and k represent the indices of the participants in the tournament. Type 1, Type 2, Type 3, and Type 4 indicate the modified Kendall correlation coefficients under four different transformations.

Figure 4. Tournament of size 11 where modifying specific transitive triads (in a specific manner) results in a correlation of 0.5.

Figure 5. Tournament of size 13 where modifying specific transitive triads (in a specific manner) results in a correlation of 0.5.

Figure 6. Tournament of size 15 where modifying specific transitive triads (in a specific manner) results in a correlation of 0.5.

Figure 7. Tournament of size 17 where modifying specific transitive triads (in a specific manner) results in a correlation of 0.5.

and 17, where the correlation coefficient reaches 0.5 after transforming specific transitive triads.

5.2. Examples with a Correlation Near 0.57

Examples with a correlation near 0.57 were found in Tournaments of sizes 12 and 14. Although these examples did not reach 0.5, they are very close.

The following Figure 8, Figure 9 and Table 2 show Tournaments of sizes 12 and 14, where the correlation coefficient reaches 0.57 after transforming specific transitive triads.

Table 2. Triangle Cycle and Modified Kendall Correlation Coefficient for Tournament. Here, i, j, and k represent the indices of the participants in the tournament. Type 1, Type 2, Type 3, and Type 4 indicate the Modified Kendall Correlation Coefficients under four different transformations.

Figure 8. Tournament of size 12 where transforming certain transitive triads (in a specific manner) can achieve a correlation coefficient close to 0.57.

Figure 9. Tournament of size 14 where transforming certain transitive triads (in a specific manner) can achieve a correlation coefficient close to 0.57.

5.3. Summary of Results

The analysis of 10,000 tournaments provides preliminary evidence that the potential invariant holds, as no counterexamples were observed. The observation of examples with a correlation of 0.5, particularly in graphs of sizes 11, 13, 15, and 17, suggests that the Modified Kendall Correlation Coefficient for ranking points calculated by the two methods can reach this value under specific conditions. Additionally, the presence of correlations closes to 0.57 in tournaments of sizes 12 and 14 suggests that the minimum correlation for even-sized participant sets may be different and needs further research. While these findings are promising, further research is necessary to explore whether counterexamples to the invariant relationship exist across a wider range of conditions and sizes of tournaments, and to establish the robustness of this invariant.

6. Conclusion

In this paper, I continued to explore a potential invariant for tournament digraphs that was first introduced in “On an Invariant of Tournament Digraphs”. I looked at the relative ranking points of players using two different methods and studied how changes in transitive triads within these tournaments affect the rankings and their correlations. After running extensive computer simulations with 10,000 randomly generated tournaments, I found that the proposed invariant seems to hold true, as no counterexamples were found. I used the Modified Kendall Correlation Coefficient to measure the relationship between the two ranking methods and found that tournaments with an odd number of players consistently had a minimum correlation of 0.5. For tournaments with an even number of players, the correlation was close to 0.57. These results support the proposed invariant. However, more research is needed to confirm this invariant across a wider range of tournament sizes and find any possible counterexamples. This study builds on previous research, providing deeper insights into our proposed invariant for tournament digraphs and expanding our understanding of this potential invariant.

Conflicts of Interest

The authors declare no conflicts of interest regarding the publication of this paper.

References

[1]	Pacheco D., de Lima L., Oliveira C.S. (2021) On the Graovac-Ghorbani Index for Bicyclic Graphs with No Pendent Vertices, MATCH Commun. MATCH Communications in Mathematical and in Computer Chemistry, 86, 429-448. https://match.pmf.kg.ac.rs/electronic_versions/Match86/n2/match86n2_429-448.pdf
[2]	Beretta, L., Nardini, F.M., Trani, R. and Venturini, R. (2019) An Optimal Algorithm to Find Champions of Tournament Graphs. In: Lecture Notes in Computer Science, Springer International Publishing, 267-273. https://doi.org/10.1007/978-3-030-32686-9_19
[3]	Shen, J., Sheng, L. and Wu, J. (2003) Searching for Sorted Sequences of Kings in Tournaments. SIAM Journal on Computing, 32, 1201-1209. https://doi.org/10.1137/s0097539702410053
[4]	Gera R., Haynes T.W., Hedetniemi S.T. (2018) Graph Theory: Favorite Conjectures and Open Problems-2. Springer. https://doi.org/10.1007/978-3-319-97686-0
[5]	Melnikov, B.F. and Liu, B. (2024) On an Invariant of Tournament Digraphs. Journal of Applied Mathematics and Physics, 12, 2711-2722. https://doi.org/10.4236/jamp.2024.127162