Volume 4(61)

CONTENTS

1. Monakhova E.A., Monakhov O.G. Discovery of analytical dependences of parameters of optimal chordal ring networks based on data analysis     
2. Korobov A.V., Migov D. A. Algorithms for calculating network reliability based on the decomposition approach  
3. Vishnevsky V.M., Klimenok V.I., Sokolov A.M., Larionov A. A. Performance evaluation of the fork-join system with Markovian Arrival and Phase-Type service time distribution
4. Bredikhin S. V., Scherbakova N. G., Yurgenson A.N. Scientific journal co-authorship network models. Part 2       
5. Bakulina M. P. Increasing efficiency of image compression based on the RLE method             
6. Gerb A. R., Omarova G. A. Graph partitioning algorithms on GPU                          

E.A. Monakhova, O.G. Monakhov

Institute of Computational Mathematics and Mathematical Geophysics SB RAS, 630090, Novosibirsk, Russia

DISCOVERY OF ANALYTICAL DEPENDENCES OF PARAMETERS OF OPTIMAL CHORDAL RING NETWORKS

BASED ON DATA ANALYSIS

The structure of chordal ring networks is being intensively studied for the construction of communication networks in various practical applications. The introduction of additional chords increases the reliability of the ring structure and reduces its diameter, which in turn reduces delays and increases the performance of the entire communication system. In this paper, we study the class of chordal ring networks of degree three, which are studied in many works as a possible topology of communication networks of infocommunication systems.

A chordal ring graph with the smallest possible diameter for a given order of the graph is called optimal. Diameter minimization optimizes a number of important characteristics of the communication network topology, such as the reliability of the communication structure in case of element failures, structural delays in data transmission, communication speed, etc. Therefore, the fundamental problem of synthesizing optimal topologies in different classes of regular graphs is to find graphs with a minimum diameter among graphs with a given degree and number of vertices. For the class of graphs under consideration, structural properties were previously investigated, including the calculation of the diameter and finding the shortest paths.

In this paper, we study the problem of finding optimal graphs in the class of chordal ring networks as a search for descriptions of families of graphs with a minimum diameter for given orders and degrees of graphs. The main methods used to construct optimal regular structure networks are local search, breadth-first search, enumeration and heuristic algorithms.

Earlier, for the class of chordal ring graphs, a family of extremal optimal graphs with a maximum order for any diameter was obtained. The problem of minimizing the diameter for a given order is more difficult to solve than obtaining extremal graphs, since the diameter does not always increase monotonically with increasing order. In the literature, only six families of graphs with the smallest possible diameter were known, obtained by the method of dense tessellation on the plane of triangles corresponding to chordal ring graphs. A method that would allow one to massively obtain descriptions of families of optimal graphs in an analytical form was not known.

Progress in this direction is made in the present work. For the first time, we have built a large dataset of parameters of optimal chordal ring graphs with the number of vertices reaching 60 thousand and with an enumeration of all generators for optimal graphs, and we have proposed a metaheuristic approach for dataset mining. Using it, we found new patterns in the emergence of families of optimal graphs and, on their basis, generalized and expanded the list of families of optimal chordal rings, constructing more than 170 new analytically defined families of optimal graphs.

When searching for families of optimal chordal rings, generators of two types of functions of the diameter, linear and quadratic, were found, since the orders of the graphs under consideration are quadratic polynomials of the diameter. To solve the problem of searching for analytical descriptions of families of optimal chordal rings, our approach is based on setting templates of descriptions with underdetermined coefficients and uses, at the first stage, metaheuristic global optimization algorithms to determine promising template parameters and, at the second stage, an exhaustive local search in a given neighborhood to determine all possible descriptions of optimal families in it.

Based on the analysis of the obtained dataset of optimal chordal rings and previously known descriptions of six optimal families, several generalized templates were used for functions that describe orders and generators of graphs. According to these templates, analytical expressions for functions are automatically generated in the search process and their evaluation and modifications are performed. Thus, for fixed values of the diameter and coefficients from the given ranges of change, the required functions are calculated and their values are obtained in the form of a triple (order, generator, diameter) and compared with the values from the dataset.

The proposed approach to the search for analytical descriptions of families of optimal chordal rings was implemented in the Wolfram Mathematica 10 system. After the execution of the first stage, metaheuristic global optimization algorithms (differential evolution and ant colony algorithms) determined several promising values for the parameters of quadratic-type generator templates, the parameter of their occurrence periodicity, and possible boundaries of areas of change of values of other coefficients of templates. At the second stage, an exhaustive local search within the given limits of parameter variation made it possible to obtain four templates and sets of parameter values for them, which determined analytical descriptions of new families of optimal chordal rings.

The array of obtained data of optimal chordal rings can be used to study the relationships between families of optimal graphs and the corresponding characteristics of the communication network, such as average delays, throughput (bisection width), fault reliability, routing algorithms, etc.

Key words: metaheuristic search, analytic dependencies, chordal ring networks, template, optimal graphs.

Supported by state assignment of ICMMG SB RAS N 0251-2021-0005.

Bibliographic reference: Monakhova E.A., Monakhov O.G. Discovery of analytical dependences of parameters of optimal chordal ring networks based on data analysis //journal “Problems of informatics”. 2023, № 4. P.5-16. DOI:10.24412/2073-0667-2023-4-5-16

article

A.V. Korobov, D.A. Migov

Novosobirsk State University, 630090, Novosibirsk, Russia

Institute of Computational Mathematics and Mathematical Geophysics SB RAS, 630090, Novosibirsk, Russia

ALGORITHMS FOR CALCULATING NETWORK RELIABILITY BASED ON THE DECOMPOSITION APPROACH

When designing and developing networks in various spheres of human activity, related, for example, to the telecommunications and banking sectors, order confirmation and creditworthiness systems, and others, an important criterion is their reliability. The task of assessing the reliability of the network arises, as a rule, in two cases: qualitative analysis of existing systems or optimization in the design of new systems. Note also that when formulating this task, it is necessary to determine from which reliability criteria to proceed. In this paper, the classical indicator of its connectivity will be considered as a parameter of network reliability.

A mathematical model describing a network is usually a random graph in which the vertices represent the network nodes in question, such as workstations, routers, servers and other devices or structures, and the edges represent the communication channels of these objects. Each element of a random graph is present in it with a certain probability, expressing its reliability. The reliability of the network in this representation will be understood as the probability of connectivity of the vertices of the graph. Next, the paper will consider the problem of calculating the probability of connectivity of an undirected graph with absolutely reliable vertices, the probability of whose presence is equal to one, and unreliable edges, the probabilities of whose presence will be determined by some real numbers from the segment from zero to one.

The exact calculation of this indicator is NP-hard problem, which makes it difficult for networks of real dimension. Modifications of the factorization method used for accurate calculation are proposed, based on the decomposition of the network by a vertex cut (section, separator) formed by two vertices. For more efficient use of decomposition, the structural similarity of the resulting subgraphs is taken into account. As well as the graphs obtained from them by gluing the cutting vertices. Three algorithms have been developed that, on average, accelerate the process of calculating the probability of connectivity of an arbitrary graph. To compare the proposed algorithms with the factorization method and the factorization method with preliminary decomposition, the results of numerical experiments are presented.

Key words: network reliability, random graph, connectivity probability, factorization method, network decomposition, cut, separator.

The work was completed according to the project N 0251-2021-0005 ПФИ ИВМиМГ CO PAH.

Bibliographic reference: Korobov A.V., Migov D. A. Algorithms for calculating network reliability based on the decomposition approach //journal “Problems of informatics”. 2023, № 4. P.17-28. DOI:10.24412/2073-0667-2023-4-17-28.

article

V. M. Vishnevsky*. V.I. Klimenok**. A.M. Sokolov*. A. A. Larionov*

PERFORMANCE EVALUATION OF THE FORK-JOIN SYSTEM WITH MARKOVIAN ARRIVAL AND PHASE-TYPE SERVICE TIME DISTRIBUTION

In this paper, we examine a fork-join queueing system. Customers enter the system in a MAP (Markovian Arrival Process). Each of the customers entering the system forks into K tasks, to be served in K independent subsystems. Each subsystem consists of a server and a buffer. The service time of a task by the k-th server has a PH (Phase type) distribution with an irreducible representation (вк,Sk). For the special case when K = 2, the stationary distribution is obtained, and algorithms are presented to compute the stationary distribution, and performance characteristics of the fork-join system. We suggested an approach based on a combination of Machine learning and Monte-Carlo method to investigate the performance characteristics of fork-join system. The results of numerical experiments are presented in this paper.

Key words: fork-join system, Markovian Arrival process, Phase-Type distribution, stationary performance characteristics, Machine Learning.

 Bibliographic reference: Vishnevsky V.M., Klimenok V.I., Sokolov A.M., Larionov A. A. Performance evaluation of the fork-join system with Markovian Arrival and Phase-Type service time distribution //journal “Problems of informatics”. 2023, № 4. P.29-56. DOI:10.24412/2073-0667-2023-4-29-56

article

S. V. Bredikhin, N. G. Scherbakova, A. N. Yurgenson

Institute of Computational Mathematics and Mathematical Geophysics SB RAS, 630090, Novosibirsk, Russia

SCIENTIFIC JOURNAL CO-AUTHORSHIP NETWORK MODELS. PART 2

The paper analyzes two models of a scientific co-authorship network. The first model (Na) is built on binary relationships that arise between authors who have jointly created at least one article. This traditional model is presented in the form of an undirected graph, the vertices of which correspond to the authors, and the edges establish connections between them. The second model (Ncaf which takes into account group relations between the authors of a same article, is presented in the form of a bipartite graph. A higher-order architecture that generalizes pairwise interaction to the interaction of an arbitrary set of nodes helps expand the capabilities of modeling and understanding the behavior of a co-authorship system. This work continues the study and testing of methods for analyzing co-authorship networks [1, 2].

Methods for constructing both models based on data extracted from an XML archive of scientific journal articles are presented. The basic parameters of the models were measured, for results see table 2. It should be noted that Nca network contains significantly fewer edges than Na, which is important when studying large amounts of data. It is revealed that the distribution of degrees of the vertices of both subsets of bipartite representation corresponds to the power law, see fig. 2. The average distance between Nca nodes is approximately six, i. e. we can apply the term “small world” [40] to it.

The centralities of the actors [32-36] that determine their potential to influence processes occurring in the network are estimated. Using the small component as an example (fig. 3), it is shown that the Nca nodes are more differentiated within the corresponding measure, see tables 3-4.

Co-authorship patterns are identified based on a study of bicliques in a bipartite representation. Analysis of bicliques showed that for this co-authorship system, the most common pattern is the presence of pairs of authors who jointly published two articles. The next most common pairs are the more stable pairs, who published three articles each, and the triplets of authors, who published two articles each. Fig. 4 illustrates the distribution of Ki,2- Further examination of bicliques can determine which authors participate in multiple groups and whether the group of authors is expanding over time.

Key words: data analysis, bibliometry, scientific co-authorship, bipartite graph, XML-archive, network parameters, centrality of actors, collaboration patterns.

This work was carried out under state contract with ICMMG SB RAS (0251-2021-0005).

Bibliographic reference: Bredikhin S. V., Scherbakova N. G., Yurgenson A.N. Scientific journal co-authorship network models. Part 2 //journal “Problems of informatics”. 2023, № 4. P.57-72. DOI:10.24412/2073-0667-2023-4-57-72

article

M. P. Bakulina

Institute of Computational Mathematics and Mathematical Geophysics SB RAS, 630090, Novosibirsk, Russia

INCREASING EFFICIENCY OF IMAGE COMPRESSION BASED ON THE RLE METHOD

In this article the problem of increasing efficiency of image compression is considered. As is known, digital image intended for transmission or storage is converted to a raster image. The RLE method based on run lengths coding is especially effective for raster images with large single-color areas. Based on RLE algorithm and arithmetic code a new algorithm for run lengths coding is proposed. This algorithm gives an increase of compression ratio of raster images compared to RLE.

Key words: lossless coding, digital image, RLE, compression ratio.