Теорія мереж

Наука про мережі
Internet_map_1024.jpg
Види мереж
Графи
Властивості
Види
Моделі
Топологія
Динаміка
  • Списки
  • Категорії

Теорія мереж — це галузь комп'ютерних та мережевих наук, яка є частиною теорії графів. Вона застосовується у багатьох дисциплінах, включаючи статистичну фізику, фізику елементарних частинок, інформатику, біологію, економіку, дослідження операцій та соціологію. Мережева теорія має справу з вивченням графів як відображень або симетричних відносин, або, більш загально, асиметричних відносин між дискретними об'єктами. Застосування теорії включає логістичні мережі, WWW, Інтернет, генно-регуляторні, метаболічні, соціальні, епістемологічні та інші мережі (більше прикладів можна знайти у списку тем мережевої теорії).

Мережева оптимізація

Мережеві задачі — це ті задачі, що включають в себе знаходження оптимального рішення; вони є предметом «комбінаторної оптимізації». Прикладами таких задач є мережевий потік, задача «найкоротшого шляху» («shortest path»), транспортна задача, задачі перевантаження, розміщення, відповідності, про призначення, пакування та маршрутизації, а також аналіз критичного шляху та PERT (програма оцінки та техніки огляду).

Аналіз мереж

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

Докладніше: Аналіз соціальних мереж

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

З 1970-х років, емпіричні дослідження мереж відіграють центральну роль у соціальній науці, — багато математичних та статистичних інструментів, що використовуються для вивчення мереж, були вперше розроблені саме в соціології.[2] Серед інших застосувань, аналіз соціальних мереж використовується, щоб зрозуміти дифузії інновацій, новин і чуток. Окрім того, аналіз соціальних мереж використовується для вивчення явищ пов'язаних зі здоров'ям людини та поширення хвороб. Він також був застосований до вивчення ринків, а саме для вивчення ролі довіри у відносинах обміну та вивчення соціальних механізмів у встановленні ціни. За допомогою аналізу вивчають поповнення (рекрутизацію) політичних рухів та громадських організацій. Він також використовується для концептуалізації наукових розбіжностей і академічного престижу. Зовсім недавно, мережевий аналіз (і близький до нього «аналіз трафіку») почав широко застосовуватись у військовій розвідці, для розкриття повстанських мереж ієрархічних типів та так званих «безлідерних» повстань.

Аналіз біологічних мереж

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

Аналіз зв'язків

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

Мережева надійність (стійкість)

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

Аналіз вебпосилань

Кілька пошукових вебалгоритмів ранжування використовують базовану на посиланнях метрику центральності (в тому числі Google's PageRank, Kleinberg's HITS алгоритм, CheiRank та TrustRank алгоритми). Аналіз посилань проводиться також в галузі науки інформаційних і комунікаційних наук, з метою зрозуміти і вміти вилучити необхідну інформацію з структури колекцій вебсторінок. Наприклад, аналіз може взаємопов'язаним між політичними вебсайтами або блогами. Інше використання — для класифікації сторінок відповідно до їх згадування в інших статтях.[5]

Вимірювання центральності

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

Групування за схожістю та несхожістю (за асортативністю та дисасортативністю)

Ці концепції були розроблені через характер вузлів («хабів») у мережі. Хабом (центровим вузлом) зазвичай називають вузли, які мають багато зв'язків. Якщо ми бачимо один лінк у вузлі, немає ніякої різниці між вузлами. Деякі хаби, посилаються на інші вузли (асортативні), в той час як інші уникають підключення до інших вузлів (дисасортативні). Вузли (хаби) є нейтральними, якщо вони мають деякі зв'язки з очікуваними випадковими ймовірностями. Існує три способи кількісно визначити ступінь кореляції.

Процеси поширення

Контент у складній мережі може поширюватися за допомогою двох основних методів: збереженого та не збереженого поширення[8]. У збереженому поширенні загальна кількість контенту, що входить в складну мережу залишається постійною при проходженні. Модель збереженого поширення найкраще може бути пояснена за допомогою глечика, в який вливають фіксовану кількість води, за допомогою кількох лійок, з'єднаних трубками. Тут глечик відображає оригінальне джерело, а вода — це контент, що поширюють. Лійки та трубки відповідно відображають вузли та зв'язки між ними. Коли вода переходить з однієї лійки в іншу, вода миттєво зникає в попередній лійці (і в повному обсязі переходить у нову лійку). В не збереженому поширенні, кількість контенту змінюється, коли він входить та проходить через складну мережу. Модель найкраще може бути пояснена на прикладі крану, я якого постійно тебе вода в ряд лійок, що пов'язані між собою трубками. Тут кількість води з початкового джерела нескінченна (кран постійно тече), крім того будь-яка лійка не просихає, навіть після того, як частина води крізь неї вже пройшла далі (в наступні лійки). Не бережене поширення є найбільш придатною моделлю для пояснення передачі більшості інфекційних захворювань, нервового збудження, інформації та чуток та ін.

Взаємозалежні мережі

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

На практиці

Див. також

Примітки

  1. ↑ Wasserman, Stanley and Katherine Faust. 1994. Social Network Analysis: Methods and Applications. Cambridge: Cambridge University Press.
  2. ↑ Newman, M.E.J. Networks: An Introduction. Oxford University Press. 2010
  3. ↑ R. Cohen, S. Havlin (2010). Complex Networks: Structure, Robustness and Function. Cambridge University Press. Архів оригіналу за 4 жовтня 2011. Процитовано 12 грудня 2012. [Архівовано 4 жовтня 2011 у Wayback Machine.]
  4. ↑ A. Bunde, S. Havlin (1996). Fractals and Disordered Systems. Springer. Архів оригіналу за 14 жовтня 2020. Процитовано 12 грудня 2012. [Архівовано 14 жовтня 2020 у Wayback Machine.]
  5. ↑ Attardi, G.; S. Di Marco, D. Salvi (1998). Categorization by Context (PDF). Journal of Universal Computer Science. 4 (9): 719—736. Архів оригіналу (PDF) за 25 жовтня 2020. Процитовано 12 грудня 2012.
  6. ↑ а б в Є.В. Мелешко, В.С. Гермак, С.М. Охотний. Дослідження методів визначення центральності акторіву соціальних мережах для задач інформаційної безпеки (PDF) (укр.) . Архів оригіналу (PDF) за 22 січня 2021. Процитовано 22 січня 2021.
  7. ↑ Restrepo, Juan, E. Ott, B. R. Hunt (2006). Characterizing the Dynamical Importance of Network Nodes and Links. Phys. Rev. Lett. 97: 094102. doi:10.1103/PhysRevLett.97.094102.
  8. ↑ Newman, M., Barabási, A.-L., Watts, D.J. [eds.] (2006) The Structure and Dynamics of Networks. Princeton, N.J.: Princeton University Press.
  9. ↑ S. V. Buldyrev, R. Parshani, G. Paul, H. E. Stanley, S. Havlin (2010). Catastrophic cascade of failures in interdependent networks. Nature. 464 (7291): 1025—28. doi:10.1038/nature08932. Архів оригіналу за 18 жовтня 2017. Процитовано 12 грудня 2012. [Архівовано 18 жовтня 2017 у Wayback Machine.]
  10. ↑ Jianxi Gao, Sergey V. Buldyrev3, Shlomo Havlin4, and H. Eugene Stanley (2011). Robustness of a Network of Networks. Phys. Rev. Lett. 107: 195701. doi:10.1103/PhysRevLett.107.195701. Архів оригіналу за 15 квітня 2021. Процитовано 12 грудня 2012. [Архівовано 2021-04-15 у Wayback Machine.]

Посилання