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

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

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

Основы теории сетей

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

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

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

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

$P(k)\sim k^{-\gamma }$

Для многих реальных сетей этот показатель равен примерно 3, однако он не является универсальной константой и постоянно зависит от параметров сети.

безмасштабные

Основная статья: модель Барабаши – Альберта

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

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

Дополнения к модели БА

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

Фитнес

Основная статья: Фитнес-модель (теория сетей)

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

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

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

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

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

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

Удаление узлов и перемонтирование связей

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

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

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

Проблема r: удалить узел.

Проблема 1-pqr: добавить узел.

характеристики развивающихся

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

к

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

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

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

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

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

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

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

Приложения

Карта маршрутов регулярных коммерческих авиаперевозок мира, 2009 г. Эта сеть постоянно развивается по мере планирования или отмены новых маршрутов.

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

Дальнейшее чтение

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