Сетевая наука

Академическая сфера

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

Предыстория и история

Изучение сетей возникло в различных дисциплинах как средство анализа сложных реляционных данных. Самая ранняя известная статья в этой области — знаменитые «Семь мостов Кенигсберга» , написанные Леонардом Эйлером в 1736 году. Математическое описание Эйлером вершин и ребер легло в основу теории графов — раздела математики, изучающего свойства парных отношений в сетевой структуре. . Область теории графов продолжала развиваться и находила приложения в химии (Сильвестр, 1878).

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

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

В 1930-е годы в США приехал Джейкоб Морено , психолог гештальт -традиции. Он разработал социограмму и представил ее публике в апреле 1933 года на съезде ученых-медиков. Морено утверждал, что «до появления социометрии никто не знал, как «точно» выглядит межличностная структура группы» (Moreno, 1953). Социограмма представляла собой представление социальной структуры группы учащихся начальной школы. Мальчики дружили с мальчиками, а девочки дружили с девочками, за исключением одного мальчика, который сказал, что ему нравится одна девушка. Это чувство не было взаимным. Это сетевое представление социальной структуры оказалось настолько интригующим, что оно было напечатано в «Нью-Йорк Таймс» (3 апреля 1933 г., стр. 17). Социограмма нашла множество применений и переросла в область анализа социальных сетей .

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

В 1998 году Дэвид Кракхардт и Кэтлин Карли представили идею метасети с помощью модели PCANS. Они предполагают, что «все организации структурированы по этим трем областям: люди, задачи и ресурсы». В их статье представлена ​​концепция, согласно которой сети существуют в нескольких областях и взаимосвязаны. Эта область переросла в другую дисциплину сетевой науки, называемую динамическим сетевым анализом .

Совсем недавно другие усилия в области сетевых наук были сосредоточены на математическом описании различных сетевых топологий. Дункан Уоттс и Стивен Строгац согласовали эмпирические данные о сетях с математическим представлением, описав сеть маленького мира . Альберт-Ласло Барабаши и Река Альберт обнаружили безмасштабные сети — свойство, отражающее тот факт, что в реальных сетевых узлах сосуществуют множество вершин малой степени, и предложили динамическую модель, объясняющую происхождение этого безмасштабного состояния.

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

Американские военные впервые заинтересовались сетецентрической войной как оперативной концепцией, основанной на сетевой науке, в 1996 году. Джон А. Парментола, директор по исследованиям и управлению лабораториями армии США, предложил Совету армии по науке и технологиям (BAST) 1 декабря 2003 г. сетевые науки стали новой областью исследований в армии. BAST, отдел инженерных и физических наук Национального исследовательского совета (NRC) национальных академий, служит органом, созывающим обсуждение вопросов науки и техники, имеющих важное значение для армии, и курирует независимые исследования, связанные с армией, проводимые Национальные академии. BAST провел исследование, чтобы выяснить, может ли определение и финансирование новой области фундаментальных исследований, сетевых наук, помочь сократить разрыв между тем, что необходимо для реализации сетецентрических операций, и нынешним примитивным состоянием фундаментальных знаний о сетях.

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

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

По инициативе Фредерика И. Моксли в 2004 году при поддержке, которую он запросил у Дэвида С. Альбертса, Министерство обороны помогло создать первый Центр сетевых наук совместно с армией США в Военной академии США (USMA). Под руководством доктора Моксли и преподавателей USMA первые междисциплинарные курсы бакалавриата по сетевым наукам преподавались курсантам Вест-Пойнта. ^{[3] [4] [5]} Чтобы лучше прививать принципы сетевой науки своим будущим лидерам, USMA также учредила программу бакалавриата из пяти курсов по сетевым наукам. ^[6]

В 2006 году армия США и Соединенное Королевство (Великобритания) сформировали Международный технологический альянс сетевых и информационных наук , совместное партнерство между Армейской исследовательской лабораторией, Министерством обороны Великобритании и консорциумом промышленных предприятий и университетов США и Великобритании. Целью альянса является проведение фундаментальных исследований в поддержку сетецентрических операций, отвечающих потребностям обеих стран.

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

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

Классификация сетей

Детерминированная сеть

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

Вероятностная сеть

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

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

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

Размер

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

Плотность

Плотность сети определяется как нормализованное отношение числа ребер от 0 до 1 к числу возможных ребер в сети с узлами. Плотность сети — это мера процента «необязательных» ребер, которые существуют в сети, и ее можно рассчитать как где и — минимальное и максимальное количество ребер в связанной сети с узлами соответственно. В случае простых графиков задается биномиальным коэффициентом и , что дает плотность . Другое возможное уравнение состоит в том, что связи однонаправлены (Вассерман и Фауст, 1994). ^[8] Это дает лучшее представление о плотности сети, поскольку можно измерить однонаправленные отношения. ${\displaystyle D}$ ${\displaystyle E}$ ${\displaystyle N}$ ${\displaystyle D={\frac {E-E_{\mathrm {min} }}{E_{\mathrm {max} }-E_{\mathrm {min} }}}}$ ${\displaystyle E_{\mathrm {min} }}$ ${\displaystyle E_{\mathrm {max} }}$ ${\displaystyle N}$ ${\displaystyle E_{\mathrm {max} }}$ ${\displaystyle {\tbinom {N}{2}}}$ ${\displaystyle E_{\mathrm {min} }=N-1}$ ${\displaystyle D={\frac {E-(N-1)}{E_{\mathrm {max} }-(N-1)}}={\frac {2(E-N+1)}{N(N-3)+2}}}$ ${\displaystyle D={\frac {T-2N+2}{N(N-3)+2}},}$ ${\displaystyle T}$

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

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

Средняя степень

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

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

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

Диаметр сети

В качестве еще одного средства измерения сетевых графов мы можем определить диаметр сети как самый длинный из всех рассчитанных кратчайших путей в сети. Это кратчайшее расстояние между двумя наиболее удаленными узлами сети. Другими словами, как только вычислена кратчайшая длина пути от каждого узла ко всем остальным узлам, диаметр становится наибольшей из всех рассчитанных длин пути. Диаметр отражает линейный размер сети. Если узел ABCD соединен, идя от A->D, это будет диаметр 3 (3 шага, 3 канала). ^{[ нужна цитата ]}

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

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

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

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

где – количество соседей '-го узла, – количество связей между этими соседями. Тогда максимально возможное число соединений между соседями равно ${\displaystyle k_{i}}$ ${\displaystyle i}$ ${\displaystyle e_{i}}$

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

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

Связность

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

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

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

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

Индексы центральности точны только для определения наиболее важных узлов. Эти меры редко, если вообще когда-либо, имеют значение для остальных узлов сети. ^{[9] [10]} Кроме того, их показания точны только в предполагаемом контексте важности и имеют тенденцию «понимать неправильно» в других контекстах. ^[11] Например, представьте себе два отдельных сообщества, единственная связь которых — это грань между самым младшим членом каждого сообщества. Поскольку любой переход из одного сообщества в другое должен осуществляться через эту связь, два младших члена будут иметь высокую центральность по отношению к посредничеству. Но, поскольку они младшие, (предположительно) у них мало связей с «важными» узлами в их сообществе, а это означает, что их центральность по собственным значениям будет довольно низкой.

Влияние узла

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

Структура сообщества

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

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

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

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

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

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

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

Для создания модели Эрдеша – Реньи необходимо указать два параметра: общее количество узлов n и вероятность p того, что случайная пара узлов имеет ребро. ${\displaystyle G(n,p)}$

Поскольку модель генерируется без смещения к конкретным узлам, распределение степеней является биномиальным: для случайно выбранной вершины ${\displaystyle v}$

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

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

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

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

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

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

Модель конфигурации

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

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

перколяцией в случайных сетях^[17]среднее расстояние между вершинами^[15] ${\displaystyle u(k)}$ ${\displaystyle u_{1}(k)={\frac {(k+1)u(k+1)}{\mathbb {E} [k]}}}$ ${\displaystyle p_{c}}$ ${\textstyle \mathbb {E} [k^{2}]<\infty }$ ${\displaystyle p_{c}=1-{\frac {\mathbb {E} [k]}{\mathbb {E} [k^{2}]-\mathbb {E} [k]}}}$ ${\displaystyle l}$ ${\displaystyle l=O(\log N)}$

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

$${\displaystyle 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.}$$

^[19] ${\textstyle \mathbb {E} [k_{\text{in}}]}$ ${\textstyle \mathbb {E} [k_{\text{out}}]}$ ${\displaystyle n}$

$${\displaystyle 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}}),}$$

${\displaystyle 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),}$

для внешних компонентов.

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

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

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

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

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

Модель предпочтительной привязанности Барабаши – Альберта (BA)

Модель Барабаши -Альберта представляет собой случайную сетевую модель, используемую для демонстрации преимущественной привязанности или эффекта «богатые становятся богаче». В этой модели ребро, скорее всего, будет прикреплено к узлам с более высокими степенями. Сеть начинается с начальной сети из m ₀ узлов. m ₀  ≥ 2, а степень каждого узла исходной сети должна быть не менее 1, иначе он всегда будет оставаться отключенным от остальной сети.

В модели BA новые узлы добавляются в сеть по одному. Каждый новый узел соединяется с существующими узлами с вероятностью, пропорциональной количеству связей, которые уже имеют существующие узлы. Формально вероятность p _i того, что новый узел подключен к узлу i, равна ^[20] ${\displaystyle m}$

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

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

Распределение степеней модели BA, подчиняющееся степенному закону. В логарифмическом масштабе степенная функция представляет собой прямую линию. ^[21]

Распределение степеней, полученное в результате модели БА, является безмасштабным, в частности, для большой степени оно представляет собой степенной закон вида:

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

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

Модель Барабаши-Альберта ^[21] была разработана для неориентированных сетей с целью объяснить универсальность свойства безмасштабности и применена к широкому спектру различных сетей и приложений. Направленной версией этой модели является модель Прайса ^{[22] [23]} , которая была разработана только для сетей цитирования.

Нелинейная льготная привязанность

В нелинейном предпочтительном присоединении (NLPA) существующие узлы в сети получают новые ребра пропорционально степени узла, возведенной в постоянную положительную степень . ^[24] Формально это означает, что вероятность того, что узел получит новое ребро, определяется выражением ${\displaystyle \alpha }$ ${\displaystyle i}$

${\displaystyle p_{i}={\frac {k_{i}^{\alpha }}{\sum _{j}k_{j}^{\alpha }}}.}$

Если , NLPA сводится к модели BA и называется «линейной». Если NLPA называется «сублинейным», а распределение степеней сети имеет тенденцию к растянутому экспоненциальному распределению . Если NLPA называется «суперлинейным», и небольшое количество узлов подключается почти ко всем остальным узлам в сети. Для обоих и свойство безмасштабности сети нарушается в пределе бесконечного размера системы. Однако, если значение лишь немного больше, чем , NLPA может привести к распределению степеней , которое может оказаться временно свободным от масштабирования. ^[25] ${\displaystyle \alpha =1}$ ${\displaystyle 0<\alpha <1}$ ${\displaystyle \alpha >1}$ ${\displaystyle \alpha <1}$ ${\displaystyle \alpha >1}$ ${\displaystyle \alpha }$ ${\displaystyle 1}$

Модель прикрепления на основе медиации (MDA)

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

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

Фактор является обратным гармоническому среднему (IHM) степеней соседей узла . Обширные численные исследования показывают, что приблизительно среднее значение IHM в большом пределе становится константой, что означает . Это означает, что чем выше уровень связей (уровня) узла, тем выше его шансы получить больше связей, поскольку они могут быть достигнуты большим количеством способов через посредников, что, по сути, воплощает интуитивную идею механизма «богатые становятся богаче» (или предпочтительного механизма богатства). правило прикрепления модели Барабаши–Альберта). Таким образом, можно увидеть, что сеть MDA следует правилу PA, но замаскировано. ^[26] ${\displaystyle {\frac {\sum _{j=1}^{k_{i}}{\frac {1}{k_{j}}}}{k_{i}}}}$ ${\displaystyle k_{i}}$ ${\displaystyle i}$ ${\displaystyle m>14}$ ${\displaystyle N}$ ${\displaystyle \Pi (i)\propto k_{i}}$

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

Фитнес-модель

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

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

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

${\displaystyle P(k)=\rho (\eta (k))\cdot \eta '(k)}$

В результате, если приспособленности распределяются по степенному закону, то и степень узла тоже. ${\displaystyle \eta }$

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

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

с константой и функцией Хэвисайда мы также получаем безмасштабные сети. ${\displaystyle Z}$ ${\displaystyle \Theta }$

Такая модель была успешно применена для описания торговли между странами, используя ВВП как приспособленность для различных узлов и подобную связующую функцию ^{[29] [30]} ${\displaystyle i,j}$

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

Экспоненциальные модели случайных графов

Экспоненциальные модели случайных графов (ERGM) — это семейство статистических моделей для анализа данных из социальных и других сетей. ^[31] Экспоненциальное семейство — это широкое семейство моделей, охватывающих многие типы данных, а не только сети. ERGM — это модель из этого семейства, описывающая сети.

Мы принимаем обозначение для представления случайного графа через набор узлов и набор связанных переменных , индексированных парами узлов , где узлы соединены ребром и в противном случае. ${\displaystyle Y\in {\mathcal {Y}}}$ ${\displaystyle n}$ ${\displaystyle \{Y_{ij}:i=1,\dots ,n;j=1,\dots ,n\}}$ ${\displaystyle ij}$ ${\displaystyle Y_{ij}=1}$ ${\displaystyle (i,j)}$ ${\displaystyle Y_{ij}=0}$

Основное предположение ERGM заключается в том, что структуру наблюдаемого графа можно объяснить заданным вектором достаточной статистики , которая является функцией наблюдаемой сети и, в некоторых случаях, узловых атрибутов. Вероятность графа в ERGM определяется: ${\displaystyle y}$ ${\displaystyle s(y)}$ ${\displaystyle y\in {\mathcal {Y}}}$

${\displaystyle P(Y=y|\theta )={\frac {\exp(\theta ^{T}s(y))}{c(\theta )}}}$

где – вектор параметров модели, связанный с и – нормировочная константа. ${\displaystyle \theta }$ ${\displaystyle s(y)}$ ${\displaystyle c(\theta )=\sum _{y'\in {\mathcal {Y}}}\exp(\theta ^{T}s(y'))}$

Сетевой анализ

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

Анализ социальных сетей исследует структуру взаимоотношений между социальными субъектами. ^[32] Этими субъектами часто являются отдельные лица, но также могут быть группы , организации , национальные государства , веб-сайты , научные публикации .

С 1970-х годов эмпирическое исследование сетей играет центральную роль в социальных науках, и многие математические и статистические инструменты, используемые для изучения сетей, были впервые разработаны в социологии . ^[33] Среди многих других приложений анализ социальных сетей использовался для понимания распространения инноваций , ^[34] новостей и слухов. Аналогичным образом, его использовали для изучения распространения как болезней, так и поведения, связанного со здоровьем . Его также применяли к изучению рынков , где его использовали для изучения роли доверия в отношениях обмена и социальных механизмов в установлении цен. Точно так же его использовали для изучения вербовки в политические движения и общественные организации. Его также использовали для концептуализации научных разногласий, а также академического престижа. В литературе по освоению второго языка он имеет устоявшуюся историю исследований за рубежом, показывающих, как сети взаимодействия со сверстниками влияют на их языковой прогресс. ^[35] Совсем недавно сетевой анализ (и его близкий родственник анализ трафика ) получил широкое применение в военной разведке для раскрытия повстанческих сетей как иерархической, так и безлидерной природы. ^{[36] [37]} В криминологии он используется для выявления влиятельных участников преступных группировок, правонарушительных движений, соучастников преступлений, прогнозирования преступной деятельности и разработки политики. ^[38]

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

Динамический сетевой анализ исследует меняющуюся структуру отношений между различными классами сущностей в результате воздействия сложных социотехнических систем и отражает социальную стабильность и изменения, такие как появление новых групп, тем и лидеров. ^{[39] [40] [41]} Динамический сетевой анализ фокусируется на метасетях, состоящих из нескольких типов узлов (объектов) и нескольких типов связей . Эти сущности могут быть весьма разнообразными. Примеры включают людей, организации, темы, ресурсы, задачи, события, места и убеждения.

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

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

С недавним взрывным ростом общедоступных биологических данных с высокой пропускной способностью анализ молекулярных сетей приобрел значительный интерес. Тип анализа этого контента тесно связан с анализом социальных сетей, но часто фокусируется на локальных закономерностях в сети. Например, сетевые мотивы — это небольшие подграфы, которые чрезмерно представлены в сети. Мотивы деятельности — это аналогичные перепредставленные шаблоны в атрибутах узлов и ребер сети, которые перепредставлены с учетом структуры сети. Анализ биологических сетей привел к развитию сетевой медицины , которая изучает влияние заболеваний на интерактом . ^[42]

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

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

Пандемический анализ

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

Восприимчив к заражению

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

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

Чтобы отслеживать изменение восприимчивых лиц в инфекционной популяции:

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

Зараженный, чтобы выздороветь

${\displaystyle \Delta I=\mu I\,\Delta t}$

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

Инфекционный период

Победит ли пандемия население, что касается модели SIR, зависит от ценности «среднего числа людей, инфицированных инфицированным человеком». ${\displaystyle R_{0}}$

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

Анализ веб-ссылок

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

Рейтинг страницы

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

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

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

Случайные прыжки

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

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

Первый — это вероятность того, что произойдет случайный скачок. Контрастность – это «фактор демпфирования», или . ${\displaystyle \alpha }$ ${\displaystyle 1-\alpha }$

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

Другой взгляд на это:

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

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

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

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

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

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

Модель СИР

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

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

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

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

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

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

При формулировке этих уравнений было сделано несколько допущений: во-первых, следует считать, что индивидуум в популяции имеет равную с любым другим индивидуумом вероятность заразиться этим заболеванием со скоростью , которая считается уровнем контакта или заражения заболеванием. . Таким образом, инфицированный человек вступает в контакт и способен передавать заболевание другим людям в единицу времени, а доля контактов инфицированного с восприимчивым составляет . Тогда число новых инфекций в единицу времени на одного инфицированного составит , что дает уровень новых инфекций (или тех, кто выходит из категории восприимчивости) как (Brauer & Castillo-Chavez, 2001). Для второго и третьего уравнений считаем, что численность населения, покидающего восприимчивый класс, равна числу людей, попадающих в зараженный класс. Однако инфицированные покидают этот класс в единицу времени и попадают в выздоровевший/удаленный класс с частотой в единицу времени (где представляет собой средний уровень выздоровления или средний период заражения). Эти процессы, которые происходят одновременно, называются законом действия масс – широко распространенной идеей, согласно которой скорость контактов между двумя группами населения пропорциональна размеру каждой из соответствующих групп (Daley & Gani, 2005). Наконец, предполагается, что скорость заражения и выздоровления намного быстрее, чем временной масштаб рождаемости и смертности, и поэтому эти факторы в этой модели игнорируются. ${\displaystyle \beta }$ ${\displaystyle \beta N}$ ${\displaystyle S/N}$ ${\displaystyle \beta N(S/N)}$ ${\displaystyle \beta N(S/N)I=\beta SI}$ ${\displaystyle \gamma }$ ${\displaystyle \gamma }$ ${\displaystyle 1/\gamma }$

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

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

Главное уравнение может выражать поведение ненаправленной растущей сети, где на каждом временном шаге в сеть добавляется новый узел, связанный со старым узлом (выбранным случайно и без предпочтений). Исходная сеть формируется из двух узлов и двух связей между ними в момент времени , такая конфигурация необходима только для упрощения дальнейших вычислений, чтобы в момент времени в сети были узлы и связи. ${\displaystyle t=2}$ ${\displaystyle t=n}$ ${\displaystyle n}$ ${\displaystyle n}$

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

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

где - вероятность иметь узел со степенью в момент времени , и - шаг по времени, когда этот узел был добавлен в сеть. Обратите внимание, что старый узел может иметь ссылки только двумя способами : ${\displaystyle p(k,s,t)}$ ${\displaystyle s}$ ${\displaystyle k}$ ${\displaystyle t+1}$ ${\displaystyle s}$ ${\displaystyle s}$ ${\displaystyle k}$ ${\displaystyle t+1}$

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

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

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

${\displaystyle 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),}$

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

Многоуровневые сети

Многоуровневые сети — это сети с несколькими видами отношений. ^[46] Попытки смоделировать системы реального мира как многомерные сети использовались в различных областях, таких как анализ социальных сетей, ^[47] экономика, история, городской и международный транспорт, экология, психология, медицина, биология, коммерция, климатология, физика. , вычислительная нейробиология, операционный менеджмент и финансы.

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

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

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

Взаимозависимые сети — это сети, в которых функционирование узлов одной сети зависит от функционирования узлов другой сети. В природе сети редко появляются изолированно, скорее, обычно сети обычно являются элементами более крупных систем и взаимодействуют с элементами этой сложной системы. Такие сложные зависимости могут иметь нетривиальные последствия друг для друга. Хорошо изученным примером является взаимозависимость инфраструктурных сетей: ^[48] электростанции, образующие узлы энергосистемы, требуют, чтобы топливо доставлялось по сети дорог или труб, а также управляются через узлы коммуникационной сети. Хотя функционирование транспортной сети не зависит от энергетической сети, сеть связи зависит. В таких инфраструктурных сетях выход из строя критического числа узлов либо в сети электропитания, либо в сети связи может привести к каскадным сбоям во всей системе с потенциально катастрофическими последствиями для функционирования всей системы. ^[49] Если бы две сети рассматривались изолированно, этот важный эффект обратной связи не был бы виден, а прогнозы устойчивости сети были бы сильно переоценены.

Смотрите также

• Каскадный отказ
• Климат как сложные сети
• Совместная инновационная сеть
• Коммуникативная экология
• Комплексная сеть
• Структуры ядро-периферия в сетях
• Двухфазная эволюция
• Модель Эрдеша – Реньи
• Глоссарий теории графов
• Градиентная сеть
• Теория высших категорий
• Теория иммунной сети
• Нерегулярная война
• Сетевой анализатор
• Сетевая динамика
• Формирование сети
• Сетевая теория в оценке рисков
• Топология сети
• Сети в экономике труда
• Нелинейная льготная привязанность
• перколяция
• Теория перколяции
• Политический сетевой анализ
• Вежливо
• Квантовая комплексная сеть
• Случайные сети
• Слух распространился в соцсети
• Безмасштабные сети
• Последовательная динамическая система
• Сервисная сеть
• Сети маленького мира
• Структурное отсечение
• Теория систем

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

1. Комитет по сетевым наукам для будущих армейских приложений (2006). Сетевая наука. Национальный исследовательский совет. дои : 10.17226/11516. ISBN 978-0309653886. S2CID  196021177.
2. Денес Кениг (1990). Теория конечных и бесконечных графов (PDF) (PDF). Биркхойзер Бостон. стр. 45–421. дои : 10.1007/978-1-4684-8971-2. ISBN 978-1-4684-8971-2.
3. «Связано: Сила шести градусов (ТВ, 2008) - IMDb» . IMDB .
4. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.301.5111
5. «Сетевая наука в Вест-Пойнте: первые годы». YouTube .
6. https://www.westpoint.edu/academics/academic-departments/mathematical-sciences/network-science
7. Коллиос, Джордж (6 декабря 2011 г.). «Кластеризация больших вероятностных графов». Транзакции IEEE по знаниям и инженерии данных . 25 (2): 325–336. дои :10.1109/TKDE.2011.243. PMID  13188797. S2CID  5650233.
8. "APA PsycNet".
9. Адвокат ab, Гленн (март 2015 г.). «Понимание мощности распространения всех узлов в сети». Научные отчеты . 5 (O8665): 8665. arXiv : 1405.6707 . Бибкод : 2015NatSR...5E8665L. дои : 10.1038/srep08665. ПМЦ 4345333 . ПМИД  25727453. 
10. Сикич, Майл; Ланчич, Ален; Антулов-Фантулин, Нино; Стефанчич, Хрвое (октябрь 2013 г.). «Эпидемическая центральность – существует ли недооценка эпидемического воздействия периферийных узлов сети?». Европейский физический журнал Б. 86 (10): 440. arXiv : 1110.2558 . Бибкод : 2013EPJB...86..440S. дои : 10.1140/epjb/e2013-31025-5. S2CID  12052238.
11. Боргатти, Стивен П. (2005). «Центральность и сетевой поток». Социальные сети . 27 : 55–71. CiteSeerX 10.1.1.387.419 . doi :10.1016/j.socnet.2004.11.008. 
12. Травенсоло, БАН; да Ф. Коста, Л. (2008). «Доступность в сложных сетях». Буквы по физике А. 373 (1): 89–95. Бибкод : 2008PhLA..373...89T. doi :10.1016/j.physleta.2008.10.069.
13. Бендер, Эдвард А; Кэнфилд, Э.Родни (май 1978 г.). «Асимптотическое число помеченных графов с заданными последовательностями степеней». Журнал комбинаторной теории, серия А. 24 (3): 296–307. дои : 10.1016/0097-3165(78)90059-6 . ISSN  0097-3165.
14. Моллой, Майкл; Рид, Брюс (март 1995 г.). «Критическая точка для случайных графов с заданной последовательностью степеней». Случайные структуры и алгоритмы . 6 (2–3): 161–180. CiteSeerX 10.1.1.24.6195 . дои : 10.1002/rsa.3240060204. ISSN  1042-9832. 
15. Ньюман, MEJ; Строгац, С.Х.; Уоттс, ди-джей (24 июля 2001 г.). «Случайные графы с произвольным распределением степеней и их приложения». Физический обзор E . 64 (2): 026118. arXiv : cond-mat/0007235 . Бибкод : 2001PhRvE..64b6118N. doi : 10.1103/PhysRevE.64.026118. PMID  11497662. S2CID  360112.
16. Кривень, Иван (2 мая 2017 г.). «Общее выражение распределения размеров компонентов в сетях бесконечной конфигурации». Физический обзор E . 95 (5): 052303. arXiv : 1703.05413 . Бибкод : 2017PhRvE..95e2303K. doi : 10.1103/PhysRevE.95.052303. PMID  28618550. S2CID  8421307.
17. Кривень, Иван (01.01.2018). «Аналитические результаты по модели случайного графа полимеризации». Журнал математической химии . 56 (1): 140–157. arXiv : 1603.07154 . дои : 10.1007/s10910-017-0785-1 . ISSN  0259-9791.
18. Кривень, Иван (27 июля 2016 г.). «Появление гигантской слабой компоненты в ориентированных случайных графах с произвольным распределением степеней». Физический обзор E . 94 (1): 012315. arXiv : 1607.03793 . Бибкод : 2016PhRvE..94a2315K. doi : 10.1103/PhysRevE.94.012315. PMID  27575156. S2CID  206251373.
19. Кривень, Иван (02.11.2017). «Конечно-связные компоненты в бесконечных направленных и мультиплексных сетях с произвольным распределением степеней». Физический обзор E . 96 (5): 052304. arXiv : 1709.04283 . Бибкод : 2017PhRvE..96e2304K. doi : 10.1103/PhysRevE.96.052304. PMID  29347790. S2CID  20741516.
20. Р. Альберт; А.-Л. Барабаши (2002). «Статистическая механика сложных сетей» (PDF) . Обзоры современной физики . 74 (1): 47–97. arXiv : cond-mat/0106096 . Бибкод : 2002РвМП...74...47А. CiteSeerX 10.1.1.242.4753 . doi : 10.1103/RevModPhys.74.47. S2CID  60545. Архивировано из оригинала (PDF) 24 августа 2015 г. 
21. Альберт-Ласло Барабаси и Река Альберт (октябрь 1999 г.). «Появление масштабирования в случайных сетях» (PDF) . Наука . 286 (5439): 509–512. arXiv : cond-mat/9910332 . Бибкод : 1999Sci...286..509B. дои : 10.1126/science.286.5439.509. PMID  10521342. S2CID  524106. Архивировано из оригинала (PDF) 17 апреля 2012 г.
22. Прайс, Дерек Дж. де Солла (30 июля 1965). «Сети научных статей: структура библиографических ссылок указывает на характер направления научных исследований». Наука . 149 (3683): ​​510–515. Бибкод : 1965Sci...149..510D. дои : 10.1126/science.149.3683.510. ISSN  0036-8075. ПМИД  14325149.
23. Прайс, Дерек Де Солла (1976). «Общая теория библиометрических и других процессов совокупного преимущества». Журнал Американского общества информатики . 27 (5): 292–306. дои : 10.1002/asi.4630270505. S2CID  8536863.
24. Крапивский, ПЛ; Реднер, С.; Лейвраз, Ф. (20 ноября 2000 г.). «Связность растущих случайных сетей». Письма о физических отзывах . 85 (21): 4629–4632. arXiv : cond-mat/0005139 . Бибкод : 2000PhRvL..85.4629K. doi : 10.1103/PhysRevLett.85.4629. PMID  11082613. S2CID  16251662.
25. Крапивский, Павел; Крюков, Дмитрий (21 августа 2008 г.). «Безмасштабные сети как предасимптотические режимы суперлинейного предпочтительного прикрепления». Физический обзор E . 78 (2): 026114. arXiv : 0804.1366 . Бибкод : 2008PhRvE..78b6114K. doi : 10.1103/PhysRevE.78.026114. PMID  18850904. S2CID  14292535.
26. Хасан, МК; Ислам, Лиана; Арефинул Хак, Сайед (март 2017 г.). «Распределение степеней, распределение по рангам и сохранение лидерства в сетях привязанностей, основанных на посредничестве». Физика А. 469 : 23–30. arXiv : 1411.3444 . Бибкод : 2017PhyA..469...23H. doi :10.1016/j.physa.2016.11.001. S2CID  51976352.
27. Калдарелли Г., А. Капоччи, П. Де Лос Риос, М. А. Муньос, Physical Review Letters 89, 258702 (2002)
28. Servedio VDP, Дж. Кальдарелли, П. Бутта, Physical Review E 70, 056126 (2004)
29. Гарлашелли Д., MI Loffredo Physical Review Letters 93, 188701 (2004)
30. Чимини Г., Т. Скуартини, Д. Гарлашелли и А. Габриелли, Scientific Reports 5, 15758 (2015)
31. Люшер, Дин; Коскинен, Йохан; Робинс, Гарри (2012). Экспоненциальные модели случайных графов для социальных сетей: теория, методы и приложения (структурный анализ в социальных науках) . дои : 10.1017/CBO9780511894701. ISBN 9780521141383. ОСЛК  1120539699.
32. Вассерман, Стэнли и Кэтрин Фауст. 1994. Анализ социальных сетей: методы и приложения. Кембридж: Издательство Кембриджского университета.
33. Ньюман, MEJ Networks: Введение. Издательство Оксфордского университета. 2010, ISBN 978-0199206650. 
34. Парадовский, Михал Б.; Йонак, Лукаш (2012). «Распространение лингвистических инноваций как социальная координация». Психология языка и коммуникации . 16 (2): 53–64. дои : 10.2478/v10057-012-0010-z .
35. Парадовский, Михал Б.; Ярыновский, Анджей; Елинска, Магдалена; Чопек, Каролина (2021). «Взаимодействие со сверстниками вне класса имеет значение для овладения вторым языком во время краткосрочных поездок за границу: вклад анализа социальных сетей [Избранные стендовые презентации с конференции Американской ассоциации прикладной лингвистики, Денвер, США, март 2020 г.]». Обучение языку . 54 (1): 139–143. дои : 10.1017/S0261444820000580 .
36. «К сложному сообществу адаптивного интеллекта, Wiki и блог» . Д. Кэлвин Андрус . cia.gov. Архивировано из оригинала 13 июня 2007 года . Проверено 25 августа 2012 г.
37. «Сетевой анализ террористических сетей». Архивировано из оригинала 23 ноября 2012 г. Проверено 12 декабря 2011 г.
38. Доктор философии, Мартин Бушар; Доктор философии, Айли Мальм (02.11.2016). «Анализ социальных сетей и его вклад в исследования преступности и уголовного правосудия». Оксфордские онлайн-руководства: криминология и уголовное правосудие . doi : 10.1093/oxfordhb/9780199935383.013.21. ISBN 978-0-19-993538-3.
39. Гросс Т. и Саяма Х. (ред.). 2009. Адаптивные сети: теория, модели и приложения. Спрингер.
40. Холм П. и Сарамяки Дж. 2013. Временные сети. Спрингер.
41. Ксантос, Арис, Панте, Исаак, Роша, Янник, Гранжан, Мартин (2016). Визуализация динамики сетей персонажей. В «Цифровых гуманитарных науках», 2016: Ягеллонский университет и Педагогический университет, Краков, стр. 417–419.
42. Барабаси, Алабама; Гулбахче, Н.; Лоскальцо, Дж. (2011). «Сетевая медицина: сетевой подход к болезням человека». Обзоры природы Генетика . 12 (1): 56–68. дои : 10.1038/nrg2918. ПМК 3140052 . ПМИД  21164525. 
43. Ньюман, М., Барабаши, А.-Л., Уоттс, DJ [ред.] (2006) Структура и динамика сетей. Принстон, Нью-Джерси: Издательство Принстонского университета.
44. Дороговцев, С. Н.; Мендес, JFF (2003). Эволюция сетей: от биологических сетей к Интернету и WWW . Нью-Йорк, штат Нью-Йорк, США: Oxford University Press, Inc. ISBN 978-0198515906.
45. Котакальпа, М; Хасэ, Миссури (2016). «Эпидемии в сетях: подход основного уравнения». Журнал физики А. 49 (6): 065001. arXiv : 1604.01049 . Бибкод : 2016JPhA...49f5001C. дои : 10.1088/1751-8113/49/6/065001. S2CID  119206200.
46. Де Доменико, Манлио (31 марта 2022 г.). Многослойные сети: анализ и визуализация (1-е изд.). Спрингер.
47. Росси, Лука; Дикисон, Марк Э.; Маньяни, Маттео (18 июля 2016 г.). Многослойные социальные сети (1-е изд.). Издательство Кембриджского университета.
48. «Выявление, понимание и анализ взаимозависимостей критической инфраструктуры». Журнал IEEE Control Systems . 21 (6): 11–25. Декабрь 2001 г. doi : 10.1109/37.969131.
49. Булдырев, Сергей В.; и другие. (апрель 2010 г.). «Катастрофический каскад сбоев во взаимозависимых сетях». Природа . 464 (7291): 1025–1028. arXiv : 0907.1182 . Бибкод : 2010Natur.464.1025B. дои : 10.1038/nature08932. PMID  20393559. S2CID  1836955.

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

• Первый курс сетевых наук , Ф. Менцер , С. Фортунато, К. А. Дэвис. (Издательство Кембриджского университета, 2020). ISBN 9781108471138 . Сайт GitHub с учебными пособиями, наборами данных и другими ресурсами. 
• «На связи: сила шести градусов», https://web.archive.org/web/20111006191031/http://ivl.slis.indiana.edu/km/movies/2008-talas-connected.mov
• Коэн, Р.; Эрез, К. (2000). «Устойчивость Интернета к случайным сбоям». Физ. Преподобный Летт . 85 (21): 4626–4628. arXiv : cond-mat/0007048 . Бибкод : 2000PhRvL..85.4626C. CiteSeerX  10.1.1.242.6797 . doi : 10.1103/physrevlett.85.4626. PMID  11082612. S2CID  15372152.
• Пу, Цунь-Лай; Вэнь-; Пей, Цзян; Майклсон, Эндрю (2012). «Анализ устойчивости управляемости сети» (PDF) . Физика А. 391 (18): 4420–4425. Бибкод : 2012PhyA..391.4420P. doi :10.1016/j.physa.2012.04.019. Архивировано из оригинала (PDF) 13 октября 2016 г. Проверено 18 сентября 2013 г.
• С. Н. Дороговцев и Дж. Ф. Мендес, Эволюция сетей: от биологических сетей к Интернету и WWW , Oxford University Press, 2003, ISBN 0-19-851590-1 
• Связано: Новая наука о сетях , А.-Л. Барабаши (Perseus Publishing, Кембридж)
• «Безмасштабные сети» , Г. Калдарелли (Oxford University Press, Оксфорд)
• Сетевые науки , Комитет по сетевым наукам для будущих армейских приложений, Национальный исследовательский совет. 2005. Издательство национальных академий (2005) ISBN 0-309-10026-7 . 
• Бюллетень сетевых наук , USMA (2007) ISBN 978-1-934808-00-9 
• Структура и динамика сетей Марк Ньюман, Альберт-Ласло Барабаси и Дункан Дж. Уоттс (The Princeton Press, 2006) ISBN 0-691-11357-2 
• Динамические процессы в сложных сетях , Ален Баррат, Марк Бартелеми, Алессандро Веспиньяни (издательство Кембриджского университета, 2008) ISBN 978-0-521-87950-7 
• Сетевые науки: теория и приложения , Тед Г. Льюис (Уили, 11 марта 2009 г.) ISBN 0-470-33188-7 
• Связь: маленькие миры и новаторская теория сетей , Марк Бьюкенен (WW Norton & Company, июнь 2003 г.) ISBN 0-393-32442-7 
• Шесть степеней: наука эпохи связей , Дункан Дж. Уоттс (WW Norton & Company, 17 февраля 2004 г.) ISBN 0-393-32542-3