Наука о сетях

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

Предпосылки и история

С изучением сетей сталкивались в различных дисциплинах и использовали эту модель как средство анализа сложных и связанных данных. Наиболее ранняя статья из этой области — знаменитая статья о семи кёнигсбергских мостах, написанная Леонардом Эйлером в 1736 году. Математическое описание вершин и рёбер Эйлером стало основой теории графов — области математики, которая изучает свойства попарных связей в сетевой структуре. Теория графов развивалась и нашла применение в химии.

Денеш Кёниг, венгерский профессор математики, написал в 1936 году первую книгу по теории графов, озаглавленную «Теория конечных и бесконечных графов».

Социограмма Морено 1-го класса.

В 1930-х годах Якоб Леви Морено, психолог, работающий в традициях гештальтпсихологии, прибыл в США. Он разработал социограмму и представил её публике в апреле 1933 года на съезде студентов-медиков. Морено утверждал, что «до изобретения социометрии никто не знал, как выглядит в точности межличностная структура группы». Социограмма была представлением социальной структуры группы учеников начальной школы. Мальчишки дружили с мальчишками, а девочки — с другими девочками, лишь с одним исключением: один из мальчиков сказал, что ему нравится одна девочка, но чувство не было обоюдным. Сетевое представление социальной структуры произвело такое сильное впечатление, что о нем написали в газете The New York Times. Социограмме нашли множество применений, на ее основе сформулировали подходы к анализу социальных сетей.

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

В 1998 Дэвид Крэкхард и Кэтлин Карли представили идею метасети с моделью PCANS. Они предположили, что «все организации структурированы в трёх направлениях, Физические лица, Задачи и Ресурсы». Их статья ввела концепцию, что сети возникают по различным направлениям, а потому они взаимосвязаны. Эта область выросла в другую подобласть науки о сетях, которая называется динамическим анализом сети.

Позднее другие научные усилия были сфокусированы на математическом описании различных сетевых топологий. Дункан Ваттс совместил данные на сетях с математическим представлением, описывающим граф «Мир тесен». Альберт-Ласло Барабаши и Река Альберт разработали масштабно-инвариантую сеть, которая в общих чертах определяет сетевую топологию, которая содержит узловые вершины (хабы) со множеством соединений, количество которых растёт, сохраняя постоянное отношение числа соединений по отношению к числу всех узлов. Хотя многие сети, такие как интернет, оказываются сохраняющими это отношение, другие сети имеют длинные хвосты распределения узлов, которые лишь приближённо сохраняют масштабную инвариантность.

Инициативы Министерства обороны

Военные силы США первыми (в 1996 году) заинтересовались в сетецентрической войне как концепции военных действий, основанных на науке о сетях. Джон А. Парментола, руководитель научно-исследовательского центра и лабораторий армии США (англ. the U.S. Army Director for Research and Laboratory Management), провозгласил на армейском совете по науке и технике (англ. the Army’s Board on Science and Technology, BAST) 1 декабря 2003 года, что наука о сетях становится новой областью исследований в армии. BAST, отдел инженерно-технических и физических наук (англ. the Division on Engineering and Physical Sciences) Национального совета по исследованиям (англ. the National Research Council, NRC) государственной академии наук, наделена полномочиями организации обсуждений научных и технологических актуальных вопросов для армии и осуществления надзора за независимыми связанными с армией изучениями, проводимыми академией наук. BAST проводит изучение, может ли помочь определение рамок и финансирование новой области, науки о сетях, закрыть разрыв между потребностями осуществления сетецентрических операций и текущим примитивным состоянием фундаментальных знаний о сетях.

Как результат BAST выпустил в 2005 исследовательскую работу NRC, озаглавленную «Наука о сетях», в которой определяется новая область основных исследований в науке о сетях для армии. Основываясь на полученных в этой работе результатах и рекомендациях и на последующем отчёте NRC 2007 года, озаглавленном «Стратегия для армейских центров науки о сетях, технологии и экспериментов», основные армейские исследовательские ресурсы были перенаправлены на инициализацию новых главных исследовательских программ в науке о сетях. Чтобы построить новые теоретические основы для комплексных сетей, поддерживаются некоторые новые ключевые моменты исследования науки о сетях, адресованные армейским лабораториям:

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

С подачи в 2004 году Фредерика И. Моксли и при поддержке Дэвида С. Альбертса Министерства обороны помогло создать первый Центр Науки о сетях (англ. Network Science Center) совместно с военной академией (англ. the United States Military Academy, USMA) армии США. Под руководством Моксли и сотрудников USMA были созданы междисциплинарные студенческие курсы науки о сетях для курсантов Вест-Пойнт. Для лучшего внедрения основных положений науки о сетях среди будущих лидеров USMA основали также курс из пяти дисциплин.

В 2006 году армия США и Великобритания (UK) сформировали Интернациональный Технологический Альянс (англ. International Technology Alliance) по Сетевой и Информационной Науке (англ. the Network and Information Science), совместное партнёрство Армейской Исследовательской лаборатории, Министерства Обороны Великобритании и консорциум индустрии и университетов в США и Великобритании. Целью альянса является осуществление исследований в поддержке сетецентрических операций в интересах обеих наций.

В 2009 году армия США сформировала Совместный Технологический Альянс Сетевой Науки, альянс по совместным исследованиям Армейской Исследовательской лаборатории, CERDEC и консорциума 30 промышленных исследовательских центров США. Целью альянса является разработка глубокого понимания общих черт переплетающихся социальных/когнитивных, информационных и коммуникационных сетей, а как результат, улучшение нашей возможности анализировать, предсказывать, разрабатывать и влиять на сложные переплетающиеся системы сетей многих видов.

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

Свойства сетей

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

Размер

Под размером сети может пониматься число узлов $N$ или, реже, число рёбер $E$, которое (для связных графов без кратных рёбер) может меняться от $N-1$ (дерево) до $E_{\max }$ (полный граф). В случае простого графа (сеть, в которой существует максимум одно (неориентированное) ребро между любой парой вершин и в которой ни одна из вершин не соединена сама с собой), мы имеем $E_{\max }={\tbinom {N}{2}}=N(N-1)/2$. Для ориентированных графов (без петель) $E_{\max }=N(N-1)$. Для ориентированных графов с разрешёнными петлями $E_{\max }=N^{2}$. Для случая графа, в котором разрешены кратные рёбра между парой вершин $E_{\max }=\infty$.

Плотность

Плотность $D$ сети с $N$ узлами определяется как отношение числа рёбер $E$ к числу возможных рёбер в сети и задаётся (в случае простых графов) биномиальным коэффициентом ${\tbinom {N}{2}}$, что даёт

$D={\frac {E-(N-1)}{Emax-(N-1)}}={\frac {2(E-N+1)}{N(N-3)+2}}$

Другое возможное уравнение — $D={\frac {T-2N+2}{N(N-3)+2}},$ где связи $T$ неориентированны. Это даёт лучшее понимание плотности сети, поскольку неориентированные связи могут быть измерены.

Планарная сетевая плотность

Плотность сети $D$, в которой нет пересечений рёбер, определяется как отношение числа рёбер $E$ к числу максимальному числу рёбер в сети с $N$ узлами без пересекающихся рёбер $(E_{\max }=3N-6)$, что даёт $D={\frac {E-N+1}{2N-5}}.$

Средняя степень узла

Степень $k$ узла — это число рёбер, связанных с ним. Тесно связана с плотностью сети средняя плотность, $\langle k\rangle ={\tfrac {2E}{N}}$ (или, в случае ориентированных графов, $\langle k\rangle ={\tfrac {E}{N}}$. Множитель 2 в предыдущем равенстве возникает из того, что каждое ребро в неориентированном графе делает вклад в степени двух различных вершин). В модели случайного графа Эрдёша — Реньи ($G(N,p)$) мы можем вычислить ожидаемое значение $\langle k\rangle$ (равно ожидаемому значению $k$ произвольной вершины) — случайная вершина имеет $N-1$ возможных других вершин с вероятностью соединения $p$. Тогда $\mathbb {E} [\langle k\rangle ]=\mathbb {E} [k]=p(N-1)$.

Средняя длина кратчайшего пути (или характеристика длины пути)

Средняя длина кратчайшего пути вычисляется путём нахождения кратчайшего пути между всеми парами узлов и вычисления средней длины по всем путям (длиной является число рёбер, содержащихся в пути, то есть расстояние $d_{u,v}$ между двумя вершинами $u,v$ в графе). Это показывает нам, в среднем, число шагов, которые нужно сделать от одного узла сети до другого. Поведение математического ожидания средней длины кратчайшего пути как функции числа вершин $N$ модели случайной сети определяет, отражает ли модель эффект малого мира. Если она ведёт себя как $O(\ln N)$, модель генерирует модель сетей малого мира. При росте большем логарифмического модель не даёт «малый мир». Специальный случай роста $O(\ln \ln N)$ известен как эффект ультрамалого мира.

Диаметр сети

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

Коэффициент кластеризации

Коэффициент кластеризации является мерой свойства «все мои друзья знают друг друга». Это иногда описывается как «друзья моего друга — мои друзья». Более точно, коэффициент кластеризации узла равен отношению существующих связей, соединяющих соседей узла друг с другом, к максимальному числу таких связей. Коэффициент кластеризации всей сети равен среднему коэффициентов кластеризации всех узлов. Высокий коэффициент кластеризации для сети является другим признаком тесного мира.

Коэффициент кластеризации $i$-ого узла равен

$C_{i}={2e_{i} \over k_{i}{(k_{i}-1)}}\,,$

где $k_{i}$ равно числу соседей $i$-го узла, а $e_{i}$ равно числу связей между этими соседями. Максимальное число возможных связей между соседями равно, тогда,

${\binom {k}{2}}={{k(k-1)} \over 2}\,.$

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

Связанность

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

• Клика/Полный Граф — полностью связанная сеть, в которой каждый узел связан с каждым другим узлом. Эти сети симметричны, поскольку все узлы имеют входящие соединения от всех других узлов и исходящие соединения во все остальные узлы.
• Гигантская компонента — одна связная компонента содержит большинство узлов сети.
• Слабо связанная компонента — набор узлов, в котором существует путь из любого узла в любой другой без учёта направления рёбер.
• Сильно связанная компонента — набор узлов, в котором существует ориентированный путь из любого узла в любой другой узел.

Центральность узла

Основная статья: Центральность

Показатели центральности порождают ранжирование, которое пытается выявить наиболее важные узлы в модели сети. Различные показатели центральности кодируют различные контексты слова «важность». Степень посредничества, например, считает узел сильно важным, если он образует мосты между многими другими узлами. Степень влиятельности, в качестве контраста, считает узел сильно важным, если много других сильно важных узлов связаны с ним. Сотни таких мир было предложено в литературе.

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

Концепция центральности в контексте статических сетей были расширены на основе эмпирических и теоретических исследований до динамической центральности в контексте зависимых от времени и скоротечных сетей.

Влияние вершин

Основная статья: Метрика влияния вершин

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

Сетевые модели

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

Модель случайного графа Эрдёша — Реньи

Модель Эрдёша — Реньи, сгенерированная с $N=$ узлами. Для каждого ребра в полном графе, образованном всеми N узлами, генерится случайное число и сравнивается с заданным значением вероятности. Если случайное число меньше p, образуется ребро.

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

Для генерации модели Эрдёша — Реньи $G(n,p)$ должны быть заданы два параметра — общее число узлов n и вероятность p, с которой произвольная пара узлов имеет связывающее ребро.

Поскольку модель генерируется без пристрастия к определённым узлам, распределение узлов по числу связей биномиально — для случайно выбранного узла $v$,

$P(\deg(v)=k)={n-1 \choose k}p^{k}(1-p)^{n-1-k}.$

В этой модели коэффициент кластеризации равен 0 почти наверняка. Поведение $G(n,p)$ можно разбить на три области.

Субкритическая $np<1$: Все компоненты простые и очень маленькие, наибольшая компонента имеет размер $|C_{1}|=O(\log n)$;

Критическая $np=1$: $|C_{1}|=O(n^{\frac {2}{3}})$;

Суперкритическая $np>1$:$|C_{1}|\approx yn$, где $y=y(np)$ является положительным решением уравнения $e^{-pny}=1-y$.

Наибольшая связная компонента имеет высокую сложность. Все другие компоненты просты и малы $|C_{2}|=O(\log n)$.

Конфигурационная модель

Для конфигурационной модели выбирается последовательность степеней вершин или распределение степеней вершин (которое затем используется для генерации последовательности вершин) в качестве входа и создаётся случайно связанный граф с сохранением всех степеней вершин последовательности. Это означает, что для данного выбора последовательности степеней граф выбирается однородно из множества всех графов, которые имеют такую последовательность степеней вершин. Степень $k$ случайно выбранной вершины является независимой и одинаково распределённой случайной переменной с целыми значениями. При ${\textstyle \mathbb {E} [k^{2}]-2\mathbb {E} [k]>0}$ конфигурационный граф содержит гигантскую связную компоненту, которая имеет неограниченный размер. Остальные компоненты имеют конечные размеры, которые могут быть выражены количественно с помощью распределения размера. Вероятность $w(n)$, что случайно отобранный узел связан с компонентой размера $n$ задаётся степенью свёртки распределения степеней

$$w(n)={\begin{cases}{\frac {\mathbb {E} [k]}{n-1}}u_{1}^{*n}(n-2),&n>1,\\u(0)&n=1,\end{cases}}$$

где $u(k)$ означает распределение узлов по числу связей и $u_{1}(k)={\frac {(k+1)u(k+1)}{\mathbb {E} [k]}}$. Гигантская компонента может быть разрушена путём случайного удаления критичной доли $p_{c}$ всех вершин. Этот процесс называется перколяцией (просачиванием) на случайных сетях. Если второй момент степени распределения конечен, то есть ${\textstyle \mathbb {E} [k^{2}]<\infty }$, эта критическая доля рёбер задаётся равенством

$p_{c}=1-{\frac {\mathbb {E} [k]}{\mathbb {E} [k^{2}]-\mathbb {E} [k]}}$

и среднее расстояние между вершинами $l$ в гигантской компоненте логарифмически пропорционально полному размеру сети $l=O(\log N)$.

В модели ориентированной конфигурации степень узла задаётся двумя числами, полустепенью входа $k_{\text{in}}$ и полустепенью исхода $k_{\text{out}}$, и, соответственно, распределения степеней вершин будут двувариантными. Ожидаемое число входящих рёбер и исходящих рёбер совпадает, так что ${\textstyle \mathbb {E} [k_{\text{in}}]=\mathbb {E} [k_{\text{out}}]}$. Ориентированная конфигурационная модель содержит гигантскую компоненту тогда и только тогда, когда

$$2\mathbb {E} [k_{\text{in}}]\mathbb {E} [k_{\text{in}}k_{\text{out}}]-\mathbb {E} [k_{\text{in}}]\mathbb {E} [k_{\text{out}}^{2}]-\mathbb {E} [k_{\text{in}}]\mathbb {E} [k_{\text{in}}^{2}]+\mathbb {E} [k_{\text{in}}^{2}]\mathbb {E} [k_{\text{out}}^{2}]-\mathbb {E} [k_{\text{in}}k_{\text{out}}]^{2}>0.$$

Заметим, что ${\textstyle \mathbb {E} [k_{\text{in}}]}$ и ${\textstyle \mathbb {E} [k_{\text{out}}]}$ равны, а потому взаимозаменяемы в последнем неравенстве. Вероятность, что случайно выбранная вершина принадлежит компоненте размера $n$, задаётся формулой

$$h_{\text{in}}(n)={\frac {\mathbb {E} [k_{in}]}{n-1}}{\tilde {u}}_{\text{in}}^{*n}(n-2),\;n>1,\;{\tilde {u}}_{\text{in}}={\frac {k_{\text{in}}+1}{\mathbb {E} [k_{\text{in}}]}}\sum \limits _{k_{\text{out}}\geq 0}u(k_{\text{in}}+1,k_{\text{out}}),$$

для входящих компонент, и

$h_{\text{out}}(n)={\frac {\mathbb {E} [k_{\text{out}}]}{n-1}}{\tilde {u}}_{\text{out}}^{*n}(n-2),\;n>1,\;{\tilde {u}}_{\text{out}}={\frac {k_{\text{out}}+1}{\mathbb {E} [k_{\text{out}}]}}\sum \limits _{k_{\text{in}}\geq 0}u(k_{\text{in}},k_{\text{out}}+1),$

для исходящих компонент.

Модель тесного мира Уаттса — Строгаца

Модель Уаттса — Строгаца использует концепцию перемонтажа для получения структуры модели. Генератор модели итерирует через все рёбра в исходной структуре решётки. Ребро может изменить связанные с ним вершины с заданной вероятностью перемонтажа. В данном примере, $\langle k\rangle =4$.

Модель Уаттса — Строгаца является моделью генерации случайного графа, которая даёт графы со свойствами «мир тесен».

Для генерации модели Уаттса — Строгаца используется начальная структура решётки. Каждый узел в сети первоначально связан с $\langle k\rangle$ ближайшими соседями. Другой параметр задаёт вероятность перемонтажа. Каждое ребро имеет вероятность $p$, что оно будет перемонтировано в граф как случайное ребро. Ожидаемое число перемонтированных соединений в модели равно $pE=pN\langle k\rangle /2$.

Так как модель Уаттса — Строгаца начинается как неслучайная решёточная структура, она имеет очень высокий коэффициент кластеризации вместе с высокой средней длиной пути. Каждый перемонтаж с большой вероятностью создаёт сокращённый путь между сильно связанными кластерами. При увеличении вероятности перемонтажа коэффициент кластеризации уменьшается медленнее, чем средняя длина пути. В результате это позволяет средней длине пути сети уменьшаться существенно при слабом уменьшении коэффициента кластеризации. Высокие значения p приводит к большему числу перемонтажа рёбер, что в результате делает модель Уаттса — Строгаца случайной сетью.

Модель Барабаши — Альберт предпочтительных присоединений

Модель Барабаши — Альберт является моделью случайной сети, используемой для демонстрации предпочтительных присоединений или эффекта «богатый становится богаче». В этой модели ребро наиболее вероятно соединяется с узлами с наибольшими степенями. Сеть начинается с сети с m₀ узлами, где $m_{0}\geqslant 2$, а степень каждого узла в начальной сети должна быть по меньшей мере 1, в противном случае узел навсегда останется отсоединённым от остальной части сети.

В модели Барабаши — Альберта новые узлы добавляются в сеть по одному. Каждый новый узел соединяется с $m$ существующими узлами с вероятностью, которая пропорциональна числу уже существующих узлов. Формально, вероятность $p_{i}$, что новый узел связен с узлом i, равен

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

где k_i является степенью узла i. Наиболее связанные узлы («хабы») стремятся быстро аккумулировать даже больше соединений, в то время как узлы с меньшим числом соединений вряд ли будут выбраны в качестве нового соединения. Новые узлы имеют «преимущество» присоединиться к уже наиболее сильно связанным узлам.

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

Распределение узлов по числу связей, получаемое из BA модели, масштабно инвариантно, в частности, это степенной закон вида

$P(k)\sim k^{-3}\,$

Хабы показывают высокую степень посредничества, позволяя существованию коротких путей между узлами. В результате модель BA стремится иметь очень короткую среднюю длину путей. Коэффициент кластеризации этой модели также стремится к 0. В то время как диаметр D многих моделей, включая модель случайного графа Эрдёша —Реньи и некоторых сетей «тесного мира», пропорционален log N, модель BA показывает D~loglogN (ультратесный мир).

Модель присоединения с помощью посредника

В модели присоединения с помощью посредника (англ. mediation-driven attachment, MDA) новый узел приходит с $m$ рёбрами, для чего выбирается случайным образом существующий связанный узел и новый узел соединяется не только с этим случайно выбранным узлом, но и также с $m$ его соседями, выбранными также случайно. Вероятность $\Pi (i)$, что соседний узел $i$ существующего узла выбирается, равна

$\Pi (i)={\frac {k_{i}}{N}}{\frac {\sum _{j=1}^{k_{i}}{\frac {1}{k_{j}}}}{k_{i}}}.$

Множитель ${\frac {\sum _{j=1}^{k_{i}}{\frac {1}{k_{j}}}}{k_{i}}}$ равен обратной величине среднего гармонического (ОСГ) степеней $k_{i}$ соседей узла $i$. Обширное численное исследование позволяет предположить, что при $m>14$ среднее значение ОСГ при больших $N$ стремится к константе, это означает, что $\Pi (i)\propto k_{i}$. Из этого следует, что чем больше связей (степень) узел имеет, тем выше шанс получить более связей, поскольку они могут быть получены большим числом способов через посредников, что, по существу, воплощает интуитивную идею «богатые становятся богаче» (или правило предпочтительного присоединения модели Барабаши — Альберт). Поэтому сети MDA, как можно понять, подчиняются правилу PA, но в неявном виде.

Однако при $m=1$ получаем механизм «победитель забирает всё», поскольку почти $99\%$ общего числа узлов имеют степень единица, а один узел становится супербогатым. По мере увеличения значения $m$ диспропорция между сверхбогатыми и бедными сокращается и при $m>14$ мы наблюдаем переход механизма от «богатый становится супербогатым» к механизму «богатый становится богаче».

Модель соответствия

Другую модель, в которой ключевым ингредиентом является природа вершины, предложил Калдарелли с соавторами. Здесь связь создаётся между двумя вершинами $i,j$ с вероятностью, задаваемой функцией связи $f(\eta _{i},\eta _{j})$ модели соответствия вовлечённых вершин. Степень вершины i задаётся формулой

$k(\eta _{i})=N\int _{0}^{\infty }f(\eta _{i},\eta _{j})\rho (\eta _{j})\,d\eta _{j}$

Если $k(\eta _{i})$ является обратимой возрастающей функцией от $\eta _{i}$, то распределение вероятности $P(k)$ задаётся формулой

$P(k)=\rho (\eta (k))\cdot \eta '(k)$

Как результат, если соответствие $\eta$ распределено по степенному закону, то так же распределены и степени узлов.

Менее очевидно при быстро убывающем распределении вероятностей $\rho (\eta )=e^{-\eta }$ вместе со связывающей функцией вида

$f(\eta _{i},\eta _{j})=\Theta (\eta _{i}+\eta _{j}-Z)$

с константой $Z$ и функцией Хевисайда $\Theta$, что мы получаем масштабно-инвариантные сети.

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

${\frac {\delta \eta _{i}\eta _{j}}{1+\delta \eta _{i}\eta _{j}}}.$

Анализ сети

Анализ социальных сетей

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

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

Динамический анализ сети

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

Техники динамической сети особенно удобны для оценки трендов в сети со временем, выделения появляющихся лидеров и исследование коэволюции людей и идей.

Анализ биологических сетей

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

Анализ связей

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

Устойчивость сети

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

Анализ пандемии

SIR-модель в эпидемиологии является одной из наиболее известных алгоритмов предсказания распространения глобальных пандемий в инфицированной популяции.

От состояния восприимчивости к заражению

$S=\beta \left({\frac {1}{N}}\right)$

Формула выше описывает «силу» инфекции для каждой восприимчивой единицы в заражённой популяции, где $\beta$ эквивалентно скорости распространения болезни.

Для отслеживания изменений этой восприимчивой единицы в заражённой популяции:

$\Delta S=\beta \times S{1 \over N}\,\Delta t$

От заражения к выздоровлению

$\Delta I=\mu I\,\Delta t$

Со временем число таких заражений зависит от заданной скорости выздоровления, представленной числом $\mu$, но за средний период заражения ${1 \over \tau }$, от числа заражённых лиц $I$ и от числа изменений за время $\Delta t$.

Контагиозный период

Поражена ли популяция пандемией, с позиции SIR-модели, зависит от значения $R_{0}$ или «среднего числа заражённых людей от других людей».

$R_{0}=\beta \tau ={\beta \over \mu }$

Анализ Web-ссылок

Некоторые алгоритмы ранжирования поисковых систем используют основанные на ссылках меры центральности, включая (в порядке появления) алгоритмы Hyper Search Марчиори, PageRank компании Google, Алгоритм HITS Клейнберга, CheiRank и TrustRank. Анализ связей может осуществляться в теории информации, чтобы понять и выделить информацию из набора веб-страниц. Например, это может быть анализ связей между сайтами или блогами политиков.

PageRank

PageRank работает путём случайного выбора «узла» или интернет-сайта и «случайного перехода» с некоторой вероятностью на другие узлы. Случайные переходы на эти другие узлы позволяют оценке PageRank полностью обойти сеть, поскольку некоторые страницы находятся на периферии сети и не могут быть легко оценены.

Каждый узел $x_{i}$ имеет PageRank, определённый как сумма для страниц $j$ обратных величин числа страниц, связанных с узлом $i$ исходящими дугами, или «полустепень исхода» узла $j$ на «важность» или PageRank узла $j$.

$x_{i}=\sum _{j\rightarrow i}{1 \over N_{j}}x_{j}^{(k)}$

Случайные переходы

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

Улучшение вышеприведённой формулы для определения PageRank включает компоненты этих случайных переходов. Без случайных переходов некоторые страницы получат PageRank, равный 0, что не есть хорошо.

Первой компонентой является $\alpha$, или вероятность, что случайный переход случится. Противоположным является «коэффициент затухания», или $1-\alpha$.

$R{(p)}={\alpha \over N}+(1-\alpha )\sum _{j\rightarrow i}{1 \over N_{j}}x_{j}^{(k)}$

Другой угол зрения на это:

$R(A)=\sum {R_{B} \over B_{\text{(outlinks)}}}+\cdots +{R_{n} \over n_{\text{(outlinks)}}}$

Меры центральности

Информация об относительной важности узлов и рёбер в графах может быть получена через меры центральности, широко используемые в дисциплинах, таких как социология. Меры центральности необходимы, когда сетевой анализ не имеет ответа на вопросы, такие как: «Какие узлы в сети следует задействовать, чтобы обеспечить, чтобы сообщение или информация распространялась на все или большинстве узлов сети?» или, наоборот, «На какие узлы следует воздействовать, чтобы остановить распространение болезни?». Формально определёнными мерами центральности являются степень связности, степень близости, степень посредничества, степень влиятельности и центральность по Кацу. Цель анализа сети обычно предопределяет используемый тип мер(ы) центральности.

• Степень связности узла сети — это число связей (вершин), инцидентных узлу.
• Степень близости определяет, насколько «близок» узел сети другим узлам путём суммирования кратчайших расстояний (геодезических путей) между этим узлом и остальными узлами сети.
• Степень посредничества определяет относительную важность узла путём измерения величины потока, протекающего через этот узел к другим узлам в сети. Это делается путём измерения доли путей, соединяющих все пары узлов и содержащих рассматриваемый узел. Групповая степень посредничества измеряет величину потока, протекающего через группу узлов.
• Степень влиятельности является более сложной версией степени центральности, когда центральность узла не только зависит от числа связей, инцидентных узлу, но и от качества этих связей. Этот множитель качества определяется собственными векторами матрицы смежности сети.
• Центральность по Кацу узла измеряется путём суммирования геодезических (то есть кратчайших) путей между этим узлом и всеми (достижимыми) узлами сети. Эти пути взвешены, пути, соединяющие узел с его непосредственными соседями, имеют более тяжёлые веса, чем узлы, которые связаны с более удалёнными узлами.

Распространение контента в сетях

Контент в сложной сети может распространяться двумя главными способами: сохраняющееся распространение и несохраняющееся распространение. При сохраняющемся распространении общее количество контента, входящего в сложные сети, остаётся постоянной при проходе через сеть. Модель сохраняющегося распространения может быть лучше всего представлена кувшином, содержащим определённое количество воды, которая выливается в ряд стоков, соединённых трубами. Здесь кувшин представляет источник, а вода представляет распространяемый контент. Ёмкости и соединяющие трубы представляют узлы и связи узлов соответственно. При переходе воды от одной ёмкости в другую вода исчезает из ёмкости-источника. В несохраняющемся распространении количество контента меняется по мере прохождения через сложные сети. Модель несохраняющегося распространения лучше всего можно представить непрерывной струёй из водопроводного крана, растекающейся по стокам, соединённых трубами. Здесь количество воды из начального источника не ограничено. Также любой сток, до которого вода дошла, продолжает получать воду, даже если она проходит к другим стокам. Несохраняющиеся модели наиболее пригодны для объяснения передачи большинства инфекций.

SIR-модель

В 1927 году В. О. Кермак и А. Г. Маккендрик создали модель, в которой они рассматривают фиксированную популяцию всего с тремя состояниями — восприимчив, $S(t)$, заражён, $I(t)$, и вылечен, $R(t)$. Категории, используемые в этой модели, состоят из трёх классов:

• $S(t)$ используется для представления числа лиц, ещё не заражённых болезнью в момент времени t (восприимчивых к болезни)
• $I(t)$ означает число заражённых лиц, которые способны передавать болезнь лицам, находящимися в категории «восприимчивые»
• $R(t)$ является категорией лиц, перенёсших болезнь и вылечившихся. Лица этой категории, не способные заразиться повторно или передать инфекцию другим лицам.

Течение этой модели можно рассматривать следующим образом:

${\mathcal {S}}\rightarrow {\mathcal {I}}\rightarrow {\mathcal {R}}$

Используя фиксированную популяцию, $N=S(t)+I(t)+R(t)$, Кермак и Маккендрик вывели следующие уравнения:

${\begin{aligned}{\frac {dS}{dt}}&=-\beta SI\\[8pt]{\frac {dI}{dt}}&=\beta SI-\gamma I\\[8pt]{\frac {dR}{dt}}&=\gamma I\end{aligned}}$

Для формулирования этих уравнений были сделаны некоторые предположения. Для первого уравнения отдельный представитель популяции должен рассматриваться как имеющий такую же вероятность заражения, как и любой другой представитель, со скоростью $\beta$, которая рассматривается как скорость распространения инфекции или болезни. Поэтому, когда заражённый представитель вступает в контакт и способен к передаче болезни $\beta N$ другим представителям за единицу времени и доля контактов заражённых представителей с восприимчивыми равна $S/N$. Число новых инфекций за единицу времени на одного заражённого тогда равно $\beta N(S/N)$, что задаёт скорость новых заражений s (или тех, кто покидает категорию восприимчивых) как $\beta N(S/N)I=\beta SI$. Для второго и третьего уравнений считается, что популяция покидает класс восприимчивых с той же скоростью, что и входит в класс заражённых. Однако число равно доле ($\gamma$ представляет среднюю скорость выздоровления, а $1/\gamma$ представляет среднее время болезни) заражённых, покидающих этот класс в единицу времени и переходящих в класс выздоровевших. Об этих происходящих одновременно процессах говорят как о законе действующих масс, широко распространённая идея, что скорость контактов между двумя группами в популяции пропорциональна размеру каждой из двух рассматриваемых групп. Наконец, предполагается, что скорость заражения и выздоровления много больше, чем рождение и умирание, а потому эти факторы в модели не учитываются.

Больше об этой модели можно прочесть на странице Модель эпидемии.

Метод основного уравнения

Основное уравнение может выразить поведение неориентированной растущей сети, в которой на каждом шаге добавляется новый узел, соединённый со старым узлом (случайно выбранным и без преференций). Начальную сеть составляют два узла и две связи между ними в момент $t=2$. Такая конфигурация необходима только для упрощения дальнейших вычислений, так что в момент времени $t=n$ сеть имеет $n$ узлов и $n$ связей.

Основное кинетическое уравнение для этой сети

$p(k,s,t+1)={\frac {1}{t}}p(k-1,s,t)+\left(1-{\frac {1}{t}}\right)p(k,s,t),$

где $p(k,s,t)$ равно вероятности иметь узел $s$ со степенью $k$ в момент времени $t+1$, а $s$ является временем, когда узел был добавлен в сеть. Заметим, что имеется только два способа для старого узла $s$ иметь $k$ соединений в момент $t+1$:

• Узел $s$ имеет степень $k-1$ в момент $t$ и будет связан с новым узлом с вероятностью $1/t$
• Уже имеет степень $k$ в момент $t$ и не будет соединён с новым узлом.

После упрощения этой модели распределение узлов по числу связей будет равно $P(k)=2^{-k}$.

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

$p_{r}(k,s,t)=r_{t}{\frac {1}{t}}p_{r}(k-1,s,t)+\left(1-{\frac {1}{t}}\right)p_{r}(k,s,t),$

где $r_{t}$ определяет заражение ($r_{t}=1$) или отсутствие заражения ($r_{t}=0$). После решения этого основного уравнения получаем следующее решение: ${\tilde {P}}_{r}(k)=\left({\frac {r}{2}}\right)^{k}.$.

Взаимозависимые сети

Основная статья: Взаимозависимые сети

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

Многослойные сети

Основная статья: Многомерная сеть

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

Оптимизация сети

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

Литература для дальнейшего чтения

• "Connected: The Power of Six Degrees," https://web.archive.org/web/20111006191031/http://ivl.slis.indiana.edu/km/movies/2008-talas-connected.mov
• Cohen R., Erez K., Havlin S. Resilience of the Internet to random breakdown // Phys. Rev. Lett.. — 2000. — Т. 85, вып. 21. — С. 4626–4628. — doi:10.1103/physrevlett.85.4626. — . — arXiv:cond-mat/0007048. — PMID 11082612.
• Cun-Lai Pu, Wen, Jiang Pei, Andrew Michaelson. Robustness analysis of network controllability // Physica A. — 2012. — Т. 391, вып. 18. — С. 4420–4425. — doi:10.1016/j.physa.2012.04.019. — . Архивировано 13 октября 2016 года.
• "Leader Profile: The Burgeoning Field of Network Science, The Military Engineer recently had the opportunity to speak with Frederick I. Moxley, Ph.D," https://web.archive.org/web/20190215025457/http://themilitaryengineer.com/index.php/item/160-leader-profile-the-burgeoning-field-of-network-science
• Dorogovtsev S.N., Mendes J.F.F. Evolution of Networks: From biological networks to the Internet and WWW. — Oxford University Press, 2003. — ISBN 0-19-851590-1.
• Albert-laszlo Barabasi, Jennifer Frangos. Linked: The New Science of Networks. — Perseus Publishing, Cambridge, 2002. — ISBN 0738206679.
• Guido Caldarelli. Scale-Free Networks: Complex Webs in Nature and Technology. — Oxford: Oxford University Press, 2007. — (Oxford Finance Series). — ISBN 9780199211517.
• Mark Newman, Albert-László Barabási, Duncan J. Watts. The Structure and Dynamics of Networks. — The Princeton Press, 2006. — ISBN 0-691-11357-2.
• Alain Barrat, Marc Barthelemy, Alessandro Vespignani. Dynamical processes on complex networks. — Cambridge University Press, 2008. — ISBN 978-0-521-87950-7.
• Ted G. Lewis. Network Science: Theory and Applications. — Wiley, 2009. — ISBN 0-470-33188-7.
• Mark Buchanan. Nexus: Small Worlds and the Groundbreaking Theory of Networks. — W. W. Norton & Company, 2003. — ISBN 0-393-32442-7.
• Duncan J. Watts. Six Degrees: The Science of a Connected Age. — W. W. Norton & Company, 2004. — ISBN 0-393-32542-3.
• Kitsak M., Gallos L. K., Havlin S., Liljeros F., Muchnik L., Stanley H. E., Makse H.A. Influential Spreaders in Networks // Nature Physics. — 2010. — Т. 6, вып. 11. — С. 888–893. — doi:10.1038/nphys1746. — . — arXiv:1001.5285.