Applying multiheuristic approach o randomly generating graphs with a given degree sequence

Background. Graphs with a given degree sequence are often regarded as models for many complex tasks. This makes it necessary to study algorithms for generating graphs with a given degree sequence. The purpose of this study is to review the existing methods and to develop our own algorithm for generating a graph with a given degree sequence. The authors give the definition of a graphic sequence, as well as the criteria to check whether a given sequence is graphic or not. Results. The paper presents the algorithm developed by the authors which is based on one of the screening criteria of the multiheuristic approach (the branch and bound method). The paper also presents the notion of the second-order degree sequence and the modification of the developed algorithm for generating random graphs with a given second-order degree sequence. This modification is also based on the branch and bound method. Thus, a new approach to the generation of random graphs has been proposed. In the computational experiments based on some distribution functions the sequence of a given size (the predicted number of graph nodes) was generated. If the generated sequence is graphical, the graph can be generated on its basis. Then, another graph based on second-order degree sequence was generated. The average execution time (in milliseconds) within the different distribution functions and different dimensions of the graph was stated. Conclusions. These different options for generating random graphs can be useful in many applications, especially in network models, the most important of them being mathematical models of the Internet and social networks, as well as artificial neural networks. Another possible direction for continuation of the research described in this paper is a “tuning” of specific algorithms for solving discrete optimization problems (e.g. the problem of testing isomorphism in specific areas of the graph application).