Скрыть
Раскрыть

ISSN 1998-0663 (print),
ISSN 2587-8166 (online)

English version: ISSN 2587-814X (print),
ISSN 2587-8158 (online)

Коломейченко М. И. 1, Чеповский А. М. 1,2
  • 1 НИУ ВШЭ, 101000, Россия, Москва, ул. Мясницкая, д.20
  • 2 Институт коммуникаций и медиабизнеса, Московский государственный университет печати им. Ивана Федорова, 127550, г. Москва, ул. Прянишникова, 2а.

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

2014. № 4 (30). С. 7–16 [содержание номера]

Коломейченко Максим Игоревич - выпускник магистратуры, Национальный исследовательский университет «Высшая школа экономики»;
Адрес: 101000, Москва, Мясницкая ул., 20.
E-mail: maxim.kolomeychenko@mail.ru   

Чеповский Андрей Михайлович - кандидат технических наук, доцент кафедры информационной безопасности, факультет бизнес-информатики, Национальный исследовательский университет «Высшая школа экономики»; профессор кафедры прикладной математики и моделирования систем, Институт коммуникаций и медиабизнеса, Московский государственный университет печати им. Ивана Федорова. 
Адрес: 127550, г. Москва, ул. Прянишникова, 2а.
E-mail: achepovskiy@hse.ru  

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

BiBTeX
RIS
 
 
Rambler's Top100 rss