РАЗВИТИЕ МАТРИЧНОГО ПРЕДСТАВЛЕНИЯ ОБОБЩЕННЫХ ГРАФОВЫХ СТРУКТУР В ЗАДАЧАХ ОПИСАНИЯ И АНАЛИЗА БОЛЬШИХ ДАННЫХ
(Стр. 9-15)

Подробнее об авторах
Блюмин Семён Львович профессор, доктор физ.-мат. наук, кафедра прикладной математики
Липецкий государственный технический университет, Россия, Липецк Приньков Алексей Сергеевич студент, кафедра прикладной математики
Липецкий государственный технический университет, Россия, Липецк
Чтобы читать текст статьи, пожалуйста, зарегистрируйтесь или войдите в систему
Аннотация:
Задача. Рассмотреть практические аспекты графоструктурного моделирования в задачах описания и анализа больших данных, а также развить матричные представления обобщенных графовых структур, в числе которых: графы, гиперграфы, сети, гиперсети и метаграфы [1-4]. Изложить полученные результаты предварительных исследований и обозначить перспективы дальнейших. Описать теоретико-множественный и матричный варианты представления графовых структур в контексте оптимизации вычислений в задачах описания и анализа больших данных, выделив недостатки и преимущества данных подходов. На этом основании показать обоснованность мотивации использования обобщенных графовых структур в таких зада чах [5, 6]. Разработать алгоритм преобразования произвольного графа в метаграф, использующий матричное представление. Модели. Область исследования - обобщенные графовые структуры и варианты их представления, в особенности матричные, а также практическое применение в области моделирования и анализа больших данных, сложных систем и сетей. В качестве моделей использованы обобщенные графовые структуры [1-4]. Выводы. В работе рассмотрены графы и обобщенные графовые структуры и приведены варианты их практического использования. Описаны теоретико-множественный и матричный варианты представления этих структур в контексте оптимизации вычислений в задачах описания и анализа больших данных. На этом основании показана обоснованность мотивации использования обобщенных графовых структур в таких задачах. Разработан эвристический алгоритм преобразования произвольного графа в метаграф, использующий матричное представление. Данный алгоритм преобразует матрицу инцидентности графа в матрицу инцидентности изоморфного ему метаграфа. Построена иерархия, отражающая последовательность обобщения одних структур другими. Выделены особенности обобщенных графовых структур, в частности метаграфа, как наиболее обобщенной и в то же время достаточной для моделирования произвольных связей структуры. Каждый раздел сопровожден выводами в контексте оптимизации вычислений и эффективности моделирования с перспективой применения технологий параллельных и распределенных вычислений.Рамки исследования и возможность последующего использования результатов научной работы. В данной работе были рассмотрены основные средства графоструктурного моделирования в задачах описания и анализа больших данных, в числе которых: графы, гиперграфы, сети, гиперсети и метаграфы. Задача разработки матричной алгебры и развития матричного представления этих структур для применения в анализе и описании больших данных является перспективной, что подтверждается материалами данной работы. Конечным продуктом исследования матричного представления обобщенных графовых структур будет развитие идей GraphBLAS [7], программной библиотеки и одноименного направления научных исследований для развития этой библиотеки, главная идея которых - попытка описания алгоритмов на графах в терминах операций линейной алгебры.Практическое значение. В данной работе рассматривается применение полученных результатов в задачах описания и анализа больших данных. Выделяются два пути: представление исходных данных и моделирование информационных систем, с помощью которых обрабатываются эти данные. Особое внимание в работе уделяется построению гибридных интеллектуальных информационных систем, которое в общем случае возможно исключительно при использовании обобщенных графовых структур. Стоит отметить, что практическая значимость не ограничивается этими областями. Также в работе упоминается возможность решения классических задач путем изменения формализации исходных и ограничивающих условий на примере задачи китайского почтальона.Оригинальность/ценность. Статья может быть интересна специалистам из области дискретной математики формализацией и ее следствиями относительно графовых структур, развитием матричного представления и разработанным алгоритмом преобразования графа в метаграф. Работа представляет ценность и для специалистов по статистике и анализу данных применением полученных результатов по обобщенным графовым структурам в задачах моделирования и анализа больших данных, по снижению сложности интерпретации промежуточных и конечных результатов за счет повышения уровня абстракции рассматриваемого объекта и описанием структуры и функционального назначения гибридных интеллектуальных информационных систем. Все вышеперечисленные темы могут быть полезны специалистам, занимающимся непосредственной разработкой программного обеспечения в этих и смежных областях. Данная статья представляет ценность в качестве обзора по ранее полученным результатам, ссылки на материалы по которым можно найти в тексте.
Образец цитирования:
Блюмин С.Л., Приньков А.С., (2018), РАЗВИТИЕ МАТРИЧНОГО ПРЕДСТАВЛЕНИЯ ОБОБЩЕННЫХ ГРАФОВЫХ СТРУКТУР В ЗАДАЧАХ ОПИСАНИЯ И АНАЛИЗА БОЛЬШИХ ДАННЫХ. Computational nanotechnology, 2: 9-15.
Список литературы:
Voloshin V. Introduction to Graph and Hypergraph Theory. Nova Kroshka Books. UK edition, 2013. 231 p.
Basu A., Blanning R. Metagraphs and Their Applications. NY: Springer, 2007. 172 р.
Анохин К.В. Когнитом: гиперсетевая модель мозга // XVII Всероссийская науч.-техн. конф. «Нейроинформатика-2015». Сб. науч. тр. Ч. 1. М.: МИФИ, 2015. С. 14-15.
Черненький В.М., Гапанюк Ю.Е., Ревунков Г.И., Терехов В.И., Каганов Ю.Т. Метаграфовый подход для описания гибридных интеллектуальных информационных систем // Прикладная информатика. Т. 12. № 3 (69). М.: Изд-во Моск. фин.-пром. ун-та «Синергия», 2017. С 57-79.
Huang J., Zhang R., Xu Yu J. Scalable Hypergraph Learning and Processing // Data Mining (ICDM), International Conference on. Atlantic City, NJ, USA, 14-17 Nov. 2015.
Zhou D., Huang J., Schölkopf B. Learning with Hypergraphs: Clustering, Classification and Embedding // Advances in Neural Information Processing Systems. 19, 2007. Р. 1601-1608.
Kepner J., Aaltonen P., Bader D. Mathematical foundations of the GraphBLAS // High Performance Extreme Computing Conference. Waltham, MA, USA, 13-15 Sept. 2016.
Приньков А.С. Графоструктурное ремоделирование метаграфами сложных систем на примере московского метрополитена // Материалы XII междунар. науч.-практ. конф. «HTCS'2017», 25-27 октября 2017 г. В 2 ч. Ч. 1. Изд-во ЛГТУ, 2017. С. 125-129.
Приньков А.С. Разработка программного обеспечения для графоструктурного ремоделирования сложных систем. В 2 ч. Ч. 2. // Материалы XII междунар. науч.-практ. конф. «HTCS'2017», 25-27 октября 2017 г. Изд-во ЛГТУ, 2017. С. 65-69.
Блюмин С.Л. Итергиперграфы: расширенный класс графовых моделей больших систем // Труды конф. «Теория активных систем-2011» (ТАС) в рамках Междунар. науч.-практ. мультиконф. «Управление большими системами» (УБС-2011). М.: ИПУ РАН, 2011. С. 11-15.
Блюмин С.Л., Приньков А.С. Графоструктурные тенденции развития ИИС: применение гиперграфов, метаграфов, итерграфов и их матричных представлений // Проблемы фундаментальной и прикладной информатики в управлении, автоматизации и мехатронике. Курск: Изд-во Юго-Зап. гос. ун-та ЗАО «Университетская книга», 2017. С. 5-13.
Drexl M. On the generalized directed rural postman problem // J. of the Operational Research Society. V. 65, Issue 8. NY: Springer, August 2014. Рp. 1143-1154.
Черненький В.М., Терехов В.И., Гапанюк Ю.Е. Структура гибридной интеллектуальной информационной системы на основе метаграфов // Нейрокомпьютеры: разработка, применение. М.: Радиотехника, 2016. C. 3-13.
Блюмин С.Л. Оргипергиперграфы: матрицы инцидентности и лапласианы // Вестник ЛГТУ. № 1 (21), 2013. С. 15-27.
Etsuji T., Akira T., Haruhisa T. The worstcase time complexity for generating all maximal cliques and computational experiments // Theoretical Computer Science. V. 363, Issue 1, 2006. Рp. 28-42.
Ключевые слова:
графоструктурное моделирование, матричное представление, гиперграф, метаграф, большие данные.