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

Аннотация

Кохов Виктор Алексеевич – кандидат технических наук, доцент кафедры высшей математики на факультете экономики, Национальный исследовательский университет «Высшая школа экономики».
Адрес: 101000, Москва, Мясницкая ул., 20.
E-mail: viktorkokhov@rambler.ru

Кохов Виктор Викторович – студент магистратуры, кафедра прикладной математики, Институт автоматики и вычислительной техники, Национальный исследовательский университет - Московский энергетический институт (НИУ-МЭИ).
Адрес: 111250, Москва, Красноказарменная ул., 14.
E-mail: viktor-kokhov@ya.ru

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

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

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

Предложенные модели сложности можно рассматривать как систему иерархического уточняющего анализа, позволяющего решать задачи исследования динамических свойств Т-орграфов, в частности монотонности их изменения. Модели сложности позволяют анализировать значимость темпоральных орграфов и их фрагментов, а также анализировать тенденции их изменения. Примером прикладной задачи использования предложенных моделей и методов является задача мониторинга изменения характеристик Т-орграфов как моделей коммуникаций акторов в корпоративных социальных сетях, с целью принятия руководством обоснованных управленческих решений. Методы анализа Т-орграфов реализованы в системе «Мастерская граф-моделей» и используются в учебном процессе НИУ ВШЭ и НИУ МЭИ.