Bowen Liu

Dr. Bowen Liu

orcid

Research Focus & Metrics

Academic Career Length

2Years (2025-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
6 June 2025 in Mathematics
Verified
Journal Article
Open access
PDF file
BMBoris Melnikov
Boris Melnikov
Bowen LiuBowen Liu
Bowen Liu
In this paper, we generate random graphs for a specific area, namely, models of real communication networks. We propose a method that determines the “best” invariant; the corresponding basic algorithm is as follows. For the generated set of graphs, we calculate the numerical values of each of the pre-selected invariants (i.e., indexes of Graovac–Ghorbani, Randic̀, Wiener, global clustering coefficients and the vector of second-order degrees). For all graphs, we arrange these numerical values in descending order, after which, for each of the 10 pairs of invariants, we calculate the rank correlation of these orders; for such calculations, we use 5 different variants of rank correlation algorithms (i.e., usual pair correlation, Spearman’s algorithm, Kendall’s algorithm and its improved version, and the algorithm proposed by the authors). In such a way, we get 10 pairs of rank correlation values, then we arrange them as the values of 10 independent elements of the 5 × 5 table (rows and columns of this table correspond to the 5 invariants under consideration). If the rank correlation values are negative, we record the absolute value of this value in the table. The basic idea is that the “most independent” invariant of the graph gets the minimum sum when summing 4 values of its row, i.e., less than for other invariants (other rows). For our subject area, we obtained the same result for 5 different variants of calculating the rank correlation: the value obtained for the vector of second-order degrees is significantly better than all the others, and among the usual invariants, the global clustering coefficients invariant is significantly better than others ones. This fact corresponds to our previous calculations, in which we ordered the graph invariants according to completely different algorithms.



1 October 2025 in Computer tools in education
Verified
Journal Article
Open access
PDF file
BMBoris Melnikov
Boris Melnikov
POPavel Oganesyan
Pavel Oganesyan
Bowen LiuBowen Liu
Bowen Liu
In this study, we present a method and its implementations for the traveling salesman problem considering matrices with a uniform random distribution of path costs. The method is a modification of the branch-and-bound method with specific heuristics. Data generation and validation used for this study are discussed. The mathematical study of the problem being solved can probably be considered complete as early as the 1970s; even earlier, an approach to its solution in the form of the branch- and-bound method was described. The purpose of this paper is to describe such a heuristic implementation of the branch-and-bound method, which with almost a single probability gives the optimal solution to a random problem in an acceptable time. We call random variants of the problem, in which each cell of the traveling salesman matrix for a problem instance represents a realization of a uniformly distributed random variable. It is important to note that approaches to the heuristic solution of a random variant differ significantly from approaches to geometric and pseudogeometric variants. In our opinion, we have achieved our goal: thus, the maximum time to obtain a solution for 100 random problem instances of dimension 99 did not exceed 2 minutes, while the exact solution was always found; the last thing was verified by the fact that the branch-and-bound method was always counted to completion. In the paper, we provide a brief description of the heuristics used for this purpose, the most important of which is the construction of the so-called sequence of right-hand subproblems.

1 April 2025 in Preprints.org
Verified
Preprint
Open access
PDF file
BMBoris Melnikov
Boris Melnikov
Bowen LiuBowen Liu
Bowen Liu
With random graph generation, most of the previously described algorithms were not related to graphs arising in any particular subject area, so in this paper we generate random graphs for a specific area, namely, models of real communication networks. In the paper we propose a method that determines the “best” invariant; the corresponding basic algorithm is as follows. For the generated set of graphs, we calculate the numerical values of each of the pre-selected invariants. For all graphs, we arrange these numerical values in descending order, after which, for each of the 10 pairs of invariants, we calculate the rank correlation of these orders; for such calculations, we use 5 different variants of rank correlation algorithms. In such a way, we get 10 pairs of rank correlation values, then we arrange them as the values of 10 independent elements of the 5x5 table (rows and columns of this table correspond to the 5 invariants under consideration). If the rank correlation values are negative, we record the absolute value of this value in the table. The basic idea is that the “most independent” invariant of the graph gets the minimum sum when summing 4 values of its row, i.e. less than for other invariants (other rows). For our subject area, we got the same result for 5 different variants of calculating the rank correlation: the value obtained for the vector of second-order degrees is significantly better than all the others, and among the usual invariants, the global clustering coefficients invariant is significantly better than others ones; this fact corresponds to our previous calculations, in which we ordered the graph invariants according to completely different algorithms.

18 December 2025 in arXiv
Verified
Preprint
Open access
PDF file
Bowen LiuBowen Liu
Bowen Liu
The score set of a tournament is defined as the set of its distinct out-degrees. In 1978, Reid proposed the conjecture that for any set of nonnegative integers $D$, there exists a tournament $T$ with a degree set $D$. In 1989, Yao presented an arithmetical proof of the conjecture, but a general polynomial-time construction algorithm is not known. This paper proposes a necessary and sufficient condition and a separate necessary condition, based on the existing Landau's theorem for the problem of reconstructing score sequences from score sets of tournament graphs. The necessary condition introduces a structured set that enables the use of group-theoretic techniques, offering not only a framework for solving the reconstruction problem but also a new perspective for approaching similar problems. In particular, the same theoretical approach can be extended to reconstruct valid score sets given constraints on the frequency of distinct scores in tournaments. Based on these conditions, we have developed three algorithms that demonstrate the practical utility of our framework: a polynomial-time algorithm and a scalable algorithm for reconstructing score sequences, and a polynomial-time network-building method that finds all possible score sequences for a given score set. Moreover, the polynomial-time algorithm for reconstructing the score sequence of a tournament for a given score set can be used to verify Reid's conjecture. These algorithms have practical applications in sports analysis, ranking prediction, and machine learning tasks such as learning-to-rank models and data imputation, where the reconstruction of partial rankings or sequences is essential for recommendation systems and anomaly detection.