Диссертация (1090614), страница 18
Текст из файла (страница 18)
Плотность – это отношение числа имеющихсярёбер графа к максимально возможному количеству рёбер данного графа.Коэффициент кластеризации (коэффициент локального объединения вкластеры) характеризует тенденцию к образованию групп взаимосвязанныхузлов. Коэффициент кластеризации используют при анализе социальныхсетей.Коэффициент кластеризации узла:() =2 ( −1),(4.2)где - вершина, для которой выполняется подсчет коэффициента, количество связанных с ней вершин, - количетсво связей между всеми еесоседями. Число - суммарное число треугольников (циклов длины 3),прикрепленных к узлу . ( − 1)/2 - максимально возможное числотреугольников. Если все ближайшие соседи узла взаимосвязаны, то() = 1.
Когда между соседними узлами вершины нет связей (как в случаес деревьями), то СС() = 0.Тогда кластеризация всей сети определяется как ( ) = 3Δ⋁,(4.3)где Δ - число всех треугольников в графе, ⋁ - число связанных троек, где«связанная тройка» означает узел и два его ближайших соседа.Когда коэффициент кластеризации высокий – это означает, что графчрезвычайно плотно сгруппирован вокруг нескольких узлов; когда он низкий142– это значит, что связи в графе относительно равномерно распространенысреди всех узлов.Так же в реализуемом программном продукте предусмотрен подсчетраспределения степеней вершин и связей.
Также можно вычислитькоэффициент ассортативного смешивания по степеням вершин (4.4).Термин «ассортативное смешивание» возник в социологии приизученииформированияисследованиятакжесупружескихпоказали,чтопар[52].социальныеСоциологическиесетидрузейтакжеформируются на основе наличия общих признаков: языка, расы, возраста,уровня образования и т. д.В таких случаях говорят, что рассматриваемые сети обладают свойствомассортативногосмешивания.Однако,еслисетиформируютсяпоантогонистическому принципу, то они в свою очередь будут обладатьсвойством диссортативного смешивания.
Ассортативность является степеньютенденции вершин сети формировать связи с узлами с одним и тем же числомсвязей.( ) = ∑∈ 1 2 −[∑∈ 1 ]2 ∑∈(1 )2 −[∑∈ 1 ]2,(4.4)где - исследуемый граф, - множество всех ребер графа, = || количество всех ребер графа, - ребро графа, 1 - количество связей первойвершины из двух концов связи , 2 - количество связей второй вершины издвух концов связи .Данный коэффициент (4.4.) принимает значения от −1 до 1 .
Есливершины с большим числом связей связаны друг с другом, то значениекоэффициента близко к 1, если вершины с большим числом связей связаны свершинами с меньшим числом связей, то значение коэффициента близко к −1.143При работе с большими графами для анализа структуры реализованалгоритм оценки связности, который позволяет для заданного порога по числусвязей между парой вершин разбить граф на компоненты связности,выполнить размещение объектов с учетом полученных компонент и показатьсписки всех вершин для каждой полученной компоненты.Крометого,реализованалгоритмавтоматическоговыделениясообществ c возможностью визуализации графа на основе полученногоразбиения на сообщества.В разработанном программном обеспечении содержаться встроенныеалгоритмыавтоматическогоразмещенияграфа.Поэтому,нарядусвозможностью ручного размещения вершин и связей, предоставляетсянесколько вариантов автоматического размещения элементов, описанные вглавах 2 и 3.1444.5.Выводы по 4 главе1.
Разработана оригинальная архитектура программного комплекса дляработы с графами, опирающаяся на специализированные хранилищаграфов, и модули визуализации и анализа графов. Архитектурапозволяет эффективно работать с графами больших размеров за счетразделения базового и локального хранения графов и его визуальныхпредставлений в программном интерфейсе.2.
Спроектированы эффективные структуры данных, которые позволилисоздать развитую систему редактирования и анализа без ущербапроизводительности и с допустимым объемом занимаемой памяти.Реализованныеструктурыданныхобеспечиваютэффективноехранение и обращение к данным, основанная на алгоритмах,оптимизированных под работу с большими графами и обладающихвысокой производительностью на специальных операциях с графами.3. Созданпрограммныйкомплекс,человеко-машинныйинтерфейскоторого позволяет проводить эффективный визуальный анализ графоввзаимодействующихобъектовипредоставляетширокуюфункциональность при работе с графами очень больших размеров внесколько миллионов вершин и связей. Преимуществом созданногопрограммного обеспечения является платформенная независимостьрешения.Всеиспользуемыесредствареализацииявляютсякроссплатформенными.
Тем самым программный комплекс способенфункционировать в различных операционных системах.145ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫОсновные результаты, полученные в диссертационной работе:1. Разработана и реализована геометрическая модель автоматическогоразмещения «быстрый павлиний хвост», основанная на методефизическиханалогий.Спецификапредложеннойоптимизациискоростных характеристик алгоритма достигается за счет анализа тольколокальной области на плоскости при вычислении взаимодействующихсил между объектами графа.2. Предложена и реализована геометрическая модель визуализации графа,на основе оригинального алгоритма построения многополосногоразмещения объектов на плоскости, который может использоваться длявизуализации связей выделенного множества объектов семантическойсети.
Созданная процедура позволяет в десятки раз сократить времявыполнения стандартной задачи аналитика — размещения на схемезначительного количества объектов и связей между ними без ихперекрытия.3. Разработана и реализована геометрическая модель автоматическогоразмещения графа на основе алгоритма выделения сообществ, спомощью которого можно выделять сообщества взаимодействующихобъектов, применимый для выделения групп общения в социальныхсетях.Предложенаиреализованапроцедураавтоматическогоразмещение графов с выделенными сообществами объектов привизуализации средствами человеко-машинного интерфейса.4. Разработана оригинальная архитектура программного комплекса дляработы с графами, опирающаяся на специализированные хранилищаграфов, и модули визуализации и анализа графов.
Архитектурапозволяет эффективно работать с графами больших размеров за счет146разделения базового и локального хранения графов и его визуальныхпредставлений в программном интерфейсе.5. Созданпрограммныйкомплекс,человеко-машинныйинтерфейскоторого позволяет проводить эффективный визуальный анализ графоввзаимодействующихобъектовипредоставляетширокуюфункциональность при работе с графами очень больших размеров внесколько миллионов вершин и связей. Преимуществом созданногопрограммного обеспечения является платформенная независимостьрешения.Всеиспользуемыесредствареализацииявляютсякроссплатформенными.
Тем самым программный комплекс способенфункционировать в различных операционных системах.147СПИСОК ЛИТЕРАТУРЫ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 с.1489.Касьянов В. Н., Золотухин Т. А. Visual Graph – системавизуализации сложно структурированной информации большогообъема на основе графовых моделей. // 25-я Международнаяконференция по компьютерной графике, обработке изображений имашинному зрению, системам визуализации и виртуального окруженияGraphiCon2015.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
