Разработка и исследование моделей графов и гиперграфов с учетом множественных и разнотипных связей тема диссертации и автореферата по ВАК РФ 05.13.17, кандидат наук Мунтян Евгения Ростиславна
Мунтян Евгения Ростиславна
кандидат наук
2020
- Специальность ВАК РФ05.13.17
- Количество страниц 242
Оглавление диссертации кандидат наук Мунтян Евгения Ростиславна
ВВЕДЕНИЕ
Глава 1. Анализ моделей теории графов
1.1. Обзор существующих моделей теории графов для анализа данных
1.2. Обзор методов и алгоритмов вычислений в графах и гиперграфах для анализа данных
1.3. Анализ существующих методов и алгоритмов преобразования графов и гиперграфов
Выводы
Глава 2. Разработка и исследование СЯ-моделей
2.1. Формы представления СЯ-графов и СЯ-гиперграфов
2.2. Представление элементов и связей в СЯ-графах в виде списков
2.3. Представление элементов и связей в СЯ-гиперграфах в виде списков
2.4. Модели СЯ-графов и СЯ-гиперграфов с учетом множественных и разнотипных связей
2.5. Исследование СЯ-моделей при помощи вычисления характеристик
Выводы
Глава 3. Алгоритмы преобразования СЯ-моделей с учетом множественных и разнотипных связей
3.1. Алгоритмы свертки СЯ-модели
3.2. Алгоритмы разделения СЯ-моделей
3.3. Алгоритм догенерации СЯ-моделей
3.4. Локализация элементов СЯ-моделей
Выводы
Глава 4. Анализ данных в СЯ-моделях для решения практических задач в системах с разнотипными информационными потоками
4.1. Представление разнотипных отношений в СЯ-моделях
4.2. Исследование и функционирование СЯ-моделей
Выводы
Глава 5. Программный комплекс моделирования взаимодействия акторов на основе СЯ-графов
5.1. Структура и функциональность ПК
5.2. Моделирование взаимодействия акторов путем вычисления метрических характеристик графа в ПК
5.3. Реализация алгоритмов преобразования СЯ-графа в ПК
Выводы
ЗАКЛЮЧЕНИЕ
СПИСОК СОКРАЩЕНИЙ
СПИСОК ЛИТЕРАТУРЫ
ПРИЛОЖЕНИЕ 1. Примеры работы алгоритмов преобразования СЯ-моделей . 185 ПРИЛОЖЕНИЕ 2. Примеры задач в организационных и технических системах 202 ПРИЛОЖЕНИЕ 3. Интерпретация элементов СЯ-моделей и их характеристик для
решения задач в организационных и технических системах
ПРИЛОЖЕНИЕ 4. Результаты применения алгоритма пропорционального
разделения СЯ-графа в ПК для решения практических задач
ПРИЛОЖЕНИЕ 5. Свидетельства о государственной регистрации программ для ЭВМ
ПРИЛОЖЕНИЕ 6. Акты о внедрении, об использовании результатов диссертационной работы
Рекомендованный список диссертаций по специальности «Теоретические основы информатики», 05.13.17 шифр ВАК
Методы покрытия гиперсети корневым деревом для оптимизации системы транспортных путей2013 год, кандидат наук Воронова, Анна Михайловна
Переключательные алгоритмы преобразования графов2010 год, кандидат физико-математических наук Лашева, Мария Игоревна
Гиперграфовые модели и методы решения дискретных задач управления в условиях неопределенности2004 год, кандидат физико-математических наук Омельченко, Галина Георгиевна
Исследование и разработка векторно-алгебраических методов проектирования топологии печатных плат1983 год, кандидат технических наук Мороговский, Борис Наумович
Разработка алгоритмов комбинаторной оптимизации для анализа графовых и гиперграфовых сетей2022 год, кандидат наук Солдатенко Александр Александрович
Введение диссертации (часть автореферата) на тему «Разработка и исследование моделей графов и гиперграфов с учетом множественных и разнотипных связей»
ВВЕДЕНИЕ
Актуальность темы. Одним из наиболее распространенных инструментов моделирования прикладных задач, позволяющих работать с данными, представленными в виде сети отношений, являются графы и обобщения на графах, для которых определены и используются средства организации вычислений. Весомый вклад в развитие теории графов и их приложений внесли ученые Л.С. Берштейн, В.А. Емеличев, А.А. Зыков, В.М. Курейчик, А.Н. Мелихов, К. Берж (K. Berge), Ф. Харари (F. Harary), О. Оре (O. Ore), У. Татт (W. Tatt), Р. Уилсон (R. Wilson) и др.
Новое направление в развитии теории графов на область нечетких графов появилось благодаря понятию нечеткого множества, введенного Лотфи Заде в 1965г., которое стало основой для представления неопределенности. Исследованию и систематизации теории нечетких графов посвящены работы ученых Л.С. Берштейна, А.В. Боженюка, А.Н. Мелихова, А. Кофмана (A. Kaufmann), Дж.Н. Мордесона (J.N. Mordeson), А. Розенфельда (A. Rosenfeld), М.С. Сунита (M.S. Sunitha) и др.
Аппарат теории графов предоставляет возможности использования различных моделей, целесообразность применения которых зависит от предметной области. В настоящее время отмечается интерес к исследованию и моделированию задач взаимодействия объектов, субъектов или их групп. Объединение объектов или субъектов в группы возможно при наличии у них некоторого общего функционала, общих принципов их взаимодействия. Примером групп объектов могут служить совокупность технических устройств (ТУ), действующих совместно в решении определенных задач; комплексы стационарных объектов с привязкой к координатной плоскости и т.д. В тоже время субъекты могут быть объединены в группы по признакам принадлежности, например социальные, профессиональные, этнические, группы, социальные сети. Однако субъекты могут объединяться в группы не только по заранее известным признакам, но и стихийно в результате изменения общественного мнения в силу влияния информационных потоков,
например средств массовой информации. Обозначим ряд актуальных в настоящее время задач взаимодействия объектов или субъектов и их групп:
1) задача охраны объекта (требуется обеспечение совместного действия ТУ охраны объекта, распределение (покрытие) зон охраны объекта, решение задачи взаимозамены устройств и т.д.) [78, 17];
2) задача обеспечения необходимых условий существования живых организмов в окружающей их среде (группу субъектов, решающих такую задачу, объединяют интересы в области экологии) [119];
3) задача моделирования перемещения людских потоков [41, 28, 66];
4) задача определения возможности распространения информации в социальных сетях с целью предотвращения угрозы терроризма (субъекты -пользователи, которые могут быть объединены в группы социальных сетей) [71, 169] и т.д.
В основе моделей, предназначенных для исследования взаимодействия субъектов, обычно, лежат знания о психологии самой личности, межличностных отношениях, а также социологии, теологии, этнографии и т.д. Для моделей, позволяющих выполнить планирование совместных действий объектов, большое значение имеют их технические характеристики, протоколы обмена информацией и др. Исследования в этих областях являются определяющими для таких моделей, однако большое значение имеет выбор средств для создания моделей.
В создании инструментов и конкретных моделей важную роль играют университетские исследования, в том числе исследования университетов University of Michigan [136], North Carolina State University [150, 168, 179, 181], University of Ottawa [177], Saint Louis University [192], Seikei University [170], University of Georgia [155], University of Pennsylvania [185] и др. Однако предоставляемая в открытой печати информация не позволяет судить о возможностях варьировать детализацией и размером моделей, о наличии возможностей получать при необходимости данные о промежуточных результатах моделирования.
В данном исследовании поставлена задача разработки моделей теории графов, предназначенных для планирования совместных действий объектов и их
групп или исследования взаимодействия субъектов, групп субъектов в системах с разнотипными информационными потоками.
В качестве элементарной единицы моделирования взаимодействия субъектов возможно использование как субъекта с частичным представлением функций, требуемых для реализации модели (оценивание ситуаций, событий, коммуникация, отдельные действия), так и результаты деятельности во внешней среде, ассоциированные с отдельной личностью. При моделировании совместных действий объектов также возможно использование не только самих объектов, но и их определенных представлений, например отдельных функций объектов, которые востребованы при взаимодействии.
В настоящее время отмечаются проблемы представления графовых моделей для анализа данных о взаимодействии объектов, субъектов или их групп. Исследованию вопросов взаимодействия субъектов в организационных системах и совместному действию объектов в технических системах с использованием графов и гиперграфов посвящены работы С.Л. Белякова, Л.С. Берштейна, А.В. Боженюка, А.Н. Целых и других ученых. В таких моделях вершина определена как элемент моделирования и отображает объект, субъект или их частичное представление, а отношения между элементами представлены ребрами (связями). Следует отметить, что предложенные модели позволяют учесть только однотипные связи, и при этом не учитывают существующие разнотипные и множественные связи в моделях. В ряде работ для моделирования систем с разнотипными информационными потоками обоснована необходимость использования разнотипных связей в графах и гиперграфах, а также связей между группами элементов в гиперграфах. Однако в литературных источниках отсутствуют результаты реализации и исследования моделей, учитывающих однотипные и разнотипные связи, использование которых может привести к росту временных затрат на организацию вычислений.
В связи с чем, отмечается необходимость разработки модифицированных графовых и гиперграфовых моделей систем с разнотипными информационными потоками, позволяющих использовать однотипные, разнотипные и множественные связи с учетом придания им смысловых значений (семантики) и снизить время на
вычисления в них. Для таких моделей требуется разработка методов представления и средств вычисления для анализа данных о взаимодействии субъектов, объектов. В графах для представления сложных смысловых структур, вершины могут представлять однотипные или разнотипные элементы модели, а ребра -однотипные или разнотипные отношения между элементами.
Научная проблема, решение которой содержится в диссертации, -отсутствие методов представления множественных и разнотипных связей в графах и гиперграфах и средств их исследования для решения практических задач в организационных и технических системах.
Цель и задачи исследования. Цель диссертационной работы заключается в разработке и исследовании графовых и гиперграфовых моделей с учетом множественных и разнотипных связей, позволяющих представить системы с разнотипными информационными потоками и уменьшить время выполнения анализа данных.
Для достижения поставленной цели необходимо решение следующих задач:
1) разработать графовую модель с учетом однотипных, разнотипных и множественных связей в виде вектора (далее множественные и разнотипные связи в графе), гиперграфовую модель, позволяющую учесть множественные и разнотипные связи между вершинами, связи вершин и групп вершин, а также связи между группами вершин (далее множественные и разнотипные связи в гиперграфе);
2) разработать единую форму представления множественных и разнотипных связей в графах и гиперграфах для их исследования;
3) разработать эффективные по критерию вычислительной сложности алгоритмы исследования графов и гиперграфов с множественными и разнотипными связями, позволяющие выполнять анализ данных с учетом полного или усеченного множества связей в моделях.
Под эффективными алгоритмами понимаются алгоритмы, вычислительная сложность которых не выше О (п3), что позволяет их использовать для решения практических задач [24];
4) разработать методы и алгоритмы преобразования графов и гиперграфов с множественными и разнотипными связями (алгоритмы свертки, разделения, догенерации графа, гиперграфа, методы локализации элементов модели);
5) разработать программный комплекс (ПК), реализующий графовые модели с учетом множественных и разнотипных связей, и алгоритмы исследования и преобразования модели.
Объектом исследования в диссертационной работе являются графовые и гиперграфовые модели.
Предметом исследования в диссертационной работе являются методы представления множественных и разнотипных связей в графах и гиперграфах и исследования таких моделей для задач анализа данных.
Методы исследований. При проведении исследований использовались аппарат теории графов и гиперграфов, теории нечетких множеств и методы имитационного моделирования.
Научная новизна работы. В диссертационной работе получены следующие новые научные результаты:
1. Разработаны модифицированные графовые модели, которые отличаются использованием множественных связей в виде вектора, объединяющих разнотипные связи, что позволяет уменьшить время выполнения анализа данных в системах с разнотипными информационными потоками (п.10 паспорта специальности, стр. 42-48).
2. Разработаны модифицированные гиперграфовые модели, отличающиеся использованием в своей структуре отдельных компонентов графов с множественными и разнотипными связями, что позволяет уменьшить время выполнения анализа данных в системах с разнотипными информационными потоками в группах элементов (п.10 паспорта специальности, стр. 48-57).
3. Предложена единая форма представления множественных и разнотипных связей в графах и гиперграфах в виде списковой структуры, отличающаяся объединением форм представления, что позволяет унифицировать представления
графов и гиперграфов для организации вычислений в таких моделях (п.10 паспорта специальности, стр. 39-42).
4. Разработаны модифицированные алгоритмы исследования графов и гиперграфов, отличающиеся учетом полного или усеченного множества связей, что позволяет при помощи вычисления характеристик модели выполнить анализ данных в системах с разнотипными информационными потоками. Предлагаемые алгоритмы сохраняют асимптотическую сложность известных алгоритмов, однако сокращают объем вычислений (п.5 паспорта специальности, стр. 62-70).
5. Разработаны новые алгоритмы преобразования графов и гиперграфов, отличающиеся от известных использованием объединенной формы представления в виде списковой структуры, позволяющие использовать средства обобщения, разделения и догенерации моделей больших размеров с множественными и разнотипными связями (п.5 паспорта специальности, стр. 72-107).
Основные положения, выносимые на защиту:
1. Модифицированные графовые и гиперграфовые модели с учетом множественных и разнотипных связей.
2. Единая форма представления множественных и разнотипных связей в графах и гиперграфах в виде списковой структуры.
3. Модифицированные алгоритмы исследования графов и гиперграфов с учетом полного или усеченного множества связей для анализа данных в системах с разнотипными информационными потоками.
4. Новые алгоритмы преобразования графов и гиперграфов с использованием объединенной формы представления в виде списковой структуры, в том числе алгоритмы свертки, разделения и догенерации моделей больших размеров с множественными и разнотипными связями.
Теоретическая значимость диссертационной работы заключается в разработке: графовых и гиперграфовых моделей, учитывающих множественные и разнотипные связи; средств представления таких моделей; алгоритмов исследования графов и гиперграфов, основанных на вычислении характеристик с учетом полного или усеченного множества связей; методов и алгоритмов
преобразования графов и гиперграфов (алгоритмы свертки, разделения, догенерации графа, гиперграфа, методы локализации элементов модели) с учетом множественных и разнотипных связей.
Практическую ценность диссертационного исследования составляют:
1) модифицированные графовые и гиперграфовые модели с учетом множественных и разнотипных связей и алгоритмы их исследования и преобразования, которые позволяют моделировать и исследовать разнотипные отношения элементов и групп элементов таких моделей для организационных и технических систем;
2) разработанный ПК, реализующий графы с учетом множественных и разнотипных связей, а также алгоритмы их исследования и преобразования (поиск кратчайших путей и вычисление метрических характеристик с учетом полного или усеченного множества связей, алгоритмы свертки и разделения модели).
Использование разработанного ПК при модернизации программного обеспечения (ПО) ДЛКМ.80611-03 «Комплекс программный обучающий по изучению промыслового расписания работ с пелагическим и донным тралами с 3D анимацией действий членов палубной команды при выполнении промысловых операций» тренажера РПТ-400 в КБМЭ «Вектор» позволило: создать модели взаимодействия операторов тренажера РПТ-400 в виде ситуационного графа для режимов выполнения упражнения «проверки знаний» и «экзамен» в соответствии с промысловым расписанием работ с пелагическим и донным тралами; повысить удобство визуального восприятия информации по результатам выполнения упражнения пользователем; снизить временные затраты на обработку взаимодействия операторов тренажера в 2 раза.
Основные результаты диссертационной работы внедрены: при модернизации ПО ДЛКМ.80611-03 тренажера РПТ-400 (ООО «Конструкторское бюро морской электроники «Вектор», г. Таганрог); в учебном процессе кафедры вычислительной техники Института компьютерных технологий и информационной безопасности (ФГАОУ ВО ЮФУ, г. Таганрог); при выполнении
НИР по проектной части государственного задания Минобрнауки России (проект №2.3928.2017/ПЧ) (ФГАОУ ВО ЮФУ, г. Таганрог).
Степень достоверности результатов проведенных исследований.
Достоверность результатов подтверждается положительными результатами применения разработанных алгоритмов, а также анализом результатов проведенных экспериментальных исследований.
Апробация работы. Основные результаты диссертационной работы были представлены на следующих конференциях: Международный конгресс по интеллектуальным системам и информационным технологиям «IS&IT», с. Дивноморское (2017-2019); Всероссийская научная конференция «Системный синтез и прикладная синергетика», пос. Н. Архыз, Карачаево-Черкесская республика (2017, 2019); Всероссийская научно-техническая конференция «Информационные технологии и информационная безопасность в науке, технике и образовании "ИНФОТЕХ-2017"», г. Севастополь (2017); XII Российская конференция с международным участием «Новые информационные технологии в исследовании сложных структур», пос. Катунь, Алтайский край (2018); VI Международная научно-практическая конференция «Инновационные технологии и дидактика в обучении «ITDT 2018», г. Таганрог (2018); III International Scientific Conference "Intelligent Information Technologies for Industry" (IITI'18), Sochi, Russia (2018); IV International Conference on Information Technologies in Engineering Education, Moscow, Russia (2018); XIV International Scientific-Technical Conference on Actual Problems of Electronics Instrument Engineering (APEIE 2018), Novosibirsk, Russia (2018); ITM Web of Conferences (ICICCI 2018).
Связь исследований с научными программами. Диссертационная работа выполнялась в рамках ряда научно-исследовательских работ. Соискатель является: исполнителем НИР (2017-2019) по проектной части государственного задания Минобрнауки России (проект № 2.3928.2017/ПЧ) по теме «Разработка и исследование принципов построения адаптивных высокопроизводительных интеллектуальных вычислительных комплексов для необитаемых мобильных роботизированных платформ коллективного сбора и обработки информации о
многомерной проблемной среде»; исполнителем гранта РФФИ (2017-2018) № 1708-00402 «Система методов и моделей интеллектуального оперативного контроля и предупреждения рисковых ситуаций на этапе проектирования сложных технических систем для объектов критических инфраструктур»; исполнителем внутреннего гранта Южного федерального университета (2017-2018) № ВнГр-07/2017-28 «Разработка теоретических основ и методов моделирования и анализа социальных графов для прогнозирования взаимодействия групп акторов»; исполнителем гранта РФФИ (2019) № 19-08-00152 «Разработка и развитие математических методов и моделей диагностики сложных технических систем при эксплуатации в условиях неопределенности».
Публикации. По основным результатам диссертации опубликовано 20 (без учета свидетельств о регистрации ПО) работ, в том числе 6 статей в рецензируемых центральных журналах, входящих в список ВАК, из них 2 опубликованы без соавторов; 4 статьи в международных научных изданиях, индексируемых Scopus; 10 тезисов докладов и статей в сборниках трудов конференций, из них 4 опубликованы без соавторов; 2 свидетельства о государственной регистрации программ для ЭВМ. Работы приведены в списке литературы и автореферате.
Структура и объем диссертации. Диссертация состоит из введения, пяти глав, заключения, списка литературы и приложений. Содержание работы изложено на 242 страницах, работа содержит 127 рисунков и 89 таблиц, список использованной литературы состоит из 197 наименований; приложения содержат 53 страницы.
Глава 1. Анализ моделей теории графов
1.1. Обзор существующих моделей теории графов для анализа данных
Аппарат теории графов достаточно развит, успешно применяется для
решения ряда практических задач и позволяет выполнять вычисления с последующим анализом данных. Весомый вклад в развитие теории графов и их приложений внесли ученые Л.С. Берштейн [57], В.А. Емеличев [29], А.А. Зыков [33, 34], В.М. Курейчик, А.Н. Мелихов, К. Берж (K. Berge) [10, 127], Ф. Харари (F. Harary) [111], Н. Кристофидес (N. Kristophides) [40], О. Оре (O. Ore) [74], У. Татт (W. Tatt) [106], Р. Уилсон (R. Wilson) [107] и др.
Формально граф [29] G = (VG, EG) задан множеством вершин V и множеством ребер E, где ve VG - вершины графа (v - vertex), где ee EG - вершины графа (е - edge).
В тоже время в работе [97] граф определен в соответствии с (1.1).
G = (Gv, Ge), (1.1)
где Gv = {gvi | i = 1, 2, ..., n} - множество вершин (gv - graph vertex) и Ge = (gey | j = 1, 2, m} (ge - graph edge), соединяющих пары вершин (gvz-, gvj) - множество ребер графа. В дальнейшем в работе будет использоваться описание графа в соответствии с (1.1) с целью унификации представления графов и гиперграфов.
Между элементами модели могут существовать различные отношения, например однонаправленные и двунаправленные. Необходимость представления данных для анализа двунаправленных отношений привело к использованию неориентированных графов (рисунок 1.1, а), ребра которых не имеют ориентации, а для представления однонаправленных отношений используют ориентированные графы (рисунок 1.1, б), где для каждого ребра задана направленность [74].
В теории графов для представления однонаправленных и двунаправленных отношений в одной модели используются смешанные графы, в которых встречаются ориентированные и неориентированные ребра (рисунок 1.1, в). Для отображения отношения элемента модели к самому себе во всех трех видах графов применяются петли, т.е. ребра типа (gvi, gvi). Использование смешанных графов дает больше возможностей для представления отношений между элементами
модели по сравнению с неориентированными и ориентированными графами, так как придание ориентации ребру или ее отсутствие позволяет придать связям различную смысловую нагрузку.
^ \ёУу \gv2j )
а) б) в)
Рисунок 1.1 - Изображения неориентированного (а) и ориентированного (б) и
смешанного (в) графа
Необходимость представления данных для анализа ряда отношений между парой элементов обосновывает использование графов с кратными ребрами (мулътиграфы), имеющих своими концами одну и ту же пару вершин [24]. Пример неориентированного мультиграфа с кратностью ребер к равной двум приведен на рисунке 1.2, а. Под величиной кратности ребер к понимается количество ребер одной ориентации, соединяющих одну и туже пару вершин. При этом мультиграфы, допускающие наличие петель называются псевдографами (рисунок 1.2, б). Простые графы - графы, не имеющие петель и кратных ребер.
ge2 §^2
а) б)
Рисунок 1.2 - Изображения мультиграфа (а) и псевдографа (б) Использование кратных ребер еще больше расширяет математический аппарат графов и позволяет одновременно задать несколько однотипных отношений между парой элементов модели. Однако требование кратности ребер накладывает определенные ограничения на граф в случае, если для элементов модели используются разные типы отношений.
Необходимость моделирования сложных структур, представленных иерархиями элементов или отношений, требует применения иерархических графов.
Формально иерархический граф [39] с учетом обозначений, принятых в (1.1):
Gh = (Gv, Ge, M, L)
задан множествами вершин Gv и ребер Ge, функцией типа M, которая назначает каждому элементу графа (gv, и/или gej) его тип M(Gh) = {M(gv,), M(gey)}, и функцией меток L, приписывающей каждому элементу графа его метку L (Gh) = {L (gv,), L (gey)}.
Всем элементам иерархического графа ставится в соответствие его тип и метка, например, в графе Gh (рисунок 1.3) используются вершины и ребра двух типов M1 (gv1-gv6), M2 (gv7), M1 (ge1-ge7), M2 (ge8-ge13). В качестве меток элементов такого графа используются их индексы.
Wy
Рисунок 1.3 - Изображение иерархического графа Gh Каждый из графов, рассмотренных выше, может быть взвешенным или невзвешенным. Взвешенный граф может иметь вершины и ребра с весовыми коэффициентами (весами).
Обоснование и примеры использования разнотипных связей для представления отношений между элементами в графах рассмотрены в работах [97, 129, 139]. При этом в работе отечественных исследователей используется термин «разнотипные связи», а ряд зарубежных исследователей применяет термины «uniplex» для представления связей одного типа и «multiplex» для представления связей разного типа в сетевых графах. А сетевые графы с такими связями называют «uniplex networks» и «multiplex networks». Термин «multiplex» (мультиплексный)
чаще используется в теории сетей, поэтому в рамках данного исследования для представления в графах связей одного типа предлагается применять термин «однотипные связи», а связей разного типа - термин «разнотипные связи».
Следует отметить, что число типов таких связей может достигать порядка десяти и более, что приводит к усложнению модели и ограничивает ее применимость на практике. Для решения этой проблемы требуется объединить ряд разнотипных связей в одну множественную связь.
Для представления групп элементов модели и их отношений применяются обобщения на графах, например гиперграфы и метаграфы.
Гиперграф представляет собой обобщение графа, в котором ребро может соединять не только две вершины, но и любые подмножества вершин [127]. Такое ребро принято называть ребром гиперграфа или гиперребром. В соответствии с работой [127] гиперграф задан парой H = (X, E), причем xi, Х2, ..., Xn - вершины из X, а множества E, состоящие из E1, E2, ..., Ef - ребра гиперграфа.
С другой стороны, в работе [97] гиперграф математически представлен как H = (Hv, He), где Hv - множество вершин гиперграфа hv (h - hypergraph) и He -множество гиперребер he. Однако с целью унификации представления моделей графа и гиперграфа предлагается использовать обозначения, введенные в (1.1). Тогда гиперграф может быть описан в (1.2) множеством вершин гиперграфа Gv и множеством гиперребер He = {hee | e = 1, 2, ...,f}, где he - hyper edge.
H = (Gv, He) (1.2)
Для формирования групп элементов используются неориентированные гиперграфы, заданные в (1.2). На рисунке 1.4, а изображен неориентированный гиперграф, заданного множеством вершин Gv = {gv1, gv2, gv3, gv4, gv5, gv6, gv7, gv8} и множеством гиперребер He = {he1, he2, he3, he4}, где he1 = {gv1, gv2, gv7}, he2 = {gv4, gvs, gvg}, he3 = {gv3, gv4, gvg} и he4 = {gv2, gv3, gv6, gv7}.
Однако отношения элементов в такой модели определяются только принадлежностью к группе. Для представления других отношений элементов целесообразно использовать ориентированные или смешанные гиперграфы.
Согласно работам А.А. Зыкова, К. Бержа [33, 127] гиперребра могут быть неориентированными (если порядок соединения вершин не имеет значение) или ориентированными, если задана последовательность соединения вершин. Л.С. Берштейном предложена другая интерпретация ориентированного гиперграфа. В каждом гиперребре оргиперграфа выделяется одна вершина из подмножества, затем выделенные вершины помечаются как вершины с особым статусом (на рисунке1.4, б это вершины gv*1, gv*3, gv*5, gv%). Особый статус в данном случае заключается в некотором отношении к данной вершине со стороны всех остальных вершин, объединенных гиперребром.
Рисунок 1.4 - Изображения неориентированного (а) и ориентированного гиперграфа с выделенными вершинами (б)
В случае, если вершины с особым статусом присутствуют не в каждом гиперребре гиперграфа, как например на рисунке 1.5, а, то такой гиперграф принято называть смешанным.
Рисунок 1.5 - Изображение смешанного гиперграфа с учетом одной выделенной вершины (а), с учетом связей между вершинами (б)
Данный подход получил развитие в работе [99], где сделано предположение, что внутри гиперребра существуют более сложные отношения между вершинами, чем принадлежность гиперребру или отношение к выделенной вершине. Тогда особое отношение к выделенной вершине со стороны других вершин предложено обозначать ребром ge, как в графе, описанном в (1.1). Таким образом, выполняется интеграция графа в гиперграф (integrated hypergraph), где под интеграцией понимается процесс использования отдельных компонентов графов в структуре гиперграфа. На рисунке 1.5, б изображен пример смешанного гиперграфа с выделенной вершиной gv*5, связанной ребрами ge1 и ge2 с вершинами gv4 и gv8. Логично предположить, что в смешанном гиперграфе может быть не одна, а несколько вершин, к которым идут связи от других вершин. Таким образом, в смешанном гиперграфе вершина может не только принадлежать гиперребру, но и иметь отношение к выделенной вершине.
Похожие диссертационные работы по специальности «Теоретические основы информатики», 05.13.17 шифр ВАК
Алгебра инвариантов и восстановление к-орбит группы перестановок1984 год, кандидат физико-математических наук Мнухин, Валерий Борисович
Математические модели агро-эколого-экономических задач на графах и гиперграфах в условиях многокритериальности2002 год, кандидат физико-математических наук Салпагаров, Солтан Исмаилович
Алгоритмы анализа сложных схем1997 год, доктор технических наук Наумов, Леонид Анатольевич
Методология информационной поддержки принятия решений при разработке технологических аппаратов многоассортиментных химических производств2018 год, кандидат наук Мокрозуб, Владимир Григорьевич
Методы и алгоритмы управления маршрутизацией в транспортных сетях на основе оперативной обработки информации в разреженных графах2015 год, кандидат наук Тимеряев, Тимофей Валерьевич
Список литературы диссертационного исследования кандидат наук Мунтян Евгения Ростиславна, 2020 год
СПИСОК ЛИТЕРАТУРЫ
1. Аверкин, А.Н. Нечеткие множества в моделях управления искусственного интеллекта / А.Н. Аверкин, И.З. Батыршин и др.; под ред. Д.А. Поспелова. - М.: Наука, 1986. - 312 с.
2. Апанович, З.В. Методы навигации при визуализации графов / З.В. Апанович // Вестник НГУ. Серия Информационные технологии. - 2008. - Т. 6. - № 3. - С. 35-47.
3. Астанин, С.В. Вложенные метаграфы как модели сложных объектов [Электронный ресурс] / С.В. Астанин, Н.В. Драгныш, Н.К. Жуковская // Инженерный вестник Дона. - 2012. - Режим доступа: http://ivdon.ru/magazine/ archive/n4p2y2012/1434.
4. Бабурин, Д.Е. Иерархический подход для автоматического размещения ациклических графов [Электронный ресурс] / Д.Е. Бабурин // Современные проблемы конструирования программ. - 2002. - С. 7-37. Режим доступа: https://www.iis.nsk. su/files/articles/sbor_ kas_09_baburin. pdf
5. Бадрызлов, В.А. Классификация случайных графов с предпочтительным связыванием / В.А. Бадрызлов // Омский научный вестник. - 2017. - № 4(154). -С. 124-128.
6. Батищев, Д.И. Применение генетических алгоритмов к решению задач дискретной оптимизации / Д.И. Батищев, Е.А. Неймарк, Н.В. Старостин. -Н. Новгород: Изд-во ННГУ, 2006. - 85 с.
7. Батищев, Д.И. Многоуровневый генетический алгоритм решения задачи декомпозиции гиперграфа / Д.И. Батищев, Н.В. Старостин, А.В. Филимонов // Известия СПбГЭТУ «ЛЭТИ». - 2007. - Вып. 2. - С. 3-13.
8. Белов, Ю.А. Генерация графа социальной сети с использованием Apache Spark / Ю.А. Белов, С.И. Вовчок // Моделирование и анализ информационных систем. - 2016. - Т. 23. - № 6. - С. 777-783.
9. Беляков, С.Л. Кластеризация при логистическом ройтинге / С.Л. Беляков, М.Н. Савельева // Известия ЮФУ. Технические науки. - 2012. -С. 242-246.
10. Берж, К. Теория графов и ее применения / К. Берж - М.: Изд-во иностранной литературы, 1962. - 311 с.
11. Берновский, М.М. Случайные графы, модели и генераторы безмасштабных графов / М.М. Берновский, Н.Н. Кузюрин // Тр. Института системного программирования РАН. - 2012. - Т.22. - С. 419-434.
12. Берштейн, Л.С. Анализ социальных графов методом оценки степени изоморфизма нечетких графов на основе нечетких клик [Электронный ресурс] / Л.С. Берштейн // Современные проблемы науки и образования. - 2013. - № 6. -Режим доступа: https://www.science-education.ru/ru/article/ view?id=11188.
13. Берштейн, Л.С. Использование нечетких темпоральных графов для моделирования в ГИС / Л.С. Берштейн, С.Л. Беляков, А.В. Боженюк // Известия ЮФУ. Технические науки. - 2012. - № 1(126). - С. 121-127.
14. Берштейн, Л.С. Нечеткие графы и гиперграфы / Л.С. Берштейн, А.В. Боженюк. - М.: Научный мир, 2005. - 256 с.
15. Берштейн, Л.С. Нечеткие инварианты нечетких графов и гиперграфов / Л.С. Берштейн, А.В. Боженюк // Нечеткие системы и мягкие вычисления. - 2011. -Т. 6. - №1. - С.43-54.
16. Биткина, В.В. Об автоморфизмах дистанционно регулярного графа с массивом пересечений [Электронный ресурс] / В.В. Биткина // Сибирские электронные математические известия. - 2017. - Т. 14. - С. 26-32. - Режим доступа: http://semr.math.nsc.ru.
17. Боровский, А.С. Интегрированный подход к разработке общей модели функционирования систем физической защиты объектов / А.С. Боровский, А.Д. Тарасов // Труды ИСА РАН. - 2011. - Т. 61(1). - С. 3-13.
18. Бувайло, Д.П. Быстрый высокопроизводительный алгоритм для разделения нерегулярных графов / Д.П. Бувайло, В.А. Толок // Вюник Запорiзького державного ушверситету. - 2002. - №2. - С. 47-53.
19. Вахштайн, В.С. Джон Ло: социология между семиотикой и топологией / В.С. Вахштайн // Социологическое обозрение. - 2006. - Т. 5. - № 1. - С. 24-28.
20. Визинг, В.Г. Некоторые нерешенные задачи в теории графов /
B.Г. Визинг // Успехи математических наук. - 1968. - Т. 23. - Вып. 6(144). -
C. 117-134.
21. Виссия, Х. Технология распределения IT-проектов коллективами распределенных исполнителей / Х. Виссия, В.В. Краснопрошин, А.Н. Вильвачев // журнал Искусственный интеллект. - 2008. - № 3. - С. 63-69.
22. Востокин, С.В. Применение предметных языков и акторной модели для автоматизации высокопроизводительных вычислений / С.В. Востокин, Е.Г. Скорюпина, Д.М. Наширванов // Известия Самарского научного центра РАН. - 2016. - Т. 18. - № 4(4). - С. 696-699.
23. Гладков, Л.А. Генетические алгоритмы / Л.А. Гладков, В.В. Курейчик, В.М. Курейчик. - М.: ФИЗМАТЛИТ, 2010. - 386 с.
24. Гладков, Л.А. Дискретная математика: учебник / Л.А. Гладков, В.В. Курейчик, В.М. Курейчик. - М.: ФИЗМАТЛИТ, 2014. - 496 с.
25. Городецкий, В.И. Многоагентные системы (обзор) / В.И. Городецкий, М.С. Грушинский, А.В. Хабалов // Новости искусственного интеллекта. - 1998. -№ 2. - С. 64-116.
26. Долинина, О.Н. Использование графовых моделей для визуализации социальных сетей образовательной организации / О.Н. Долинина, В.В. Печенкин, В.В. Тарасова // Вестник СГТУ, 2009. - № 4(43). - Вып. 2. - С. 210-214.
27. Евин, И.А. Введение в теорию сложных сетей / И.А. Евин // Компьютерные исследования и моделирование. - 2010. - Т. 2. - № 2. - С. 121-141.
28. Егоров, А.А. Математические модели и алгоритмы эвакуации людей в аварийных ситуациях в учебных заведениях : автореф. дис. ... канд. техн. наук : 05.13.18 / Егоров Алексей Александрович. - Саратов., 2008. - 19 с.
29. Емеличев, В.А. Лекции по теории графов / В.А. Емеличев, О.И. Мельников, В.И. Сарванов, Р.И. Тышкевич. - М.: Наука, 1990. - 384 с.
30. Емельянов, В.В. Теория и практика эволюционного моделирования / В.В. Емельянов, В.В. Курейчик, В.М. Курейчик. - М.: ФИЗМАТЛИТ, 2003. - 432 с.
31. Задорожный, В. Н. Случайные графы с нелинейным правилом предпочтительного связывания / В. Н. Задорожный // Проблемы управления. -2010. - № 6. - С. 2-11.
32. Задорожный, В.Н. О неоднородной структуре социальных сетей /
B.Н. Задорожный, Е.Б. Юдин // Омский научный вестник. - 2017. - № 2(152). -
C. 91-96.
33. Зыков, А.А. Гиперграфы / А.А. Зыков // Успехи математических наук. -1974. - Т. 29. - № 6. - С. 89-154.
34. Зыков, А.А. Основы теории графов / А.А. Зыков. - М.: Вузовская книга, 2004. - 664 с.
35. Иванова, Г.С. Оценка эффективности параллельных алгоритмов операций преобразования графовой модели [Электронный ресурс] / Г.С. Иванова, А.А. Головков // Наука и Образование. - 2014. - №11. - С. 535-554. - Режим доступа: https://technomagelpub. elpub.ru/jour/article/view/754.
36. Инструмент для работы с графами онлайн [Электронный ресурс]. -Режим доступа: http://graphonline.ru/.
37. Каганов, Ю.Т. Гибридизация метаграфового подхода и подхода на основе символической динамики для разработки интеллектуальных информационных систем / Ю.Т. Каганов, Г.И. Ревунков, Ю.Е. Гапанюк // Гибридные и синергетические интеллектуальные системы: матер. IV Всерос. Поспеловской конф. с Междунар. участием. - Калининград: Изд-во БФУ им. И. Канта. - 2018. - С. 192-199.
38. Карелин, В.П. Модели и методы теории графов в системах поддержки принятия решений / В.П. Карелин // Вестник Таганрогского института управления и экономики. - 2014. - № 2(20). - С. 69-73.
39. Касьянов, В.Н. Иерархические графы и графовые модели: вопросы визуальной обработки / В.Н. Касьянов // Проблемы систем информатики и программирования. - Новосибирск: ИСИ СО РАН, 1999. - С. 7-32.
40. Кристофидес, Н. Теория графов. Алгоритмический подход / Н. Кристофидес. - М.: Мир, 1978. - 432 с.
41. Колодкин, В.М. Модель движения людских потоков для управления эвакуацией при пожаре в здании / В.М. Колодкин, Б.В. Чирков, В.К. Ваштиев // Вестник Удмуртского университета. Математика. Механика. Компьютерные науки. - 2015. - Т. 25. - № 3. - С. 430-438.
42. Коломейченко, М.И. Программный комплекс для анализа и визуализации графов / М.И. Коломейченко, А.А. Золотых, И.В. Поляков, А.М. Чеповский // Моделирование и анализ информационных систем. - 2014. -Т. 21. - № 6. - С. 155-168.
43. Кормен, Т. Алгоритмы. Построение и анализ / Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн. - М.: Вильямс, 2006. - 960 с.
44. Коршунов, А.В. Задачи и методы определения атрибутов пользователей социальных сетей / А.В. Коршунов // Электронные библиотеки: перспективные методы и технологии, электронные коллекции: тр. 15-й Всерос. науч. конф. -RCDL'2013. - 2013. - С. 183-193.
45. Котенко, И.В. Многоагентное моделирование распределенных атак «Отказ в обслуживании» и механизмов защиты от них / И.В. Котенко, А.В. Уланов // Труды СПИИРАН. - 2006. - Т. 1. - № 3. - С. 105-125.
46. Кофман, А. Введение в теорию нечетких множеств / А. Кофман. - М.: Радио и связь, 1982. - 432 с.
47. Курапов, С.В. Топологические методы построения рисунка графа / С.В. Курапов, В.С. Чеченя // Радюелектрошка, шформатика, управлшня. - 2013. -№ 1. - С. 72-81.
48. Курапов, С.В. Проверка планарности и построение топологического рисунка плоского графа (поиском в глубину) / С.В. Курапов, М.В. Давидовский // Прикладная дискретная математика. - Томск: ТГУ. - 2016. - № 2(32). - С. 100-114.
49. Курейчик, В.В. Эволюционные алгоритмы разбиения графов и гиперграфов / В.В. Курейчик, П.В. Сороколетов // Известия ТРТУ. - 2004. -№ 3(38). - С. 42-49.
50. Курейчик, В.М. Гибридный алгоритм разбиения на основе природных механизмов принятия решений / В.М. Курейчик, Б.К. Лебедев, О.Б. Лебедев // Искусственный интеллект и принятие решений. - 2012. - № 2. - С. 3-15.
51. Латур, Б. Пересборка социального. Введение в акторно-сетевую теорию / Б. Латур. - М.: ГУ-ВШЭ, 2014. - 384 с.
52. Левитин, А.В. Алгоритмы: введение в разработку и анализ / А.В. Левитин. - М.: Вильямс, 2006. - 570 с.
53. Ло, Дж. Объекты и пространства / Дж. Ло // Социологическое обозрение. - 2006. - № 1. - С. 30-42.
54. Малов, Е.А. О концепции «актор-сети» Бруно Латура / Е.А. Малов // Идеи и идеалы. - 2014. - Т. 2. - № 1(19). - С. 127-134.
55. Мелентьев, В.А. Аналитический подход к синтезу регулярных графов с заданными значениями порядка, степени и обхвата / В.А. Мелентьев // Прикладная дискретная математика. - 2010. - № 2(8). - С. 74-86.
56. Мелихов, А.Н. Ситуационные советующие системы с нечеткой логикой / А.Н. Мелихов, Л.С. Берштейн, С.Я. Коровин. - М.: Наука, 1990. - 272 с.
57. Мелихов, А.Н. Применение графов для проектирования дискретных устройств / А.Н. Мелихов, Л.С. Берштейн, В.М. Курейчик. - М.: Наука, 1974. -304 с.
58. Мунтян, Е.Р. О задаче разделения графа на пропорциональные подмножества вершин / Е.Р. Мунтян // Информационные технологии и информационная безопасность в науке, технике и образовании: сб. стат. Всерос. науч.-техн. конф.: СевГУ. - 2017. - С. 71-73.
59. Мунтян, Е.Р. Подходы к догенерации графа репрезентативной выборки для моделирования взаимодействия социальных групп / Е.Р. Мунтян // Информатизация и связь. - 2018. - №4. - С. 18-24.
60. Мунтян, Е.Р. О задаче догенерации графа при моделировании взаимодействия социальных групп / Е.Р. Мунтян // Новые информационные технологии в исследовании сложных структур: мат. 12-й конф. с Междунар. уч. -Томск: Издательский Дом ТГУ. - 2018. - С. 99-100.
61. Мунтян, Е.Р. Разработка программного комплекса для моделирования взаимодействия акторов и их групп на основе графов / Е.Р. Мунтян // Инновационные технологии и дидактика в обучении: сб. стат. Междунар. науч.-практ. конф. - Таганрог: Изд-во ЮФУ, 2018. - Т. 1. - С. 74-78.
62. Мунтян, Е.Р. Программный модуль для моделирования взаимодействия акторов и групп акторов на основе графов. Свид. о гос. регистр. прогр. для ЭВМ № 2018665593; зарег. 06.12.2018. - М.: Роспатент, 2018.
63. Мунтян, Е.Р. Программный модуль для представления акторов и отношений между акторами на основе графов. Свид. о гос. регистр. прогр. для ЭВМ № 2018665499; зарег. 05.12.2018. - М.: Роспатент, 2018.
64. Мунтян, Е.Р. Особенности использования графов при моделировании сложных технических систем / Е.Р. Мунтян // Системный синтез и прикладная синергетика: сб. науч. тр. VIII Всерос. научн. конф. - Ростов-на-Дону; Таганрог: Изд-во ЮФУ. - 2019. - С. 228-233.
65. Мунтян, Е.Р. Реализация нечеткой модели взаимодействия объектов сложных технических систем на основе графов / Е.Р. Мунтян // Программные продукты и системы. - 2019. - Т. 32. - № 3. - С. 411-418.
66. Мунтян, Е.Р. Анализ методов моделирования движения людских потоков / Е.Р. Мунтян, В.В. Лиотвейзен // Информационные технологии, системный анализ и управление: сб. трудов XII Всерос. научн. конф. молодых ученых, аспир. и студ. - Таганрог: Изд-во ЮФУ. - 2015. - Т. 1. - С. 86-90.
67. Муравьев, А.А. Некоторые подходы к определению эффективности сетевой структуры и реализация рентоориентированного поведения актора в сети / А.А. Муравьев // Вестник КГУ им. Н.А. Некрасова. - 2011. - № 2. - С. 330-333.
68. Муха, Ю.П. Алгоритм для определения возможности наложения направленных графов / Ю.П. Муха, В.А. Секачев // Известия ВолТГУ. - 2014. -Т. 9. - № 10(137). - С. 87-97.
69. Назар, Б. Генерация социальных графов и поиск сообществ [Электронный ресурс] / Б. Назар. - Режим доступа: http://docplayer.ru/59872524-Generaciya-socialnyh-grafov-i-poisk-soobshchestv.html.
70. Нечепуренко, М.И. Алгоритмы и программы решения на графах и сетях / М.И. Нечепуренко, В.К. Попков, С.М. Майнагашев и др. - Новосибирск: Наука. Сиб. Отд-ие, 1990. - 515 с.
71. Носова, М.В. Моделирование распространения информации в децентрализованных сетевых системах с нерегулярной структурой / М.В. Носова, Л.И. Сенникова // Новые информационные технологии в автоматизированных системах: матер. XVII Науч.-практ. сем. - М.: ИПМ им. М.В. Келдыша. - 2014. -С. 329-335.
72. Овчинников, В.А. Математические модели объектов задач структурного синтеза [Электронный ресурс] / В.А. Овчинников // Наука и образование. - 2009. -№3. - Режим доступа: http://engineering-science.ru/doc/115712.html.
73. Овчинников, В.А. Графы в задачах анализа и синтеза структур сложных систем / В.А. Овчинников. - М.: Изд-во МГТУ им. Н.Э. Баумана, 2014. - 423 с.
74. Оре, О. Теория графов / О. Оре. - М.: Наука, 1980. -336 с.
75. Пастухов, Р.К. Улучшение качества разбиения графа с помощью многоуровневой оптимизации / Р.К. Пастухов, А.В. Коршунов, Д.Ю. Турдаков, С.Д. Кузнецов // Труды ИСП РАН. - 2014. - Т. 26. - Вып. 4. - С. 21-31.
76. Подольский, В.Э. Об организации параллельной работы некоторых алгоритмов поиска кратчайшего пути на графе в вычислительной системе с многими потоками команд и одним потоком данных [Электронный ресурс] / В.Э. Подольский // Наука и Образование. - 2015. - № 04. - С. 189-214. - Режим доступа: https://technomagelpub. elpub.ru/jour/article/view/320.
77. Полонская, И.Н. Альтернативная социология Б. Латура: к характеристике методологии / И.Н. Полонская // Теория и практика общественного развития. - 2012. - № 6. - С. 72-75.
78. Полянский, И.С. Математическая модель комплекса инженерно-технических средств системы физической защиты объекта охраны / И.С. Полянский, И.И. Беседин, Б.Л. Панин // Фундаментальные исследования. Технические науки. - 2013. - № 6. - С. 1359-1365.
79. Поляков, И.В. Алгоритмы поиска путей на графах большого размера / И.В. Поляков, А.А. Чеповский, А.М. Чеповский // Фундаментальная и прикладная математика. - 2014. - Т. 19. - № 1. - С. 165-172.
80. Поспелов, Д.А. Многоагентные системы - настоящее и будущее / Д.А. Поспелов // Информационные технологии и вычислительные системы. - 1998. - № 1. - С. 14-21.
81. Прохоренкова, Л.А. Свойства случайных веб-графов, основанных на предпочтительном связывании: автореф. дис. ... канд. физ.-мат. наук : 01.01.05 / Прохоренкова Людмила Александровна. - М., 2015. - 19 с.
82. Райгородский, А.М. Модели случайных графов / А.М. Райгородский. -М.: МЦНМО, 2011. - 136 с.
83. Рассел, Дж. Модель акторов / Дж. Рассел, Р. Кон. - VSD, 2012. - 102 с.
84. Русаков, А.С. Оптимизация алгоритма разбиения гиперграфа с произвольными весами вершин / А.С. Русаков, М. В. Шеблаев // Вычислительные методы и программирование. - 2014. - Т. 15. - С. 400-410.
85. Сазанов, В.М. Социальные сети и технологии / В.М. Сазанов. - М.: Лаборатория СВМ, 2013. - 362 с.
86. Сайт программы Графоанализатор [Электронный ресурс]. - Режим доступа: http: //grafoanalizator.unick- soft.ru/about.html.
87. Самосват, Е.А. Моделирование Интернета с помощью случайных графов: автореф. дис. ... канд. физ.-мат. наук 05.13.18 / Самосват Егор Александрович. - М., 2014. - 28 с.
88. Сергеев, Н.Е. Оценка квалификации выпускников вузов на основе нечетких графовых подходов / Н.Е. Сергеев, А.Е. Колоденкова, Е.Р. Мунтян // Информатизация инженерного образования: тр. Междунар. науч.-практич. конф. -М.: Издательский дом МЭИ. - 2018. - С. 196-201.
89. Сергеев, Н.Е. О решении некоторых задач, возникающих при моделировании взаимодействия социальных групп / Н.Е. Сергеев, Е.Р. Мунтян // Системный синтез и прикладная синергетика: сб. науч. труд. VIII Всерос. научн. конф. - Ростов-на-Дону; Таганрог: Изд-во ЮФУ. - 2017. - С. 240-249.
90. Сергеев, Н.Е. О проблемах при моделировании взаимодействия социальных групп / Н.Е. Сергеев, Е.Р. Мунтян // Конгресс по интеллектуальным системам и информационным технологиям «IS&IT'17»: тр. конгресса. -Таганрог: Изд-во Ступина С.А. - 2017. - Т. 2. - С. 149-151.
91. Сергеев, Н.Е. Локализация вершин графа для задач представления объектов / Н.Е. Сергеев, Е.Р. Мунтян // Известия ЮФУ. Технические науки. - 2017. - № 7. - С. 144-154.
92. Сергеев, Н.Е. Применение алгоритма свертки для разделения графа на пропорциональные подграфы / Н.Е. Сергеев, Е.Р. Мунтян // Вестник УГАТУ. -2018. - Т. 22. - № 1(79). - С. 121-130.
93. Сергеев, Н.Е. Обобщение графов ситуаций на основе спискового алгоритма свертки для задач ситуационного управления / Н.Е. Сергеев, Е.Р. Мунтян, А.А. Целых, А.Н. Самойлов // Известия ЮФУ. Технические науки. -2017. - № 3. - С. 111-121.
94. Сергеев, Н.Е. Использование списков для представления социальных отношений / Н.Е. Сергеев, Е.Р. Мунтян // Информатизация и связь. - 2018. - № 4. -С. 43-49.
95. Сергеев, Н.Е. Интерпретация социальных отношений в гиперграфовых моделях / Н.Е. Сергеев, Е.Р. Мунтян // Конгресс по интеллектуальным системам и информационным технологиям «IS&IT'18»: тр. конгресса. - Таганрог: Изд-во Ступина С.А. - 2018. - Т. 2. - С. 79-87.
96. Сергеев, Н.Е. Представление объектов сложных технических систем в моделях на основе нечетких графов / Н.Е. Сергеев, Е.Р. Мунтян // Конгресс по интеллектуальным системам и информационным технологиям «IS&IT'19»: тр. конгресса. - Таганрог: Изд-во Ступина С.А. - 2019. - Т. 2. - С. 20-23.
97. Сергеев, Н.Е. Нечеткие теоретико-графовые подходы к моделированию и анализу социосемантических сетей знаний для задач принятия решений в научной и научно-технической экспертизе [Электронный ресурс] / Н.Е. Сергеев, А.А. Целых // Науч. журн. КубГАУ. - Краснодар: КубГАУ. - 2016. - № 09(123). -С. 1-21. Режим доступа: http://ej.kubagro.ru/2016/09/pdf/27.pdf.
98. Сергеев, Н.Е. Методологические аспекты моделирования социальных систем для анализа и управления конфликтами [Электронный ресурс] / Н.Е. Сергеев, А.А. Целых, Ю.А. Смелова // Науч. журн. КубГАУ. - Краснодар: КубГАУ. - 2017. - № 133(09). - С. 1-24. Режим доступа: http://ej.kubagro.ru/ 2017/09/pdf/71 .pdf.
99. Сергеев, Н.Е. GH-модели социальных сетей / Н.Е. Сергеев, Ю.А. Целых // Известия ЮФУ. Технические науки. - 2009. - № 1. - С. 90-95.
100. Сироткин, Д.В. Способ редукции графов и его приложения / Д.В. Сироткин, Д.С. Малышев // Дискретная математика. - 2017. - Т. 29. - Вып. 3.
- С. 114-125.
101. Скобелев, П.О. Открытые мультиагентные системы для оперативной обработки информации в процессах принятия решений : автореф. дис. ... докт. техн. наук 05.13.01 / Скобелев Петр Олегович. - Самара, 2003. - 38 с.
102. Смирнов, А.В. Задача о кратчайшем пути в кратном графе / А.В. Смирнов // Моделирование и анализ информационных систем. - 2017. - Т. 24.
- № 6. - С. 788-801.
103. Социология вещей. Сборник статей; под ред. В. Вахштайна. - М.: Издательский дом «Территория будущего», 2006. - 392 с.
104. Старостин, Н.В. Многоуровневый параллельный алгоритм k-декомпозиции гиперграфов / Н.В. Старостин, А.В. Филимонов // Высокопроизводительные параллельные вычисления на кластерных системах: сб. матер. IX Междунар. конф.-сем. - 2009. - С. 371-374.
105. Тарасов, В.Б. От многоагентных систем к интеллектуальным организациям: философия, психология, информатика / В.Б. Тарасов. - М.: Эдиториал УРСС, 2002. - 352 с.
106. Татт, У. Теория графов / У. Татт. - М.: Мир, 1988. - 424 с.
107. Уилсон, Р. Введение в теорию графов / Р. Уилсон. - М.: Мир, 1977. -
208 с.
108. Ураков, А.Р. Использование особенностей взвешенных графов для более быстрого определения их характеристик / А.Р. Ураков, Т.В. Тимеряев // Прикладная дискретная математика. - 2012. - № 2(16). - С. 95-99.
109. Ураков, А.Р. Алгоритмы быстрого поиска для двух задач о метрических характеристиках взвешенных графов / А.Р. Ураков, Т.В. Тимеряев // Управление большими системами: сб. труд. - 2013. - № 42. - С. 153-172.
110. Фостер, Дж. Обработка списков / Дж. Фостер. - М.: Мир, 1974. - 72 с.
111. Харари, Ф. Теория графов / Ф. Харари. - М.: Мир, 1973. - 300 с.
112. Целых, А.А. Графогиперграфовая модель сементической социальной сети / А.А.Целых // Известия ЮФУ. Технические науки. - 2012. - №4. - С. 225-229.
113. Целых, А.Н. Методы нечетко-множественного анализа и моделирования социальных графов [Электронный ресурс] / А.Н. Целых, Э.М. Котов // Современные проблемы науки и образования. - 2013. - № 6. - Режим доступа: https://www.science-education.ru/ru/article/view?id=11178.
114. Черненький, В.М. Метаграфовый подход для описания гибридных интеллектуальных информационных систем / В.М. Черненький, Ю.Е. Гапанюк, Г.И. Ревунков, В.И. Терехов, Ю.Т. Каганов // Прикладная информатика. - 2017. -Т. 12. - № 3(69). - С. 57-78.
115. Чураков, А.Н. Анализ социальных сетей / А.Н. Чураков // Социологические исследования. - 2001. - № 1. - С. 109-121.
116. Шахов, В.В. Эффективный метод генерации случайных геометрических графов для моделирования беспроводных сетей / В.В. Шахов, А.Н. Юргенсон, О.Д. Соколова // Прикладная дискретная математика. - 2016. -№ 4(34). - С. 99-109.
117. Швецов, А.Н. Агентно-ориентированные системы: от формальных моделей к промышленным приложениям [Электронный ресурс] / А.Н Швецов. -Информационно-телекоммуникационные системы: Всерос. конкурс. отбор обзорно-аналит. стат. по приоритетному направлению, 2008. - 101 с. Режим доступа: http://window.edu.ru/resource/179/56179/responses.
118. Шматков, С.И. Анализ распараллеливания алгоритма задачи оптимального разделения графа на подграфы / С.И. Шматков, Е.Г. Толстолужская, Ю.А. Артюх // Сбор. научн. тр. Харьковского университета Воздушных Сил. -2013. - Вып. 2(35). - С. 132-134.
119. Шмелева, И.А. Проблема взаимодействия человека с окружающей средой: области и аспекты психологического исследования / И.А. Шмелева // Вестник Московского университета. Психология. - 2010. - № 3. - С. 105-120.
120. Щербакова, В.А. Мощностная задача Штейнера на ориентированном градуированном графе / В.А. Щербакова //Известия УрГУ. - 1998. - № 10. -С. 127-146.
121. Ярушкина, Н.Г. Основы теории нечетких и гибридных систем / Н.Г. Ярушкина. - М.: Финансы и статистика, 2004. - 320 с.
122. Agha, G. An algebraic theory of actors and its application to a simple object-based language [Электронный ресурс] / G. Agha, P. Thati. - Режим доступа: https://web.archive.org/web/20040420064252/http://formal.cs.uiuc.edu/papers/ATactors _festschrift.pdf.
123. Aiello, W. A random graph model for massive graphs / W. Aiello, F. Chung, L. Lu. // STOC'2000: proc. of the thirty-second annual ACM symposium on Theory of computing. - N.Y.: ASM Press. - 2000. - P. 171-180.
124. Barabasi, A.-L. Emergence of scaling in random networks / A.-L. Barabasi, R. Albert // Science. - 1999. - Vol. 286. - No 5439. - P. 509-512.
125. Basu, A., Blanning R. Metagraphs and their applications / A. Basu, R.W. Blanning // Springer, 2010. - 173p.
126. Bellman, R. On a routing problem / R. Bellman // Quarterly of Applied Mathematics. - 1958. - Vol. 16. - No. 1. - P. 87-90.
127. Berge, C. Hypergraphs: combinatorics of finite sets / C. Berge // North-Holland, 1989. - 255 p.
128. Berman, P. Faster Approximation of Distances in Graphs / P. Berman, S.P. Kasiviswanathan // Algorithms and data structures. Lecture notes in computer science. - 2007. - Vol. 4619. - P. 541-552.
129. Boccalettia, S. The structure and dynamics of multilayer networks / S. Boccalettia, G. Bianconic, R. Criadod, C.I. del Geniof, J. Gomez-Gardenesi, M. Romanced, I. Sendina-Nadalj, Z. Wangk, M. Zaninm // Preprint submitted to Physics Reports July 16, 2014. - p. 157.
130. Boldi, P. HyperANF: approximating the neighbourhood function of very large graphs on a budget / P. Boldi, M. Rosa, S. Vigna // Proc. of the 20th Internat. conf. on World wide web. - N.Y.: ACM Press. - 2011. - P. 625-634.
131. Bollobas, B. Directed scale free graphs / B. Bollobas, C. Borgs, J. Chayes, O. Riordan // Proc. of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms. - N.Y.: ACM Press. - 2003. - P. 132-139.
132. Bos, N.D. Sociocultural modeling in the social identity look-ahead simulation and the green country model / N.D. Bos, A.M. Greenberg, J.J. Kopecky, A.G. Ihde, S.D. Simpkins // Johns Hopkins APL Technical Digest (Applied Physics Laboratory). - 2001. - № 30(1). - P. 13-21.
133. Caldwell, A.E. Improved algorithms for hypergraph bipartitioning / A.E. Caldwell, A.B. Kahng, I.L. Markov // Proc. of the 2000 ACM Asia and South Pacific Design Automation Conference. - N.Y.: ACM Press. - 2000. - P. 661-666.
134. Callon, M. Society in the Making: The Study of Technology as a Tool for Sociological Analysis / M. Callon // The social construction of technological systems: new directions in the sociology and history of technology. - London: MIT Press. - 1987. - P. 83-103.
135. Chen, X. The Shortest Path Algorithms of Hypergraphs Based on Search Strategies / X. Chen // Journal of Software. - 2015. - Vol. 10. - No. 1. - P. 94-105.
136. Chen, R. The potential of social identity for equilibrium selection / R. Chen, Y. Chen // American economic review. - 2011. - Vol. 101. - No. 6. - P. 2562-2589.
137. Chepoi, V. Center and diameter problems in plane triangulations and quadrangulations / V. Chepoi, F. Dragan et al // Proc. of the thirteenth annual ACM-SIAM symposium on Discrete algorithms. - Philadelphia: Society for Industrial and Applied Mathematics. - 2002. - P. 346-355.
138. Chevalier, C. Improvement of the efficiency of genetic algorithms for scalable parallel graph partitioning in a multi-level framework / C. Chevalier, F. Pellegrini // Springer. - 2006. - P. 243-252.
139. Contractor, N.S. Multidimensional networks and the dynamics of sociomateriality: bringing technology inside the network / N.S. Contractor, P.R. Monge, P.M. Leonardi // International Journal of Communication. - 2011. - No 5, P. 682-720.
140. Cooper, C. A general model of web graphs / C. Cooper, A. Frieze // Random Structures Algorithms. - 2003. - Vol. 22. - No 3. - P. 311-335.
141. Dean, J. Map-Reduce: simplified data processing on large clusters / J. Dean, S. Ghemawat // Communications of the ACM. -2008. - Vol. 51. - No. 1. - P. 107-113.
142. Dereich, S. Random networks with concave preferential attachment rule / S. Dereich, P. Morters // Jahresberichte der Deutschen Mathematiker Vereinigung. -2011. - Vol. 113. - No 1. - P. 21-40.
143. Dijkstra, E.W. A note on two problems in connexion with graphs / E.W. Dijkstra // Numer. Math - Springer Science Business Media. - 1959. - Vol. 1(1). -P. 269-271.
144. Erdo"s, P. On random graphs I / P. Erdo"s, A. R'enyi. - Publ. Math. Debrecen. - 1959. -Vol. 6. - P. 290-297.
145. Ergun, G. Growing random networks with fitness / G. Ergun, G.J. Rodgers. - Physica A. - 2002. - Vol. 303. - P. 261-272.
146. Fiduccia, C.M. A Linear-time Heuristics for Improving Network Partitions /
C.M. Fiduccia, R.M. Mattheyses // 19th Design Automation Conf. - 1982. - P. 175-181.
147. Freeman, L.C. Research methods in social network analysis / L.C. Freeman,
D.R. White, A.K. Romney. - Transaction Publ., 1992. - 544 p.
148. Ford, L.R. Flows in Networks / L.R. Ford, D.R. Fulkerson. - Princeton University Press, 1962. - 216 p.
149. Gao, J. Dynamic Shortest Path Algorithms for Hypergraphs / J. Gao, Q. Zhao, W. Ren, A. Swami, R. Ramanathan, A. Bar-Noy // WiOpt'12: Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks. - Paderborn. - 2012. -P. 238-245.
150. Gao, Y. Modeling and simulation of the open source software community / Y. Gao, G. Madey, V. Freeh // Agent-directed simulation conf. - 2005. - P. 113-122.
151. Goehring, T. Heuristic algorithms for automatic graph partitioning / T. Goehring, Y. Saad // Techn. rep. department of computer science. - University of Minnesota. Minneapolis. - 1994. - P. 1-19.
152. Grier, R.A. SCIPR: A computational model to simulate cultural identities for predicting reactions to events / R.A. Grier, B. Skarin, A. Lubyansky, L. Wolpert // Proc. of the Second Internat. conf. on computational cultural dynamics. - 2008. - P. 32-38.
153. Hendrickson, B. The Chaco User's Guide, Vers. 2.0. SAND95-2344 / B. Hendrickson and R. Leland. - Unlimited Release, 1995. - 44 p.
154. Hewitt, C. A universal modular ACTOR formalism for artificial intelligence / C. Hewitt, P. Bishop, and R. Steiger // Proc. International Joint Conference on Artificial Intelligence. - 1973. - P. 235-245.
155. Hickey, D.T. Engaged participation: a sociocultural model of motivation with implications for educational assessment / D.T. Hickey, S.J. Zuiker // Educational Assessment. - 2005. - No 3. - P. 277-305.
156. Janson, S. Large cliques in a power-law random graph / S. Janson, T. Luczak, I. Norros // J. Appl. Probab. - 2010. - Vol. 47. - No 4. - P. 1124-1135.
157. Jennings, N.R. Agent technology. Foundations, applications and markets / N.R. Jennings, N.R. Wooldridge. - Berlin Heidelberg N.Y.: Springer-Verlag, 1998. -325 p.
158. Karypis, G. A fast and high quality multilevel scheme for partitioning irregular graphs / G. Karypis, V. Kumar // SIAM Journal on Scientific Computing. -1998. - Vol. 20. - No 1. - P. 359-392.
159. Kernighan, B.W. An efficient heuristic procedure for partitioning graphs / B.W. Kernighan and S. Lin // Bell System Technical Journal. - 1970. - Vol. 49. -P. 291-307.
160. Kolodenkova, A.E. Researches of Interaction of Actors with Use Fuzzy Hypergraph and Cognitive Modeling / A.E. Kolodenkova, E.R. Muntyan // 14th Intern.
scien.-techn. conf.: Actual problems of electronic instrument engineering (APEIE) Proc. - 2018. - Vol. 1. - Part 4. - P. 127-131.
161. Kolodenkova, A.E. Modern Approaches to Modeling of Risk Situations during Creation Complex Technical Systems / A.E. Kolodenkova, E.R. Muntyan, V.V. Korobkin // Advances in Intelligent Systems and Computing. - 2018. - Vol. 875. -P. 209-217.
162. Kopecky, J. Social identity modeling: Past work and relevant issues for socio-cultural modeling / J. Kopecky, N. Bos, A. Greenberg // 19th Annual Conference on Behavior Representation in Modeling and Simulation 2010. - 2010. - P. 136-143.
163. Kossinets, G. Effects of missing data in social networks / G. Kossinets // Social Networks. - 2006. - Vol. 28(3). - P. 247-268.
164. Krapivsky, P.L. Connectivity of growing random networks / P.L Krapivsky, S. Redner, F. Leyvraz // Physical review letters. - 2000. - Vol. 85. - No. 21. -P. 4629-4632.
165. Kung, U. Radius plots for mining tera-byte scale graphs: algorithms, patterns, and observations / U. Kung, C.E. Tsourakakis, A.P. Appel, C. Faloutsos, J. Leskovec // SIAM Intern. conf. on data mining. - 2010. - P.548-558.
166. Latour, B. Reassembling the social: an introduction to actor-network-theory / B. Latour. - Oxford: Oxford University Press, 2005. - 281 p.
167. Lee, C.Y. An algorithm for path connections and its applications / C.Y. Lee // IRE Trans. Electronic Computers. - 1961. - Vol. 10. - No 2. - P. 346-365.
168. Lester, J.C. Modeling metacognitive monitoring in narrative-centered learning environments / J.C. Lester, S.W. McQuiggan, J.L. Nietfeld, K.L. Hoffmann, J.L. Robison, H.A. Spires // Intern. conf. on Artif. Intellig. in Educ. - 2011. - No 6. -P. 163-170.
169. Liben-Nowell, D. Tracing information flow on a global scale using Internet chain-letter data / D. Liben-Nowell and J. Kleinberg // PNAS. - 2008. - No 105(12). -P. 4633-4638.
170. Lipil, A. A socio-cultural model based on empirical data of cultural and social relationships / A. Lipil, Y. Nakanol, M. Rehm // Culture and Computing. - LNCS 6259. - 2010. - P. 71-84.
171. Lustick, I.S. PS-I: A user-friendly agent-based modeling platform for testing theories of political identity and political stability / I.S. Lustick // Journal of Artificial Societies and Social Simulations. - 2002. - Vol. 5(3). - P. 1-7.
172. Mol, A. Regions, networks, and fluids: Anaemia and social topology / A. Mol, J. Law // Social Studies of Science. - 1994. - Vol. 24(4). - P. 641-672.
173. Moore, E.F. The shortest path through a maze / E.F. Moore // Proc. of an Internat. symp. on the theory of switching. - Harvard University Press. - 1959. - Vol. 2. - P. 285-292.
174. Mordeson, J.N. Fuzzy Graphs and Fuzzy Hypergraphs / J.N. Mordeson, P.S. Nair. - Springer. Heidelberg. Germany, 2000. - 248p.
175. Muntyan, E. Analysing Big Social Graphs Using a List-based Graph Folding Algorithm [Электронный ресурс] / E. Muntyan, N. Sergeev, A. Tselykh // ITM Web of Conf. (ICICCI 2018). - 2019. - Vol 25. Режим доступа: https://www.itm-conferences. org/articles/itmconf/abs/2019/02/itmconf_icicci2018_01003/itmconf_icicci2018_01003. html.
176. Nielsen, L.R. Finding the K shortests hyperpaths / L.R. Nielsen, K.A. Andersen, D. Pretolani // Computers & Operations Research. - 2005. - Vol. 32. -P. 1477-1497.
177. Oren, T.I. Rationale for a code of professional ethics for simulationists / T.I. Oren // Proc. of the Summer Computing Simulation conf. - 2002. - Vol. 1. - P. 1-6.
178. Papa, D.A. Hypergraph partitioning and clustering / D.A. Papa, I.L. Markov // Handbook of Approximation Algorithms and Metaheuristics. - Boca Raton: CRC Pr. -2007. - P. 1-38.
179. Riedl, M.O. Social Navigation: Modeling, Simulation, and Experimentation / M.O. Riedl, R.S. Amant // Proc. of the second Intern. joint conf. on Autonomous agents and multiagent system. - 2003. - P. 361-368.
180. Rosenfeld, A. Fuzzy graphs / A. Rosenfeld // In: L.A. Zadeh, K.S. Fu, M. Shimura (Eds.). - Fuzzy Sets and Their Applications. Academic Press. New York. USA.
- 1975. - P. 77-95.
181. Rowe, J.P. Modeling user knowledge with dynamic bayesian networks in interactive narrative environments / J.P. Rowe, J.C. Lester // Proc. of the sixth AAAI conf. on artificial intelligence and interactive digital entertainment. - 2010. - P. 57-62.
182. Salzarulo, L. A continuous opinion dynamics model based on the principle of meta-contrast [Электронный ресурс] / L. Salzarulo // Journal of Artificial Societies and Social Simulation. - 2006. - № 9(1). - Режим доступа: http://jasss.soc.surrey. ac.uk/9/1/13.html.
183. Sergeev, N. Assessment of Qualification of University Graduates on the Basis of Fuzzy Graph Approaches / N. Sergeev, A. Kolodenkova, E. Muntyan // IV Intern. Conf. on Information Technologies in Engineering Education (Inforino): IEEE. - 2018.
- P.1-5.
184. Shoham, Y. Agent-Oriented programming / Y. Shoham // AI. - 1993. -Vol. 60. - P. 51-92.
185. Silverman, B.G. Human behavior models for agents in simulators and games: Part I: Enabling science with PMFserv / B.G. Silverman, M. Johns, J. Cornwell, K. O'Brien // Teleoperators and Virtual Environments. - 2006. - Vol.15(2). - P. 139-162.
186. Soper, A.J. A Combined Evolutionary Search and Multilevel Optimization Approach to Graph-Partitioning / A.J. Soper, C. Walshaw, M. Cross // Journ. of Global Optimization. - 2004. - No 29. - P. 225-241.
187. Spence, R. A framework for navigation / R. Spence // Intern. Journ. of Human-Computer Studenys. - 1999. - Vol. 51. - P. 919-945.
188. Srinivasan, S. Kilim: Isolation-Typed Actors for Java / S. Srinivasan, A. Mycroft // Europe Conf. on Object Oriented Program. ECOOP, 2008. - SpringerVerlag Berlin Heidelberg. - 2008. - P. 104-128.
189. Sunitha, M.S. Complement of a fuzzy graph / M.S. Sunitha, A.V. Kumar // Indian Journal of Pure and Applied Mathematics. - 2002. - No 33(9). - P. 1451-1464.
190. Takes, F.W. Determining the diameter of small world networks / F.W. Takes, W.A. Kösters // Proc. of the 20th ACM Intern. conf. on Inform and knowledge management. - N.Y.: ACM Press. - 2011. - P. 1191-1196.
191. Takes, F.W. Balanced Label Propagation for Partitioning Massive Graphs / F.W. Takes, W.A. Kosters // Proc. of the Sixth ACM Intern. conf. on Web Search and Data Mining. - ACM Press. - 2013. - P. 507-516.
192. Vander Wal, J.S. The sociocultural model of eating disorder development: application to a Guatemalan sample / J.S. Vander Wal, J.L. Gibbons, M.P. Grazioso // Eating Behaviors. - 2008. - No 9(3). - P. 277-284.
193. Visual-graph [Электронный ресурс]. - Режим доступа: https://bitbucket.org/tzolotuhin/visual-graph/downloads/.
194. Walshaw, C. JOSTLE: parallel multilevel graph-partitioning software - an overview / C. Walshaw, M. Cross // School of Engineering. - 2007. - P.27-58.
195. Wooldridge, M.J. An introduction to multiagent systems / M.J. Wooldridge. - John Wiley&Sons Ltd, 2002. - 366 p.
196. Zadeh, L. Similarity relations and fuzzy orderings / L. Zadeh // Information Sciences. - 1971. - No 3(2). - P. 177-200.
197. Zadeh, L. Fuzzy logic, neural networks, and soft computing / L. Zadeh // Communications of the ACM. - 1994. - Vol. 37. - No. 3. - P. 77-84.
ПРИЛОЖЕНИЕ 1. Примеры работы алгоритмов преобразования
GH-моделей
Пример 1. Пример работы алгоритма свертки GH-гиперграфа
Исходный гиперграф Ш2 (рисунок П1.1) задан множествами вершин (Nodesj)
G12v = (gvi, ggv2, ..., gvi5}; ребер между вершинами G12e = {gei, ge2, ..., gei7}; гиперребер H12e = {he1, he2, ..., he5}; ребер между вершинами и гиперребрами H12g = {hg1, hg2}; ребер между гиперребрами H12h = {hh1}. Для вершин и связей в модели определены атрибуты. Ниже опишем этапы свертки. 1 этап.
1.1. Представление гиперграфа в виде списка ребер:
Le (H12) = Cons (Le (G), Le (Hh), Le (Hg)), Le (G) = (<gv1> : <gv2>, [0]; [he1]), (<gv1> : <gv3>, [0]; [he1]), (<gv2> : <gv1>, [0]; [he1, he2, he3]), (<gv2> : <gv3>, [0]; [he1, he2, he3]),
(<gv2> : <gv4>, [0]; [he1, he2, he3]), (<gv2> : <gv5>, [0]; [he1, he2, he3]),
(<gv2> : <gv6>, [0]; [he1, he2, he3]), (<gv3> : <gv2>, [0]; [he1]), (<gv3> : <gv1>, [0]; [he1]), (<gv1> : <gv2>, [ge1o/0]; [he1]), (<gv2> : <gv1>, [ge1o/0]; [he1, he2, he3]), (<gv2> : <gv3>, [ge9/0]; [he1, he2, he3]),
(<gv3> : <gv2>, [ge9/0]; [he1]), (<gv2> : <gv5>, [ge8/0]; [he1, he2, he3]),
(<gv4> : <gv5>, \ge5/1, gen/0]; [he2]), (<gv4> : <gv2>, [0]; [he2]), (<gv4> : <gv6>, [0]; [he2]), (<gv5> : <gv2>, [0]; [he3]), (<gv5> : <gv4>, [gen/0]; [he3]),
(<gv5> : <gv8>, [ge12/0]; [he3]), (<gv5> : <gv2>, [ge8/0]; [he3]),
(<gv6> : <gv2>, [0]; [he2]), (<gv6> : <gv4>, [0]; [he2]), (<gv6> : <gv10>, [ge7/1]; [he2]), (<gv7> : <gv8>, [0]; [he4]), (<gv7> : <gv9>, [0]; [he4]), (<gv8> : <gv7>, [0]; [he4]), (<gv8> : <gv9>, [0]; [he4]), (<gv9> : <gv7>, [0]; [he4]), (<gv9> : <gv8>, [0]; [he4]), (<gv8> : <gv5>, [ge12/0]; [he4]), (<gvw> : <gv6>, [ge^l]; [0]), (<gv10> : <gv14>, [ge16/1/tp2]; [0]), (<gvn> : <gv12>, [0]; [he5]), (<gvn> : <gv13>, [0]; [he5]), (<gv12> : <gvn>, [0]; [he5]), (<gv12> : <gv13>, [0]; [he5]),
(<gv13> : <gv12>, [0]; [he5]), (<gv13> : <gvn>, [0]; [he5]), (<gvn> : <gv12>, [ge13/1/ v]; [he5]), (<gvn> : <gv13>, [ge14/1/ v]; [he5]), (<gv12> : <gv13>, [ge15/1/ v]; [he5]), (<gv15> : <gv14>, [gen/1/tp1]; [0]).
Le (Hh) = (<hei> : <he5>, [hhi/1]; [0]). Le (Hg) = (<gV9> : <hes>, [hgi/1]; [he4]), (<gv15> : <he4>, [hg2/1]; [0]).
Рисунок П1.1 - Исходный гиперграф Я12
1.2. Кластер 0-го уровня (k = 0);
1.3. Определение исходной вершины cNode = gv2.
1.4. Определение для cNode множества смежных вершин Neighbors и инцидентных гиперребер IncidentIhe:
Neighbors = (gv1; gv3, gv4, gv5, gv6}; IncidentIhe = {he1, he2, he3};
1.5. Поглощение вершин из выбранных подмножеств и инцидентных им ребер в вершину gv16 (рисунок П1.2).
„______ge'*
Рисунок П1.2 - Гиперграф Н11 после 1 этапа свертки (кластер 1-го уровня) Для кластера 1-го уровня список ребер С1т1ег1.
СШвГ1 = (^1> : ^2>, [0]; [Ле1]), (<gvl> : <gv3>, [0]; [Ле1]),
(<gv2> : <gvl>, [0]; [Леь Ле2, Лез]), (^2> : ^з>, [0]; [Леь Ле2, Лез]),
(<^2> : <gv4>, [0]; [Леь Ле2, Лез]), (^2> : ^5>, [0]; [Леь Ле2, Лез]),
(<^2> : ^б>, [0]; [Леь Ле2, Лез]), (^з> : <gv2>, [0]; [Ле1]),
(<^з> : <gvl>, [0]; [Ле1]), (<gvl> : <gv2>, [gelo/0]; [Ле1]),
(<gv2> : <gv1>, [gew/0]; [heb he2, he3]), (<gv2> : <gv3>, [ge9/0]; [he1, he2, he3]),
(<gv3> : <gv2>, [ge9/0]; [he1]), (<gv2> : <gv5>, [ge8/0]; [he1, he2, he3]),
(<gv4> : <gv5>, \ge5/1, gen/0]; [he2]), (<gv4> : <gv2>, [0]; [he2]),
(<gv4> : <gv6>, [0]; [he2]), (<gv5> : <gv2>, [0]; [he3]), (<gv5> : <gv4>, [gen/0]; [he3]), (<gv5> : <gv2>, [ge8/0]; [he3]), (<gv6> : <gv2>, [0]; [he2]), (<gv6> : <gv4>, [0]; [he2]).
При этом списки ребер после 1-го этапа свертки Le1 (G), Le1 (Hh) и Le1 (Hg): Le1 (G) = (Cluster 1), (<gv16> : <gv8>, [ge12*/0]; [0]), (<gv16> : <gv10>, [ge7*/1]; [0]), (<gv7> : <gv8>, [0]; [he4]), (<gv7> : <gv9>, [0]; [he4]), (<gv8> : <gv7>, [0]; [he4]),
(<gv8> : <gv9>, [0]; [he4]), (<gv9> : <gv7>, [0]; [he4]), (<gv9> : <gv8>, [0]; [he4]), (<gv8> : <gv16>, [ge12*/0]; [he4]), (<gvw> : <gv16>, [ge6*/1]; [0]), (<gvn> : <gv12>, [0]; [he5]), (<gvn> : <gv13>, [0]; [he5]), (<gv12> : <gvn>, [0]; [he5]), (<gv12> : <gv13>, [0]; [he5]), (<gv13> : <gv12>, [0]; [he5]), (<gv13> : <gvn>, [0]; [he5]), (<gvn> : <gv12>, [ge13/1/ v]; [he5]), (<gvn> : <gv13>, [ge14/1/ v]; [he5]), (<gv12> : <gv13>, [ge15/1/ v]; [he5]), (<gv15> : <gv14>, [gen/1/tp1]; [0]), (<gv10> : <gv14>, [ge16/1/tp2]; [0]); Le1 (Hh) = (<gv16> : <he5>, [hhWl]; [0]); Le1 (Hg) = (<gv9> : <he5>, [hg1/1]; [he4]), (<gv15> : <he4>, [hg2/1]; [0]). 1.6. Исходная вершина cNode = gv16. 2 этап.
2.1. Определение для cNode множества смежных вершин Neighbors и инцидентных гиперребер IncidentIhe: Neighbors = {gv10, gv8}; IncidentIhe = {0};
2.2. Поглощение вершин из выбранных подмножеств и инцидентных им ребер в вершину gv17 (рисунок П1.3).
Для кластера 2-го уровня список ребер Cluster2: Cluster2= (<gv16> : <gv8>, [ge12*/0]; [0]), (<gv16> : <gvw>, [ge7*/1]; [0]), (<gv8> : <gv16>, [ge12*/0]; [he4]), (<gvw> : <gv16>, [ge6*/1]; [0]). Списки ребер после 2-го этапа свертки Le2(G), Le2(Hh) и Le2(Hg): Le2 (G) = (Cluster 1), (Cluster), (<gv7> : <gvn>, [0]; [he4]), (<gv7> : <gv9>, [0]; [he4]), (<gv17> : <gv7>, [0]; [he4]), (<gv17> : <gv9>, [0]; [he4]), (<gv9> : <gv7>, [0]; [he4]),
(<gv9> : <gv17>, [0]; [he4]), (<gvn> : <gv12>, [0]; [he5]), (<gvn> : <gv13>, [0]; [he5]),
(<gv12> : <gvn>, [0]; [he5]), (<gv12> : <gv13>, [0]; [he5]), (<gv13> : <gv12>, [0]; [he5]),
(<gv13> : <gvn>, [0]; [he5]), (<gvn> : <gv12>, [ge13/1/ v]; [he5]), (<gvn> : <gv13>, [ge14/1/ v]; [he5]), (<gv12> : <gv13>, [ge15/1/ v]; [he5]), (<gv15> : <gv14>, [ge1'/1/tp1]; [0]), (<gv17> : <gv14>, [ge16/1/tp2*]; [0]);
Le2 (Hh) = (<gv17> : <he5>, [hM*/1]; [0]); Le2 (Hg) = (<gv9> : <he5>, [hg1/1]; [he4]), (<gv15> : <he4>, [hg2/1]; [0]).
Рисунок П1.3 - Гиперграф Н12 после 2 этапа свертки (кластер 2-го уровня) 2.3. Исходная вершина cNode = gv17.
3 этап.
3.1. Определение для cNode множества смежных вершин Neighbors и инцидентных гиперребер IncidentIhe:
Neighbors = {gv7, gv9, gv14}; IncidentIhe = {he4}.
3.2. Поглощение вершин из выбранных подмножеств и инцидентных им ребер в вершину gv18 (рисунок П1.4, а).
Для кластера 3-го уровня список ребер Cluster3: Cluster3 = (<gv7> : <gv17>, [0]; [he4]), (<gv7> : <gv9>, [0]; [he4]), (<gv17> : <gv7>, [0]; [he4]), (<gvn> : <gv9>, [0]; [he4]), (<gv9> : <gv7>, [0]; [he4]), (<gv9> : <gv17>, [0]; [he4]), (<gvn> : <gv14>, [ge16/1/tp2*]; [0]).
Списки ребер после 3-го этапа свертки Le3(G), Le3(Hh) и Le3(Hg): Le3 (G) = (Cluster 1), (Cluster), (Cluster), (<gvn> : <gv12>, [0]; [he5]), (<gvn> : <gv13>, [0]; [he5]), (<gv12> : <gvn>, [0]; [he5]), (<gv12> : <gv13>, [0]; [he5]), (<gv13> : <gv12>, [0]; [he5]), (<gv13> : <gvn>, [0]; [he5]), (<gvn> : <gv12>, [ge13/1/ v]; [he5]), (<gvn> : <gv13>, [ge14/1/ v]; [he5]), (<gv12> : <gv13>, [ge15/1/ v]; [he5]), (<gv15> : <gv18>, [ge17*/1/tp1]; [0]);
Рисунок П1.4 - Гиперграф Н12 после 3 этапа свертки (а) и после 4 этапа свертки (б) 3.3. Исходная вершина cNode = gv18.
4 этап.
4.1. Определение для cNode множества смежных вершин Neighbors и инцидентных гиперребер IncidentIhe: Neighbors = {gv15}; IncidentIhe = {0}.
4.2. Поглощение вершин из выбранных подмножеств и инцидентных им ребер в вершину gv19 (рисунок П1.4, б).
Для кластера 4-го уровня список ребер Clustery
Cluster4 = (<gv15> : <gv18>, [gen*/1/tp1]; [0]); Списки ребер после 4-го этапа свертки Le^(G), Le4(Hh) и Le^(Hg): Le4 (G) = (Cluster1), (Cluster2), (Cluster3), (Cluster4), (<gv11> : <gv12>, [0]; [he5]), (<gvn> : <gv13>, [0]; [he5]), (<gv12> : <gvn>, [0]; [he5]), (<gv12> : <gv13>, [0]; [he5]), (<gv13> : <gv12>, [0]; [he5]), (<gv13> : <gvn>, [0]; [he5]), (<gvn> : <gv12>, [ge13/1/ v]; [he5]), (<gvn> : <gv13>, [ge14/1/ v]; [he5]), (<gv12> : <gv13>, [ge15/1/ v]; [he5]); Le4 (Hh) = (<gv19> : <he5>, [hM*/1]; [0]); Le4 (Hg) = (<gv19> : <he5>, [hg1*/1]; [0]), (<gv19> : < gv19>, [hg1*/1]; [0]).
4.3. Исходная вершина cNode = gv19.
5 этап.
5.1. Определение для cNode множества смежных вершин Neighbors и инцидентных гиперребер IncidentIhe: Neighbors = {0}; IncidentIhe = {0}.
5.2. В формах (2.33) и (2.34) для вершины cNode выполняется функция поиска ребер типа ihg и ihh: IncidentIhg = {hg1*, hg2*} IncidentIhh = {hh1*}.
5.3. Для вершины cNode из форм (2.33) и (2.34) определяется множество смежных вершин Neighbors среди вершин, принадлежащих гиперребру, связанному с cNode ребром из списков ihg и ihh: Neighbors = {gvn, gv12, gv13}.
5.4. Поглощение вершин из выбранных подмножеств и инцидентных им ребер в вершину gV20.
Для кластера 5-го уровня список ребер Clusters:
Cluster5 = (<gvn> : <gV12>, [0]; [he5]), (<gvn> : <gV13>, [0]; [he5]), (<gV12> : <gv11>, [0]; [he5]), (<gv12> : <gv13>, [0]; [he5]), (<gv13> : <gv12>, [0]; [he5]), (<gv13> : <gvn>, [0]; [he5]), (<gvn> : <gv12>, \ge13IH v]; [he5]), (<gv11> : <gv13>, [ge14l1I v]; [he5]), (<gv12> : <gv13>, [ge15l1I v]; [he5]), (<gv19> : <he5>, [hhW1]; [0]), (<gv19> : <he5>, [hg1*/1]; [0]),
(<gv19> : < gv19>, [hg1*/1]; [0]).
Списки ребер после 5-го этапа свертки Les(G), Les(Hh) и Les(Hg): Le5 (G) = (1Cluster1), (Cluster2), (Cluster3), (Cluster4), (Cluster5); Le5 (Hh) = 0; Les (Hg) = 0. Теперь cNode = gv20, а Neighbors = {0}. Таким образом свертка гиперграфа GH12 выполнена за пять этапов с возможностью восстановления структуры исходной модели, что показывает количество кластеров в данной модели.
Пример 2. Пример работы алгоритма пропорционального разделения GH-графа
Особенности применения данного алгоритма продемонстрируем на примере
задачи разделения графа G9 = (G9v, G9e), представленного на рисунке П1.5, который задан множеством вершин G9v = {<gv1, ^1>, <gv2, ц2>, ..., <gv18, ц18>} и множеством ребер G'9e = {ge1, ge2, ..., ge39}, значения весов вершин ц приведены в таблице П1.1.
Необходимо выполнить разделение графа G9 на части (part = 3) с заданными пропорциями (P1 = 0,5; P2 = 0,25; P3 = 0,25). Критерий разделения графа: суммарное
значение весов вершин подграфов. Обозначим подграфы А, В, С, которые должны получиться в результате разделения графа на части 1, 2, 3.
tg
tg
g14
ges
С
<«0
-Se28
€
gvs^
tg
iv
v
tg
ч£™2>
e>b
tg
ge31
J?
О
<s
ft
gv15
gv18
gv17
ge7
gve
%
tg
%
w
gv16
Таблица П1.1
gVr Л'
1 0,9
2 0,7
3 °,5
4 °,6
5 °,7
6 °,6
7 °,7
8 °,6
9 °,3
1° °,4
11 °,7
12 °,4
13 °,3
14 0,8
15 °,6
16 °,3
17 °,4
18 °,5
Z 10,0
Рисунок П1.5 - Демонстрация 1-го этапа свертки графа G'9
Этап свертки 1. В качестве исходных вершин для подграфов A, B, C используем периферийные вершины cNodes1 = gv1, cNodes2 = gv3, cNodes3 = gv18. При этом множества смежных вершин: Neighbors (cNodes1) = {gv2, gv4, gv5}, Neighbors (cNodes2) = {gv2, gv6, gv9}, Neighbors (cNodes3) = {gv15, gv16, gv17}. Имеет место конфликтная ситуация - смежная для cNodes1 и cNodes2 вершина gv2, которая в соответствии с критерием разделения будет поглощена вершиной gv19. Результат параллельной свертки групп вершин показан на рисунке П1.6.
A
Суммарный вес вершин подграфов А, В, С соответственно составляет 2,9; 1,4; 1,8, тогда как с учетом заданных пропорций должны быть значения - 3,0; 1,5; 1,5. Таким образом, для следующего этапа свертки расставим приоритеты исходных вершин для поглощения в порядке убывания: с^ойв81, с^ойв82 и с^ойв83.
Этап свертки 2. Для подграфов A, B, C исходные вершины: cNodes1 = gv19, cNodes2 = gv2o, cNodes3 = gv21, множества смежных вершин: Neighbors (cNodes1) = ={gv7, gv8, gv1o}, Neighbors (cNodes2) = {gv8, gvn}, Neighbors (cNodes3) = {gvn, gv12, gv13, gv14}. Множества Neighbors (cNodes2) и Neighbors (cNodes1) пересекаются по вершине gv8, а Neighbors (cNodes2) и Neighbors (cNodes3) - по вершине gv11, тогда в соответствии с назначенными приоритетами исходных вершин подграфы A, B, C формируются как показано на рисунке П1.6. Суммарный вес вершин подграфов A, B, C соответственно теперь составляет 4,6; 2,1; 3,3, тогда как с учетом заданных пропорций должны быть значения - 5,0; 2,5; 2,5. Если результат разделения графа не удовлетворяет заданным критериям, как в данном случае, тогда требуется выполнения дополнительных этапов свертки.
Рисунок П1.6 - Демонстрация 2-го этапа свертки графа G'9
Дополнительный этап свертки 3. Для оптимизации результата разделения графа предлагается передать вершину ^12 из подграфа С в А, а вершину ^13 из подграфа С в В (рисунок П1.7). Тогда суммарные веса подграфов А, В, С составят 5,0; 2,4; 2,6. Полученный результат разделения графа 0'9 на части приблизительно удовлетворяет постановке задачи. Таким образом, граф О 9 разделен на три подграфа А, В, С, состоящих из подмножеств вершин ~Ыойв$1 = %у4, %у5,
^7, ^10, ^12}, Nodes2 = {^3, £Гб, ^9, ^ц, ^13} и Nodesз = {^14, ^15, ^^17, ^8} в соответствии с заданными пропорциями и критериями разделения.
Рисунок П1.7 - Демонстрация 3-го этапа свертки графа 0'9 для оптимизации
Пример 3. Пример работы алгоритма пропорциональной догенерации ОИ-графа
Использование разработанного в диссертации алгоритма пропорциональной
догенерации можно продемонстрировать на примере графа 710, заданного графически (рисунок П1.8) и в виде списка ребер Ьв (О). Форма записи списка данного графа аналогична рассмотренным ранее. Требуется догенерировать исходный граф 010 на 30%. Модель выполнена с учетом обозначений: акторы а1-
результата разделения
а9 (вершины - субъекты, назначения и отношения которых представлены в
таблицах П1.2 и П1.3.
Таблица П1.2 - Соответствие акторов и вершин в графе 010
Актор Назначение актора Вершина графа
а1, а2, а9 Оппоненты общественного деятеля gVl, gV2
аз Общественный деятель gvз
а4-а8 Субъекты gv4-gv8
geu/ tp2
Рисунок П1.8 - Пример исходного графа G10 для догенерации Таблица П1.3 - Соответствие отношений между акторами ребрам графа G10
Вид ребра Вид связи Отношение между акторами
Однотипное ^ Влияние одного актора на другого
Совместное сотрудничество в профессиональной сфере
Вектор gv-v-gv Факт обсуждения: Vl - «обсуждать тему, связанную с угрозой терроризма», V2 - «обсуждать политические ситуации», vз - «обсуждать социальные вопросы».
Разнотипное tpl - «сочувствовать»
tp2 - «подчинять»
tpз - «использовать»
Шаги работы алгоритма догенерации рассматриваемого графа: Шаг 1. Исходные данные графа С10: число вершин п = 9; число ребер т = 21; общее число вершин в графе после догенерации составит 2 = 9 + (90,3) = 12. Шаг 2. Подмножество вершин для выбора связи с текущей вершиной:
СН^Ыойея = ^2, gvз, gV4, gV5, gу6, gУ7, gУ8, gV9}.
Шаг 3. Загрузка таблицы статистических данных об исходном графе для предпочтительного связывания.
В качестве характеристик для предпочтительного связывания при догенерации графа предлагается использование локальных степеней вершин я (^¡). Поскольку в исходном графе присутствуют ориентированные и неориентированные ребра, то локальные степени вершин графа 08 в общем виде представлены кортежем:
я (8Уд = <50? 50 , 50 , 5 stp1, 5+р25 Stp3, 5+р3> ^>.
Анализ таблицы П1.4 показал: максимальное число связей в графе те = 8 у вершины £Уб, минимальное число связей етп = 2 у вершин и при этом среднее число связей ет1а = 4,6.
stp 1 5{р1 ъtp2 ^рЗ ЧрЗ ^г? число связей вершины, е возможность добавления связей
1 1 0 1 1 0 0 0 0 0 3 6 4
2 1 0 1 1 0 0 0 0 0 3 6 2
3 3 3 0 0 0 0 0 0 0 0 6 2
4 0 0 0 0 1 0 0 0 0 3 4 4
5 0 0 0 1 1 1 0 0 0 2 5 3
6 0 0 0 2 1 0 1 0 1 3 8 0
7 0 0 0 0 1 0 0 1 0 1 3 5
8 0 0 0 0 1 0 0 0 0 1 2 6
9 1 0 1 0 0 0 0 0 0 0 2 6
сумма 42
е mid 4,666666667
те 8
е тт 2
Шаг 4.1. Определение соответствия критерию догенерации (1) по количеству вершин: (п = 9) < (г = 12).
Шаг 5.1. Добавление новой текущей вершины: п = 10 (вершина £г10). Шаг 6.1. Выбор вершины из подмножества СИ^ойея для связи с текущей вершиной £У10 с использованием ГСЧ1 (^1).
Обратите внимание, представленные выше научные тексты размещены для ознакомления и получены посредством распознавания оригинальных текстов диссертаций (OCR). В связи с чем, в них могут содержаться ошибки, связанные с несовершенством алгоритмов распознавания. В PDF файлах диссертаций и авторефератов, которые мы доставляем, подобных ошибок нет.