Оптимiзацiя укладань графiв з використанням проекцiй з багатовимiрних просторiв

Abstract

У данiй магiстерськiй роботi дослiджується задача вiзуалiзацiї графiв iз використанням бага товимiрного укладання та подальшої проєкцiї у двовимiрний простiр. Основну увагу придiлено пiдходу Nd →2d, за якого граф спочатку оптимiзується у просторi пiдвищеної розмiрностi, а потiм отрима не розташування вершин проєктується на площину. Така схема розглядається як спосiб покращення структурної органiзацiї графового укладання, зокрема для регулярних, симетричних i багатовимiрно органiзованих графiв. У роботi розглянуто основнi класи методiв укладання графiв: силовi алгори тми, методи мiнiмiзацiї стресу, геометричнi та детермiнованi укладання, багатовимiрнi, багаторiвневi, спектральнi та нейромережевi пiдходи. Окремо сформульовано математичну модель багатовимiрного укладання, у якiй якiсть розташування вершин описується через узгодження геометричних вiдстаней мiж точками з топологiчними вiдстанями у графi. Як основний iнструмент оптимiзацiї використано алгоритм Kamada–Kawai у просторi довiльної розмiрностi, а для переходу до площинного зображення застосовано метод головних компонент PCA. Запропонований алгоритм реалiзовано мовою Python у середовищi Google Colab з використанням бiблiотек NetworkX, NumPy, pandas, matplotlib та openpyxl. Програмна реалiзацiя забезпечує побудову тестових графiв, виконання багатовимiрного укладання, PCA-проєкцiю у двовимiрний простiр, вимiрювання часу роботи окремих етапiв, формування Excel таблиць i побудову рисункiв. Код i результати експериментiв розмiщено у репозиторiї дослiдження, що забезпечує вiдтворюванiсть отриманих результатiв. Експериментальне дослiдження проведено на кiль кох класах регулярних i симетричних графiв. Основним тестовим класом стали гiперкуби Q4, Q6, Q8, Q10 та Q12, для яких природна розмiрнiсть визначається безпосередньо їхньою комбiнаторною стру ктурою. Додатково розглянуто повнi графи K4, K6, K8, K10, K12, граф Геммiнга H(4,2), граф октаедра та тороїдальну сiтку 4×4. Для аналiзу використовувалися часовi характеристики Kamada–Kawai, PCA та сумарного часу, а також якiсне порiвняння вiзуальної структури отриманих укладань. Отриманi результати показують, що етап PCA практично не впливає на сумарний час побудови укладання, а основне обчислювальне навантаження припадає на багатовимiрну оптимiзацiю Kamada–Kawai. Для гiперкубiв попередня оптимiзацiя у просторi бiльшої розмiрностi у низцi випадкiв дозволяє краще ви явити регулярну структуру графа: шари, симетрiї, паралельнi групи ребер та характернi кубiчнi пiд структури. Водночас природна розмiрнiсть не завжди є найкращим вибором для кiнцевої двовимiрної проєкцiї, що показує необхiднiсть експериментального пiдбору промiжної розмiрностi. Таким чином, пiдхiд Nd → 2d є перспективним iнструментом для вiзуалiзацiї регулярних, симетричних i багатовимiр но органiзованих графiв. Вiн може бути використаний для аналiзу гiперкубiв, графiв Геммiнга, графiв Келi, кристалiчних i молекулярних структур, а також iнших дискретних об’єктiв iз природною бага товимiрною органiзацiєю. Подальшi дослiдження доцiльно спрямувати на кiлькiсне оцiнювання якостi укладань за додатковими метриками, порiвняння PCA з iншими методами проєкцiї та застосування запропонованого пiдходу до ширших класiв графiв.

This master’s thesis investigates the problem of graph visualization using multidimensional graph layout followed by projection into a two-dimensional space. The main focus is placed on the Nd → 2d approach, in which a graph is first optimized in a higher-dimensional space and then the resulting vertex configuration is projected onto a plane. This scheme is considered as a way to improve the structural organi zation of graph layouts, particularly for regular, symmetric, and multidimensionally organized graphs. The thesis reviews the main classes of graph layout methods: force-directed algorithms, stress minimization methods, geometric and deterministic layouts, multidimensional, multilevel, spectral, and neural-network based approaches. A mathematical model of multidimensional graph layout is formulated, in which the quality of vertex placement is described through the correspondence between geometric distances among points and topological distances in the graph. The Kamada–Kawai algorithm in an arbitrary-dimensional space is used as the main optimization tool, while Principal Component Analysis (PCA) is applied to obtain the final two-dimensional representation. The proposed algorithm is implemented in Python in the Google Colab environment using the NetworkX, NumPy, pandas, matplotlib, and openpyxl libraries. The software implementation supports the generation of test graphs, multidimensional layout construction, PCA projecti on into two-dimensional space, measurement of execution time for individual stages, creation of Excel tables, and generation of visualizations. The code and experimental results are stored in the research repository, ensuring the reproducibility of the obtained results. The experimental study was conducted on several classes of regular and symmetric graphs. The main test class consists of hypercubes Q4, Q6, Q8, Q10, and Q12, for which the natural dimensionality is directly determined by their combinatorial structure. In addition, complete graphs K4, K6, K8, K10, and K12, the Hamming graph H(4,2), the octahedral graph, and the toroidal grid 4×4 were considered. The analysis used execution-time characteristics of the Kamada–Kawai stage, the PCA stage, and the total runtime, as well as a qualitative comparison of the visual structure of the obtained layouts. The obtained results show that the PCA stage has almost no effect on the total layout construction time, while the main computational cost is associated with the multidimensional Kamada–Kawai optimization. For hypercubes, preliminary optimization in a higher-dimensional space in a number of cases makes it possible to reveal the regular structure of the graph more clearly, including layers, symmetries, parallel classes of edges, and characteristic cubic substructures. At the same time, the natural dimensi onality is not always the best choice for the final two-dimensional projection, which demonstrates the need for experimental selection of the intermediate dimensionality. Thus, the Nd → 2d approach is a promising tool for visualizing regular, symmetric, and multidimensionally organized graphs. It can be applied to the analysis of hypercubes, Hamming graphs, Cayley graphs, crystalline and molecular structures, as well as other discrete objects with a natural multidimensional organization. Further research should focus on the quantitative evaluation of layout quality using additional metrics, comparison of PCA with other projection methods, and application of the proposed approach to broader classes of graphs. General characteristics of the thesis: the thesis consists of an introduction, 4 chapters, chapter conclusions, and a list of references. The thesis contains 30 pages, 12 figures, 5 tables, and 34 references. Keywords: graph, graph visualization, graph layout, multidimensional layout, Kamada–Kawai, PCA, projection, stress, hypercube, regular graphs, symmetric graphs.