maisМоделирование и анализ информационных системModeling and Analysis of Information Systems1818-10152313-5417Yaroslavl State University10.18255/1818-1015-2014-6-155-168mais-79Research ArticleОригинальные статьиArticlesПрограммный комплекс для анализа и визуализации графовSoftware for Graph Analysis and VisualizationКоломейченкоМаксим ИгоревичKolomeychenkoM. I.

магистр, 101000 Россия, г. Москва, ул. Мясницкая, 20

магистр, Myasnitskaya str., 20, Moscow, 101000, Russia

maxim.kolomeychenko@mail.ruЗолотыхАлексей АндреевичZolotyhA. A.

аспирант, 127550 Россия, г. Москва, ул. Прянишникова, 2А

аспирант, Pryanishnikova str., 20, Moscow, 127550, Russia

azolotykh@mail.ruПоляковИгорь ВикторовичPolyakovI. V.

канд. физ.-мат. наук, 101000 Россия, г. Москва, ул. Мясницкая, 20

канд. физ.-мат. наук, Myasnitskaya str., 20, Moscow, 101000, Russia

igorp86@mail.ruЧеповскийАндрей МихайловичChepovskiyA. M.

канд. техн. наук, доцент, 101000 Россия, г. Москва, ул. Мясницкая, 20

канд. техн. наук, доцент, Myasnitskaya str., 20, Moscow, 101000, Russia

achepovskiy@hse.ruНациональный исследовательский университет "Высшая школа экономики"РоссияNational Research University Higher School of EconomicsRussian FederationМосковский государственный университет печати имени Ивана ФедороваРоссияMoscow State University of Printing ArtsRussian Federation201420122014216155168Copyright © Коломейченко М.И., Золотых А.А., Поляков И.В., Чеповский А.М., 20142014Коломейченко М.И., Золотых А.А., Поляков И.В., Чеповский А.М.Kolomeychenko M.I., Zolotyh A.A., Polyakov I.V., Chepovskiy A.M.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://www.mais-journal.ru/jour/article/view/79

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

This paper describes the software for graph storage, analysis and visualization. The article presents a comparative analysis of existing software for analysis and visualization of graphs, describes the overall architecture of application and basic principles of construction and operation of the main modules. Furthermore, a description of the developed graph storage oriented to storage and processing of large-scale graphs is presented. The developed algorithm for finding communities and implemented algorithms of autolayouts of graphs are the main functionality of the product. The main advantage of the developed software is high speed processing of large size networks (up to millions of nodes and links). Moreover, the proposed graph storage architecture is unique and has no analogues. The developed approaches and algorithms are optimized for operating with big graphs and have high productivity.

графанализ графавизуализация графаграфовое хранилищеархитектура программного обеспеченияgraphgraph analysisgraph visualizationgraph storagesoftwareReferencesЧураков А. Н. Анализ социальных сетей // СоцИс. 2001. № 1. С. 109–121. [Churakov A.N. Analiz sotsial’nykh setey // SotsIs. 2001. No 1. S. 109–121 (in Russian)].Чураков А. Н. Анализ социальных сетей // СоцИс. 2001. № 1. С. 109–121. [Churakov A.N. Analiz sotsial’nykh setey // SotsIs. 2001. No 1. S. 109–121 (in Russian)].Kaufmann, Wagner. Drawing Graphs // Springer, 2001. P. 1–274.Kaufmann, Wagner. Drawing Graphs // Springer, 2001. P. 1–274.Battista, Tamassia, Tollis. Graph Drawing : Algorithms for the Visualization of Graphs // Springer, 1999. P. 1–430.Battista, Tamassia, Tollis. Graph Drawing : Algorithms for the Visualization of Graphs // Springer, 1999. P. 1–430.Newman M. E. Networks: An Introduction // Oxford, UK: Oxford University Press, 2010. P. 1–784.Newman M. E. Networks: An Introduction // Oxford, UK: Oxford University Press, 2010. P. 1–784.i2 Analyst’s Notebook. URL: http://www-03.ibm.com/software/products/ru/analystsnotebook. 05.04.2014.i2 Analyst’s Notebook. URL: http://www-03.ibm.com/software/products/ru/analystsnotebook. 05.04.2014.Sentinel Visualyzer. URL: http://www.fmsasg.com/Products/SentinelVisualizer. 05.04.2014.Sentinel Visualyzer. URL: http://www.fmsasg.com/Products/SentinelVisualizer. 05.04.2014.CrimeLink. URL: http://www.pciusa.us/Crimelink.aspx. 05.04.2014.CrimeLink. URL: http://www.pciusa.us/Crimelink.aspx. 05.04.2014.Tom Sawyer. URL: http://www.tomsawyer.com. 05.04.2014.Tom Sawyer. URL: http://www.tomsawyer.com. 05.04.2014.XAnalys Link Explorer. URL: http://www.xanalys.com/solutions/linkexplorer.html. 05.04.2014.XAnalys Link Explorer. URL: http://www.xanalys.com/solutions/linkexplorer.html. 05.04.2014.

The authors declare that there are no conflicts of interest present.