Оптимізація графових укладань для мереж із структурою спільнот

Abstract

У даній магістерській роботі досліджується задача візуалізації графів із акцентом на відображення їхньої спільнотної структури. Запропоновано підхід, заснований на поєднанні алгоритму Камада–Каваї з нейромережевим прискоренням (KamadaNN), який дозволяє отримувати вкладення графів у евклідовий простір із збереженням як глобальних, так і локальних структурних властивостей. Особливу увагу приділено оцінюванню якості отриманих укладок у контексті подальшого виявлення спільнот. Експериментальне дослідження проведено на кількох сімействах графів, зокрема симетричних графах із чітко вираженими спільнотами, несиметричних графах зі спільнотною структурою, а також графах без чітких спільнот. Для кожного графа застосовано різні алгоритми виявлення спільнот, включаючи Louvain, Girvan–Newman, greedy modularity та Label Propagation. Якість результатів оцінювалась за сукупністю метрик, серед яких коефіцієнт силуету, індекс Девіса–Болдіна, нормалізовані показники компактності та сепарованості, метрика найближчих сусідів, а також оцінка перекриття випуклих оболонок. Отримані результати показують, що для графів із чіткою спільнотною структурою алгоритм KKNN демонструє стабільну перевагу над методом NeuLay-2 за всіма розглянутими метриками. Для більш складних випадків, зокрема несиметричних графів та графів без виражених спільнот, обидва підходи демонструють конкурентні результати, підкреслюючи різні аспекти структури графа: KKNN краще відображає глобальну компактність і узгодженість кластерів, тоді як NeuLay-2 у ряді випадків ефективніше зберігає локальні зв’язки між вершинами. Таким чином, запропонований підхід є ефективним інструментом для 2 візуалізації графів із різною структурою та може бути використаний у задачах аналізу складних мереж, де важливим є коректне відображення спільнотної організації.

In this master's thesis the problem of graph visualization with a focus on accurately representing community structure is considered. A method based on combining the Kamada–Kawai algorithm with neural network acceleration (KKNN) is proposed, enabling the construction of graph embeddings in Euclidean space while preserving both global and local structural properties. Particular attention is given to evaluating the quality of the obtained embeddings in the context of subsequent community detection. The experimental study is conducted on several families of graphs, including symmetric graphs with clearly defined communities, asymmetric graphs with community structure, and graphs without well-defined communities. For each graph, multiple community detection algorithms are applied, including Louvain, Girvan Newman, greedy modularity, and Label Propagation. The quality of the results is evaluated using a set of metrics, such as the silhouette coefficient, Davies–Bouldin index, normalized compactness and separability, the k-nearest neighbors metric, and convex hull overlap. The results show that for graphs with well-defined community structure, the KKNN algorithm consistently outperforms NeuLay-2 across all considered metrics. For more complex cases, including asymmetric graphs and graphs without clear community structure, both approaches demonstrate competitive performance, highlighting different aspects of graph structure: KKNN better captures global compactness and cluster coherence, while NeuLay-2, in some cases, more effectively preserves local relationships between nodes. In conclusion, the proposed approach is an effective tool for visualizing graphs with varying structural properties and can be applied to the analysis of complex networks where accurate representation of community structure is essential.