Н.В. Блохин1

1Финансовый университет при Правительстве Российской Федерации (Москва, Россия)

1nvblokhin@fa.ru

Постановка проблемы. Визуализация играет ключевую роль в анализе сетевых структур, позволяя исследователям наглядно выявлять структурные особенности, закономерности и взаимосвязи. В процессе исследования часто возникает необходимость фокусирования на конкретном узле и его окрестности для детального изучения локальной структуры графа. Такого эффекта можно достигнуть за счет придания укладке иерархической структуры. Однако традиционные методы построения укладок либо не предназначены для построения такого вида визуализаций, либо предназначены исключительно для работы с деревьями. Кроме этого важным аспектом реальных сетей является наличие дополнительных атрибутов узлов и ребер. Тем не менее классические алгоритмы, как правило, игнорируют эту информацию, что потенциально снижает качество получаемых визуализаций. Используя современные методы машинного обучения, можно построить гибкий алгоритм, который может использовать дополнительную информацию об элементах сети и объединяет преимущества классических подходов с возможностью формирования иерархической структуры укладки для повышения ее читаемости.

Цель. Разработать алгоритм построения укладки графа, который сочетает преимущества классических силовых методов с возможностью фокусирования на окрестности заданного узла путем формирования иерархической структуры визуализации, а также учитывает дополнительные атрибуты элементов графа.

Результаты. Предложен гибридный метод визуализации графов, объединяющий графовые нейронные сети и силовые алгоритмы с введением концентрической силы для фокусировки на заданном узле. Проведен анализ на модельных и реальных графах. Показано влияние атрибутов узлов на качество и структуру укладки.

Практическая значимость. Разработанный алгоритм может быть использован для визуализации реальных сетей в прикладных задачах анализа графов.

Блохин Н.В. Метод построения иерархической укладки графов на основе силовых алгоритмов и графовых нейронных сетей // Информационно-измерительные и управляющие системы. 2025. Т. 23. № 3. С. 37−46. DOI: https://doi.org/10.18127/ j20700814-202503-04

1. Ylinen H. Improvements to a Force-Directed Method for Graph Drawing: выпускная квалификационная работа магистра. Хельсинки. 2003. 91 с.
2. Zachary W. An information flow model for conflict and fission in small groups // Journal of Anthropological Research. 1977. № 33. С. 452−473.
3. Kobourov S. Spring embedders and force directed graph drawing algorithms. Preprint arXiv:1201.3011. 2012.
4. Eades P. A heuristic for graph drawing // Congressus numerantium. 1984. № 42. С. 149−160.
5. Fruchterman T., Reingold E. Graph drawing by force-directed placement // Software: Practice and Experience. 1991. № 11. С. 1129−1164.
6. Kamada T., Kawai S. An algorithm for drawing general undirected graphs // Inform. Process. Lett. 1989. № 31. С. 7−15.
7. Herman I., Melancon G., Marshall M. Graph visualization and navigation in information visualization: A survey // IEEE Transactions on Visualization and Computer Graphics. 2000. № 1. С. 24−43.
8. Both C., Dehmamy N., Yu R., Barabási A. Accelerating network layouts using graph neural networks // Nature Communications. 2023. Т. 14.
9. Huang W., Luo J., Bednarz T., Duh H. Making Graph Visualization a User-Centered Process // Journal of Visual Languages & Computing. 2018. Т. 48.
10. Bennett C., Ryall J., Spalteholz L., Gooch A. The Aesthetics of Graph Visualization // Proceedings of Computational Aesthetics in Graphics. Visualization and Imaging. 2007. С. 57−64.
11. Gilmer J., Schoenholz S., Riley P., Vinyals O., Dahl G. Message passing neural networks // Machine Learning Meets Quantum Physics. 2020. С. 199−214.
12. Kipf T., Welling M. Semi-Supervised Classification with Graph Convolutional Networks. ArXiv abs/1609.02907. 2016.
13. PyG Documentation. URL: https://pytorch-geometric.readthedocs.io/ (дата обращения: 25.01.2025).
14. NetworkX documentation. URL: https://networkx.org/ (дата обращения: 25.01.2025).
15. Lamping J., Rao R. The Hyperbolic Browser: A Focus + Context Technique for Visualizing Large Hierarchies // J. Vis. Lang. Comput. 1996. Т. 7. С. 33−55.