Наука про мережі — це наукова галузь, яка вивчає складні мережі, такі як комунікаційні, комп'ютерні, біологічні, когнітивні і семантичні мережі, а також соціальні мережі, і розглядає різні елементи або учасників процесу, представлених вузлами (або вершинами), і зв'язки між елементами або учасниками, представлені зв'язками (або ребрами). Ця наукова галузь використовує теорії і методи теорії графів, статистичної механіки, інтелектуального аналізу даних і візуалізації інформації з інформатики, моделювання логічного висновку зі статистики і соціальної структури із соціології. визначає науку про мережі як «вивчення мережевих подань фізичних, біологічних і соціальних явищ, що веде до прогностичних моделей цих явищ».
Передумови та історія Вивчення мереж зустрічається в різних дисциплінах і мережева модель використовується як засіб аналізу складних і пов'язаних даних. Найраніша стаття з цієї галузі — знаменита стаття про сім кенігсберзьких мостів, яку написав Леонард Ейлер 1736 року. Запропонований Ейлером математичний опис вершин і ребер став основою теорії графів — галузі математики, яка вивчає властивості попарних зв'язків у мережевій структурі. Теорія графів розвинулася і знайшла застосування в хімії.
Денеш Кеніг, угорський професор математики, написав 1936 року першу книгу з теорії графів «Теорія скінченних і нескінченних графів».
У 1930-х роках Якоб Леві Морено, психолог, що працював у традиціях гештальтпсихології, прибув до США. Він розробив й представив її публіці в квітні 1933 року на з'їзді студентів-медиків. Морено стверджував, що «до винаходу соціометрії ніхто не знав, як точно виглядає міжособистісна структура групи». Соціограма була поданням соціальної структури групи учнів початкової школи. Хлопці дружили з хлопцями, а дівчата — з іншими дівчатами, лише з одним винятком: один із хлопців сказав, що йому подобається одна дівчина, але почуття не було обопільним. Мережеве подання соціальної структури справило таке сильне враження, що про нього написали в газеті The New York Times. Соціограми знайшли безліч застосувань, на їх основі сформувались підходи до аналізу соціальних мереж.
Застосування теорії ймовірності в науці про мережі розвивалося як відгалуження теорії графів у вигляді восьми знаменитих статей Пала Ердеша і Альфреда Реньї про випадкові графи. Для соціальних мереж або p* є чудовою основою для подання простору ймовірнісних зв'язків, що з'являються в соціальній мережі. Альтернативним підходом до ймовірнісних мережевих структур є , яка моделює ймовірність ребер, що виникають у мережі, ґрунтуючись на історичній присутності або відсутності ребра в мережах, що виникають.
У 1998 Девід Крекгард і Кетлін Карлі представили ідею метамережі з моделлю PCANS. Вони припустили, що «всі організації утворюють три домени: Люди, Завдання і Ресурси». В їхній статті введено концепцію, що мережі виникають у кількох доменах, а тому вони взаємозв'язані. Ця галузь виросла в іншу підгалузь науки про мережі, яка називається .
Пізніше наукові зусилля були сфокусовані на математичному описі різних мережевих топологій. Дункан Ваттс поєднав дані на мережах з математичним поданням, яке описує граф «Світ тісний». Альберт-Ласло Барабаші і розробили масштабно-інваріантну мережу, яка в загальних рисах визначає мережеву топологію, яка містить вузлові вершини (хаби) зі множиною з'єднань, кількість яких зростає, зберігаючи постійне відношення числа з'єднань до числа вузлів. Хоча багато мереж, такі як інтернет, зберігають це відношення, інші мережі мають довгі хвости розподілу вузлів, які лише наближено зберігають масштабну інваріантність.
Ініціативи Міністерства оборони США Військовики США першими (1996 року) зацікавилися мережево-центричною війною як концепцією військових дій, заснованих на науці про мережі. Джон А. Парментола, керівник науково-дослідного центру і лабораторій армії США (), проголосив на армійській раді з науки і техніки () 1 грудня 2003 року, що наука про мережі стає новою галуззю досліджень в армії. BAST, відділ інженерно-технічних та природничих наук () Національної ради з досліджень () державної академії наук, наділений повноваженнями організації обговорень наукових і технологічних актуальних питань для армії і здійснення нагляду за незалежними пов'язаними з армією вивченнями, які проводить академія наук. BAST вивчає, чи може допомогти визначення рамок та фінансування нової галузі науки про мережі, закрити розрив між потребами здійснення інформаційних операцій та поточним примітивним станом фундаментальних знань про мережі.
Як результат BAST випустив 2005 року дослідницьку роботу NRC, з назвою «Наука про мережі», в якій визначено нову галузь основних досліджень у науці про мережі для армії. Ґрунтуючись на отриманих у цій роботі результатах та рекомендаціях і на подальшому звіті NRC 2007 року під назвою «Стратегія для армійських центрів науки про мережі, технології й експериментів», основні армійські дослідницькі ресурси перенаправлено на ініціалізацію нових головних дослідницьких програм у науці про мережі. Щоб побудувати нові теоретичні засади для складних мереж, підтримуються деякі нові ключові моменти дослідженнь науки про мережі, адресовані армійським лабораторіям:
Математичні моделі поведінки мереж для прогнозування продуктивності за розміром, складністю мережі й оточенням. Оптимізована продуктивність людей, необхідна для мережевої війни. Організація мереж в екосистемах та в комірках на молекулярному рівні.
2004 року з подачі Фредеріка В. Мокслі і за підтримки Девіда С. Альбертса Міністерство оборони допомогло створити, спільно з військовою академією () армії США, перший Центр науки про мережі (). Під керівництвом Мокслі і співробітників USMA створено міждисциплінарні студентські курси науки про мережі для курсантів Вест-Пойнт. Для кращого впровадження основних положень науки про мережі серед майбутніх лідерів USMA заснували також курс з п'яти дисциплін.
2006 року армія США і Велика Британія (UK) сформували () з мережевої та інформаційної науки (), партнерство армійської дослідної лабораторії Міністерства оборони Великої Британії і консорціуму індустрії та університетів США і Великої Британії. Метою альянсу є здійснення досліджень з підтримки інформаційних операцій в інтересах обох націй.
2009 року армія США сформувала , альянс зі спільних досліджень Дослідницької лабораторії Армії США, і консорціуму 30 промислових дослідницьких центрів США. Метою альянсу є розробка глибокого розуміння загальних рис переплетених соціальних/когнітивних, інформаційних і комунікаційних мереж, а як результат, покращення можливості аналізувати, передбачати, розробляти і впливати на складні переплетені системи мереж багатьох видів.
Потім, як результат цих зусиль, міністерство оборони США спонсорувало численні дослідницькі проєкти, що підтримують науку про мережі.
Властивості мереж Часто мережі мають деякі атрибути, які можуть бути обчислені для аналізу їхніх властивостей і характеристик. Поведінку цих властивостей мереж часто визначають мережеві моделі і вони можуть бути використані для аналізу, чим відрізняються одні моделі від інших. Багато визначень інших термінів, які використовуються в науці про мережі, можна знайти в статті «Словник термінів теорії графів».
Розмір Під розміром мережі може розумітися число вузлів або, рідше, число ребер , яке (для зв'язних графів без кратних ребер) може змінюватися від (дерево) до (повний граф). У разі простого графу (мережа, в якій існує максимум одне (неорієнтоване) ребро між будь-якою парою вершин і в якій жодна з вершин не з'єднана сама з собою), ми маємо . Для орієнтованих графів (без петель) . Для орієнтованих графів з дозволеними петлями . Для випадку графу, в якому можливі кратні ребра між парою вершин .
Щільність Щільність мережі з вузлами визначається як відношення числа ребер до числа можливих ребер у мережі і задається (у разі простих графів) біноміальним коефіцієнтом , що дає
Інше можливе рівняння — де зв'язки неорієнтованіhttp://psycnet.apa.org/journals/prs/9/4/172/. Це дає краще розуміння щільності мережі, оскільки неорієнтовані зв'язки можна виміряти.
Планарна мережева щільність Щільність мережі , в якій немає перетинів ребер, визначається як відношення числа ребер до максимального числа ребер у мережі з вузлами без перетинів ребер , що дає
Середній степінь вузла Степінь вузла — це кількість ребер, пов'язаних з ним. Тісно пов'язана з щільністю мережі середня щільність, (або, у разі орієнтованих графів . Множник 2 в попередній рівності виникає з того, що кожне ребро в неорієнтованому графі робить внесок у степені двох різних вершин). У моделі випадкового графу Ердеша — Реньї () ми можемо обчислити очікуване значення (рівне очікуваному значенню довільної вершини) — випадкова вершина має можливих інших вершин з імовірністю з'єднання . Тоді .
Середня довжина найкоротшого шляху (або характеристика довжини шляху) Середня довжина найкоротшого шляху обчислюється відшуканням найкоротшого шляху між усіма парами вузлів та обчисленням середньої довжини за всіма шляхами (довжиною є кількість ребер, що містяться в шляху, тобто відстань між двома вершинами в графі). Це показує нам, у середньому, число кроків, які потрібно зробити від одного вузла мережі до іншого. Поведінка математичного очікування середньої довжини найкоротшого шляху як функції числа вершин моделі випадкової мережі визначає, чи відбиває модель ефект тісного світу. Якщо вона поводиться як , модель генерує модель мереж малого світу. За зростання більшого, ніж логарифмічне, модель не дає «тісного світу». Особливий випадок зростання відомий як ефект ультратісного світу.
Діаметр мережі Як інший засіб вимірювання графів мереж можна визначити діаметр мережі, як найдовший з обчислених найкоротших шляхів у мережі. Це найкоротша відстань між двома найвіддаленішими один від одного вузлами мережі. Іншими словами, після того, як обчислено довжину найкоротшого шляху з кожного вузла у всі інші вузли, діаметр є найдовшим з усіх обчислених довжин шляхів. Діаметр є поданням лінійного розміру мережі.
Коефіцієнт кластеризації Коефіцієнт кластеризації є мірою властивості «всі мої друзі знають один одного». Це іноді описується як «друзі мого друга — мої друзі». Точніше, коефіцієнт кластеризації вузла дорівнює відношенню наявних зв'язків, що з'єднують сусідів вузла один з одним, до найбільшого числа таких зв'язків. Коефіцієнт кластеризації всієї мережі дорівнює середньому коефіцієнту кластеризації всіх вузлів. Високий коефіцієнт кластеризації для мережі є іншою ознакою тісного світу.
Коефіцієнт кластеризації -го вузла дорівнює
де — число сусідів -го вузла, а — число зв'язків між цими сусідами. Максимальна кількість можливих зв'язків між сусідами тоді дорівнює
З точки зору теорії ймовірності очікуваний локальний коефіцієнт кластеризації дорівнює ймовірності існування зв'язку між двома довільно вибраними сусідами одного вузла.
Зв'язність Спосіб, яким мережа зв'язана, грає велику роль в аналізі й інтерпретації мережі. Мережі класифікуються на чотири категорії:
Кліка/повний граф — повністю зв'язна мережа, в якій кожен вузол пов'язаний з кожним іншим вузлом. Ці мережі симетричні, оскільки всі вузли мають вхідні з'єднання від всіх інших вузлів і вихідні з'єднання у всі інші вузли. Гігантська компонента — одна зв'язна компонента містить більшість вузлів мережі. Слабко-зв'язна компонента — набір вузлів, у якому існує шлях з будь-якого вузла в будь-який інший без урахування напрямку ребер. Сильно-зв'язна компонента — набір вузлів, у якому існує орієнтований шлях з будь-якого вузла в будь-який інший.
Центральність вузла