Теорія мереж

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку

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

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

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

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

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

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

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

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

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

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

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

Мережева надійність (стійкість)[ред. | ред. код]

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

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

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

Вимірювання центральності[ред. | ред. код]

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

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

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

Процеси поширення[ред. | ред. код]

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

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

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

На практиці[ред. | ред. код]

Див. також[ред. | ред. код]

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

  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. A. Bunde, S. Havlin (1996). Fractals and Disordered Systems. Springer. 
  5. Attardi, G.; S. Di Marco, D. Salvi (1998). Categorization by Context. Journal of Universal Computer Science 4 (9): 719–736. 
  6. 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. 
  7. Newman, M., Barabási, A.-L., Watts, D.J. [eds.] (2006) The Structure and Dynamics of Networks. Princeton, N.J.: Princeton University Press.
  8. 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. 
  9. 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. 

Посилання[ред. | ред. код]