Assessing Dual Approaches for Ranking Score Computation via Transitive Triads  

作　　者：Bowen Liu Bowen Liu(Department of Mathematics, Shenzhen MSU-BIT University, Shenzhen, China)

机构地区：[1]Department of Mathematics, Shenzhen MSU-BIT University, Shenzhen, China

出　　处：《Journal of Applied Mathematics and Physics》2024年第11期4020-4029,共10页应用数学与应用物理（英文）

摘　　要：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.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.

关 键 词：Graph Invariant Directed Graphs Tournament Theory Transitive Triads 

分 类 号：O15[理学—数学]