Показники центральності або близькості до центру в теорії графів та аналізі мереж визначають найважливіші вершини графа. Їх використовують для виявлення найвпливовішої особи (осіб) у соціальній мережі, ключових вузлів інфраструктури в інтернеті або міських мережах і розносників хвороби. Концепції центральності спочатку розвивалися в аналізі соціальних мереж і багато термінів центральності використовуються для вимірювання соціологічних першоджерел. Не слід плутати ці показники з , які шукають кількісні характеристики впливу кожного з вузлів у мережі.
Визначення та опис центральності Показники центральності є відповідями на питання «Що характеризує важливість вершини?». Відповідь дається в термінах дійснозначної функції на вершинах графа, значення якої (як очікується) забезпечують ранжування, яке визначає найважливіші вузли.
Слово «важливість» має широкий спектр значень, що призводить до багатьох різних визначень центральності. Запропоновано дві схеми категоризації. «Важливість» можна розглядати стосовно типу потоку або передавання даних через мережу. Це дозволяє класифікувати центральності за типом потоку, який вважається важливим. З іншого боку, «важливість» можна пов'язати зі впливом на цілісність мережі. Це дозволяє класифікувати центральності на основі того, як вони вимірюють внесок у згуртованість мережі. Обидва ці підходи поділяють центральності на різні категорії. Центральність, яка придатна для однієї категорії, часто буває непридатною, коли застосовується до іншої категорії.
Якщо центральності категоризуються за їх участю, стає зрозуміло що більшість центральностей належать до однієї категорії. Кількість маршрутів, що починаються з даного вузла, відрізняється лише тим, яким чином маршрути визначаються і підраховуються. Обмеження домовленостей для цієї групи дозволяє опис центральностей на спектрі маршрутів від довжини один (центральність за степенем) до необмежених маршрутів (центральність за впливовістю). Спостереження, що багато центральностей поділяють ці зв'язки, пояснює високий рівень кореляції між цими показниками.
Опис потоками в мережі Мережу можна вважати описом шляхів, якими щось тече. Це дозволяє опис на основі типів потоків і типів шляхів, закодованих центральністю. Потік може бути заснований на перенесенні, де кожен неподільний елемент проходить від одного вузла до іншого подібно до доставки пакунків з поштового відділення до будинку клієнта. В іншому випадку, проходячи в наступний вузол елемент розмножується, так що і джерело, і ціль містять цей елемент. Прикладом такого випадку є поширення чуток, коли інформація поширюється приватно, при цьому в кінці процесу і джерело, і ціль виявляються поінформованими. Останнім випадком є паралельне розмноження, коли елемент розмножується за кількома зв'язками одночасно на зразок трансляції по радіо, що забезпечує надходження тієї самої інформації багатьом слухачам одночасно.
Аналогічно, вид шляху можна обмежити: геодезичними (найкоротші шляхи), шляхами (жодна вершина не відвідується більше одного разу), ланцюгами (вершини можуть відвідуватися по кілька разів, але по жодному ребру не проходять двічі) або маршрутами (і вершини, і ребра можуть зустрітися кілька разів) .
Опис за структурою обходів Іншу класифікацію можна отримати зі способу побудови центральності. Це знову призводить до розбиття на два класи — радіальні або медіанні. Радіальні центральності підраховують кількість маршрутів, що починаються/закінчуються в даній вершині. Центральність за степенем і центральність за впливовістю є прикладами радіальних показників центральності, підраховуючи число маршрутів довжини один або необмеженої довжини. Медіанні центральності підраховують маршрути, які проходять через дану вершину. Канонічним прикладом є центральність за посередництвом Фрімана — кількість найкоротших маршрутів, які проходять через дану вершину.
Аналогічно, підрахунок може захоплювати або обсяг, або довжину маршруту. Обсяг — це повне число маршрутів даного типу. Три приклади з попереднього абзацу потрапляють у цю категорію. Довжина — це відстань від цієї вершини до інших вершин графа. Центральність за близькістю до інших вузлів Фрімана, повна геодезична відстань від цієї вершини до всіх інших вершин є найвідомішим прикладом. Зауважте, що ця класифікація залежить від типу підраховуваних маршрутів (тобто маршрути, ланцюги, шляхи чи геодезичні).
Боргатті і Еверетт висловили думку, що ця типологія дає уявлення, як порівнювати міри центральності. Центральності, що потрапляють в ту саму комірку в цій 2×2 класифікації, досить схожі, щоб бути прийнятними альтернативами, і можна обґрунтовано порівнювати, який показник кращий для даної задачі. Міри з різних комірок, однак, абсолютно різні. Будь-яке визначення відносної придатності може відбуватися тільки у визначеному контексті, яка категорія більш придатна і що робить порівняння неможливим.
Радіально-об'ємні центральності, що існують на спектрі Опис структурою маршруту показує, що майже всі вживані центральності є радіально-об'ємними мірами. Це наштовхує на думку, що центральність вершини є функцією центральності вершин, з якими вона асоційована. Центральності відрізняються способом асоціації.
Боначич показав, що якщо асоціація визначена в термінах маршрутів, то сімейство центральностей можна визначити на основі розглянутих довжин маршрутів. Центральність за степенем підраховує кількість маршрутів завдовжки одиниця, центральність за впливовістю підраховує маршрути необмеженої довжини. Можливі також альтернативні визначення асоціацій. дозволяє вершинам мати зовнішні джерела впливу. Центральність Естради за підграфами підраховує тільки замкнуті шляхи (трикутники, чотирикутники тощо).
Основою таких мір є спостереження, що матриці суміжності графа дають число маршрутів з довжиною, рівною мірі. Аналогічно, експонента матриці тісно пов'язана з числом маршрутів заданої довжини. Початкове перетворення матриці суміжності дозволяє різні визначення підрахунку типів маршрутів. За будь-якого підходу центральність вершини можна виразити як нескінченну суму, або
для степенів матриці, або
для експонент матриці, де
дорівнює довжині маршруту, є перетвореною матрицею суміжності, а є компенсаційним параметром, що забезпечує збіжність суми.
Сімейство мір Боначича не перетворює матрицю суміжності. замінює матрицю суміжності її резольвентою. Центральність підграфа замінює матрицю суміжності її слідом. Незалежно від початкового перетворення матриці суміжності всі ці підходи мають спільну обмежувальну поведінку. За прямування до нуля показник збігається до центральності за степенем. За прямування до найбільшого значення показник збігається до центральності за впливовістю.
Теоретико-ігрова центральність Загальна властивість більшості згаданих вище стандартних заходів полягає в тому, що вони оцінюють важливість вузла, фокусуючись лише на ролі, яку вузол відіграє сам по собі. Однак у багатьох застосуваннях такий підхід не є адекватним, оскільки, застосовуючи міри до груп вузлів, слід врахувати взаємодію вузлів.
Наприклад, розглянемо задачу зупинки епідемії. Перегляньмо наведене зображення мережі: які вузли слід вакцинувати? Спираючись на описані вище міри, ми хочемо розпізнати вузли, які найважливіші в поширенні хвороби. Використання підходів, заснованих на центральностях, які фокусуються на індивідуальних властивостях вузлів, виявитись поганою ідеєю. Вузли в червоному прямокутнику окремо не можуть зупинити поширення хвороби, але при розгляді їх як групи ми ясно бачимо, що вони можуть зупинити хворобу, якщо вона починається у вузлах ,,. Теоретико-ігрові центральності намагаються взяти до уваги описані проблеми і можливості, використовуючи засоби теорії ігор. Підхід, запропонований у статті Михаляка (зі співавторами), використовує вектор Шеплі. Зважаючи на складність обчислення (за часом) вектора Шеплі більша частина зусиль у цій галузі вкладається в розробку нових алгоритмів і методів, які спираються на конкретну топологію мережі і особливий характер завдання. Такий підхід може скоротити часову складність алгоритму з експоненціальної до поліноміальної.
Важливі обмеження Показники центральності мають два важливих обмеження, одне з яких очевидне, інше ж ледь уловиме. Очевидне обмеження полягає в тому, що центральність, яка оптимальна для одного застосування, часто не оптимальна для іншого. Більш того, якщо б це було не так, не треба було б стільки різних центральностей. Ілюстрацію цього феномена дає повітряний змій Крекгарда, для якого три різних поняття центральності дають три різних найбільш центральних вершини.
Слабко вловиме обмеження полягає в тому, що має місце повсюдна омана: центральність вершини відбиває відносну важливість вершин. показники центральності розроблялися явно для ранжування, що дозволяє виділяти найважливіші вершини. Вони роблять це добре за згаданих обмежень. Вони не розроблялися для вимірювання вузлів у загальному вигляді. Нещодавно фізики, які працюють у галузі мереж, почали розробляти для розв'зання цієї задачі.
Помилка двояка. По-перше, ранжування тільки за порядком вершин як їх важливістю не відбиває різниці важливостей між різними рівнями ранжування. Цей факт можна пом'якшити, застосувавши центральності Фрімана до розглянутої міри центральності, що дає деяке розуміння важливості вузлів за їхніми різними кількісними показниками центральності. Більш того, центральність Фрімана дозволяє порівняти деякі мережі за показниками вузлів з найбільшими значеннями.
По-друге, властивості, які (правильно) відбивають найважливіші вершини в даній мережі/застосуванні, не обов'язково узагальнюються на інші вершини. Для більшості інших вузлів мережі ранжування може виявитися безглуздим. Це пояснює, наприклад, чому тільки перші кілька результатів пошуку зображення в Google з'являються в адекватному порядку. PageRank є вкрай нестабільною мірою, демонструючи часто протилежний ранг після невеликої зміни параметра пошуку.
Хоча неможливість узагальнення показника центральності на іншу мережу може здатися на перший погляд неочевидною, вона випливає прямо з наведених вище визначень. Складні мережі мають неоднорідну топологію. Наскільки оптимальна міра залежить від мережевої структури найважливіших вершин, настільки ж міра, оптимальна для таких вершин, не є оптимальною для решти мережі.
Центральність за степенем Історично першим і концептуально найпростішим поняттям є центральність за степенем, який визначається як число зв'язків, інцидентних вузлу (тобто число зв'язків, які має вузол). Степінь можна інтерпретувати в термінах прямого ризику вузла підхопити щось, що проходить через мережу (наприклад, вірус або якусь інформацію). У разі орієнтованої мережі (де зв'язки мають напрям) зазвичай визначають дві різні міри центральності за степенем, а саме, напівстепінь входу і напівстепінь виходу. Відповідно, напівстепінь входу — це число зв'язків з вузлом, а напівстепінь виходу — це число зв'язків вузла з іншими вузлами. Коли зв'язок асоціюється з деяким позитивним аспектом, таким як дружба чи співпраця, напівстепінь входу часто інтерпретується як вид популярності, а напівстепінь виходу як товариськість.
Центральність за степенем вершини цього графа з вершинами і ребрами, визначається як
Обчислення центральності за степенем для всіх вузлів у графі займає час в поданні графа у вигляді щільної матриці суміжності, а для ребер займає час в поданні з розрідженою матрицею.
Визначення центральності за рівнем вузла можна поширити на весь граф і в цьому випадку ми говоримо про центральність графа. Нехай буде вузлом з найвищою центральністю за степенем у . Нехай буде зв'язним графом з вузлами, який максимізує таку величину (з як вузлом з найвищою центральністю за степенем в ):
Відповідно, центральність за степенем графа дорівнює:
Значення найбільше, коли граф містить один центральний вузол, з яким з'єднані всі інші вузли (граф-зірка), і в цьому випадку
Таким чином, для будь-якого графа
Центральність за близькістю