Развивающаяся сеть

Анимация развивающейся сети в соответствии с исходной моделью Барабаши – Альберта.

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

Предпосылки создания теории сетей [ править ]

Палатки создали исследование следов сетей и его основы для развития теории графов , которая была впервые проанализирована Леонардом Эйлером в 1736 году, когда он написал знаменитую статью « Семь мостов в Кенигсберге» . Затем вероятностная теория сетей была развита с помощью восьми известных работ, посвященных изучению случайных графов, написанных Полом Эрдёшем и Альфредом Реньи . Модель Эрдеша – Реньи (ER) предполагает, что граф состоит из N помеченных узлов, где каждая пара узлов связана с заданной вероятностью p .

График Ваттса – Строгаца

Хотя простота модели ER помогла ей найти множество приложений, она не точно описывает многие реальные сети. Модель ER не может генерировать локальную кластеризацию и триадные замыкания так часто, как они встречаются в реальных сетях. Поэтому была предложена модель Уоттса и Строгаца , согласно которой сеть строится в виде регулярной кольцевой решетки, а затем узлы перемонтируются в соответствии с некоторой вероятностью β . ^[1] Это создает локально сгруппированную сеть и резко сокращает среднюю длину пути , создавая сети, которые представляют собой явление маленького мира, наблюдаемое во многих реальных сетях. ^[2]

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

${\ Displaystyle Р (к) \ сим к ^ {- \ гамма}}$

Этот показатель для многих реальных сетей оказывается приблизительно равным 3, однако он не является универсальной константой и непрерывно зависит от параметров сети ^[3]

Первая развивающаяся сетевая модель - безмасштабные сети [ править ]

Модель Барабаши – Альберта (BA) была первой широко принятой моделью для создания безмасштабных сетей . Это было достигнуто за счет включения предпочтительного присоединения и роста, когда узлы добавляются в сеть с течением времени и с большей вероятностью будут подключаться к другим узлам с высокой степенью распределения. Модель BA впервые была применена к распределению степеней в сети, где оба эти эффекта можно четко увидеть. Новые веб-страницы добавляются с течением времени, и каждая новая страница с большей вероятностью будет ссылаться на хорошо заметные узлы, такие как Google, которые имеют высокую степень распространения, чем на узлы с несколькими ссылками. Формально эта льготная привязка:

${\ displaystyle p_ {i} = {\ frac {k_ {i}} {\ displaystyle \ sum _ {j} k_ {j}}},}$

Дополнения к модели БА [ править ]

Модель BA была первой моделью, которая выводила топологию сети на основе того, как сеть была построена, с добавлением узлов и ссылок с течением времени. Однако модель делает только простейшие допущения, необходимые для появления безмасштабной сети, а именно, что существует линейный рост и линейное предпочтительное присоединение. Эта минимальная модель не учитывает вариации формы распределения степеней, вариации показателя степени или коэффициента кластеризации, не зависящего от размера . Следовательно, с тех пор исходная модель была изменена ^{[ кем? ],} чтобы более полно охватить свойства развивающихся сетей, введя несколько новых свойств.

Фитнес [ править ]

Одна из проблем модели BA заключается в том, что распределения степеней каждого узла испытывают сильную положительную обратную связь, в результате чего самые ранние узлы с распределениями высокой степени продолжают доминировать в сети на неопределенный срок. Однако это можно облегчить, введя соответствие для каждого узла, что изменяет вероятность создания новых ссылок с этим узлом или даже удаления ссылок на этот узел. ^[4]

Чтобы сохранить предпочтительную привязку из модели BA, эта пригодность затем умножается на предпочтительную привязку на основе распределения степеней, чтобы получить истинную вероятность того, что создается ссылка, которая подключается к узлу i .

${\displaystyle \Pi (k_{i})={\frac {\eta _{i}k_{i}}{\displaystyle \sum _{j}\eta _{j}k_{j}}},}$

Где фитнес, который тоже может зависеть от времени. Ухудшение приспособленности во времени может происходить и может быть формализовано следующим образом:${\displaystyle \eta }$

${\displaystyle \Pi (k_{i})\propto k_{i}(t-t_{i})^{-\nu },}$

где увеличивается с${\displaystyle \gamma }$${\displaystyle \nu .}$

Удаление узлов и изменение проводки ссылок [ править ]

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

Проб п: добавить внутреннюю ссылку.

Проблема q: удалить ссылку.

Вероятно: удалить узел.

Вероятность 1-pqr: добавить узел.

Другие способы характеристики развивающихся сетей [ править ]

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

Конвергенция к равновесию [ править ]

В сетевых системах, где имеет место конкурентное принятие решений, теория игр часто используется для моделирования динамики системы, а сближение к равновесию можно рассматривать как движущую силу топологической эволюции. Например, Kasthurirathna и Piraveenan ^[5] показали, что когда люди в системе демонстрируют различные уровни рациональности, улучшение общей рациональности системы может быть эволюционной причиной появления безмасштабных сетей. Они продемонстрировали это, применив эволюционное давление на изначально случайную сеть, которая имитирует ряд классических игр, так что сеть сходится к равновесию по Нэшу, при этом позволяя повторно подключаться. В ходе этого процесса сети становятся все более масштабируемыми.

Рассматривайте развивающиеся сети как последовательные снимки статической сети [ править ]

Наиболее распространенный способ рассматривать развивающиеся сети - рассматривать их как последовательные статические сети. Это можно представить как отдельные неподвижные изображения, составляющие кинофильм . Существует множество простых параметров для описания статической сети (количество узлов, ребер, длина пути, связанные компоненты) или для описания конкретных узлов в графе, таких как количество ссылок или коэффициент кластеризации. Затем эти свойства могут быть индивидуально изучены как временные ряды с использованием понятий обработки сигналов. ^[6] Например, мы можем отслеживать количество ссылок, установленных на сервер в минуту, просматривая последовательные снимки сети и подсчитывая эти ссылки в каждом снимке.

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

Определите динамические свойства [ править ]

Может быть важно посмотреть на свойства, которые нельзя непосредственно наблюдать, рассматривая развивающиеся сети как последовательность моментальных снимков, например, продолжительность контактов между узлами ^[7] Можно определить другие аналогичные свойства, а затем вместо этого можно отслеживать эти свойства. через эволюцию сети и визуализировать их напрямую.

Еще одна проблема, связанная с использованием последовательных снимков, заключается в том, что только небольшие изменения в топологии сети могут иметь большое влияние на результат работы алгоритмов, предназначенных для поиска сообществ. Следовательно, необходимо использовать неклассическое определение сообществ, которое позволяет отслеживать эволюцию сообщества с помощью набора правил, таких как рождение, смерть, слияние, разделение, рост и сокращение. ^{[8] [9]}

Приложения [ править ]

Почти все сети реального мира являются развивающимися сетями, поскольку они строятся с течением времени. Варьируя соответствующие вероятности, описанные выше, можно использовать расширенную модель BA для построения сети с почти такими же свойствами, что и многие наблюдаемые сети. ^[10] Более того, концепция сетей без масштаба показывает нам, что эволюция во времени является необходимой частью понимания свойств сети, и что сложно смоделировать существующую сеть как созданную мгновенно. Реальные развивающиеся сети, которые в настоящее время изучаются, включают социальные сети , сети связи , Интернет , сеть киноактеров , всемирную паутину итранспортные сети .

Дальнейшее чтение [ править ]

• «Понимание сетевой науки», https://web.archive.org/web/20110718151116/http://www.zangani.com/blog/2007-1030-networkingscience.
• «Связано: новая наука о сетях», А.-Л. Издательство Barabási Perseus Publishing, Кембридж.

Ссылки [ править ]