Наука про мережі — Вікіпедія

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

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

Передумови та історія[ред. | ред. код]

Вивчення мереж зустрічається в різних дисциплінах і мережева модель використовується як засіб аналізу складних і пов'язаних даних. Найраніша стаття з цієї галузі — знаменита стаття про сім кенігсберзьких мостів, яку написав Леонард Ейлер 1736 року. Запропонований Ейлером математичний опис вершин і ребер став основою теорії графів — галузі математики, яка вивчає властивості попарних зв'язків у мережевій структурі. Теорія графів розвинулася і знайшла застосування в хімії^[2].

Денеш Кеніг, угорський професор математики, написав 1936 року першу книгу з теорії графів «Теорія скінченних і нескінченних графів»^[3].

У 1930-х роках Якоб Леві Морено, психолог, що працював у традиціях гештальтпсихології, прибув до США. Він розробив соціограму^[en] й представив її публіці в квітні 1933 року на з'їзді студентів-медиків. Морено стверджував, що «до винаходу соціометрії ніхто не знав, як точно виглядає міжособистісна структура групи»^[4]. Соціограма була поданням соціальної структури групи учнів початкової школи. Хлопці дружили з хлопцями, а дівчата — з іншими дівчатами, лише з одним винятком: один із хлопців сказав, що йому подобається одна дівчина, але почуття не було обопільним. Мережеве подання соціальної структури справило таке сильне враження, що про нього написали в газеті The New York Times^[5]. Соціограми знайшли безліч застосувань, на їх основі сформувались підходи до аналізу соціальних мереж.

Застосування теорії ймовірності в науці про мережі розвивалося як відгалуження теорії графів у вигляді восьми знаменитих статей Пала Ердеша і Альфреда Реньї про випадкові графи. Для соціальних мереж експоненційна модель випадкового графу^[en] або p* є чудовою основою для подання простору ймовірнісних зв'язків, що з'являються в соціальній мережі. Альтернативним підходом до ймовірнісних мережевих структур є матриця ймовірностей мережі^[en], яка моделює ймовірність ребер, що виникають у мережі, ґрунтуючись на історичній присутності або відсутності ребра в мережах, що виникають.

У 1998 Девід Крекгард і Кетлін Карлі представили ідею метамережі з моделлю PCANS. Вони припустили, що «всі організації утворюють три домени: Люди, Завдання і Ресурси». В їхній статті введено концепцію, що мережі виникають у кількох доменах, а тому вони взаємозв'язані. Ця галузь виросла в іншу підгалузь науки про мережі, яка називається динамічним аналізом мережі^[en].

Пізніше наукові зусилля були сфокусовані на математичному описі різних мережевих топологій. Дункан Ваттс поєднав дані на мережах з математичним поданням, яке описує граф «Світ тісний». Альберт-Ласло Барабаші і Река Альберт^[en] розробили масштабно-інваріантну мережу, яка в загальних рисах визначає мережеву топологію, яка містить вузлові вершини (хаби) зі множиною з'єднань, кількість яких зростає, зберігаючи постійне відношення числа з'єднань до числа вузлів. Хоча багато мереж, такі як інтернет, зберігають це відношення, інші мережі мають довгі хвости розподілу вузлів, які лише наближено зберігають масштабну інваріантність.

Ініціативи Міністерства оборони США[ред. | ред. код]

Військовики США першими (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) сформували Міжнародний технологічний альянс^[en] (англ. International Technology Alliance) з мережевої та інформаційної науки (англ. the Network and Information Science), партнерство армійської дослідної лабораторії Міністерства оборони Великої Британії і консорціуму індустрії та університетів США і Великої Британії. Метою альянсу є здійснення досліджень з підтримки інформаційних операцій в інтересах обох націй.

2009 року армія США сформувала Спільний технологічний альянс з науки про мережі^[en], альянс зі спільних досліджень Дослідницької лабораторії Армії США, CERDEC^[en] і консорціуму 30 промислових дослідницьких центрів США. Метою альянсу є розробка глибокого розуміння загальних рис переплетених соціальних/когнітивних, інформаційних і комунікаційних мереж, а як результат, покращення можливості аналізувати, передбачати, розробляти і впливати на складні переплетені системи мереж багатьох видів.

Потім, як результат цих зусиль, міністерство оборони США спонсорувало численні дослідницькі проєкти, що підтримують науку про мережі.

Властивості мереж[ред. | ред. код]

Часто мережі мають деякі атрибути, які можуть бути обчислені для аналізу їхніх властивостей і характеристик. Поведінку цих властивостей мереж часто визначають мережеві моделі і вони можуть бути використані для аналізу, чим відрізняються одні моделі від інших. Багато визначень інших термінів, які використовуються в науці про мережі, можна знайти в статті «Словник термінів теорії графів».

Розмір[ред. | ред. код]

Під розміром мережі може розумітися число вузлів ${\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 }$.

Щільність[ред. | ред. код]

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

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

Інше можливе рівняння — ${\displaystyle D={\frac {T-2N+2}{N(N-3)+2}},}$ де зв'язки ${\displaystyle T}$ неорієнтовані^[6][7]. Це дає краще розуміння щільності мережі, оскільки неорієнтовані зв'язки можна виміряти.

Планарна мережева щільність[ред. | ред. код]

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

Середній степінь вузла[ред. | ред. код]

Степінь ${\displaystyle k}$ вузла — це кількість ребер, пов'язаних з ним. Тісно пов'язана з щільністю мережі середня щільність, ${\displaystyle \langle k\rangle ={\tfrac {2E}{N}}}$ (або, у разі орієнтованих графів ${\displaystyle \langle k\rangle ={\tfrac {E}{N}}}$. Множник 2 в попередній рівності виникає з того, що кожне ребро в неорієнтованому графі робить внесок у степені двох різних вершин). У моделі випадкового графу Ердеша — Реньї (${\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)}$ відомий як ефект ультратісного світу.

Діаметр мережі[ред. | ред. код]

Як інший засіб вимірювання графів мереж можна визначити діаметр мережі, як найдовший з обчислених найкоротших шляхів у мережі. Це найкоротша відстань між двома найвіддаленішими один від одного вузлами мережі. Іншими словами, після того, як обчислено довжину найкоротшого шляху з кожного вузла у всі інші вузли, діаметр є найдовшим з усіх обчислених довжин шляхів. Діаметр є поданням лінійного розміру мережі.

Коефіцієнт кластеризації[ред. | ред. код]

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

Коефіцієнт кластеризації ${\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}\,.}$

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

Зв'язність[ред. | ред. код]

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

• Кліка/повний граф — повністю зв'язна мережа, в якій кожен вузол пов'язаний з кожним іншим вузлом. Ці мережі симетричні, оскільки всі вузли мають вхідні з'єднання від всіх інших вузлів і вихідні з'єднання у всі інші вузли.
• Гігантська компонента — одна зв'язна компонента містить більшість вузлів мережі.
• Слабко-зв'язна компонента — набір вузлів, у якому існує шлях з будь-якого вузла в будь-який інший без урахування напрямку ребер.
• Сильно-зв'язна компонента — набір вузлів, у якому існує орієнтований шлях з будь-якого вузла в будь-який інший.

Центральність вузла[ред. | ред. код]

Показники центральності породжують ранжування, яке намагається виявити найважливіші вузли в моделі мережі. Різні показники центральності кодують різні контексти слова «важливість». Центральність за посередництвом^[8], наприклад, вважає вузол дуже важливим, якщо він утворює мости між багатьма іншими вузлами. На противагу, центральність за впливовістю вважає вузол дуже важливим, якщо багато інших дуже важливих вузлів пов'язані з ним. В літературі запропоновано сотні таких мір.

Ознаки центральності точні тільки для виявлення найбільш центральних вузлів. Ці міри рідко мають сенс, якщо взагалі мають, для інших вузлів мережі^[9][10]. Також вони точні, тільки тоді, коли використовуються в контексті важливості вузлів і прагнуть «стати помилковими» в інших контекстах^[11]. Наприклад, уявімо дві спільноти, які з'єднуються тільки ребром між наймолодшими членами кожної зі спільнот. Оскільки перехід із однієї спільноти в іншу має йти через це ребро, двоє молодших членів будуть мати високу центральність за посередництвом. Але, оскільки вони молоді (очевидно), вони мають мало зв'язків з «важливими» вузлами у власній спільноті, це означає, що їхня центральність за впливовістю буде досить низькою.

Концепцію центральності в контексті статичних мереж розширено на основі емпіричних і теоретичних досліджень до динамічної центральності^[12] в контексті залежних від часу і тимчасових мереж^[13][14][15].

Вплив вершин[ред. | ред. код]

Обмеження мір центральності призвели до розвитку більш загальних мір. Двома прикладами є досяжність, яка використовує розкид довжини випадкових маршрутів для вимірювання, наскільки досяжна решта мережі від вибраного початкового вузла^[16], і очікувана сила, похідна від очікуваного значення сили інфекції, породженої вузлом^[9]. Обидві ці міри можна змістовно обчислити з самої структури мережі.

Мережеві моделі[ред. | ред. код]

Мережеві моделі використовуються як основа для розуміння взаємозв'язків всередині емпіричних складних мереж. Різні моделі генерування випадкових графів утворюють мережеві структури, які можна використати в порівнянні зі складними мережами реального світу.

Модель випадкового графу Ердеша — Реньї[ред. | ред. код]

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

Для генерування моделі Ердеша — Реньї ${\displaystyle G(n,p)}$ потрібно задати два параметри — загальну кількість вузлів 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)}$.

Конфігураційна модель[ред. | ред. код]

Як вхід для конфігураційної моделі вибирається послідовність степенів вершин^[17][18] або розподіл степенів вершин^[19][20] (яка потім використовується для генерування послідовності вершин) і створюється випадково зв'язний граф зі збереженням усіх степенів вершин послідовності. Це означає, що для даного вибору послідовності степенів граф вибирається однорідно із множини всіх графів, які мають таку послідовність степенів вершин. Степінь ${\displaystyle k}$ випадково вибраної вершини є незалежною і однаково розподіленою випадковою змінною з цілими значеннями. При ${\textstyle \mathbb {E} [k^{2}]-2\mathbb {E} [k]>0}$ конфігураційний граф містить гігантську зв'язну компоненту необмеженого розміру^[18]. Інші компоненти мають скінченні розміри, які можна виразити кількісно за допомогою розподілу розміру. Ймовірність ${\displaystyle w(n)}$, що випадково вибраний вузол пов'язаний з компонентою розміру ${\displaystyle n}$ визначається степенем згортки^[en] розподілу степенів^[21]

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

де ${\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 }$, ця критична частка ребер задається рівністю^[22]

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

і середня відстань між вершинами ${\displaystyle l}$ гігантської компоненти логарифмічно пропорційна повному розміру мережі ${\displaystyle l=O(\log N)}$^[19].

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

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

Зауважимо, що ${\textstyle \mathbb {E} [k_{\text{in}}]}$ і ${\textstyle \mathbb {E} [k_{\text{out}}]}$ рівні, а тому взаємозамінні в останній нерівності. Ймовірність того, що випадково вибрана вершина належить компоненті розміру ${\displaystyle n}$, задається формулою^[24]

$${\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 }$ найближчими сусідами. Інший параметр задає ймовірність перемонтування. Кожне ребро має ймовірність ${\displaystyle p}$, що його буде перемонтовано в граф як випадкове ребро. Очікуване число перемонтованих з'єднань у моделі дорівнює ${\displaystyle pE=pN\langle k\rangle /2}$.

Оскільки модель Ваттса — Строгаца починається як невипадкова ґратчаста структура, вона має дуже високий коефіцієнт кластеризації разом з високою середньою довжиною шляху. Кожне перемонтування з великою ймовірністю створює скорочений шлях між сильно зв'язними кластерами. При збільшенні ймовірності перемонтування коефіцієнт кластеризації зменшується повільніше, ніж середня довжина шляху. Як наслідок, це дозволяє середній довжині шляху мережі істотно зменшуватися за слабкого зменшення коефіцієнта кластеризації. Високі значення p приводять до більшого числа перемонтувань ребер, що в цілому робить модель Ваттса — Строгаца випадкової мережею.

Модель Барабаші — Альберт бажаних приєднань[ред. | ред. код]

Модель Барабаші — Альберт — це модель випадкової мережі, яка використовується для демонстрування бажаних приєднань або ефекту «багатий стає багатшим». У цій моделі ребро найімовірніше з'єднує вузли з найбільшими степенями. Мережа починається з мережі з m₀ вузлами, де ${\displaystyle m_{0}\geqslant 2}$, а степінь кожного з вузлів початкової мережі має бути принаймні 1, в іншому випадку вузол назавжди залишиться від'єднаним від решти мережі.

У моделі Барабаші — Альберт нові вузли додаються в мережу по одному. Кожен новий вузол з'єднується з ${\displaystyle m}$ наявними вузлами з імовірністю, яка пропорційна числу вузлів, що вже існують. Формально, ймовірність ${\displaystyle p_{i}}$, що новий вузол зв'язний з вузлом i, дорівнює^[25]

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

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

Розподіл вузлів за кількістю зв'язків, що отримується з BA моделі, масштабно інваріантний, зокрема, це степеневий закон вигляду

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

Хаби показують високу центральність за посередництвом, дозволяючи існування коротких шляхів між вузлами. Як наслідок, модель BA прагне мати дуже коротку середню довжину шляхів. Коефіцієнт кластеризації цієї моделі також прямує до 0. Тоді як діаметр D багатьох моделей, зокрема моделі випадкового графу Ердеша — Реньї і деяких мереж «тісного світу», пропорційний log N, модель BA показує D~loglogN (ультратісний світ)^[27].

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

У моделі приєднання через посередника^[en] (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}}}.}$

Множник ${\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}}$. З цього випливає, що чим більше зв'язків (степінь) вузол має, тим вищий у нього шанс отримати більше зв'язків, оскільки їх можна отримати більшим числом способів через посередників, що, по суті, втілює інтуїтивну ідею «багаті стають багатшими» (або правило переважного приєднання моделі Барабаші — Альберт). Тому мережі MDA, як можна зрозуміти, підкоряються правилу PA, але в неявному вигляді^[28].

Однак при ${\displaystyle m=1}$ отримуємо механізм «переможець забирає все», оскільки майже ${\displaystyle 99\%}$ загального числа вузлів мають степінь 1, а один вузол стає супербагатим. У міру збільшення значення ${\displaystyle m}$ диспропорція між надбагатими і бідними скорочується і при ${\displaystyle m>14}$ спостерігаємо перехід від механізму «багатий стає супербагатим» до механізму «багатий стає багатшим».

Модель відповідності[ред. | ред. код]

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

${\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 }$, що ми отримуємо масштабно-інваріантні мережі.

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

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

Аналіз мережі[ред. | ред. код]

Аналіз соціальних мереж[ред. | ред. код]

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

Від 1970-х років емпіричне вивчення мереж відіграє центральну роль у соціальній науці і багато математичних і статистичних засобів, що використовуються для вивчення мереж, розроблено в соціології^[33]. Серед багатьох інших застосувань аналіз соціальної мережі використовується для розуміння дифузії інновацій, новин і чуток. Аналогічно, його можна використати як для дослідження поширення хвороб, так і пов'язаної зі здоров'ям поведінки. Його застосовували для вивчення ринку, де використовували для перевірки ролі довіри в товарно-грошових відносинах і соціальних механізмів у формуванні цін. Аналогічно його використовували для вивчення залучення в політичні рухи і соціальні організації. Використовували його також для осмислення наукових розбіжностей і академічної репутації. Нещодавно мережевий аналіз (і його найближчий родич, аналіз трафіку^[en]) почали інтенсивно використовувати у військовій розвідці для розкриття соціальних мереж опору, що мають як ієрархічну, так і безлідерну природу^[34][35].

Динамічний аналіз мережі[ред. | ред. код]

Динамічний аналіз мережі^[en] досліджує зміни структури зв'язків серед різних класів об'єктів у складних соціо-технічних системах і відбиває соціальну стабільність і зміни, такі як поява нових груп, дискусій і лідерів^{[12][13][14][15][36]}. Динамічний аналіз мережі фокусується на метамережах, складених з вузлів багатьох різних видів (об'єктів) та множинних типах зв'язків^[en]. Ці об'єкти можуть дуже варіюватися^[12]. Прикладами можуть бути люди, організації, теми, ресурси, завдання, події, місця розташування і віри (погляди).

Техніки динамічної мережі особливо зручні для оцінки часових трендів, виділення лідерів, що з'являються, і дослідження коеволюції людей та ідей.

Аналіз біологічних мереж[ред. | ред. код]

При недавньому вибуховому збільшенні публічно доступних біологічних даних аналіз молекулярних мереж набув значного інтересу. Аналіз у цих умовах тісно пов'язаний з аналізом соціальної мережі, але часто фокусується на локальних закономірностях у мережі. Наприклад, мережеві мотиви — це маленькі підграфи, які надмірно представлені в мережі. Мотиви активності подібні надмірно представленим закономірностям у властивостях вузлів і ребер у мережі, які надмірно представлені в мережевій структурі. Аналіз біологічних мереж привів до розвитку мережевої медицини^[en], яка розглядає ефект хвороб у интерактомі^[37].

Аналіз зв'язків[ред. | ред. код]

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

Стійкість мережі[ред. | ред. код]

Структурна стійкість мереж^[38] вивчається за допомогою теорії перколяції. Коли критична частка вузлів видаляється з мережі, мережа розпадається на дрібні кластери. Цей феномен називається перколяцією^[39] і являє собою тип фазового переходу «порядок-безлад» з критичним значенням.

Аналіз пандемії[ред. | ред. код]

SIR-модель в епідеміології належить до найвідоміших алгоритмів передбачення поширення глобальних пандемій в інфікованій популяції.

Від стану сприйнятливості до зараження[ред. | ред. код]

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

Формула вище описує силу інфекції для кожної сприйнятливої одиниці в зараженій популяції, де ${\displaystyle \beta }$ еквівалентне швидкості поширення хвороби.

Для відстеження змін цієї сприйнятливої одиниці в зараженій популяції:

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

Аналіз Web-посилань[ред. | ред. код]

Деякі алгоритми ранжування пошукових систем використовують засновані на посиланнях міри центральності, серед яких (у порядку появи) алгоритми Hyper Search^[en] Марчіорі^[en], PageRank Google, алгоритм HITS Клейнберга, CheiRank^[en] і TrustRank^[en]. Аналіз зв'язків може здійснюватися в інформаційній аналітиці, щоб зрозуміти і виділити інформацію з набору вебсторінок. Наприклад, це може бути аналіз зв'язків між сайтами або блогами політиків.

PageRank[ред. | ред. код]

PageRank працює шляхом випадкового вибору вузла або інтернет-сайту і «випадкового переходу» з деякою ймовірністю на інші вузли. Випадкові переходи на ці та інші вузли дозволяють оцінці PageRank повністю обійти мережу, оскільки деякі сторінки містяться на периферії мережі і їх складно оцінити.

Кожен вузол ${\displaystyle x_{i}}$ має PageRank, визначений як сума для сторінок ${\displaystyle j}$ обернених величин до числа сторінок, пов'язаних з вузлом ${\displaystyle i}$ вихідними дугами, або «півстепінь виходу» вузла ${\displaystyle j}$ на «важливість» або PageRank вузла ${\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)}}}}$

Міри центральності[ред. | ред. код]

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

• Центральність за степенем вузла мережі — це число зв'язків (вершин), інцидентних вузлу.
• Центральність за близькістю визначає, наскільки «близький» вузол мережі іншим вузлам обчисленням суми найкоротших відстаней (геодезичних шляхів) між цим вузлом і іншими вузлами мережі.
• Центральність за посередництвом визначає відносну важливість вузла шляхом вимірювання величини потоку, що протікає через цей вузол до інших вузлів у мережі. Це робиться шляхом вимірювання частки шляхів, що з'єднують всі пари вузлів і містять розглянутий вузол. Групова центральність за посередництвом вимірює величину потоку, що протікає через групу вузлів^[40].
• Центральність за впливовістю є складнішою версією ступеня центральності, коли центральність вузла не тільки залежить від числа зв'язків, інцидентних вузлу, але й від якості цих зв'язків. Цей показник якості визначається власними векторами матриці суміжності мережі.
• Центральність за Кацом вузла вимірюється як сума геодезичних (тобто найкоротших) шляхів між цим вузлом і всіма (досяжними) вузлами мережі. Ці шляхи зважені: шляхи, що з'єднують вузол з його безпосередніми сусідами, мають більшу вагу, ніж зв'язки з віддаленішими вузлами.

Поширення вмісту в мережах[ред. | ред. код]

Вміст у складній мережі може розповсюджуватися двома головними способами: поширення зі збереженням і поширення без збереження^{[прояснити][41]}. Під час поширення зі збереженням загальна кількість вмісту під час його проходження через мережу залишається сталою. Модель поширення зі збереженням можна уявити як глечик, що містить певну кількість води, яка виливається в ряд стоків, сполучених трубами. Тут глечик моделює джерело, а вода — поширюваний вміст. Ємності і з'єднувальні труби моделюють вузли і зв'язки між ними відповідно. При переході води з однієї ємності в іншу вона зникає з ємності-джерела. У поширенні без збереження кількість вмісту змінюється в міру проходження через мережу. Модель без збереження можна уявити як неперервний струмінь з водопровідного крана, що розтікається по стоках, сполучених трубами. Тут кількість води з початкового джерела не обмежена. Також будь-який стік, до якого вода дійшла, продовжує отримувати воду, навіть якщо вона проходить до інших стоків. Моделі без збереження найпридатніші для пояснення передання більшості інфекцій.

SIR-модель[ред. | ред. код]

1927 року В. О. Кермак^[en] і А. Г. Маккендрик^[en] створили модель^[en], у якій вони розглядають фіксовану популяцію всього з трьома станами — сприйнятливий, ${\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}}}$

Для формулювання цих рівнянь зроблено деякі припущення. Для першого рівняння імовірність зараження окремого представника популяції така ж, як і будь-якого іншого представник, зі швидкістю ${\displaystyle \beta }$, яка приймається як швидкість поширення інфекції або хвороби. Отже, заражений представник контактує і здатний передати хворобу ${\displaystyle \beta N}$ інших представників за одиницю часу і частка контактів заражених представників зі сприйнятливими дорівнює ${\displaystyle S/N}$. Кількість нових інфікувань за одиницю часу на одного зараженого тоді становить ${\displaystyle \beta N(S/N)}$, що дає швидкість нових заражень (або тих, хто залишає категорію сприйнятливих) як ${\displaystyle \beta N(S/N)I=\beta SI}$^[42]. Для другого і третього рівнянь вважається, що особи залишають клас сприйнятливих з тією ж швидкістю, з якою входять у клас заражених. Однак, за одиницю часу цей клас залишають ${\displaystyle \gamma }$ інфкованих (${\displaystyle \gamma }$ — середня швидкість одужання, а ${\displaystyle 1/\gamma }$ — середній час хвороби) і переходять до класу видужалих. Ці процеси, що відбуваються одночасно, описує закон діючих мас, поширена ідея, що швидкість контактів між двома групами в популяції пропорційна розміру кожної з двох розглянутих груп^[43]. Нарешті, передбачається, що швидкість зараження і одужання значно більша, ніж народження і вмирання, а тому ці фактори в моделі не враховуються.

Більше про цю модель можна дізнатися на сторінці Полігамні моделі в епідеміології.

Метод основного рівняння[ред. | ред. код]

Основне рівняння описує зростання неорієнтованої мережі, в якій на кожному кроці додається новий вузол, з'єднаний зі старим вузлом (вибраним випадково і без привілеїв). Початкова мережа містить два вузли і два зв'язки між ними в момент ${\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}$ і не буде з'єднаний з новим вузлом.

Після спрощення цієї моделі розподіл вузлів за числом зв'язків дорівнюватиме ${\displaystyle P(k)=2^{-k}}$^[44].

Ґрунтуючись на цій зростальній мережі, епідемічна модель розвивається за таким простим правилом: щоразу додається новий вузол і після вибору, до якого вузла приєднувати, вирішується, буде цей вузол зараженим чи ні. Основне рівняння для цієї епідемічної моделі

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

де ${\displaystyle r_{t}}$ визначає зараження (${\displaystyle r_{t}=1}$) або відсутність зараження (${\displaystyle r_{t}=0}$). Для цього основного рівняння отримуємо такий розв'язок:${\displaystyle {\tilde {P}}_{r}(k)=\left({\frac {r}{2}}\right)^{k}.}$^[45].

Взаємозалежні мережі[ред. | ред. код]

Взаємозалежна мережа — це система пов'язаних мереж, у яких вузли однієї або більше мереж залежать від вузлів інших мереж. Такі залежності посилюються розвитком сучасних технологій. Залежності можуть призвести до каскадних пошкоджень мереж і відносно малі пошкодження можуть спричинити катастрофічне руйнування системи. Відключення електрики демонструє важливість зв'язків мереж. Нещодавно^[коли?] розвинулась концепція вивчення каскадних порушень у системі взаємозалежних мереж^[46][47].

Багатошарові мережі[ред. | ред. код]

Багатошарові мережі — це мережі з декількома видами зв'язків^{[48][49][50][51][52][53]}. Витончені спроби змоделювати системи реального світу як багатозв'язні мережі дали цінні знання в галузі аналізу соціальних мереж^{[49][50][54][55][56][57]}, економіці, історії^[58], міському та міжнародному транспорті^{[59][60][61][62]}, екології^{[63][64][65][66]}, психології^[67], медицині, біології^[68], комерції, кліматології, фізиці^[69][70], нейроінформатиці^[71][72][73], управлінні операціями і фінансах.

Оптимізація мережі[ред. | ред. код]

Мережеві задачі, які використовують пошук оптимального шляху в будь-яких цілях, вивчаються під назвою комбінаторної оптимізації. Прикладами є потоки в мережі, задача про найкоротший шлях, транспортна задача, задача про перевезення^[en], задача про розміщення об'єктів, задача про парування, задача про призначення, задачі пакування, задача маршрутизації, метод критичного шляху і PERT (метод оцінювання та аналізу проектів).

Примітки[ред. | ред. код]

Література[ред. | ред. код]

Література для подальшого читання[ред. | ред. код]

• "Connected: The Power of Six Degrees, " https://web.archive.org/web/20111006191031/http://ivl.slis.indiana.edu/km/movies/2008-talas-connected.mov
• Cohen R., Erez K., Havlin S. Resilience of the Internet to random breakdown // Phys. Rev. Lett.. — 2000. — Т. 85, вип. 21 (16 квітня). — С. 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 (16 квітня). — С. 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 (16 квітня). — С. 888–893. — arXiv:1001.5285. — Bibcode:2010NatPh...6..888K. — DOI:10.1038/nphys1746.