Растущие сети с потерями связей

научный вестник. Сер. Приборы, машины и технологии. — 2015. - № 1 (137). - С. 215-219.

9. Задорожный, В. Н. Переходные процессы в растущих сетях с нелинейным правилом предпочтительного связывания // В. Н. Задорожный, В. А. Бадрызлов // Омский научный вестник. Сер. Приборы, машины и технологии. — 2016. — № 1 (145). - С. 95-99.

10. Задорожный, В. Н. Система агентного моделирования 81шЫдгарЬ / В. Н. Задорожный, Е. Б. Юдин // Навигатор в мире науки и образования. - 2012. - № 4-7 (20-23). - С. 536.

ЗАДОРОЖНЫЙ Владимир Николаевич, доктор технических наук, доцент (Россия), профессор кафедры «Автоматизированные системы обработки информации и управления». Адрес для переписки: zwn2015@yandex.ru

Статья поступила в редакцию 24.02.2016 г. © В. Н. Задорожный

УДК 519.2:004.421.5:004.7

В. Н. ЗАДОРОЖНЫЙ В. А. БАДРЫЗЛОВ Е. Б. ЮДИН

Омский государственный технический университет

РАСТУЩИЕ СЕТИ С ПОТЕРЯМИ СВЯЗЕЙ

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

Ключевые слова: растущие сети, случайные графы, стационарные и переходные случайные процессы.

1. Введение. Многие свойства реальных больших сетей удается объяснить развитием этих сетей по так называемому линейному правилу предпочтительного связывания (ЛППС) [1]. Согласно этому правилу рост сети является результатом добавления к ней новых узлов, которые имеют m связей и предпочитают соединяться этими связями с теми узлами сети, у которых степень связности к выше [2, 3]. Математически ЛППС выражается формулой pt = kt /Z jkj, которая определяет вероятность того, что новая связь (выбирающая узел графа независимо от других m — 1 новых связей) соединится с узлом i, степень связности которого равна к.. Таким образом, в ЛППС вероятность p. связывания с узлом i пропорциональнастепенисвязности этого узла: p. ~ к.

Моделью таких сетей является граф Барабаши — Альберт (граф БА), предложенный Альбертом Барабаши и Рекой Альберт [2, 3]. Свойства графа БА согласуются со свойствами многих, хотя и далеко не всех реальных сетей [1, 4]. Дальнейшее развитие моделей растущих сетей привело к созданию нового раздела статистической механики, называемого теорией сетей (Network Science). Как показывает аналитический обзор публикаций, одним из наиболее удачных направлений развития Network Science, успешно конкурирующих с другими подходами, является теория случайных графов (сл.г.) с нелинейным правилом предпочтительного связывания (НППС) [5—10]. Многие результаты, полученные при использовании других подходов, являются простыми частными случаями результатов

теории сл.г. с НППС, получаемыми из ее формул немедленно при подстановке в них соответствующих значений параметров [6 — 8]. Ряд задач Network Science решен методами теории сл.г. с НППС впервые [5—10]. К таким задачам относится и задача расчета характеристик растущих графов с потерями связей, решаемая в данной статье.

Решаемая задача является шагом к повышению адекватности математического моделирования социальных сетей, бурное развитие которых оказывает серьезное влияние на общественные процессы, проявляющееся через рекламу, информационное противостояние, идеологическую борьбу, вербовку новых членов террористическими организациями и т.д.

Существующие модели социальных сетей нередко подвергаются обоснованной критике [11], поскольку не учитывают такие особенности сетей, как ограниченность возможного числа связей у любого участника сети и случайное изменение существующих связей между участниками. Эти особенности учитываются моделью, разрабатываемой в настоящей статье на основе теории сл.г. с НППС.

2. Основные положения теории случайных графов с НППС. Теория сл.г. с НППС отличается от теории сл.г. с ЛППС двумя основными положениями.

Во-первых, в теории сл.г. с НППС приращения графа (добавляемые к графу новые вершины с исходящими из них дугами) стохастические, т.е. число x дуг каждого приращения является независимой случайной величиной с распределением вероятностей P(x. = к) = rk, g < к < h, Ък (rk) = 1.

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

Р1 =

ш

2 Ы

1, ] = 1,

ы,

Рис. 1. Пример выращивания сл.г. с НППС из затравки, содержащей три вершины

где /(к) — вес в ерш=ны, имеющ ей сте пень связ но-сти к; /(к) > 0, есл^ < к < М, иначе /(к) = 0 (здесь М < N — число вершин в графе. Поскольку аргумент весовое функции /(к) еелочерленный, мы будем обозначать ее также через /к, рассматривая ее при этом как числовую последовательность весов. Этот прием позволит нам без лишних оговорок работать с внсовыми фу=куинмщ, нщ выражаемыми в элементарных функциях в замкнутым виде.

В качестве примера на рис. 1 показаны первые шаги выращиваныя г/афщ с НПП(У из треугольного графа-затравки. Приращения с одной или двумя дугами появляются с едшаковой вероятносеын, г = г2 = 1/2. При выборе вершин для присоединения дуг приращений используется щ(завило (1) с весовой функцией /(к) = 1п(к). Здесь минимальное число дуг в приращении g = 1, максимальное число дуг в приращении Л = 2.

Одной из особенностей теории сл.г. с НППС является регулярное использование прямого теоретико-вероятностного анализа процессов, происходящих при выращивании сл.г. с НППС. Это позволяет выводить уравнения динамики для распределения степеней связности (РСС) вершин и/или дуг графа и переходить от уравнений динамики к уравнениям финальных РСС, получаемым предельным переходом при N ^

При этом РСС вершин определяется как дискретное распределение вероятностей |дк|, которым описывается степень случайно (равновероятно) выбранной вершины графа. Если обозначить через Ак множество вершин в графе (слой), имеющих степень к, то qk = |Ак|/М При неограниченном добавлении приращений к графу число его вершин N ^ ~ и {дк} ^ Шк}, где (бк| — финальное РСС вершин графа.

Для дуг графа РСС определяется как двумерное дискретное распределение вероятностей {ц,к}, которым описываются концевые степени (начальная 1 и терминальная к) случайно выбранной дуги (с.в.д.) графа. Начальная степень дуги — это степень вершины, из которой дуга исходит, терминальная степень — это степень вершины, в которую дуга заходит. Если обозначить через В(1,к) множество дуг в графе (туннель), имеющих начальную степень 1 и терминальную степень к, то д1к = В,к1/Я, где Я — число дуг в графе. Из построения графа с очевидностью вытекает, что Я ~ mN при N ^ где т = Хк (кгк) — среднее число дуг в приращении графа. Поэтому при анализе РСС дуг графа мы используем асимптотически точное приближение

ч,,к~ В,,к1/(^). С ростом графа {ч1Л} ^ {Qlk}, где

{б1к} — финальное РСС дуг.

Туннели В(1,к) с наименьшим возможным значением 1 = g называются входными, все остальные туннели — внутренними. Понятия слоев и туннелей, используемые в теории сл.г. с НППС, иллю-

Рис. 2. Распределение по слоям вершин графа, построенного на рис. 1

стрируются на рис. 2 на примере графа, полученного на рис. 1 после присоединения вершины 9.

Граф представлен с явным распределением вершин по слоям А1, ..., А6. Входной туннель В(1, 4) содержит только одну дугу, т.е. В(1, 4) ={(5, 1)}. Другие входные туннели пусты. Из внутренних туннелей непустыми являются:

В(2, 6) = {(8, 4), (9, 4), (7, 4), (6, 4)};

В(2, 4) = {(8, 1), (6, 2)};

В(4, 3) = {(1, 3)}; В(3, 4) = {(3, 2)};

В(4, 4) = {(1, 2)}; В(6, 3) = {(4, 3)};

В(6, 4) = {(4, 2)}, В(2, 2) = {(9, 7)}.

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

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

1) к графу присоединяется по правилу (1) новое приращение;

2) из графа удаляется случайное число с.в.д., в среднем у дуг (0 < у < т).

Обратим внимание на то, что потери с.в.д. могут с положительной вероятностью приводить к тому, что будут появляться вершины со степенью к = 0 (изолированные вершины). Это означает, что наименьшим номером слоя в графах с потерями дуг является номер g =0. В соответствии с этим

естественно считать, что последовательность положительных весов может начинаться ненулевым весом / обеспечивающим возможность «возвращения» в граф вершин, потерявших с ним все связи.

Число дуг, добавляемых в граф за один шаг, в среднем составляет М(х) - у = т - у = т > 0. Будем считать, что случайное число удаляемых на каждом шаге дуг задано на конечном диапазоне возможных значений. Тогда среднее число дуг в графе М(К) при больших N сходится с относительной погрешностью нуль к величине тN, т.е. М(Л) ~ тN.

Выведем уравнения динамики РСС {дк} вершин графа путем определения асимптотически точных приближений для изменений вероятностей дк в результате выполнения шага t. Примем за начало отсчета времени момент Щ0 = где N — число вершин в затравке графа. Тогда в результате выполнения любого шага t > Щ0 выполняется равенство t = N.

Как показано в [10], в соответств и и с правилом (1) каждая дуга поступившего на /аге t приращения выбирает для связывания в ерш ину е лоя Ак с вероятностью Рк = дк/ //), в результате чего распределение вершин по слоям изменяется:

Шк(Щ) = у (к + 1)^+1/(га^ - уkNk /(тИ) = = у(к + 1) Цк+/т - укок /т.

^^ + 1) = щц + Гк + + тРк_^) - тРк(Щ),

к > 0,

где Nk — среднее число вершин в слое Ак. зуписи (2) цитируемого соотношения учтено, что в нашем случае g = 0.

В графе с потерями дуг на каждом шаге Щ, после присоединения к графу нового приращения, происходит также потеря в среднем у с.в.д., в ре -зультате которой среднее число дуг (2) в каждом слое претерпевает дополнительно следующие изменения. С вероятностью (д ) любая я:в.д. может заходить в вершину слоя Ак. В таком случае потеря этой с.в.д. уменьшает на единицу степень соответствующей вершины слоя Ак, и вершина уходит из данного слоя в слой А . Число вершин в слое Ак уменьшается на единицу. С учетом вероятности 21 (д ) рассматриваемого случая и среднего числа у теряемых на шаге t дуг в среднем за счет возможности захода теряемых дуг в слой Ак число вершин в нем уменьшается на у2, (д1к). Рассматривая аналогичным образом возможность захода с.в.д. в слой А , находим, что за счет этой возможности в среднем на шаге t число вершин в слое Ак возрастает на у2, (д1к+1). Кроме того, число вершин в этом слое убывает [возрастает] в среднем на у2, (д ) [в среднем на у2 (дк+11)] за счет возможности исхода с.в.д. из слоя Ак [из слоя А ]. Таким образом, общая поправка к среднему числу дуг в слое Ак, вносимая потерей с.в.д., составляет величину

ШкЩ = у2, (д,+) - у2, (д1Л) + у2, (д) -

- у2, ад = у[2 (д1к+,) + 2 (Чк+и)] - у[2 (д,,к) +

+ (дк,)] = у{[М2, \Б(1,к+1)\ + М2, \Б(к+1,1)\] --[М2, \Б(1,к)\ + М2, \Б(к,1)\]]/(т^,

где М — символ математического ожидания. Нетрудно видеть, что выражение в первой паре квадратных скобок есть не что иное, как среднее число дуг, инцидентных вершинам слоя Ак+1 и равное, очевидно, (к + 1)^ , во второй паре квадратных скобок — среднее число дуг, инцидентных вершинам слоя Ак (равное кЫк,). Отсюда

Добавляя поправку (3), вносимую потерей с.в.д., к (2), получаем:

Nk(t + 1) = Nk(t) + Гк + тРк_1(Щ) - тР(Щ) + + у (к + 1) дк+/т - укдк /т.

Наконец, выражая здесь Р. = д. / //) через исходные; дунны63 и текущее РСС вершин {дк} = = {дк(Щ)}, приуодим к соотношению

ну (( с я = ну (() с Гу с р/^^у_я (и)/у_я -

- еу (=) Н ] -ии [(ус р с! (и) - уек (и)],

р

г Не /(() = 2/,)0 /Гес(И) — СР) -не- в ес вершин

на шаге ^

или

р

е с Яед(р с!) = ве,(() (Г(( и—[ед-, ©Л-я-

и

- Я( ] с и ((((с 1)еус! (О - (е, (и)], м

р

где Щ = N — чииио в сех с ерш ин на шаяе И или, еронсятельно,

е) (И с 1) =

(Ну (() с Гу с /(и) [Иу-я(() Ш(-1 - Иу (() /у] с

(Й^Я

сИ [

для всех к > 0.

Соотношение (5) представляет собой асимптотически точную систему уравнений динамики РСС {дк(Щ)} вершин графа с НППС с потерями дуг.

4. Расчет финального РСС вершин при ограниченной степени связности. Вершины растущего графа с НППС имеют ограниченную степень связности, если ограничена последовательность ненулевых весов/, ...,/М, используемая в НППС (1), т.е. если М <

Действительно, в этом случае максимальная степень вершин графа равна М + 1, так как к вершинам, переместившимся по мере роста их степени в слой АМ+1, новые дуги присоединяться не будут (вес /М+1 таких вершин равен нулю). Тем самым в теории сл.г. с НППС автоматически учитываются критические замечания (высказываемые в отношении теории сл.г. с ЛППС, [11]), в которых указывается на ограниченность степеней связности в социальных сетях.

Уравнение для финального РСС ^к} вершин графа с потерями дуг легко выводится из соотношения (4). Записывая левую часть равенства (4) в виде Щдк(Щ + 1) + дк(Щ + 1) и устремляя Щ к бесконечности, можно сократить члены Щдк(Щ + 1) в левой части и Щдк(Щ) в правой, поскольку оба они сходятся к одной и той же величине tQk. Оставшиеся в уравнении вероятности слоев и средний вес вершин также следует заменить их финальными (предельными) значениями. В результате получаем:

Рис. 3. Сравнение результатов точного расчета РСС вершин с результатами ИМ

Рис. 4. Демонстрация сходимости переходных РСС [якЮ] к финальному РСС {@к}

Рис. 5. Сравнение РСС {@к} эквивалентных по /(к) и по (к) графов без потерь и с потерями

& = г +ы [&-Ыы-( -&ыы+

+ СС-[(, * + (&-(-*&/, к > 0.

Выражая от+юда (Н+ы в вид-

г + щ&-1ык-(к к+я

&к =

ны >

& -

к > 0,

, в/к кг (/> й

получаем вые=те с уравнением

(/) = ыл

но (ы) и всех Лк методом минимизации невязок или методом простых итераций. В случае применения простых итераций в качестве начального приближения рекомендуем брать равномерное РСС

&0 = &1 = . = Лм+1 = 1/(M + 2).

5. Примеры финального и переходных РыС вершин графа с потерями дуг. На рис. 3 показан график финального РСС, рассчитанного путем точного решения системы (7), (Щ чи+лелными методами и оцененного методом имитационного моделирования (ИМ), в котором был выращен гр аф рсзм я ром 100 007 вершин (затрзв ка состоыла из семи вершин). Весовая функция при 0 < к < 20 опщыд+лясась в виде

ы, =

к1 + (0 к + (

систему (7), (8) из M + 3 уравнений с M + 3 неизвестными, которая при ограничении «/. = 0, когда I < 0 или I > M + 1» легко решается относитель-

и равнялась нулю при прочих к. Число x дуг приращения (1 < x < 4) имело распределение вероятностей (г0, г1, г2, г3, г4) = (0,001, 0,1, 0,4, 0,2 0,299), т.е. допускались приращения, не содержащие дуг (изолированные вершины).

Как видно из рис. 3, результаты расчета и моделирования согласуются с точностью до статистических погрешностей имитационных оценок.

На рис. 4 с финальным РСС {&к} = {^к(тс)} этого же графа сравниваются переходные РСС {дк(100)} и {дк(1000)}, рассчитанные по формуле (5).

Эксперименты показывают, что в графах с ограниченной степенью вершин переходные РСС достаточно быстро сходятся к стационарным. Это позволяет при относительно небольших размерах исследуемых социальных сетей с хорошей точностью идентифицировать их структурные характеристики, обуславливаемые распределениями степеней связности.

Как показывают дополнительные эксперименты, в графах с потерями с.в.д. всегда имеется определенная доля изолированных вершин. Так, даже если в рассмотренном примере все приращения графа будут содержать 4 дуги, то в финальном распределении {&к} вероятность &0 составит 3,2740-5.

6. Заключение. На рис. 5 представлены РСС двух эквивалентных по средней степени связности графов С0 и С1, имеющих весовую функцию ы(к) = к, 1 < к < M (M = 1000). Максимальная степень связности у обоих графов M+ 1 = 1001. В графе С0 дуги не теряются и все приращения имеют одну дугу (m = 1), поэтому средняя степень связности его вершин (к) = 2m = 2. В графе С1 с потерями дуг все приращения имеют две дуги и на каждом шаге теряется одна с.в.д. В результате на каждом шаге в граф С1 добавляется в среднем одна вершина и одна дуга (т = 1), и его средняя степень связности тоже составляет (к) = 2т = 2.

Из рис. 5 видно, что эти два графа с одинаковыми весами ы и одинаковой плотностью дуг имеют существенно различную структуру: в графе С1 с потерями дуг доля вершин с высокой степенью связности на несколько порядков меньше, чем в графе С0. Если графы имеют около 1 млн вершин, то самая высокая степень, достигаемая вершинами графа С1, будет находиться в пределах 50, в то время как в графе без потерь будет много вершин с сотнями связей, и вполне может появиться несколько вершин со степенью к = 1001.

Выполненное сравнение показывает, сколь важно учитывать случайные потери связей при моделировании социальных сетей и ограниченную степень связности их участников. Это эффективно

реализуется посредством разработанных в данной статье уравнений динамики РСС вершин и численных методов расчета финальных РСС вершин растущих графов с потерями дуг.

Библиографический список

1. Krapivsky P. L., Redner S. Organization of growing random networks, Phys. Rev. E 63 (2001) 066123.

2. Barabasi A. L., Albert R. Emergence of scaling in random networks, Science 286 (1999) 509-512.

3. Barabasi A. L., Albert R. Statistical mechanics of complex networks, Rev. Mod. Phys 74 (2002) 47-97.

4. Amaral L. A. N., Scala A., Barthelemy M., Stanley H. E., Classes of small-world networks, in: Proc. Natl. Acad. Sci. U.S.A. 97, 2000, p. 11149.

5. Задорожный, В. Н. Случайные графы с нелинейным правилом предпочтительного связывания / В. Н. Задорожный // Проблемы управления, 2011. — № 6. — C. 2-11.

6. Zadorozhnyi V. N., Yudin E. B. Structural properties of the scale-free Barabasi-Albert graph // Automation and Remote Control. — Vol. 73, № 4, 2012. — P. 252 — 261. DOI: 10.1134/ S0005117908020070.

7. Zadorozhnyi V., Yudin E. Growing Network: Nonlinear Extension of the Barabasi-Albert Model // Communications in Computer and Information Science, 2014. Т. 487. С. 432 — 439.

8. Zadorozhnyi V., Yudin E. Structural Identification of Large Statistically Distributed Vertex Degree // Dynamics of Systems, Mechanisms and Machines (Dynamics), 2014, December, 2014, pp 1 — 4. DOI: 10.1109 / Dynamics. — 2014.7005703.

9. Zadorozhnyi V. N., Yudin E. B. Growing network: models following nonlinear preferential attachment rule, Physica A: Statistical Mechanics and its Applications, v. 428, pp. 111 — 132, 2015 DOI: 10.1016/j.physa.2015.01.052.

10. Задорожный, В. Н. Переходные процессы в растущих сетях с нелинейным правилом предпочтительного связывания // В. Н. Задорожный, В. А. Бадрызлов // Омский научный вестник. Сер. Приборы, машины и технологии. — 2016. — № 1 (145). - С. 95-99.

11. The structure of growing social networks, Emily M. Jin, Michelle Girvan, and M. E. J. Newman, Phys. Rev. E 64, 046132 (2001).

ЗАДОРОЖНЫЙ Владимир Николаевич, доктор технических наук, доцент (Россия), профессор кафедры «Автоматизированные системы обработки информации и управления». Адрес для переписки: zwn2015@yandex.ru БАДРЫЗЛОВ Владимир Александрович, аспирант кафедры «Автоматизированные системы обработки информации и управления». Адрес для переписки: v_bad@mai1.ru ЮДИН Евгений Борисович, кандидат технических наук, доцент кафедры «Автоматизированные системы обработки информации и управления». Адрес для переписки: udinev@asoiu.com

Статья поступила в редакцию 29.02.2016 г. © В. Н. Задорожный, В. А. Бадрызлов, Е. Б. Юдин

Книжная полка

004/В52

Вирт, Н. Алгоритмы и структуры данных. Новая версия для Оберона / Н. Вирт ; пер. с англ. под ред. Ф. В. Ткачева. - М. : ДМК Пресс, 2014. - 272 c. - ISBN 978-5-97060-011-5.

В классическом учебнике тьюринговского лауреата Н. Вирта аккуратно, на тщательно подобранных примерах прорабатываются основные темы алгоритмики — сортировка и поиск, рекурсия, динамические структуры данных. Перевод на русский язык выполнен заново, все рассуждения и программы проверены и исправлены, часть примеров по согласованию с автором переработана с целью максимального прояснения их логики (в том числе за счет использования цикла Дейкстры). Нотацией примеров теперь служит Оберон/Компонентный Паскаль — наиболее совершенный потомок старого Паскаля по прямой линии. Все программы проверены и работают в популярном варианте Оберона — системе Блэкбокс, и доступны в исходниках на сайте издательства вместе с самой системой и дополнительными материалами. Большая часть материала книги составляет необходимый минимум знаний по алгоритмике не только для программистов-профессионалов, но и для любых других специалистов, активно использующих программирование в работе. Книга может быть использована как учебное пособие при обучении будущих программистов, начиная со старшеклассников в профильном обучении, а также подходит для систематического самообразования.

004/П64

Потапов, В. И. Противоборство технических систем в конфликтных ситуациях: модели и алгоритмы : моногр. / В. И. Потапов. - Омск : Изд-во ОмГТУ, 2015. - 166 с.

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

Предназначена для научных работников, аспирантов и магистрантов, занимающихся изучением и использованием на практике математических моделей и алгоритмов оптимального управления противоборствующими техническими системами в конфликтных ситуациях.