Comparative analysis of random graph models.pdf В настоящее время активно развивается научное направление анализа сетей, базирующееся на положениях теории графов. Это обусловлено существенным ростом вычислительных мощностей ЭВМ, появлением языков высокого уровня и специального программного обеспечения, позволяющего эффективно исследовать сети. При этом под сетями подразумеваются сети различной природы: сети взаимодействия белков в живых организмах, сети цитирования, информационно-коммуникационные сети (ИКС), социальные сети и др. Для исследования сетей к настоящему времени разработан достаточно богатый инструментарий, базирующийся на графовых моделях [1-4]. С помощью таких моделей становится возможным тестировать гипотезы о сетевых структурах, процессах их формирования и динамике эволюции. Кроме того, активное развитие методов машинного обучения и анализа данных открывает новые перспективы для использования моделей случайных графов, например при разработке систем распознавания топологий исследуемых сетей. Эти системы активно применяются для решения задач обеспечения информационной безопасности в информационно-телекоммуникационных сетях, при анализе социальных сетей и сетей цитирования. Формирование множества размеченных образов на основе той или иной модели случайного графа позволяет проверять точность систем распознавания. Вместе с тем при всем многообразии моделей случайных графов не существует достаточных оснований для формирования суждения о том, какие же из этих моделей наиболее адекватно отражают природу реальных сетей. Целью исследования, основные результаты которого представлены в настоящей публикации, является разработка методической схемы сравнительного анализа адекватности моделей случайных графов реальным сетям. 1. Математические модели случайных графов Современная теория графов предлагает около десяти математических моделей случайных графов, основными из которых считаются модель случайного графа Эрдеша-Реньи (ЭР), свободно масштабируемая модель Барабаши-Альберт (БА) и экспоненциальная модель случайного графа (ЭМСГ) [1, 3]. 1.1. МоДель случайного графа ЭрДеша-Реньи Модель случайного графа впервые предложена венгерскими математиками П. Эрдешем и Э. Реньи. Принцип построения случайного графа заключается в поочередном выборе натурального целого числа n из множества {n е N} до «треб, таким образом V = {v,...,vn} - множество вершин моделируемого случайного графа. При этом E = {е ,•••, еп} - все возможные ребра, которые можно образовать между парами элементов из V. Далее по схеме Бернулли выбираются ребра из множества {е1,..., en} с заданной вероятностью успеха р, и в случае успеха очередное ребро вносится в строящееся множество ребер E, а в случае неудачи - не вносится. Итогом этой схемы является реализация случайного графа G = [V, E} ЭР [3]. 1.2. МоДель предпочтительного присоединения Барабаши-Альберт В реальных сетях новые вершины с большей вероятностью соединяются с вершинами, которые наиболее центральны по степени. Для анализа реальных сетей разработаны так называемые свободно масштабируемые модели, и самой распространенной среди них является модель предпочтительного присоединения, предложенная А. Барабаши и Р. Альберт [5, 6]. Эта модель описывает формирование случайного графа по следующим правилам: 1. В начальный момент времени t = 0 задается Vt несвязных вершин. 2. На каждом временном шаге t = (1, 2, 3...) добавляется новая вершина с Et ребрами; 3. Количество ребер, с которыми приходит в граф новая вершина - фиксировано, но соединяется она с уже существующей вершиной сети с вероятностью, пропорциональной степени этой вершины. Свойства реальных сетей наиболее полно описывает версия модели БА с фиксированным параметром распределения вероятностей соединения вершин [6] и вариативным числом новых ребер. Отличие заключается в том, что в модель вводится кортеж распределения вероятностей образования вершин, в котором p0 - вероятность изолированности вершины, p1 - вероятность соединения вершины с одной вершиной, p2 - вероятность соединения вершины с двумя вершинами, p3 - вероятность соединения вершины с тремя вершинами. 1.3. Экспоненциальная модель случайного графа Экспоненциальные модели случайных графов нашли широкое применение при решении различных задач анализа сетей, в первую очередь социальных. При формировании ЭМСГ математический аппарат позволяет учитывать множество параметров, важных именно для рассматриваемой сети, например меры центральности [7-12], плотность графа, ассортативность, триадный вектор и т.п. [13-17]. Формируемая модель представляет собой граф G из пространства всех возможных графов для n вершин Л. Ряд распределения графов по пространству Л оценивается на основе следующего выражения: P (G ) =1 c ®1-z1(G)+02-z2 (G)+...+® p •zp (G) (1) где с - нормирующая константа, ®1 • z1(G )+®2’ z2 (G)+...+® p-zp (G) ®k - коэффициент, определяющий GeA склонность сети к образованию связей k-го типа (например, ребер, 2-star, 2-path и т.п.); Zk(G) - сетевая статистика / терм (от англ. term), характеризующая число связей k-го типа в модели. Таким образом вероятность графа G определяется суммой сетевых статистик, взвешенных коэффициентами, в степени экспоненты. Мощность множества Л для ненаправленного графа равна 2n, для направленного - 2n(n-1). Несложно заметить, что даже для небольших n поиск графа с максимальной вероятностью методом полного перебора является крайне ресурсоемким процессом. Один из методов формирования ЭМСГ, получивший широкое распространение на практике, представляет собой Марковские цепи по методу Монте-Карло (МЦМК; англ. MCMC - Markov chain Monte Carlo), в частности реализация модели по алгоритму Метрополиса-Гастингса [13, 14]. В ходе таких испытаний параметры модели подбираются под реальную сеть, в результате чего исследователь получает представление о лежащих в основе сети процессах. ЭМСГ являются относительно новым средством анализа, поэтому рассмотрим содержание основных этапов моделирования. Формирование ЭМСГ по алгоритму Метрополиса-Гастингса - это итеративный процесс последовательного выбора графов (G0, G1, . Gt, .GT) из множества Л, который включает в себя ряд этапов. На первом этапе по реализации анализируемой сети оцениваются число вершин n и интересующие коэффициенты ©k . На втором этапе задается начальный граф G0 с n вершинами. Обычно начальный граф формируется без связей между вершинами, при этом он также может формироваться со случайными связями. Этапы с третьего по пятый итеративно повторяются T раз. Необходимое число итераций для каждой сети определяется отдельно и зависит от скорости сходимости модели. На третьем этапе случайным образом выбирается пара вершин h и k текущего графа Gt. Если между этими узлами связь отсутствует, то эта связь добавляется, если связь есть, то удаляется. Таким образом, формируется новый граф Gt+1. На четвертом этапе, исходя из выражения (1), вычисляется отношение вероятностей графов: нового Gt+1 и текущего Gt: P (Gt+i) P (G) ©1Z (G+1 )+©2-Z2 (G+1 )+...+© p Zp (G+1 ) ©1 'z1 (Gt+1 )+®2 "z2 (G/+1 )+...+® p Zp (Gt+1 ) _ £>©1'(Z1(Gt+1 ) Z1(Gt ))+©2 ’( z2 (Gt+1 ) z2 (Gt ))+...+©p ’(zp (G/+1 ) zp (Gt )) На пятом этапе принимается решение, какой граф выбирается в качестве текущего для последующей итерации. Для этого оценивается вероятность принятия нового графа Gt+1 в качестве текущего: = min t 1, P (Gt+1) P (Gt) Если p (Gt+1 )> p (Gt), то p+1 = 1 и в качестве текущего графа однозначно выбирается Gt+1. Если P(Gt+1 )< P(Gt), то p+1 < 1 . В этом случае генерируется одна реализация случайной величины и с равномерным законом распределения в диапазоне от 0 до 1. Когда и < Д+1, в качестве текущего графа выбирается Gt+i, когда и > Pt+i - Gt. В результате выполнения всех итераций формируется граф GT, который представляет собой ЭМСГ анализируемой сети. В исследованиях [15-17] показано, что существует около 15 основных базовых сетевых статистик, характеризующих реальные сети. Одно из важнейших качеств ЭМСГ заключается в том, что с их помощью можно сделать статистически значимые выводы: какие термы управляют исследуемой сетью. В табл. 1 приведены базовые термы, формирующие сети. Таблица 1 Основные термы экспоненциальных моделей случайных графов № п/п Наименование терма Описание русскоязычное | англоязычное Общие 1 Взаимосвязанность Mutual Взаимосвязанность сети 2 Эквивалентность ребер Edges Эквивалентность количества ребер 3 Изолированные вершины Isolates Эквивалентность количества изолированных вершин 4 Средняя степень вершины Meandeg Равенство средних степеней для вершин моделируемой сети 5 Плотность сети Density Равенство плотности сети Структурные 6 Транзитивность Transitive Эквивалентность транзитивности сети 7 Интранзитивность Intransitive Равенство триад типов 111D, 201, 111U, 021C и 030C 8 Двойной путь Twopath Эквивалентность количества элементов, представляющих собой минимально возможный путь от одной вершины к другой через транзитную вершину 9 Симмелианская триада Simmelian Равенство триад simmelian (основаны на сильной взаимосвязи между двумя вершинами через третью) 10 Балансные триады Balance Равенство триад типов 102 и 300 Приведенные в табл. 1 термы предназначены только для направленных сетей. Вместе с русским наименованием указано и английское оригинальное имя терма; это сделано потому, что на русский язык они переводятся впервые. Таким образом, основная особенность ЭМСГ состоит в том, что при формировании графов, в частности при принятии решения о наличии связи между любыми двумя узлами, учитывается структура всего графа, а именно сколько интересующих базовых элементов в графе уже присутствует. Термы разделены на две большие группы - общие и структурные. Общие отражают базовые характеристики графа, такие как степенное распределение, степень взаимосвязанности вершин графа, доля изолированных вершин и плотность графа. Структурные термы представляют собой минимальные элементы построения сети различной природы, иными словами, для каждой сети характерны свои уникальные термы [15-17]. Одним из преимуществ ЭМСГ является возможность работы с различными типами предикторов. Их можно разбить на четыре большие группы: предикторы узлов (ПУ), предикторы ребер (ПР), предикторы диад (ПД) и предикторы локальных структур (ПЛС). Существует более сотни вариантов предикторов, в настоящей статье, без ущерба для общности представления, ограничимся ПУ и ПР. Примерами ПУ являются номинативные или численные характеристики узла, например расстояние между узлами или гендерная принадлежность человека, представленного узлом, если рассматривается социальная сеть. Примером ПР является интенсивность передачи данных между узлами в ИКС. На этапе моделирования ЭМСГ оценивается статистическая значимость предикторов, и если гипотеза о их значимости подтверждается, то они включаются в модель, что может значительно повысить ее адекватность. 2. Подбор параметров математических моделей случайных графов Исследование реальных сетей с использованием моделей случайных графов реализуется в два этапа. На первом этапе осуществляются выбор математической модели и подбор ее параметров, наиболее полно соответствующих исследуемой сети. На втором этапе проводится исследование сети с использованием выбранной модели. В этой связи особую важность имеет именно первый этап, представляющий собой этап структурной и параметрической идентификации сети, состоящий в отыскании наилучшей структуры и параметров модели. Исходным параметром при моделировании является количество вершин n в исследуемой реальной сети. Это начальная установка, на основании которой осуществлялось моделирование в настоящем исследовании. 2.1. ПоДбор параметров Для моДели случайного графа ЭрДеша-Реньи Модель ЭР является двупараметрической, т.е. при ее формировании используются число вершин n и число ребер m. Количество вершин фиксировано и соответствует исходной сети, а число ребер изменяется от 1 до mmax, где mmax - максимально возможное количество ребер при фиксированном количестве вершин (mmax = n2 - n). Перебор параметров модели ЭР заключается в формированиии множества реализаций случайных графов с заданным числом вершин для каждого значения варьируемого параметра - числа ребер. 2.2. ПоДбор параметров Для моДели преДпочтительного присоеДинения Барабаши-Альберт Как было отмечено, свойства реальных сетей наиболее полно описывает версия модели БА с кортежем распределений вероятностей образования вершин P = (p0,p1,p2,p3} . При этом, чтобы исключить наличие изолированных вершин, вероятность p0 приравнивается нулю. Каждая из вероятностей образования вершин (кроме p0) принимает значение на интервале (0; 1). В такой ситуации кортеж вероятностей всегда состоит из трех варьируемых элементов, а общее число кортежей равно 93 = 729. Поиск параметров модели БА состоит в последовательном переборе возможных кортежей вероятностей P с последующим формированием множества реализаций случайных графов для каждого кортежа. 2.3. Подбор параметров для экспоненциальной модели случайного графа Для ЭМСГ оцениваемым параметром, позволяющим выбрать оптимальную модель, являются информационный критерий Акаике (AIC) и значение статистической значимости p-value для каждого терма. По AIC выбирается модель ЭМСГ с оптимальной комбинацией термов, одновременно с этим термы должны быть статистически значимы на заданном уровне p-value. Считается, что чем ниже значение AIC, тем лучше модель [18, 19]. Для подбора параметров ЭМСГ использован следующий алгоритм: 1. По 10 термам, представленным в табл. 1, рассчитываются все возможные комбинации по 2, 3 и 4 терма; 2. Осуществляется построение ЭМСГ по каждой полученной комбинации из 2, 3, и 4 термов; 3. Выбираются только те модели, у которых статистическая значимость p-value термов не менее 0,05, а затем из них выбирается модель с наименьшим AIC. 3. Оценка адекватности модели 3.1. Структурная схема оценки адекватности модели Под адекватностью модели понимают степень ее соответствия тому реальному явлению или объекту, для описания которого она строится. Вместе с тем создаваемая модель ориентирована, как правило, на исследование определенного подмножества свойств этого объекта. Поэтому можно считать, что адекватность модели определяется степенью ее соответствия не столько реальному объекту, сколько свойствам объекта в предметной области проводимого исследования. Рис. 1. Структурная схема сравнительного анализа адекватности моделей случайных графов Fig. 1. Block diagram of the comparative analysis of mathematical models of random graphs Если объектом исследования является сеть, то подмножеством ее свойств являются следующие характеристики, описанные в теории графов [7-12]: среднее расстояние пути (СРс), плотность (ПГ), ассортативность (АС), централизация по степени (СЦ), централизация по близости (СБ), централизация по посредничеству (СП), централизация по собственному вектору (СВЦ), транзитивность (Тр), диаметр (Ди) [13-17]. На рис. 1 представлена структурная схема проведения сравнительного анализа различных моделей реальных сетей. Она состоит из трех основных этапов, которые, в свою очередь, делятся на подэтапы. Этап моделирования. На этом этапе производится первичный анализ реальной сети - объекта моделирования. В ходе анализа подсчитываются первичные характеристики реальной сети - число узлов и вершин, определяется ее тип - связная или несвязная, направленная или ненаправленная. На основе первичного анализа реальной сети формируются модели ЭР, БА и ЭМСГ. Этап расчета свойств моделей. Для каждой реализации графа рассчитывается совокупность значений 9 основных свойств графов: F = WcPcJnr(АС,/ди,/сЦ(СБ,fcn,/свЦ(Тр ) . Элементы F формируют образ рассматриваемой модели графа или графа реальной сети в пространстве параметров. В результате расчета F для N реализаций графов получаем матрицу наблюдений n\\ =|fj || , где n - номер свойства графов. Для полученной матрицы проводится статистический анализ изменчивости значений свойств графов, чтобы оценить однородность наблюдений. Статистический анализ осуществляется путем построения доверительных интервалов (ДИ) для коэффициента вариации (кв) [20]. В статистике принято считать, что совокупность наблюдений, коэффициент вариации которых превышает 33%, является неоднородной. Таким образом, из матрицы наблюдений исключаются признаки, которые выходят за границы рассчитанного для них ДИ, и те, кв которых превышает 33%. ДИ (95%) рассчитываются на основе статистики Мак Кея [20, 21]: -1/2 -1/2 кв 1 U1 -11 (кв)2 + < кв < кв 1 U2 -11 (кв)2 + V 2 v _ v 2 v _ 2 где и1 =Х21-а/2 и и2 = %2 а/2,100(1 -а/2) % и 100(а/2) % - перцентили распределения Хи-квадрат с v=n-1 степенями свободы [22]. Этап оценки адекватности модели. На этом этапе рассчитывается матрица евклидовых расстояний между модельными образами и образом исследуемой реальной сети в пространстве значений F. По расстоянию между образами моделей различных типов и реальной сетью осуществляется оценка статистической значимости различия между образом реальной сети и образом модели графа по критерию согласия Пирсона (Хи-квадрат). Считается, что те модели, которые статистически незначимо отличаются по расстоянию в пространстве параметров от исходной реальной сети, являются адекватными. 3.2. Результапты экспериментальный исследований Проведем сравнительный анализ моделей ЭР, БА и ЭМСГ с реальной сетью отношений между менеджерами одной из компаний США (англоязычное название сети ht_friends), представленной в пакете «нетворкдата» (англ. networkdata), который является самым крупным набором сетевых данных для языка статистического моделирования R. Рассматриваемая реальная сеть № 1 является связной и направленной, имеет 21 вершину и 102 ребра. Произведем моделирование путем формирования множеств реализаций случайных графов с использованием рассмотренных моделей на множестве их параметров, как показано в п. 2. Для каждой полученной модели рассчитаем образ F В результате получены три матрицы наблюдений: для БА размерности Y БА , для ЭР размерности Y ЭР . Размерности матриц обусловлены особенностями установки параметров моделей, указанных в п. 2. Отдельно производится расчет ЭМСГ, на основе его получено минимальное значение AIC = 422 при комбинации термов intransitive + mutual + meandeg + simmelianties. Для полученных матриц наблюдений был осуществлен статистический анализ изменчивости, который заключался в измерении кв и построении ДИ для него. Результаты анализа представлены в табл. 2. Таблица 2 Результаты расчета коэффициента вариации и ДИ ДИ/F СРс ПГ Ас Ди СЦ СБ СП СВЦ Тр Кв 21,6 31,6 46,5 30,3 29,2 103,3 10,7 41,3 27,6 ДИ нижний 20,7 29,0 44,3 29,0 28,0 96,3 9,3 39,4 26,2 ДИ верхний 22,5 33,5 48,9 31,8 30,6 111,9 11,4 43,4 28,3 Из табл. 2 видно, что однородны совокупности наблюдений СРс, Ди, СЦ, СП, ПГ и Тр (выделены серым), поэтому из дальнейшего анализа исключаем остальные три свойства и рассчитываем евклидово расстояние между образами сетей в пространстве шести оставшихся свойств графов. На рис. 2 представлены зависимости евклидова расстояния между образами и тестовой сетью от номера модели для ЭР (черная пунктирная линия) и БА (красная сплошная линия), причем для наглядности представлены зависимости не только для сети ht_friends, но и для сетей № 2-4 из табл. 3. На рис. 2, а показано евклидово расстояние образов моделируемых сетей от образа тестовой сети № 1 ht_friends, на рис. 2, b - от образа сети № 2, на рис. 2, c - от образа сети № 3, на рис. 2, d - от образа сети № 4. Видно, что зависимость для модели ЭР изменчива, а для БА - однородна. ■ ’( s......... .Л Номер модели , d c Рис. 2. Зависимости евклидова расстояния между образами сетей и номерами моделей сети Fig. 2. Dependencies of Euclidean distance between network patterns and network model numbers I • ! I } > / Из 729 моделей БА и 420 ЭР выбирается по одной, наиболее близкой к реальной сети. Для наилучшей по критерию AIC ЭМСГ аналогично рассчитываются образ и расстояние от него до образа реальной сети. По критерию согласия Пирсона (Хи-квадрат) осуществлена оценка статистической значимости расстояний между образами моделей и образом реальной сети. В соответствии с этой оценкой на уровне значимости p-value = 0,005 статистически значимыми являются различия в расстоянии между образом реальной сети и образами моделей ЭМСГ, ЭР, БА. Следовательно, не представляется возможным сформировать адекватную модель сети № 1, т.е. статистически незначимо отличающуюся от нее в пространстве параметров свойств графов. 3.3. Сравнительный анализ моделей графов по тестовому набору реальных сетей Для обобщения полученного выше результата верификации моделей по представленной на рис. 1 схеме осуществлен сравнительный анализ рассмотренных моделей случайных графов с использованием данных о реальных сетях, представленных в пакете «нетворкдата». Выбранные реальные данные отражают различные стороны человеческой деятельности: сеть № 1 - сеть дружеских взаимоотношений в кампусе Австралийского национального университета, № 2, 3 - ИКС в датацентрах одной из коммерческих организаций, № 4 - иерархия в стае птиц, № 5 -сеть взаимоотношений в колледже штата Иллинойс, № 6 - сеть менеджеров крупной корпорации, № 7 -рабочая ИКС в адвокатской конторе, № 8 - транспортная сеть авиаперевозок в США, № 9 - сеть межбелковых взаимодействий в человеческом организме. Результаты анализа представлены в табл. 3. Таблица 3 Результаты сравнительного анализа моделей графов Сеть ЭМСГ ЭР БА 1 2 3 1 2 3 1 2 3 № 1 intransitive + mutual + meandeg + simmelianties (AIC = 422) 5,05 З E = 58 19,22 З P = (0;0,6;0,2;0,2) 24,85 З № 2 twopath + density + intransitive (AIC = 630) 1,56 З E = 29 0,41 Н P = (0;0,4;0,2;0,2) 1,94 З № 3 intransitive + mutual + edges + simmelianties (AIC = 220) 0,48 Н E = 29 0,46 Н P = (0;0,9;0,1;0,2) 1,82 З № 4 intransitive + simmelianties + density + mutual (AIC = 689) 1,46 З E = 47 0,69 З P = (0;0,8;0,2;0,2) 1,11 З № 5 balance + intransitive+ mutual + transitive (AIC = 3541) 14,14 З E = 102 5,48 З P =

Скачать электронную версию публикации