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

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

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

Фон теории сети

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

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

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

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

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

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

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

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

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

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

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

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

Фитнес

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

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

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

${\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: удалить ссылку.

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

Prob 1-p-q-r: добавить узел.

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

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

Сближение к равновесию

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

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

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

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

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

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

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

Приложения

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

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

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

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

Рекомендации

1. Watts, D.J .; Строгац, С. (1998). «Коллективная динамика сетей« маленького мира »». Природа. 393 (6684): 409–10. Bibcode:1998 Натур.393..440Вт. Дои:10.1038/30918. PMID  9623998.
2. Трэверс Джеффри; Милгрэм Стэнли (1969). «Экспериментальное исследование проблемы малого мира». Социометрия. 32 (4): 425–443. Дои:10.2307/2786545. JSTOR  2786545.
3. Р. Альберт; А.-Л. Барабаши (2000). «Топология развивающихся сетей: локальные события и универсальность» (PDF). Письма с физическими проверками. 85 (24): 5234–5237. arXiv:cond-mat / 0005085. Bibcode:2000ПхРвЛ..85.5234А. Дои:10.1103 / PhysRevLett.85.5234. HDL:2047 / d20000695. PMID  11102229.
4. Альберт Р. и Барабаши А.-Л., "Статистическая механика сложных сетей", Обзоры современной физики 74, 47 (2002)
5. Каштуриратна, Дхаршана; Пиравинан, Махендра. (2015). «Возникновение безмасштабных характеристик в социоэкологических системах с ограниченной рациональностью». Научные отчеты. В прессе.
6. Пьер Борна; Эрик Флери; и другие. «Развивающиеся сети» (PDF).
7. А. Шентро; П. Хуэй; Дж. Кроукрофт; К. Диот; Р. Гасс; Дж. Скотт (2006). «Влияние мобильности людей на разработку гибких алгоритмов переадресации» (PDF). Инфоком.
8. Г. Палла; А. Барабаши; Т. Вичек; Ю. Чи, С. Чжу, X. Сонг, Дж. Татемура, Б.Л. Ценг (2007). «Количественная оценка эволюции социальных групп». Природа. 446 (7136): 664–667. arXiv:0704.0744. Bibcode:2007Натура.446..664П. Дои:10.1038 / природа05670. PMID  17410175.
9. Ю. Чи, С. Чжу; X. Песня; Дж. Татемура; Б.Л. Ценг (2007). Структурный и временной анализ блогосферы через факторизацию сообщества. KDD '07: Материалы 13-й Международной конференции ACM SIGKDD по открытию знаний и интеллектуальному анализу данных. С. 163–172. CiteSeerX  10.1.1.69.6959. Дои:10.1145/1281192.1281213. ISBN  9781595936097.
10. И. Фаркаш; И. Дереньи; Х. Хеонг; и другие. (2002). «Сети в жизни: масштабные свойства и спектры собственных значений» (PDF). Physica. 314 (1–4): 25–34. arXiv:cond-mat / 0303106. Bibcode:2002PhyA..314 ... 25F. Дои:10.1016 / S0378-4371 (02) 01181-0. Архивировано из оригинал (PDF) на 2011-10-04. Получено 2011-04-21.