Наука про мережі

Наука про мережі
Теорія
Граф Складні мережі Світ тісний Безмасштабна мережа Перколяція Структура спільноти Еволюція Керованість Візуалізація графів Соціальний капітал Аналіз зв’язків Оптимізація Транзитивність Теорія балансу Ефект мережі Соціальний вплив
Види мереж
Інформаційна (комп'ютерна) Телекомунікаційна Транспортна Соціальна аналіз Біологічна Штучна нейронна мережа Семантична Просторова Залежностей Потокова
Графи
Властивості Кліка Компонент Розріз Цикл Структура даних Ребро Петля Окіл Шлях Вершина Список суміжності / матриця Список інцидентності / матриця Види Двочастковий Повний Орієнтований Гіперграф Мультиграф Випадковий Зважений
Метрики Алгоритми
Центральність Степінь Близькість PageRank Кластеризація Асортативність Відстань Модулярність Ефективність
Моделі
Топологія Випадковий граф Модель Ердеша — Реньї Модель Барабаші — Альберт Модель Воттса — Строгаца Гіперболічна (HGN) Ієрархічна Стохастична блокова модель Динаміка Булева мережа Агентне моделювання Епідемічні/SIR
Списки Категорії
Категорія:Теорія мереж Категорія:Теорія графів

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

Передумови та історія

Вивчення мереж зустрічається в різних дисциплінах і мережева модель використовується як засіб аналізу складних і пов'язаних даних. Найраніша стаття з цієї галузі — знаменита стаття про сім кенігсберзьких мостів, яку написав Леонард Ейлер 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 року з подачі Фредеріка В. Мокслі і за підтримки Девіда С. Альбертса Міністерство оборони допомогло створити, спільно з військовою академією (англ. the United States Military Academy, USMA) армії США, перший Центр науки про мережі (англ. Network Science Center). Під керівництвом Мокслі і співробітників 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=4$ вузлами. Для кожного ребра в повному графі, утвореному усіма 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 (ультратісний світ).

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

У моделі приєднання через посередника (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\%$ загального числа вузлів мають степінь 1, а один вузол стає супербагатим. У міру збільшення значення $m$ диспропорція між надбагатими і бідними скорочується і при $m>14$ спостерігаємо перехід від механізму «багатий стає супербагатим» до механізму «багатий стає багатшим».

Модель відповідності

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

$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}}}.$

Аналіз мережі

Аналіз соціальних мереж

Аналіз соціальної мережі досліджує структуру зв'язків між громадськими суб'єктами. Ці суб'єкти є часто людьми, але можуть бути також і групами, організаціями, національними державами, сайтами, науковими публікаціями.

Від 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)$, що дає швидкість нових заражень (або тих, хто залишає категорію сприйнятливих) як $\beta N(S/N)I=\beta SI$. Для другого і третього рівнянь вважається, що особи залишають клас сприйнятливих з тією ж швидкістю, з якою входять у клас заражених. Однак, за одиницю часу цей клас залишають $\gamma$ інфкованих ($\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 (метод оцінювання та аналізу проектів).

Література

• Юрий Лифшиц. Структура сложных сетей. Лекция № 4 курса «Алгоритмы для Интернета». — 2006. — 30 жовтня.
• Евин И.А. Введение в теорию сложных сетей // КОМПЬЮТЕРНЫЕИССЛЕДОВАНИЯИМОДЕЛИРОВАНИЕ. — 2010. — Т. 2, № 2 (30 жовтня). — С. 121–141.
• Epidemic Modelling: An Introduction. — 2001. — Т. 15. — (Cambridge Studies in Mathematical Biology) — ISBN 0521014670.
• Jacob Levy Moreno. Who Shall Survive?. — Beacon House, Inc, 1953.
• Dénes Kőnig. Theory of finite and infinite graphs. — Boston : Birkhäuser, 1990. — ISBN 0-8176-3389-8. Перевод Ричарда Маккоарта, комментарии Татта
• Fred Brauer, Carlos Castillo-Chavez. Mathematical Models in Population Biology and Epidemiology. — New York, NY : Springer, 2001. — (Texts in Applied Mathematics) — ISBN 978-1-4614-1685-2.
• Network Science. — Washington, D.C. : THE NATIONAL ACADEMIES PRESS, 2006. — ISBN 978-0309653886. — DOI:10.17226/11516.
• Stephen P. Borgatti. Centrality and Network Flow // Social Networks. — 2005. — Т. 27 (30 жовтня). — DOI:10.1016/j.socnet.2004.11.008.
• Glenn Lawyer. Understanding the spreading power of all nodes in a network // Scientific Reports. — 2015. — Т. 5, № O8665 (March). — arXiv:1405.6707. — Bibcode:2015NatSR...5E8665L. — DOI:10.1038/srep08665. — PMID 25727453 .
• Mile Sikic, Alen Lancic, Nino Antulov-Fantulin, Hrvoje Stefancic. Epidemic centrality -- is there an underestimated epidemic impact of network peripheral nodes? // European Physical Journal B. — 2013. — Т. 86, № 10 (October). — С. 440. — arXiv:1110.2558. — Bibcode:2013EPJB...86..440S. — DOI:10.1140/epjb/e2013-31025-5.
• Braha D., Bar-Yam Y. From Centrality to Temporary Fame: Dynamic Centrality in Complex Networks // Complexity. — 2006. — Т. 12, вип. 2 (30 жовтня). — arXiv:physics/0611295. — Bibcode:2006Cmplx..12b..59B. — DOI:10.1002/cplx.20156.
• Hill S.A., Braha D. Dynamic Model of Time-Dependent Complex Networks // Physical Review E. — 2010. — Т. 82, вип. 4 (30 жовтня). — arXiv:0901.4407. — Bibcode:2010PhRvE..82d6105H. — DOI:10.1103/physreve.82.046105. — PMID 21230343 .
• Adaptive Networks: Theory, Models and Applications / Gross T., Sayama H. — Springer, 2009.
• Holme P., Saramäki J. Temporal Networks. — Springer, 2013.
• Travençolo B. A. N., da Costa F. L. Accessibility in complex networks // Physics Letters A. — 2008. — Т. 373, вип. 1 (30 жовтня). — Bibcode:2008PhLA..373...89T. — DOI:10.1016/j.physleta.2008.10.069.
• Edward A. Bender, E. Rodney Canfield. The asymptotic number of labeled graphs with given degree sequences // Journal of Combinatorial Theory, Series A. — 1978. — Т. 24, вип. 3 (May). — ISSN 0097-3165. — DOI:10.1016/0097-3165(78)90059-6.
• Michael Molloy, Bruce Reed. A critical point for random graphs with a given degree sequence // Random Structures & Algorithms. — 1995. — Т. 6, вип. 2–3 (March). — С. 161–180. — ISSN 1042-9832. — DOI:10.1002/rsa.3240060204.
• Newman M. E. J., Strogatz S. H., Watts D. J. Random graphs with arbitrary degree distributions and their applications // Physical Review E. — 2001. — Т. 64, вип. 2 (07). — arXiv:cond-mat/0007235. — Bibcode:2001PhRvE..64b6118N. — DOI:10.1103/PhysRevE.64.026118. — PMID 11497662 .
• Ivan Kryven. Emergence of the giant weak component in directed random graphs with arbitrary degree distributions // Physical Review E. — 2016. — Т. 94, вип. 1 (07). — arXiv:1607.03793. — Bibcode:2016PhRvE..94a2315K. — DOI:10.1103/PhysRevE.94.012315. — PMID 27575156 .
• Ivan Kryven. General expression for the component size distribution in infinite configuration networks // Physical Review E. — 2017. — Т. 95, вип. 5 (05). — arXiv:1703.05413. — Bibcode:2017PhRvE..95e2303K. — DOI:10.1103/PhysRevE.95.052303. — PMID 28618550 .
• Ivan Kryven. Finite connected components in infinite directed and multiplex networks with arbitrary degree distributions // Physical Review E. — 2017. — Т. 96, вип. 5 (11). — arXiv:1709.04283. — Bibcode:2017PhRvE..96e2304K. — DOI:10.1103/PhysRevE.96.052304. — PMID 29347790 .
• Ivan Kryven. Analytic results on the polymerisation random graph model // Journal of Mathematical Chemistry. — 2018. — Т. 56, вип. 1 (01). — С. 140–157. — ISSN 0259-9791. — DOI:10.1007/s10910-017-0785-1.
• Garlaschelli D., Loffredo M. I. Patterns of link reciprocity in directed networks. — Physical Review Letters. — 2004. — Т. 93. — С. 268701.
• Cimini G., Squartini T., Garlaschelli D., Gabrielli A. Systemic risk analysis on reconstructed economic and financial networks. — Scientific Reports. — 2015. — С. 15758.
• Servedio V.D.P., Caldarelli G., Buttà P. Vertex intrinsic fitness: How to produce arbitrary scale-free networks // Physical Review E. — 2004. — Т. 70 (30 жовтня).
• Hassan M. K., Liana Islam, Syed Arefinul Haque. Degree distribution, rank-size distribution, and leadership persistence in mediation-driven attachment networks // Physica A. — 2017. — Т. 469 (March). — arXiv:1411.3444. — Bibcode:2017PhyA..469...23H. — DOI:10.1016/j.physa.2016.11.001.
• Caldarelli G., Capocci A., De Los Rios P., Muñoz M.A. Scale-Free Networks from Varying Vertex Intrinsic Fitness // Physical Review Letters. — 2002. — Т. 89, вип. 25 (30 жовтня).
• Cohen R., Havlin S. Scale-free networks are ultrasmall // Phys. Rev. Lett.. — 2003. — Т. 90, вип. 5 (30 жовтня). — arXiv:cond-mat/0205476. — Bibcode:2003PhRvL..90e8701C. — DOI:10.1103/PhysRevLett.90.058701. — PMID 12633404 .
• Albert R., Barabási A.-L. Statistical mechanics of complex networks // Reviews of Modern Physics. — 2002. — Т. 74, вип. 1 (30 жовтня). — С. 47–97. — arXiv:cond-mat/0106096. — Bibcode:2002RvMP...74...47A. — DOI:10.1103/RevModPhys.74.47. Архівовано з джерела 24 серпня 2015.
• Albert-László Barabási, Réka Albert. Emergence of scaling in random networks // Science. — 1999. — Т. 286, вип. 5439 (October). — arXiv:cond-mat/9910332. — Bibcode:1999Sci...286..509B. — DOI:10.1126/science.286.5439.509. — PMID 10521342 . Архівовано з джерела 17 квітня 2012.
• Cohen R., Havlin S. Complex Networks: Structure, Robustness and Function. — Cambridge University Press, 2010.
• Bunde A., Havlin S. Fractals and Disordered Systems. — Springer, 1996.
• Stanley Wasserman, Katherine Faust. Social Network Analysis: Methods and Applications. — Cambridge : Cambridge University Press, 1994.
• Newman M.E.J. Networks: An Introduction. — Oxford University Press, 2010.
• Aris Xanthos, Isaac Pante, Yannick Rochat, Martin Grandjean. Visualising the Dynamics of Character Networks // Digital Humanities 2016: Jagiellonian University & Pedagogical University. — Kraków, 2016. — С. 417–419.
• Barabási A. L., Gulbahce N., Loscalzo J. Network medicine: a network-based approach to human disease // Nature Reviews Genetics. — 2011. — Т. 12, вип. 1 (30 жовтня). — DOI:10.1038/nrg2918. — PMID 21164525 .
• Puzis R., Yagil D., Elovici Y., Braha D. Collaborative attack on Internet users' anonymity // Internet Research. — 2009. — Т. 19 (30 жовтня). — DOI:10.1108/10662240910927821. Архівовано з джерела 7 грудня 2013.
• The Structure and Dynamics of Networks / Newman M., Barabási A.-L., Watts D.J. — Princeton, N.J. : Princeton University Press, 2006.
• Dorogovtsev S. N., Mendes J. F. F. Evolution of Networks: From Biological Nets to the Internet and WWW. — New York, NY, USA : Oxford University Press, Inc, 2003. — ISBN 978-0198515906.
• Cotacallapa M., Hase M. O. Epidemics in networks: a master equation approach // Journal of Physics A. — 2016. — Т. 49, вип. 6 (30 жовтня). — arXiv:1604.01049. — Bibcode:2016JPhA...49f5001C. — DOI:10.1088/1751-8113/49/6/065001.
• Buldyrev S. V., Parshani R., Paul G., Stanley H. E., Havlin S. Catastrophic cascade of failures in interdependent networks // Nature. — 2010. — Т. 464, вип. 7291 (30 жовтня). — arXiv:0907.1182. — Bibcode:2010Natur.464.1025B. — DOI:10.1038/nature08932. — PMID 20393559 .
• Jianxi Gao, Sergey V. Buldyrev, Shlomo Havlin, H. Eugene Stanley. Robustness of a Network of Networks // Phys. Rev. Lett.. — 2011. — Т. 107, вип. 19 (30 жовтня). — arXiv:1010.5829. — Bibcode:2011PhRvL.107s5701G. — DOI:10.1103/PhysRevLett.107.195701. — PMID 22181627 .
• Michele Coscia, Giulio Rossetti, Diego Pennacchioli, Damiano Ceccarelli, Fosca Giannotti. "You Know Because I Know": A Multidimensional Network Approach to Human Resources Problem. — Advances in Social Network Analysis and Mining (ASONAM). — 2013. — Т. 2013. — ISBN 9781450322409. — DOI:10.1145/2492517.2492537.
• Kivela M., Arenas A., Barthelemy M., Gleeson J. P., Moreno Y., Porter M. A. Multilayer networks // Journal of Complex Networks. — 2014. — Т. 2, вип. 3 (30 жовтня). — DOI:10.1093/comnet/cnu016.
• Boccaletti S., Bianconi G., Criado R., del Genio C. I., Gómez-Gardeñes J., Romance M., Sendiña-Nadal I., Wang Z., Zanin M. The structure and dynamics of multilayer networks // Physics Reports. — 2014. — Т. 544, вип. 1 (30 жовтня). — arXiv:1407.0742. — Bibcode:2014PhR...544....1B. — DOI:10.1016/j.physrep.2014.07.001.
• Federico Battiston, Vincenzo Nicosia, Vito Latora. The new challenges of multiplex networks: Measures and models // The European Physical Journal Special Topics. — 2017. — Т. 226, вип. 3 (02). — ISSN 1951-6355. — arXiv:1606.09221. — Bibcode:2017EPJST.226..401B. — DOI:10.1140/epjst/e2016-60274-8.
• De Domenico M., Solé-Ribalta, A., Cozzo E., Kivelä M., Moreno Y., Porter M., Gómez S., Arenas A. Mathematical Formulation of Multilayer Networks // Physical Review X. — 2013. — Т. 3, вип. 4 (30 жовтня). — arXiv:1307.4977. — Bibcode:2013PhRvX...3d1022D. — DOI:10.1103/PhysRevX.3.041022. Архівовано з джерела 25 лютого 2014.
• Battiston F., Nicosia V., Latora V. Structural measures for multiplex networks // Physical Review E. — 2014. — Т. 89, вип. 3 (30 жовтня). — С. 032804. — arXiv:1308.3182. — Bibcode:2014PhRvE..89c2804B. — DOI:10.1103/PhysRevE.89.032804. — PMID 24730896 .
• Mucha P. Community structure in time-dependent, multiscale, and multiplex networks // Science. — 2010. — Т. 328, вип. 5980 (30 жовтня). — arXiv:0911.1824. — Bibcode:2010Sci...328..876M. — DOI:10.1126/science.1184819. — PMID 20466926 .
• De Domenico M., Lancichinetti A., Arenas A., Rosvall M. Identifying Modular Flows on Multilayer Networks Reveals Highly Overlapping Organization in Interconnected Systems // Physical Review X. — 2015. — Т. 5, вип. 1 (30 жовтня). — С. 011027. — arXiv:1408.2925. — Bibcode:2015PhRvX...5a1027D. — DOI:10.1103/PhysRevX.5.011027.
• De Domenico M., Sole-Ribalta A., Omodei E., Gomez S., Arenas A. Ranking in interconnected multilayer networks reveals versatile nodes // Nature Communications. — 2015. — Т. 6 (30 жовтня). — С. 6868. — arXiv:1311.2906. — Bibcode:2015NatCo...6E6868D. — DOI:10.1038/ncomms7868. — PMID 25904405 .
• Federico Battiston, Jacopo Iacovacci, Vincenzo Nicosia, Ginestra Bianconi, Vito Latora. Emergence of Multiplex Communities in Collaboration Networks // PLOS ONE. — 2016. — Т. 11, вип. 1 (01). — ISSN 1932-6203. — arXiv:1506.01280. — Bibcode:2016PLoSO..1147451B. — DOI:10.1371/journal.pone.0147451. — PMID 26815700 .
• Martin Grandjean. Archives Distant Reading: Mapping the Activity of the League of Nations’ Intellectual Cooperation // Digital Humanities 2016. — Jagiellonian University & Pedagogical University, Kraków, 2016. — С. 531–534.
• Cardillo A. Emergence of network features from multiplexity // Scientific Reports. — 2013. — Т. 3 (30 жовтня). — arXiv:1212.2153. — Bibcode:2013NatSR...3E1344C. — DOI:10.1038/srep01344. — PMID 23446838 .
• Boeing G. OSMnx: New Methods for Acquiring, Constructing, Analyzing, and Visualizing Complex Street Networks // Computers, Environment and Urban Systems. — 2017. — Т. 65 (30 жовтня). — С. 126–139. — arXiv:1611.01890. — DOI:10.1016/j.compenvurbsys.2017.05.004. Процитовано 2017-08-26.
• Gallotti R., Barthelemy M. Anatomy and efficiency of urban multimodal mobility // Scientific Reports. — 2014. — Т. 4 (30 жовтня). — С. 6911. — arXiv:1411.1274. — Bibcode:2014NatSR...4E6911G. — DOI:10.1038/srep06911. — PMID 25371238 .
• De Domenico M., Sole-Ribalta A., Gomez S., Arenas A. Navigability of interconnected networks under random failures // PNAS. — 2014. — Т. 111, вип. 23 (30 жовтня). — С. 8351–8356. — Bibcode:2014PNAS..111.8351D. — DOI:10.1073/pnas.1318469111. — PMID 24912174 .
• Pilosof S., Porter M.A., Pascual M., Kefi S. The Multilayer Nature of Ecological Networks // Nature Ecology & Evolution. — 2015. — Т. 1, вип. 4 (30 жовтня). — arXiv:1511.04453. — DOI:10.1038/s41559-017-0101. — PMID 28812678 .
• Kouvaris N.E., Hata S., Diaz-Guilera A. Pattern Formation in Multiplex Networks // Scientific Reports. — 2015. — Т. 5, вип. 1 (30 жовтня). — arXiv:1412.2923. — Bibcode:2015NatSR...510840K. — DOI:10.1038/srep10840. — PMID 26042606 .
• Timóteo S., Correia M., Rodríguez-Echeverría S., Freitas H., Heleno R. Multilayer networks reveal the spatial structure of seed-dispersal interactions across the Great Rift landscapes // Nature Communications. — 2018. — Т. 9, вип. 1 (30 жовтня). — DOI:10.1038/s41467-017-02658-y. — PMID 29321529 .
• Costa J.M., Ramos J.A., Timóteo S., da Silva L.P., Ceia R.C., Heleno R. Species activity promote the stability of fruit-frugivore interactions across a five-year multilayer network. — 2018. — 30 жовтня. — DOI:10.1101/421941.
• Fiori K. L., Smith J., Antonucci T. C. Social network types among older adults: A multidimensional approach // The Journals of Gerontology Series B. — 2007. — Т. 62, вип. 6 (30 жовтня). — С. P322–30. — DOI:10.1093/geronb/62.6.p322. — PMID 18079416 .
• De Domenico M., Nicosia V., Arenas A., Latora V. Structural reducibility of multilayer networks // Nature Communications. — 2015. — Т. 6 (30 жовтня). — С. 6864. — Bibcode:2015NatCo...6E6864D. — DOI:10.1038/ncomms7864. — PMID 25904309 .
• Gao, Buldyrev, Stanley, Havlin. Networks formed from interdependent networks // Nature Physics. — 2011. — Т. 8, вип. 1 (December). — Bibcode:2012NatPh...8...40G. — DOI:10.1038/nphys2180.
• De Domenico M., Granell C., Porter M. A., Arenas A. The physics of multilayer networks // Nature Physics. — 2016. — Т. 12, вип. 10 (April). — arXiv:1604.02021. — Bibcode:2016NatPh..12..901D. — DOI:10.1038/nphys3865.
• Timme N., Ito S., Myroshnychenko M., Yeh F.C., Hiolski E., Hottowy P., Beggs J.M. Multiplex Networks of Cortical and Hippocampal Neurons Revealed at Different Timescales // PLoS ONE. — 2014. — Т. 9, вип. 12 (30 жовтня). — Bibcode:2014PLoSO...9k5764T. — DOI:10.1371/journal.pone.0115764. — PMID 25536059 .
• De Domenico M., Sasai S., Arenas A. Mapping multiplex hubs in human functional brain networks // Frontiers in Neuroscience. — 2016. — Т. 10 (30 жовтня). — DOI:10.3389/fnins.2016.00326. — PMID 27471443 .
• Battiston F., Nicosia V., Chavez M., Latora V. Multilayer motif analysis of brain networks // Chaos: An Interdisciplinary Journal of Nonlinear Science. — 2017. — Т. 27, вип. 4 (30 жовтня). — arXiv:1606.09115. — Bibcode:2017Chaos..27d7404B. — DOI:10.1063/1.4979282. — PMID 28456158 .

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

• "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 (30 жовтня). — С. 4626–4628. — arXiv:cond-mat/0007048. — Bibcode:2000PhRvL..85.4626C. — DOI:10.1103/physrevlett.85.4626. — PMID 11082612 .
• Cun-Lai Pu, Wen, Jiang Pei, Andrew Michaelson. Robustness analysis of network controllability // Physica A. — 2012. — Т. 391, вип. 18 (30 жовтня). — С. 4420–4425. — Bibcode:2012PhyA..391.4420P. — DOI:10.1016/j.physa.2012.04.019. Архівовано з джерела 13 жовтня 2016.
• "Leader Profile: The Burgeoning Field of Science Network, 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 (30 жовтня). — С. 888–893. — arXiv:1001.5285. — Bibcode:2010NatPh...6..888K. — DOI:10.1038/nphys1746.