Математическое и программное обеспечение визуального анализа графовой информации сети взаимодействующих объектов тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат наук Коломейченко, Максим Игоревич

• Коломейченко, Максим Игоревич
• кандидат наук
• 2016

Оглавление диссертации кандидат наук Коломейченко, Максим Игоревич

СОДЕРЖАНИЕ

ВВЕДЕНИЕ

ГЛАВА 1. Средства визуального анализа графа

1.1. Программное обеспечение для анализа графов

1.2. Многополосное размещение

1.3. Визуальный анализ структуры графа взаимодействующих объектов на основе выделения «сообществ»

1.4. Выводы по 1 главе

ГЛАВА 2. Геометрические модели автоматических размещений объектов графа на плоскости

2.1. Базовые геометрические модели автоматического размещений

2.2. Геометрическая модель автоматического размещений на основе метода физических аналогий

2.3. Многополосное размещение

2.4. Выводы по 2 главе

ГЛАВА 3. Визуальный анализ графа социальной сети, допускающего выделение подграфов

3.1. Методика выделения сообществ

3.2. Вычислительные эксперименты

3.3. Построение геометрической модели автоматического размещения объектов графа с выделенными сообществами

3.4. Выводы по 3 главе

ГЛАВА 4. Программный комплекс визуального анализа графов

4.1. Общая архитектура программного комплекса

4.2. Хранение данных

4.3. Используемые структуры данных

4.4. Инструменты анализа

4.5. Выводы по 4 главе

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

СПИСОК ЛИТЕРАТУРЫ

ПРИЛОЖЕНИЕ А. Описание функциональности программного комплекса

ПРИЛОЖЕНИЕ Б. Акты внедрения

230

Введение диссертации (часть автореферата) на тему «Математическое и программное обеспечение визуального анализа графовой информации сети взаимодействующих объектов»

ВВЕДЕНИЕ

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

Несмотря на многообразие библиотек для создания инструментов визуализации сетей, в существующих программных продуктах наблюдается ряд недостатков: отсутствие платформенно-независимых решений, отсутствие собственных специализированных хранилищ, человеко-машинные интерфейсы систем не ориентированы на аналитическую работу с графами больших размеров по причине отсутствия встроенных в системы визуализации многих эффективных методов автоматического размещения объектов (многополосное размещение, разделение по группам взаимосвязанных объектов).

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

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

Объект исследования - параметры расположения объектов графа на плоскости при его визуальном представлении в программном интерфейсе.

Предмет исследования - методы и алгоритмы автоматического размещения объектов графа при его визуализации в человеко-машинном интерфейсе программ анализа структуры графа.

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

Для достижения поставленной цели требуется решение следующих задач:

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

2. Разработать алгоритмы для создания процедур нахождения и визуализации связанных групп вершин (сообществ) в анализируемых графах.

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

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

Научная новизна результатов исследования состоит в том, что 1. Разработан алгоритм автоматического размещения «быстрый павлиний хвост», основанный на методе физических аналогий и оптимизирующий скоростные

характеристики алгоритма метода физических аналогий за счет анализа только локальной области на плоскости.

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

3. Разработан и реализован метод выделения групп взаимодействующих объектов, применимый к большим данным реальных сетей.

4. Разработана и реализована в программном интерфейсе геометрическая модель автоматического размещения на плоскости групп связанных вершин (сообществ) графа.

Практическая значимость. Научные и практические результаты диссертации использованы при разработке информационных систем и проведения научно-исследовательских и опытно-конструкторских работ, о чем свидетельствуют: акт о внедрении результатов диссертационного исследования, предоставленный ЗАО «Медианн-Решения»: акт об использовании результатов диссертации, предоставленный Международным Центром по Ядерной безопасности (АНО МЦЯБ); акт о внедрении результатов диссертационного исследования, предоставленный АО РДТЕХ. Результаты диссертации использованы в учебном пособии [84].

Результаты исследований по теме диссертационной работы использованы при выполнении научно-исследовательских работ по следующим грантам РФФИ: • Проект № 16-07-00641 «Исследование и разработка математических моделей, методов и алгоритмов визуализации и анализа графов на примере социальных сетей»

• Проект N° 16-29-09546 «Разработка новых методов мониторинга и комплексного лингвистического и тематического анализа сообщений социальных медиа в целях противодействия экстремизму и терроризму».

Основные положения, выносимые на защиту:

1. Методика оптимизации скоростных характеристик алгоритма построения размещения объектов для визуализации связей графа на основе метода физических аналогий.

2. Алгоритмы построения многополосного размещения для визуализации связей выделенного множества объектов графа.

3. Геометрическая модель и алгоритм для выделения в графе групп связанных вершин (сообществ) и автоматического их размещения на плоскости с целью визуального анализа в рамках программного интерфейса.

4. Архитектура программного комплекса визуализации и хранения графов больших размеров с целью анализа их структуры средствами человеко-машинного интерфейса и используемые в программном комплексе структуры данных.

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

Апробация работы. Материалы диссертации докладывались на международных конференциях: Международной конференции по физико-

технической информатике CPT-2013, 12-19 мая 2013 г., Ларнака, Республика Кипр; Международной научной конференции Международного центра по ядерной безопасности Института физико-технической информатики SCVRT2013, Протвино, 25-29 ноября 2013 г.; Ершовской конференции по информатике 2014, Санкт-Петербург, 2014 г.; Международной научной конференции по физико-технической информатике (CPT2015), 10-17 мая 2015 г., Ларнака, Республика Кипр; III Международной научно-практической конференции «Управление информационной безопасностью в современном обществе», Москва, 19-21 мая

2015 г.; IV Международной научно-практической конференции «Управление информационной безопасностью в современном обществе», Москва, 31 мая-2 июня

2016 г.; Международной научной конференции по физико-технической информатике (CPT2016), 8-15 мая 2016 г., Ларнака, Республика Кипр; 26 Международной конференции GraphiCon2016, Нижний Новгород, 19-23 сентября 2016 г.; Международной научной конференции Московского физико-технического института (государственного университета) и Института физико-технической информатики (SCVRT16), Протвино, 21-24 ноября 2016 г.

Публикации. Основные результаты исследований изложены в 10 научных трудах [74 - 83], 4 из которых [74 - 77] опубликованы в изданиях, рекомендованных ВАК, или приравненных к ним изданиям.

Личный вклад автора. Основные научные результаты получены автором лично. К основным научным результатам, полученным автором лично относятся нижеперечисленные положения, опубликованные в работах из списка литературы:

• методики построения размещения объектов для визуализации связей графа на основе метода физических аналогий и их реализация в [74, 75, 82, 83];

• алгоритмы построения многополосного размещения для визуализации связей выделенного множества объектов графа и их реализация в [75, 80];

• алгоритмы выявления сообществ графа взаимодействующих объектов с целью визуализации структуры графа на плоскости в [76, 77];

• эффективные структуры данных для хранения индексов и графов больших размеров в [74, 78, 81];

• архитектура комплекса визуализации и анализа графов больших размеров и ее реализация в [74, 75, 79, 82, 83];

Другим соавторам принадлежат математические обоснования алгоритмов, внедрение разработанных моделей и алгоритмов.

Структура и объем работы. Диссертация состоит из введения, четырех глав, выводов, библиографического списка, включающего в себя 84 наименования, и одного приложения. Работа содержит 156 страниц машинописного текста основной части, включающих 60 рисунков, 1 таблицу и 10 страниц библиографии, включающей в себя 84 наименования, Приложение А содержит 73 страницы текста, включающих 76 рисунков. Приложение Б содержит три акта о внедрении.

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

Во второй главе «Геометрические модели автоматических размещений объектов графа на плоскости» описаны геометрические модели для автоматического размещения графа на плоскости, позволяющие делать эффективный визуальный анализ структуры графа. Описана геометрическая модель автоматического размещений объектов графа на плоскости, базирующегося на методе физических аналогий. Разработаны геометрические модели, позволяющие реализовывать многополосное размещение объектов графа.

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

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

В «Основных результатах работы» сформулированы основные выводы и результаты диссертационной работы.

В Приложении А описана основная функциональность интерфейса разработанного программного комплекса.

Приложение Б содержит акты о внедрении

ГЛАВА 1. Средства визуального анализа графа

1.1. Программное обеспечение для анализа графов

1.1.1.Существующие средства анализа

При анализе графов взаимодествующих объектов, социальных сетей возникает задача визуального представления их структур [3, 18, 38]. Необходимое для этого программное обеспечения должно предоставлять широкие возможности для визуализации и анализа сетей c большим количеством вершин. Область применения такого программного обеспечения обширна [3, 18, 52] и затрагивает многие смежные дисциплины, такие как социология, психология, политология, маркетинг.

Существует много промышленных продуктов для анализа графов. Например, i2 Analyst's Notebook [37], Sentinel Visualizer [65], CrimeLink [24], Xanalys Link Explorer [71], Gephi [32], Tom Sawyer Software [67], igraph [36], NetMiner4 [49], Cytoscape [25], VisuaLyzer [70], Tulip [68], COSBILab [23], Графоанализатор [4], GraphViz [34], yED [73], aiSee [16], Visual Graph [9, 69].

Gephi [32] - инструмент для аналитиков данных и исследователей, позволяющий проводить анализ и визуализацию графов (Рис. 1.1). У пользователя есть возможность управлять визуальным представлением графа и интерактивно взаимодействовать с ним. Основные характеристики Gephi:

• исходный код: доступен (open-source);

• операционная система: Windows, Mac OS X and Linux;

• форматы импорта: txt, csv, xls, graphml;

• интерактивное взаимодействие с графом: инструменты визуализации и навигации, инструменты редактирования графа и его визуального представления;

• ограничения на визуализацию: до 100 000 вершин и 1 000 000 связей;

• алгоритмы авторазмещений: круговое размещение, гео-размещение, 4 алгоритма на основе метода физических аналогий, радиальное размещение;

• дополнительные инструменты анализа: выделение сообществ, подсчет метрик центральности вершин и связей.

Рис. 1.1. Gephi - пример пользовательского интерфейса.

NetMiner [49] - коммерческий программный продукт для анализа и визуализации больших социальных сетей, основные характеристики которого:

• исходный код: недоступен;

• операционная система: Windows XP/ Vista/ 7 / 8;

• форматы импорта: xls (excel) , xlsx (excel 2007), csv (text), dl (ucinet), net (pajek), dat(stocnet), gml, nmf;

• интерактивное взаимодействие с графом (Рис. 1.2): инструменты визуализации и навигации, инструменты редактирования графа и его визуального представления;

• ограничения на визуализацию: по утверждению разработчиков более 10 000 000 вершин, по числу ребер информация отсутствует, в бесплатной версии продукта - 100 вершин;

• алгоритмы авторазмещений: 3d размещение, круговое размещение, размещение на основе кластеризации графа, размещение на основе метода физических аналогий;

• дополнительные инструменты анализа: содержат большое число метрик для анализа социальных сетей: гомофилия (homophily), множественность (multiplexity), взаимность (mutuality), сетевая закрытость (network closure); метрик, которые отражают характеристики графа поделённого на сегменты: клика (cliques), социальный круг (social circles), коэффициент кластеризации (dustering coefficient), сплоченность (œhesion); для анализа графов: нахождение мостов, диаметра, плотности графа, расстояния между двумя вершинами, коэффициент центральности;

• дополнительно: предусмотрен как графический интерфейс, встроенный скриптовый язык, основанный на ру^п.

Cytoscape [25] - программный продукт (Рис. 1.3) с открытым исходным кодом для визуализации и анализа сетей взаимодействующих молекул и биологических путей. Изначально был разработан для биологических исследований, теперь используется для анализа и визуализации сложных сетей. Основные характеристики:

• исходный код: доступен (open-source);

• операционная система: написан на Java и может быть запущен из под любой операционной системы, поддерживающей ее;

• форматы импорта: sif (simple interaction format), gml, fgmml, biopax, psi-mi, graphml, kgml (kegg xml), sbml, obo, gene association. csv, ms excel;

Рис. 1.2. NetMmer 4 - пример пользовательского интерфейса.

• интерактивное взаимодействие с графом: инструменты визуализации и навигации, инструменты редактирования графа и его визуального представления;

• ограничения на визуализацию: размер графов при визуализации ограничен несколькими сотнями тысяч объектов, тест на работу с большим графом (300 000 вершин и 2 млн. связей) показал, что обработка таких объемов уже не может проходить в реальном времени;

• алгоритмы авторазмещений: круговое, иерархическое, на основе метода физических аналогий;

• дополнительные инструменты анализа: имеется возможность применения фильтров для выделения подграфов по определенным параметрам, возможен поиск кластеров, нахождение наиболее значимых подсетей;

• дополнительно: доступна возможность подключения собственных плагинов.

Рис. 1.3. Cytoscape - пример пользовательского интерфейса.

VisuaLyzer [65] (Рис. 1.4) - интерактивный инструмент для анализа и визуализации графов социальных сетей с следующими характеристиками:

• исходный код: недоступен;

• операционная система: Windows 2000/XP/7/8;

• форматы импорта: edgelist/edgearray/nodelist, Excel, CSV, DyNetML, GraphML;

• интерактивное взаимодействие с графом: инструменты визуализации и навигации, инструменты редактирования графа и его визуального представления;

• ограничения на визуализацию: предназначен для работы с графами маленьких и средних размеров (из документации);

• алгоритмы авторазмещений: на основе метода физических аналогий, на основе кругового размещения;

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

Рис. 1.4. VisuaLyzer - пример пользовательского интерфейса.

Tulip [68] - аналитическая платформа (набор инструментов в виде библиотеки), направленная на исследование и визуализацию реляционных данных. Основные характеристики:

• исходный код: доступен (open-source);

• операционная система: Linux, Windows, Mac OS;

• форматы импорта: tulip format (.tlp), graphviz (.dot), gml, txt, adjacency matrix, csv, gexf, pajek;

• интерактивное взаимодействие с графом: инструменты визуализации и навигации, инструменты редактирования графа и его визуального представления;

• ограничения на визуализацию: позволяет визуализировать и редактировать графы размерами до 10 000 000 вершин и связей, однако, для графа из 300 000 вершин и 2 млн. ребер визуализация и алгоритм кругового размещения работают нестабильно и медленно (далеко не в режиме реального времени);

• алгоритмы авторазмещений: круговое, иерархическое, на основе метода физических аналогий;

• дополнительные инструменты анализа: подсчет метрик центральности и алгоритм иерархической кластеризации;

• дополнительно: реализована интеграция с популярной зарубежной социальной сетью FaceBook и возможен импорт друзей, есть возможность добавлять новые плагины, в том числе через интерфейс пользователя на языке python.

CoSBiLab [23] - инструмент для визуализации и анализа ориентированных и неориентированных графов, с следующими основными характеристиками:

• исходный код: недоступен;

• операционная система: Windows;

• форматы импорта: dot, txt, dl, spec;

• интерактивное взаимодействие с графом: инструменты визуализации и навигации, инструменты редактирования графа и его визуального представления;

• ограничения на визуализацию: информация отсутствует;

• алгоритмы авторазмещений: случайное, круговое, на основе метода физических аналогий;

• дополнительные инструменты анализа: подсчет различных метрик цетральности вершин и связей, поиск циклов и кратчайших путей, кластеризация графа.

Графоанализатор [4] - приложение с открытым исходным кодом, используемое в учебных целях, которое обладает следующими основными характеристиками:

• исходный код: доступен;

• операционная система: Windows;

• форматы импорта: ввод графа через задание матрицы или списка смежности;

• интерактивное взаимодействие с графом: позволяет визуализировать графы;

• ограничения на визуализацию: информация отсутствует;

• алгоритмы авторазмещений: отсутствуют;

• дополнительные инструменты анализа: поиск минимального пути, поиск эйлеровых и гамильтоновых маршрутов, поиск минимального оставного дерева, определение максимального потока как для одного стока и истока, так и для множества стоков и истоков, проверка на связность, поиск радиуса и диаметра графа, проверка, является ли граф деревом, проверка на планарность, возможность сохранения и загрузки графа с поддержкой сохранения визуального представления.

GraphViz [34] - пакет утилит по автоматической визуализации графов, заданных в виде описания на языке dot, а также дополнительных tui и gui программ, виджетов и библиотек, используемых при разработке программного обеспечения для визуализации структурированных данных. Пакет Graphviz разработан специалистами лаборатории AT&T и распространяется с открытыми исходными файлами по лицензии EPL (Eclipse Public License). Основные характеристики:

• исходный код: доступен;

• операционная система: Linux, Mac OS, MS Windows;

• форматы импорта: csv, txt;

• интерактивное взаимодействие с графом: инструмент dotty - графический пользовательский интерфейс для создания графов;

• ограничения на визуализацию: предназначен для работы с небольшими графами, явных ограничений на размер не наклыдвается ;

• алгоритмы авторазмещений: twopi, circo - инструменты кругового и множественного кругового автоматического размещения, neato, fdp, sfdp -инструменты автоматического размещения графа на основе метода физических аналогий;

• дополнительные инструменты анализа: dot - инструмент создания многоуровневого графа с возможностью вывода изображения результирующего графа во множестве форматов (png, pdf, postscript, svg и т.д.).

yEd [73] - бесплатная программа, построенная на базе java-библиотеки для визуализации графов с следующими основными характеристиками:

• исходный код: недоступен;

• операционная система: Windows, Mac OS X, Linux;

• форматы импорта: xls, xml, gml, gedcom;

• интерактивное взаимодействие с графом: инструменты визуализации и навигации, инструменты редактирования графа и его визуального представления;

• ограничения на визуализацию: информация отсутствует;

• алгоритмы авторазмещений: иерархический, круговой, на основе метода физических аналогий, многоуровневый круговой;

• дополнительные инструменты анализа: подсчет метрик центральности, поиск кратчайших путей, реализован экспорт в форматы png, jpg, svg, pdf, swf.

aiSee [16] -приложение, больше не поддерживаемое как отдельный продукт для анализа и визуализации графов. Размер обрабатываемых графов ограничен

несколькими сотнями тысяч вершин. Используется для автоматического размещения графов на плоскости. Детальная информация отсутствует.

i2 Analyst's Notebook [37] - визуальная аналитическая среда, позволяющая анализировать, сопоставлять и визуализировать данные из различных источников, там самым уменьшая время на выделение важной информации из данных. Направление анализа связано с выявлением преступной, террористической и мошеннической деятельностей. Основные характеристики:

• исходный код: недоступен;

• операционная система: Windows;

• форматы импорта: csv, txt, xml, xls, doc;

• интерактивное взаимодействие с графом: инструменты визуализации и навигации, инструменты редактирования графа и его визуального представления;

• ограничения на визуализацию: официальная информация отсутствует, экспериментальным путем установлено, что для схем с количеством вершин и связей более 10 000, отклик программного продукта при навигации существенно замедляется;

• алгоритмы авторазмещений: круговое авторазмещение, групповое, иерархическое, временное (упорядоченное и пропорциональное), на основе метода физических аналогий, и размещение, минимизирующее количество пересекающихся связей;

• дополнительные инструменты анализа: присутствуют.

С точки зрения инструментов визуализации данных, этот продукт предоставляет довольно богатую функциональность: ручное добавление вершин и связей, настройка отображения объектов (цвета, шрифты, иконки, стили), имеет удобные инструменты перемещения и масштабирования по схеме, присутствует возможность добавления атрибутов к объектам на схеме. Имеется возможность отображения множественных связей между вершинами графа.

В i2 Analyst's Notebook реализован импорт из различных форматов (csv, txt, xml, xls, doc) данных в виде пошагового мастера, с возможностью визуального пред-просмотра финального результата. В качестве инструментов визуального анализа данное программное обеспечение выделяется большим количеством встроенных алгоритмов автоматического размещение вершин и связей на схеме: круговое авторазмещение, групповое, иерархическое, временное (упорядоченное и пропорциональное), на основе метода физических аналогий, и размещение, минимизирующее количество пересекающихся связей.

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

Visual Graph [9, 69] - отечественная программа, распространяемая по лицензии BSD, в первую очередь для визуализации атрибутированных иерархических графов. Создаётся в рамках ведущегося в лаборатории конструирования и оптимизации программ ИСИ СО РАН проекта по разработке методов и средств для визуализации сложно структурированной информации большого объема на основе графовых моделей. Программное обеспечение (Рис. 1.5) адаптировано под использование разработчиками систем конструирования программ (компиляторы) для визуализации структур данных, возникающих при работе этих систем. Основные характеристики:

• исходный код: доступен, лицензия BSD;

• форматы импорта: graphml;

интерактивное взаимодействие с графом: инструменты визуализации и навигации, инструменты редактирования графа и его визуального представления;

ограничения на визуализацию: до 100 000 вершин и связей; алгоритмы авторазмещений: круговое, иерархические;

дополнительные инструменты анализа: подсветка кратчайшего пути, циклов, а также поиск максимального общего подграфа двух графов; дополнительно: в качестве базы данных для хранения графов используется SQLite, присутствует возможность добавления новой функциональности в виде плагинов.

Список литературы диссертационного исследования кандидат наук Коломейченко, Максим Игоревич, 2016 год

СПИСОК ЛИТЕРАТУРЫ

1. Базенков Н. И., Губанов Д. А. Обзор информационных систем анализа социальных сетей. // Управление большими системами: сборник трудов. — 2013. — С. 357-394.

2. Батура Т.В. Методы анализа компьютерных социальных сетей. // Вестник НГУ. Серия: Информационные технологии. — 2012. — Т. 10.

— № 4. — С. 13-28.

3. Борисенко В.В., Лахно А.П., Чеповский А.М. Специальное представление графов и визуализация семантических сетей. // Фундаментальная и прикладная математика. — 2010. — Т. 16. — № 8 .

— C. 27-35.

4. Графоанализатор. // URL: http://grafoanalizator.unick-soft.ru/ (Дата обращения: 05.04.2016).

5. Губанов Д.А., Новиков Д.А., Чхартишвили А.Г. Социальные сети: модели информационного влияния, управления и противоборства. — М.: Физматлит: МЦНМО, 2010. — 228 с.

6. Доронин А.И. Бизнес-разведка. — М.: Ось-89, 2010. - 704 с.

7. Йозе С., Эссейва П., Рибо О., Вейерманн С., Англада Ф., Лосисиро С., Айо П., Баэр И., Гасте Л., Терретта-Зюфферей А.-Л., Делапорт С., Марго П. Создание оперативной системы составления профилей наркотических средств: опыт Швейцарии. // Бюллетень по наркотическим средствам. Управление организации объединенных наций по наркотикам и преступности. — Вена. — 2005. — Том LVII. — № 1-2. — С. 121-148.

8. Касьянов В.Н., Евстигнеев В.А. Графы в программировании: обработка, визуализация и применение. - СПб.: БХВ-Петербург, 2003.

— 1104 с.

9. Касьянов В. Н., Золотухин Т. А. Visual Graph - система визуализации сложно структурированной информации большого объема на основе графовых моделей. // 25-я Международная конференция по компьютерной графике, обработке изображений и машинному зрению, системам визуализации и виртуального окружения GraphiCon2015. — 2015. — C. 154-163.

10. Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ, 2-е издание. Пер. с англ. - М.:Издательский дом "Вильямс", 2010. - 1296 с.

11. Лахно А.П., Чеповский А.М., Чернобай В.Б. Визуализация связей выделенного множества объектов семантической сети. // Прикладная информатика. - 2010. - № 6(30). - С. 55-61.

12. Лесковец Ю., Раджараман А., Ульман Дж. Анализ больших наборов данных. - М.: ДМК Пресс, 2016. - 498 с.

13. Рабинович Б.И. Кластерный анализ детализаций телефонных переговоров. // Системы и средства информатики, Ин-т пробл. информатики РАН. - 2007. - № 17. - С. 52-78.

14. Adai A.T., Date S.V., Wieland S., Marcotte E.M. LGL: creating a map of protein function with an algorithm for visualizing very large biological networks. // Journal of Molecular Biology. - 2004. - V 340. - PP. 179-190.

15. Aggarwal C.C. Social network data analytics. - Springer US, 2011. -502 p.

16. aiSee - Graph Visualization. // URL: https://www.absint.com/aisee/ (Дата обращения: 05.04.2016).

17. Battista D.G., Tamassia R. Algorithms for Plane Representations of Acyclic Digraphs. // Theoretical Computer Science. - № 61(2). - 1988. - PP. 175-198.

18. Battista D.G., Tamassia R., Tollis G.I. Graph Drawing: Algorithms for the Visualization of Graphs. - Springer, 1999. - 397 p.

19. Baur M., Brandes U. Crossing Reduction in Circular Layouts // WG'04 Proceedings of the 30th international conference on Graph-Theoretic Concepts in Computer Science. - 2004. - PP. 332-343.

20. Blondel V.D., Guillaume J.-L., Lambiotte R., Lefebvre E. Fast unfolding of communities in large networks. // Journal of Statistical Mechanics: Theory and Experiment. - 2008. № 10, P10008. - 12 p.

21. Borgatti S.P., Everett M.G., Johnson J.C. Analyzing social networks. -SAGE Publications Limited, 2013. - 304 p.

22. Clauset A., Newman M.E.J., Moore C. Finding community structure in very large networks. // Physical Review. - 2004. - E 70, 066111. - 6 p.

23. COSBILab Graph. // URL: http://www.cosbi.eu/research/prototypes/graph (Дата обращения: 05.04.2016).

24. CrimeLink. // URL: http://www.pciusa.us/Crimelink.aspx. (Дата обращения: 08.02.2015).

25. Cytoscape. // URL: http://www.cytoscape.org/ (Дата обращения: 05.04.2016).

26. Domenico M., Lancichinetti A., Arenas A., Rosvall M. Identifying modular flows on multilayer networks reveals highly overlapping organization in interconnected systems. // Physical Review. - 2015. - X. 5, 011027. - 14 p.

27. Donetti L., Munoz M. A. Improved spectral algorithm for the detection of network communities. // The Proceedings of the 8th Granada Seminar -Computational and Statistical Physics. - 2005. - 0504059. - 4 p.

28. Duchet P., Hamidoune Y., Vergnas M., Meyniel H. Representing a planar graph by vertical lines joining different levels. // Discrete Math. - 1983.

- Vol. 46 (3). - PP. 319-321.

29. Dwyer T., Marriott K., Stuckey P.J. Fast node overlap removal. // In Proc. 13th Intl. Symp. Graph Drawing GD '05. Lecture Notes in Computer Science. - 2006. - Vol. 3843. - PP. 153-164.

30. Esquivel A., Rosvall M. Compression of flow can reveal overlapping modular organization in networks. // Physical Review. - 2011. - X 1, 021025.

- 10 p.

31. Fortunato S. Community Detection in Graphs. // Physics Reports. -2010. - Vol.486. - № 3. - PP. 75-174.

32. Gephi. // URL: https://gephi.org/(Дата обращения: 05.04.2016).

33. Girvan M., Newman M.E.J.. Community structure in social and biological networks. // Proc. Natl. Acad. Sci. USA. - 2002. - Vol.99. - № 12. - PP. 7821-7827.

34. GraphViz. // URL: http://www.graphviz.org/ (Дата обращения: 05.04.2016).

35. Guimera R., Sales-Pardo M., Amaral L.A.N. // Modularity from fluctuations in random graphs and complex networks // Physical Review. -2004. - E 70, 025101. - 4 p.

36. Igraph software. // URL: http://igraph.org/ (Дата обращения: 05.04.2016).

37. i2 Analyst's Notebook. // URL: http://www-03.ibm.com/software/products/ru/analysts-notebook/ (Дата обращения: 05.04.2014).

38. Kaufmann M., Wagner D. Drawing Graphs, Methods and Models. -Springer, 2001. - 312 p.

39. Lambiotte R., Rosvall M. Ranking and clustering of nodes in networks with smart teleportation. // Physical Review. - 2012. - E 85, 056107. - 10 p.

40. Lancichinetti A., Fortunato S. Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities. // Physical Review. - 2009. - E 80, 016118. - 9 p.

41. Lancichinetti A., Fortunato S. Community detection algorithms: a comparative analysis. // Physical Review. - 2009. - E 80, 056117. - 12 p.

42. Lancichinetti A., Fortunato S., Radicchi F.. Benchmark graphs for testing community detection algorithms. // Physical Review. - 2008. - E 78, 046110. - 6 p.

43. Liu H., Salerno J., Young M. Social Computing, Behavioral Modeling, and Prediction. - Springer Science, 2008. - 264 p.

44. Lovasz L. Random Walks on Graphs: A Survey. // Combinatorics, Paul erdos is eighty, Keszthely, Hungary. - 1993. - Vol.2. - PP. 1-46.

45. Luke D.A. A User's Guide to Network Analysis in R. - Springer International Publishing Switzerland, 2015. - 240 p.

46. Marriott K., Stuckey P., Tam V., He W. Removing node overlapping in graph layout using constrained optimization. // Constraints. - 2003. - Vol. 8 (2). - PP. 143-171.

47. Massen C.P., Doye J.P. Identifying communities within energy landscapes. // Physical Review. - 2005. E 71, 046101. - 13p.

48. Mena J. Investigative Data Mining for Security and Criminal Detection. - Elsevier Science, 2003. - 280 p.

49. NetMiner 4. // URL: http://www.netminer.com/main/main-read.do (Дата обращения: 05.04.2016)

50. Newman M.E.J. Fast algorithm for detecting community structure in networks. // Physical Review. - 2004. - E 69, 066133. - 5 p.

51. Newman M.E.J. Modularity and community structure in networks. // Proc. Natl. Acad. Sci. USA. - 2006. - Vol.103. - № 23. - PP. 8577-8582.

52. Newman M.E.J. Networks: An Introduction. - Oxford University Press, 2010. - 784 p.

53. Newman M.E.J. The structure and function of complex networks. // SIAM Review. - 2003. - Vol.45. - № 10. - PP.167-256.

54. Newman M.E.J., Girvan M. Finding and evaluating community structure in networks. // Physical Review. - 2004. - E 69, 026113. - 16 p.

55. Olson D. L., Dursun D. Advanced Data Mining Techniques. - Springer, 2008. - 180 p.

56. Otten R.H.J.M., Wijk J.G. Graph representations in interative layout design. // In Proc. IEEE Internat. Sympos. On Circuits and Systems. - 1978. - PP. 914-918.

57. Palla G., Derenyi I., Farkas I., Vicsek T. Uncovering the overlapping community structure of complex networks in nature and society. // Nature. -2005. - Vol. 435. - PP. 814-818.

58. Radicchi F., Castellano C., Loreto V., Cecconi F., Parisi D. Defining and identifying communities in networks. // Proc. Natl. Acad. Sci. USA. -2004. - Vol.101. - № 9. - PP. 2658-2663.

59. Richards J.H. Psychology of Intelligence Analysis. - Central Intelligence Agency, 1999. - 210 p.

60. Rosenstiehl P., Tarjan R.E. Rectilinear planar layouts and bipolar orientations of planar graphs. // Discrete Comput. Geom. - 1986. - Vol. 1. -No. 4. - PP. 343-353.

61. Rosvall M., Bergstrom C. T. An information-theoretic framework for resolving community structure in complex networks. // Proc. Natl. Acad. Sci. USA. - 2007. - Vol.104. - № 18. PP. 7327-7331.

62. Rosvall M., Bergstrom C. T. Maps of information flow reveal community structure in complex networks. // Proc. Natl. Acad. Sci. USA. -2008. - Vol.105. - № 4. - PP. 1118-1123.

63. Rosvall M., Bergstrom C. T., Axelsson D. The map equation // The European Physical Journal Special Topics. - 2009. - Vol. 178. - № 1. - PP. 13-23.

64. Rosvall M., Esquivel A., Lancichinetti A., West J., Lambiotte R. Memory in network flows and its effects on spreading dynamics and community. // Nature Communications. - 2014. - Vol. 5, 4630. - 8 p.

65. Sentinel Visualyzer. // URL: http://www.fmsasg.com/Products/SentinelVisualizer/. (Дата обращения: 05.04.2016).

66. Shannon C.E. A Mathematical Theory of Communication.// Bell System Technical Journal. - 1948. - Vol. 27. - PP. 379-423.

67. Tom Sawyer. // URL: http://www.tomsawyer.com. (Дата обращения: 05.04.2016).

68. Tulip. // URL: http://tulip.labri.fr/TulipDrupal/ (Дата обращения: 05.04.2016).

69. VisualGraph. // URL: https://bitbucket.org/tzolotuhin/visual-graph (Дата обращения: 05.04.2016).

70. VisuaLyzer 2.1. // URL: http://socioworks.com/productsall/visualyzer (Дата обращения: 05.04.2016).

71. XAnalys Link Explorer. // URL: http://www.xanalys.com/solutions/linkexplorer.html. (Дата обращения: 05.04.2016).

72. Xu J., Chen H. Criminal network analysis and visualization: a data mining perspective. // Communications of the ACM. - 2005. - Vol. 48. - PP. 100-107.

73. yEd. // URL: http://www.yworks.com/products/yed (Дата обращения: 05.04.2016).

Публикации в перечне ведущих рецензируемых научных журналов, рекомендованных ВАК, и приравненных к ним изданиям:

74. Коломейченко, М.И. Программный комплекс для анализа и визуализации графов/ М. И. Коломейченко, А. А. Золотых , И. В. Поляков , А.М. Чеповский // Моделирование и анализ информационных систем. - 2014. - Т. 21, № 6. - С. 155-168.

75. Коломейченко, М.И. Визуализация и анализ графов больших размеров/ М.И.Коломейченко, А.М.Чеповский// Бизнес-информатика. -2014. - № 4(30). - С. 7-16.

76. Коломейченко, М.И. Выделение сообществ в графе взаимодействующих объектов/ М.И.Коломейченко, А.А.Чеповский, А.М.Чеповский// Фундаментальная и прикладная математика. - 2016. - Т. 21, вып 3. - С. 115-123. (Scopus).

77. Kolomeychenko M. I., Chepovskiy A.A., Chepovskiy A.M. An Algorithm for Detecting Communities in Social Networks. // Journal of Mathematical Sciences . — 2015. — Vol. 211. — №. 3. — P. 310-318. [Перевод: Коломейченко М.И., Чеповский А. А., Чеповский А. М. Алгоритм выделения сообществ в социальных сетях. // Фундаментальная и прикладная математика. — 2014. — Т. 19. — Вып 1. — С. 21-32.]

Статьи в сборниках научных трудов и сборниках трудов конференций:

78. Коломейченко М.И. О хранении графа социальной сети / М.И.Коломейченко, И.В. Поляков, А.А.Чеповский, А.М.

Чеповский// CPT2015. Труды Международной научной конференции по физико-технической информатике. М., Протвино: Институт физико-технической информатики, 2016. С. 175-178.

79. Коломейченко, М. И. Геометрическое моделирование и визуальный анализ графов, отображающих сети взаимодействующих объектов/ М.И.Коломейченко, А.М.Чеповский // GraphiCon2016: сб. тр. 26-й Междунар. науч. конф. - Н. Новгород, 2016. - С. 332-333.

80. Коломейченко, М.И. Алгоритм многополосного размещения сети/ М.И.Коломейченко // Resilience2014: тр. Междунар. науч. конф. Междунар. центра по ядерной безопасности Института физико -технической информатики. - М., Протвино: Изд-во ИФТИ, 2015. -С. 135-138.

81. Коломейченко, М.И. Хранение и скачивание сетей больших размеров/ М. И. Коломейченко, И. В. Поляков, А. А. Чеповский// Resilience2014: тр. Международ. науч. конф. Междунар. центра по ядерной безопасности Института физико-технической информатики. -М., Протвино: Изд-во ИФТИ, 2015. -С. 139-143.

82. Коломейченко, М.И. Архитектура и инструменты программного комплекса для визуализации и анализа графов/ Т.Н.Борисов, М.И.Коломейченко , И.В.Поляков, А.М. Чеповский // Resilience2013: тр. Междунар. науч. конф. Междунар. центра по ядерной безопасности Института физико-технической информатики. - Протвино: Изд-во ИФТИ, 2014. - С. 32-37.

83. Коломейченко, М.И. Программный комплекс для анализа и визуализации графов/ М. И. Коломейченко, И. В. Поляков, А. М. Чеповский// Ершовская конференция по информатике 2014: сб. докл. -М.: ИНТУИТ, 2014. - С. 49-56.

Учебное пособие, в котором использованы результаты диссертационных исследований:

84. Коломейченко, М.И. Методы визуального анализа графов: учеб. пособие/ М.И.Коломейченко , И.В.Поляков, А.А. Чеповский, А.М. Чеповский. - М.: Национальный открытый университет «ИНТУИТ», 2016. - 157 с.

ПРИЛОЖЕНИЕ А. Описание функциональности программного

комплекса

В данном Приложении приводиться краткое описание «Руководства пользователя» разработанного программного комплекса визуализации и анализа графов.