Визуализация И Анализ Графов Больших Размеров

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