Визуализация и анализ графов больших размеров

Коломейченко М. И. and Чеповский А. М.
Additional contact information
Коломейченко М. И.: Национальный исследовательский университет «Высшая школа экономики»
Чеповский А. М.: Национальный исследовательский университет «Высшая школа экономики»

Бизнес-информатика, 2014, issue 4 (30), 7-16

Abstract: Задача визуализации графов больших размеров возникает в различных областях социологии и маркетинга. Актуальность данной работы определяется потребностью в программном комплексе для анализа и визуализации таких графов. В работе приводится анализ нескольких программных продуктов и выделяются их недостатки: отсутствие кроссплатформенности и специализированных графовых хранилищ, а также невозможность работы с графами больших размеров. Приводится детальное описание общей архитектуры разработанного программного обеспечения и каждого модуля в отдельности, способы взаимодействия основных модулей. Для хранения графов используется разработанное специализированное графовое хранилище, позволяющее обрабатывать графы, имеющие порядка 100 миллионов вершин и нескольких миллиардов связей. Также представлено описание основных принципов организации хранилища. Использование собственной файловой системы обеспечивает отсутствие дополнительных системных вызовов при работе с хранилищем и отсутствие сложной системы адресации и лишних механизмов, что приводит к избавлению от дополнительных накладных расходов, связанных с организацией хранения данных. Кроме того, присутствует описаниеметодикиработымодуля визуализации данных, используемых структур данных и алгоритмов машинной графики, которые позволяют работать с графами, состоящими из нескольких миллионов вершин, в режиме реального времени. Отдельно стоит отметить широкий набор алгоритмов автоматического размещения графов: случайное размещение, круговое размещение, круговое покомпонентное размещение, размещение «павлиний хвост», размещения «одна и две линии темы», размещения, основанные на алгоритме выделения сообществ или на алгоритме оценки связности. Приводится детальное описание каждого приведенного выше алгоритма. Особое внимание стоит уделить используемым методам анализа графа. Разработаны алгоритмы выделения сообществ в социальных сетях, оценки связности графа, поиск кратчайших путей между любой парой вершин, объединение и пересечение графов и многое другое. Ключевой особенностью всех приведенных в работе алгоритмов является возможность работы с графами больших размеров.

Keywords: ГРАФ; АНАЛИЗ ГРАФА; ВИЗУАЛИЗАЦИЯ ГРАФА; ГРАФОВОЕ ХРАНИЛИЩЕ; АВТОРАЗМЕЩЕНИЕ (search for similar items in EconPapers)
Date: 2014
References: Add references at CitEc
Citations:

Downloads: (external link)
http://cyberleninka.ru/article/n/vizualizatsiya-i-analiz-grafov-bolshih-razmerov

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:scn:025686:15695851

Access Statistics for this article

More articles in Бизнес-информатика from CyberLeninka, Федеральное государственное автономное образовательное учреждение высшего образования «Национальный исследовательский университет «Высшая школа экономики»
Bibliographic data for series maintained by CyberLeninka ().