Центральність

Показники центральності або близькості до центру в теорії графів та аналізі мереж визначають найважливіші вершини графу. Їх використовують для виявлення найвпливовішої особи (осіб) у соціальній мережі, ключових вузлів інфраструктури в інтернеті або міських мережах і розносників хвороби. Концепції центральності спочатку розвивалися в аналізі соціальних мереж і багато термінів центральності використовуються для вимірювання соціологічних першоджерел[2]. Не слід плутати ці показники з метриками впливу вузлів, які шукають кількісні характеристики впливу кожного з вузлів у мережі.

A) Центральність за посередництвом[1], B) центральність за близькістю[1], C) центральність за впливовістю, D) центральність за степенем[1], E) гармонічна центральність і F) центральність за Кацом того самого графу.

Визначення та опис центральності

Показники центральності є відповідями на питання «Що характеризує важливість вершини?». Відповідь дається в термінах дійснозначної функції на вершинах графу, значення якої (як очікується) забезпечують ранжування, яке визначає найважливіші вузли[3][4][5].

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

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

Опис потоками в мережі

Мережу можна вважати описом шляхів, якими щось тече. Це дозволяє опис на основі типів потоків і типів шляхів, закодованих центральністю. Потік може бути заснований на перенесенні, де кожен неподільний елемент проходить від одного вузла до іншого подібно до доставки пакунків з поштового відділення до будинку клієнта. В іншому випадку, проходячи в наступний вузол елемент розмножується, так що і джерело, і ціль містять цей елемент. Прикладом такого випадку є поширення чуток, коли інформація поширюється приватно, при цьому в кінці процесу і джерело, і ціль виявляються поінформованими. Останнім випадком є паралельне розмноження, коли елемент розмножується за кількома зв'язками одночасно на зразок трансляції по радіо, що забезпечує надходження тієї самої інформації багатьом слухачам одночасно[4].

Аналогічно, вид шляху можна обмежити: геодезичними (найкоротші шляхи), шляхами (жодна вершина не відвідується більше одного разу), ланцюгами (вершини можуть відвідуватися по кілька разів, але по жодному ребру не проходять двічі) або маршрутами (і вершини, і ребра можуть зустрітися кілька разів) [4].

Опис за структурою обходів

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

Аналогічно, підрахунок може захоплювати або обсяг, або довжину маршруту. Обсяг — це повне число маршрутів даного типу. Три приклади з попереднього абзацу потрапляють у цю категорію. Довжина — це відстань від цієї вершини до інших вершин графу. Центральність за близькістю до інших вузлів Фрімана, повна геодезична відстань від цієї вершини до всіх інших вершин є найвідомішим прикладом[6]. Зауважте, що ця класифікація залежить від типу підраховуваних маршрутів (тобто маршрути, ланцюги, шляхи чи геодезичні).

Боргатті і Еверетт висловили думку, що ця типологія дає уявлення, як порівнювати міри центральності. Центральності, що потрапляють в ту саму комірку в цій 2×2 класифікації, досить схожі, щоб бути прийнятними альтернативами, і можна обґрунтовано порівнювати, який показник кращий для даної задачі. Міри з різних комірок, однак, абсолютно різні. Будь-яке визначення відносної придатності може відбуватися тільки у визначеному контексті, яка категорія більш придатна і що робить порівняння неможливим[6].

Радіально-об'ємні центральності, що існують на спектрі

Опис структурою маршруту показує, що майже всі вживані центральності є радіально-об'ємними мірами. Це наштовхує на думку, що центральність вершини є функцією центральності вершин, з якими вона асоційована. Центральності відрізняються способом асоціації.

Боначич показав, що якщо асоціація визначена в термінах маршрутів, то сімейство центральностей можна визначити на основі розглянутих довжин маршрутів[3]. Центральність за степенем підраховує кількість маршрутів завдовжки одиниця, центральність за впливовістю підраховує маршрути необмеженої довжини. Можливі також альтернативні визначення асоціацій. Альфа-центральність дозволяє вершинам мати зовнішні джерела впливу. Центральність Естради за підграфами підраховує тільки замкнуті шляхи (трикутники, чотирикутники тощо).

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

\sum _{k=0}^{\infty }A_{R}^{k}\beta ^{k}

для степенів матриці, або

\sum _{k=0}^{\infty }{\frac {(A_{R}\beta )^{k}}{k!}}

для експонент матриці, де

$k$ дорівнює довжині маршруту,
$A_{R}$ є перетвореною матрицею суміжності, а
$\beta$ є компенсаційним параметром, що забезпечує збіжність суми.

Сімейство мір Боначича не перетворює матрицю суміжності. Альфа-центральність замінює матрицю суміжності її резольвентою. Центральність підграфу замінює матрицю суміжності її слідом. Незалежно від початкового перетворення матриці суміжності всі ці підходи мають спільну обмежувальну поведінку. За прямування $\beta$ до нуля показник збігається до центральності за степенем. За прямування $\beta$ до найбільшого значення показник збігається до центральності за впливовістю[7].

Теоретико-ігрова центральність

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

Наприклад, розглянемо задачу зупинки епідемії. Перегляньмо наведене зображення мережі: які вузли слід вакцинувати? Спираючись на описані вище міри, ми хочемо розпізнати вузли, які найважливіші в поширенні хвороби. Використання підходів, заснованих на центральностях, які фокусуються на індивідуальних властивостях вузлів, виявитись поганою ідеєю. Вузли в червоному прямокутнику окремо не можуть зупинити поширення хвороби, але при розгляді їх як групи ми ясно бачимо, що вони можуть зупинити хворобу, якщо вона починається у вузлах $v_{1}$ , $v_{4}$ , $v_{5}$ . Теоретико-ігрові центральності намагаються взяти до уваги описані проблеми і можливості, використовуючи засоби теорії ігор. Підхід, запропонований у статті Михаляка (зі співавторами)[8], використовує вектор Шеплі. Зважаючи на складність обчислення (за часом) вектора Шеплі більша частина зусиль у цій галузі вкладається в розробку нових алгоритмів і методів, які спираються на конкретну топологію мережі і особливий характер завдання. Такий підхід може скоротити часову складність алгоритму з експоненціальної до поліноміальної.

Важливі обмеження

Показники центральності мають два важливих обмеження, одне з яких очевидне, інше ж ледь уловиме. Очевидне обмеження полягає в тому, що центральність, яка оптимальна для одного застосування, часто не оптимальна для іншого. Більш того, якщо б це було не так, не треба було б стільки різних центральностей. Ілюстрацію цього феномена дає повітряний змій Крекгарда, для якого три різних поняття центральності дають три різних найбільш центральних вершини[9].

Слабко вловиме обмеження полягає в тому, що має місце повсюдна омана: центральність вершини відбиває відносну важливість вершин. показники центральності розроблялися явно для ранжування, що дозволяє виділяти найважливіші вершини[3][4]. Вони роблять це добре за згаданих обмежень. Вони не розроблялися для вимірювання вузлів у загальному вигляді. Нещодавно фізики, які працюють у галузі мереж, почали розробляти метрики впливу вузлів для розв'зання цієї задачі.

Помилка двояка. По-перше, ранжування тільки за порядком вершин як їх важливістю не відбиває різниці важливостей між різними рівнями ранжування. Цей факт можна пом'якшити, застосувавши центральності Фрімана до розглянутої міри центральності, що дає деяке розуміння важливості вузлів за їхніми різними кількісними показниками центральності. Більш того, центральність Фрімана дозволяє порівняти деякі мережі за показниками вузлів з найбільшими значеннями[10].

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

Хоча неможливість узагальнення показника центральності на іншу мережу може здатися на перший погляд неочевидною, вона випливає прямо з наведених вище визначень. Складні мережі мають неоднорідну топологію. Наскільки оптимальна міра залежить від мережевої структури найважливіших вершин, настільки ж міра, оптимальна для таких вершин, не є оптимальною для решти мережі[11].

Центральність за степенем

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

Центральність за степенем вершини $v$ цього графу $G:=(V,E)$ з $|V|$ вершинами і $|E|$ ребрами, визначається як

C_{D}(v)=\deg(v)

Обчислення центральності за степенем для всіх вузлів у графі займає час $\Theta (V^{2})$ в поданні графу у вигляді щільної матриці суміжності, а для ребер займає час $\Theta (E)$ в поданні з розрідженою матрицею.

Визначення центральності за рівнем вузла можна поширити на весь граф і в цьому випадку ми говоримо про центральність графу[10]. Нехай $v*$ буде вузлом з найвищою центральністю за степенем у $G$ . Нехай $X:=(Y,Z)$ буде зв'язним графом з $|Y|$ вузлами, який максимізує таку величину (з $y*$ як вузлом з найвищою центральністю за степенем в $X$ ):

H=\sum _{j=1}^{|Y|}[C_{D}(y*)-C_{D}(y_{j})]

Відповідно, центральність за степенем графу $G$ дорівнює:

C_{D}(G)={\frac {\sum _{i=1}^{|V|}[C_{D}(v*)-C_{D}(v_{i})]}{H}}

Значення $H$ найбільше, коли граф $X$ містить один центральний вузол, з яким з'єднані всі інші вузли (граф-зірка), і в цьому випадку

H=(n-1)\cdot ((n-1)-1)=n^{2}-3n+2.

Таким чином, для будь-якого графу $G:=(V,E),$

C_{D}(G)={\frac {\sum _{i=1}^{|V|}[C_{D}(v*)-C_{D}(v_{i})]}{|V|^{2}-3|V|+2}}

Центральність за близькістю

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

Центральність за близькістю Алекс Бавелас (1950) визначив як величину, обернену до віддаленості[16][17], тобто

C(x)={\frac {1}{\sum _{y}d(y,x)}}

,

де $d(y,x)$ дорівнює відстані між вершинами $x$ і $y$ . Проте, коли кажуть про центральність за близькістю до інших вузлів, зазвичай мають на увазі його нормалізовану форму, що зазвичай отримується з попередньої формули множенням на $N-1$ , де $N$ — число вузлів у графі. Нормалізація робить можливим порівняння між вузлами графів різного розміру.

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

Гармонічна центральність

В (необов'язково зв'язному) графі гармонічна центральність обертає операції підсумовування та обернення у визначенні центральності за близькістю:

H(x)=\sum _{y\neq x}{\frac {1}{d(y,x)}}

,

де $1/d(y,x)=0$ , якщо немає шляху з $y$ в $x$ . Гармонічну центральність можна нормалізувати діленням на $N-1$ , де $N$ — число вузлів у графі.

Гармонічну центральність запропонували Марчіорі і Латора (2000)[18], потім, незалежно, Деккер (2005) під назвою «значуща центральність» (англ. valued centrality)[19], і Рочат (2009)[20].

Центральність за посередництвом

Колір (від червоного = 0 до синього = max) показує центральність за посередництвом вузла.

Центральність за посередництвом — це міра центральності вершини в графі (існує також центральність за посередництвом ребра, який тут не обговорюється). Центральність за посередництвом кількісно виражає число разів, коли вузол є мостом у найкоротшому шляху між двома іншими вузлами. Центральність за посередництвом увів Лінтон Фріман як міру кількісного вираження взаємодії людини з іншими людьми в соціальній мережі[21]. У цій концепції вершини, що мають найбільшу ймовірність опинитися на випадково вибраному найкоротшому шляху між двома випадково вибраними вершинами, мають високу центральність за посередництвом.

Центральність за посередництвом вершини $v$ в графі $G:=(V,E)$ з $V$ вершинами обчислюється так:

Для кожної пари вершин (s,t) обчислюють найкоротші шляхи між ними.
Для кожної пари вершин (s,t) визначають частку найкоротших шляхів, які проходять через розглянуту вершину (тут, вершину v).
Підсумовують ці частки за всіма парами вершин (s,t).

Компактніше центральність за посередництвом можна подати як[22]:

C_{B}(v)=\sum _{s\neq v\neq t\in V}{\frac {\sigma _{st}(v)}{\sigma _{st}}}

,

де $\sigma _{st}$ дорівнює загальному числу найкоротших шляхів від вузла $s$ до вузла $t$ , а $\sigma _{st}(v)$ дорівнює числу таких шляхів, які проходять через $v$ . Центральність за посередництвом можна нормалізувати шляхом ділення на число пар вершин, які не включають v, що для орієнтованих графів дорівнює $(n-1)(n-2)$ , а для неорієнтованих графів дорівнює $(n-1)(n-2)/2$ . Наприклад, в неорієнтованій зірці центральна вершина (яка міститься в будь-якому з можливих найкоротших шляхів) має центральність за посередництвом $(n-1)(n-2)/2$ (1, якщо нормалізувати), тоді як листки (які не містяться в жодному найкоротшому шляху) мають центральність за посередництвом 0.

З точки зору обчислень, як центральність за посередництвом, так і центральність за близькістю всіх вершин графу тягнуть за собою обчислення найкоротших шляхів між усіма парами вершин графу, що вимагає час $O(V^{3})$ за використання алгоритму Флойда — Воршелла. Однак на розріджених графах алгоритм Джонсона може виявитися ефективнішим, працюючи за час $O(V^{2}\log V+VE)$ . У разі незважених графів обчислення можна виконати за допомогою алгоритму Брандеса[22], який витрачає час $O(VE)$ . Зазвичай ці алгоритми припускають, що графи не орієнтовані і зв'язні з дозволом петель і кратних ребер. Коли ж йдеться про мережеві графи, що зображають прості зв'язки, вони часто не мають петель або кратних ребер (де ребра зображають зв'язки між людьми або вершинами). У цьому випадку використання алгоритму Брандеса кінцевий показник центральності ділиться на 2, щоб урахувати, що кожен найкоротший шлях враховано двічі[22].

Центральність за впливовістю

Центральність за впливовістю є мірою впливу вузла в мережі. Вона призначає відносні показники всім вузлам у мережі, ґрунтуючись на концепції, що зв'язки з вузлами з високим показником дають більший внесок у показник розглянутого вузла, ніж такий самий зв'язок з вузлом, що має низький показник[23][5][5]. Показник PageRank компанії Google і центральність вузла за Кацом є варіантами центральності за впливовістю[24].

Використання матриці суміжності для знаходження центральності за впливовістю

Для заданого графу $G:=(V,E)$ з $|V|$ вершинами нехай $A=(a_{v,t})$ — матриця суміжності, тобто $a_{v,t}=1$ , якщо вершина $v$ зв'язана з вершиною $t$ , і $a_{v,t}=0$ в іншому випадку. Відносний показник центральності вершини $v$ можна визначити як

x_{v}={\frac {1}{\lambda }}\sum _{t\in M(v)}x_{t}={\frac {1}{\lambda }}\sum _{t\in G}a_{v,t}x_{t}

,

де $M(v)$ — множина сусідів вершини $v$ , а $\lambda$ — константа. Після невеликих перетворень цей вираз можна переписати у векторних позначеннях як рівняння для власного вектора

\mathbf {Ax} ={\lambda }\mathbf {x}

В загальному випадку є багато різних власних значень $\lambda$ , для яких існують ненульові власні вектори. Оскільки елементи матриці суміжності невід'ємні, існує єдине найбільше власне значення, яке дійсне і додатне, за теоремою Перрона — Фробеніуса. Це найбільше власне значення дає бажану міру центральності[23]. Компонента $v^{th}$ зв'язаного власного вектора дає відносний показник центральності вершини $v$ у мережі. Власний вектор визначений з точністю до множника, так що цілком визначено тільки відношення центральностей вершин. Щоб визначити абсолютне значення показника, слід нормалізувати власний вектор, наприклад, так, щоб сума за всіма вершинами дорівнювала 1, або нормалізувати загальним числом вершин n. Степеневий метод є одним з багатьох алгоритмів отримання власних значень, який можна використати для знаходження цього домінівного власного вектора[24]. Більш того, це можна узагальнити так, що елементи матриці A можуть бути дійсними числами, які вказують на силу зв'язку як у стохастичній матриці.

Центральність за Кацом

Центральність за Кацом[25] є узагальненням центральності за степенем. Центральність за степенем вимірює кількість прямих сусідів, а центральність за Кацом вимірює кількість усіх вузлів, які можна пов'язати шляхами, при штрафування далеких вузлів. Математично ця центральність визначається як

x_{i}=\sum _{k=1}^{\infty }\sum _{j=1}^{N}\alpha ^{k}(A^{k})_{ji}

,

де $\alpha$ є коефіцієнтом ослаблення з інтервалу $(0,1)$ .

Центральність за Кацом можна розглядати як варіант центральності за впливовістю. Іншою формою центральності за Кацом є

x_{i}=\alpha \sum _{j=1}^{N}a_{ij}(x_{j}+1).

Порівняно із центральністю за впливовістю $x_{j}$ замінюється на $x_{j}+1.$

Показано[26], що головний власний вектор (відповідний найбільшому власному значенню матриці суміжності $A$ ) є границею центральності за Кацом при прямуванні $\alpha$ до ${\tfrac {1}{\lambda }}$ знизу.

PageRank

PageRank задовольняє такій рівності

x_{i}=\alpha \sum _{j}a_{ji}{\frac {x_{j}}{L(j)}}+{\frac {1-\alpha }{N}},

де

L(j)=\sum _{i}a_{ji}

дорівнює числу сусідів вузла $j$ (або числу вихідних з'єднань орієнтованого графу). Порівняно із центральністю за впливовістю і центральністю за Кацом, важливою відмінністю є масштабний множник $L(j)$ . Відмінність PageRank і центральності за впливовістю полягає в тому, що вектор PageRank є лівим власним вектором (тобто власним вектором транспонованої матриці, зауважте, що множника $a_{ji}$ має зворотний порядок індексів)[27].

Центральність за протіканням

Існує багато мір центральності для виявлення «важливості» окремого вузла складної мережі. Однак, вони відбивають важливість вузла чисто в топологічних термінах і значення вузла ніяк не залежить від його «стану». Значення залишається сталим незалежно від динаміки мережі. Це справді так навіть для мір зваженого посередництва. Проте вузол може бути також центрально розташований у термінах центральності за посередництвом або іншої міри центральності, але не бути «центрально розташованим» у контексті мережі, в якій є протікання. Протікання «зарази» відбувається в складних мережах за великою кількістю сценаріїв. Вірусна або бактеріальна інфекція може поширюватися по соціальних мережах людей, відомих як мережі контактів. Поширення хвороби можна також розглядати на високому рівні абстракції, розглядаючи мережі міст або центрів зосередження людей, з'єднаних шосейними дорогами і залізницями або авіалініями. Комп'ютерні віруси можуть поширюватися комп'ютерними мережами. Чутки або новини про ділові пропозиції та угоди можуть також поширюватися між людьми через соціальні мережі. У всіх цих сценаріях «інфекція» поширюється через зв'язки складної мережі, змінюючи «стан» вузлів оборотно або необоротно. Наприклад, в епідеміологічному сценарії індивідууми переходять зі стану «вразливий» у стан «заражений». Стани конкретних вузлів у міру поширення «зарази» можуть набувати в наведених вище прикладах двійкових значень (таких як «порцію новин отримано/не отримано»), дискретних значень (сприйнятливий/заражений/вилікуваний), або навіть неперервних (таких як частка заражених людей у місті). Спільне для всіх цих сценаріїв те, що поширення «зарази» призводить до зміни стану вузлів мережі. Для врахування цього запропоновано центральність за протіканням (англ. Percolation centrality, PC), яка вимірює важливість вузла в термінах сприяння протіканню через мережу. Цю міру запропонували Пайравінан зі співавторами[28].

Центральність за протіканням визначається для заданого вузла і в даний час пропорційно кількості «шляхів протікання», які проходять через вузол. «Шлях протікання» — це найкоротший шлях між парою вузлів, де вузол-джерело зазнав протікання (наприклад, заражений). Цільовий вузол може перебувати в стані просоченості, непросоченості або в стані часткової просоченості.

PC^{t}(v)={\frac {1}{N-2}}\sum _{s\neq v\neq r}{\frac {\sigma _{sr}(v)}{\sigma _{sr}}}{\frac {{x^{t}}_{s}}{{\sum {[{x^{t}}_{i}}]}-{x^{t}}_{v}}}

,

де $\sigma _{sr}$ — повне число найкоротших шляхів від вузла $s$ до вузла $r$ , а $\sigma _{sr}(v)$ — число таких шляхів, що проходять через $v$ . Стан просоченості вузла $i$ в момент $t$ позначається як ${x^{t}}_{i}$ і є два спеціальних випадки, коли ${x^{t}}_{i}=0$ що показує стан непротікання в момент $t$ , і коли ${x^{t}}_{i}=1$ , що свідчить про повне протікання в момент часу $t$ . Значення між цими величинами означають стани часткового протікання (наприклад, у мережі міст це може бути відсоток заражених людей у місті).

Ваги шляхів протікання залежать від рівнів просоченості, призначених початковим вузлам, виходячи з постулату, що чим вищий рівень просоченості початкового вузла, тим важливіші шляхи, що виходять з цього вузла. Вузли, що лежать на найкоротших шляхах, які починаються у вузлах з високою просоченістю, потенційно важливіші для просочування. Визначення центральності за протіканням можна розширити, щоб включити також ваги цільових вузлів. Центральність за протіканням обчислюється за час $O(NM)$ за ефективної реалізації, запозиченої зі швидкого алгоритму Брандеса, а якщо при обчисленнях потрібно враховувати ваги кінцевих вузлів, час найгіршого випадку дорівнює $O(N^{3})$ .

Кросклікова центральність

Кросклікова центральність окремого вузла в складному графі визначає зв'язки вузла з різними кліками. Вузол з високою кросокліковою центральністю сприяє поширенню інформації або хвороби в графі. Кліки — це підграфи, в яких кожен вузол з'єднаний з усіма іншими вузлами кліки. Кросклікова центральність вузла $v$ для даного графу $G:=(V,E)$ з $|V|$ вершинами і $|E|$ ребрами позначається як $X(v)$ і дорівнює числу клік, яким вершина $v$ належить. Цю міру використано в статті Фагані[29], але вперше її запропонували Еверетт і Боргатті 1998 під назвою «центральність за перекриттям клік».

Централізованість Фрімана

Централізованість будь-якої мережі є мірою того, наскільки центральним є її найцентральніший вузол порівняно з іншими вузлами[10]. Міра централізованості тоді (a) обчислюється як сума різниць центральності між центральним вузлом мережі і всіма іншими вузлами та (b) це значення ділиться на теоретично найбільшу таку суму різниць будь-якої мережі того ж розміру[10]. Тоді будь-яка міра центральності може мати свою власну міру централізованості. Формально кажучи, якщо $C_{x}(p_{i})$ є мірою центральності точки $i$ , якщо $C_{x}(p_{*})$ є найбільшою такою мірою в мережі і якщо

\max \sum _{i=1}^{N}C_{x}(p_{*})-C_{x}(p_{i})

є найбільшою сумою різниць точкової центральності $C_{x}$ для будь-якого графу з тим самим числом вузлів, то централізованість мережі дорівнює[10]

C_{x}={\frac {\sum _{i=1}^{N}C_{x}(p_{*})-C_{x}(p_{i})}{\max \sum _{i=1}^{N}C_{x}(p_{*})-C_{x}(p_{i})}}.

Міри центральності, засновані на відмінностях

У зображеній мережі зелений і червоний вузли найбільш несхожі, оскільки вони не мають спільних сусідів. Таким чином, зелений вузол робить більший внесок у центральність червоного вузла ніж сірі вузли, оскільки червоний вузол може досягти синіх вузлів тільки через зелений вузол, а сірі вузли є в надлишку, оскільки можуть бути досягнуті без посередників.

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

W\mathbf {c} =\lambda \mathbf {c}

,

де $W_{ij}=A_{ij}D_{ij}$ (покоординатний добуток), а $D_{ij}$ — довільна матриця несхожості, визначена через міру несхожості. Наприклад, через несхожість Жаккара, що задається формулою

D_{ij}=1-{\dfrac {|V^{+}(i)\cap V^{+}(j)|}{|V^{+}(i)\cup V^{+}(j)|}}

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

Слід звернути увагу, що $W$ невід'ємна, оскільки $A$ і $D$ є неотрицательными матрицями, так що можна використати теорему Перрона — Фробеніуса, щоб забезпечити єдиність розв'язку задачі вище для $\lambda =\lambda _{max}$ з невід'ємним c, що дозволяє отримати центральність кожного вузла мережі. Таким чином, центральність i-го вузла дорівнює

c_{i}={\dfrac {1}{n}}\sum _{j=1}^{n}W_{ij}c_{j},\,\,\,\,\,\,j=1,\cdots ,n

,

де $n$ дорівнює числу вузлів мережі. Деякі мережі та міри несхожості випробувано в роботі Алвареза-Сокорро (зі співавторами)[31] і в досліджуваних випадках одержано поліпшені результати.

Узагальнення

Емпіричні та теоретичні дослідження узагальнюють концепцію центральності в контексті статичних мереж на динамічну центральність[32] в контексті залежних від часу і недовговічних мереж[33][34][35].

Для узагальнення на зважені мережі див. статтю Опсала зі співавторами[36].

Концепцію центральності узагальнено також на груповий рівень. Наприклад, ступінь групового посередництва показує пропорцію геодезичних зв'язків пар (тобто шляхів з мінімальною довжиною) вузлів, що не належать до групи, які проходять через групу[37][38].

Див. також

Альфа-центральність
Модель «центр-периферія»
Відстань у графах

Примітки

Є.В. Мелешко, В.С. Гермак, С.М. Охотний. Дослідження методів визначення центральності акторіву соціальних мережах для задач інформаційної безпеки (укр.). Процитовано 22 січня 2021.
Newman, 2010.
Bonacich, 1987, с. 1170–1182.
Borgatti, 2005, с. 55–71.
Negre, Morzan, Hendrickson и др., 2018, с. E12201-E12208.
Borgatti, Everett, 2006, с. 466–484.
Benzi, Klymko, 2013, с. 686–706.
Michalak, Aadithya, Szczepański, Ravindran, Jennings, 2013, с. 607-650.
Krackhardt, 1990, с. 342–369.
Freeman, 1979, с. 215–239.
Lawyer, 2015, с. 8665.
da Silva, Viana, da F. Costa, 2012, с. P07005.
Bauer, Lizier, 2012, с. 68007.
Sikic, Lancic, Antulov-Fantulin, Stefanic, 2013, с. 1–13.
Ghoshal, Barabsi, 2011, с. 394.
Bavelas, 1950, с. 725–730.
Sabidussi, 1966, с. 581–603.
Marchiori, Latora, 2000, с. 539–546.
Dekker, 2005.
Rochat, 2009.
Freeman, 1977, с. 35–41.
Brandes, 2001, с. 163–177.
Newman, 2007, с. 1-12.
American Mathematical Society.
Katz, 1953, с. 39–43.
Bonacich, 1991, с. 155–168.
How does Google rank webpages? Шаблон:Архивировано 20Q: About Networked Life
Piraveenan, Prokopenko, Hossain, 2013, с. e53095.
Faghani, 2013, с. 1815–1826.
Alvarez-Socorro, Herrera-Almarza, González-Díaz, 2015, с. 17095.
Alvarez-Socorro A.J., Herrera-Almarza L. A., González-Díaz. Supplementary Information for Eigencentrality based on dissimilarity measures reveals central nodes in complex networks. Nature Publishing Group.
Braha, Bar-Yam, 2006, с. 59–63.
Hill, Braha, 2010, с. 046105.
Gross, Sayama, 2009.
Holme, Saramäki, 2013.
Opsahl, Agneessens, Skvoretz, 2010, с. 245–251.
Everett, Borgatti, 2005, с. 57–76.
Puzis, Yagil, Elovici, Braha, 2009.

Література

Newman M.E.J. Networks: An Introduction. — Oxford, UK : Oxford University Press, 2010.
Newman M. E. J. The mathematics of networks, // The New Palgrave Encyclopedia of Economics. — Basingstoke, : Palgrave Macmillan, 2007.

Phillip Bonacich. Power and Centrality: A Family of Measures // American Journal of Sociology. — 1987. — Т. 92, вип. 5 (13 лютого). — DOI:10.1086/228631.
Bonacich P. Simultaneous group and individual centralities // Social Networks. — 1991. — Т. 13, вип. 2 (13 лютого). — DOI:10.1016/0378-8733(91)90018-o.
Stephen P. Borgatti. Centrality and Network Flow // Social Networks. — 2005. — Т. 27 (13 лютого). — DOI:10.1016/j.socnet.2004.11.008.
Christian F. A. Negre, Uriel N. Morzan, Heidi P. Hendrickson, Rhitankar Pal, George P. Lisi, J. Patrick Loria, Ivan Rivalta, Junming Ho, Victor S. Batista. Eigenvector centrality for characterization of protein allosteric pathways // Proceedings of the National Academy of Sciences. — 2018. — Т. 115 (13 лютого). — DOI:10.1073/pnas.1810452115.
Stephen P. Borgatti, Martin G. Everett. A Graph-Theoretic Perspective on Centrality // Social Networks. — 2006. — Т. 28, вип. 4 (13 лютого). — DOI:10.1016/j.socnet.2005.11.005.
Michele Benzi, Christine Klymko. A matrix analysis of different centrality measures // SIAM Journal on Matrix Analysis and Applications. — 2013. — Т. 36, вип. 2 (13 лютого). — arXiv:1312.6722. — DOI:10.1137/130950550.
Tomasz P. Michalak, Karthik V. Aadithya, Piotr L. Szczepański, Balaraman Ravindran, Nicholas R. Jennings. Efficient Computation of the Shapley Valuefor Game-Theoretic Network Centrality // Journal of Artificial Intelligence Research. — 2013. — Т. 46 (13 лютого).
David Krackhardt. Assessing the Political Landscape: Structure, Cognition, and Power in Organizations // Administrative Science Quarterly. — 1990. — Т. 35, вип. 2 (June). — DOI:10.2307/2393394.
Renato da Silva, Matheus Viana, Luciano da F. Costa. Predicting epidemic outbreak from individual features of the spreaders // J. Stat. Mech.: Theory Exp.. — 2012. — Т. 2012 (13 лютого). — arXiv:1202.0024. — Bibcode:2012JSMTE..07..005A. — DOI:10.1088/1742-5468/2012/07/p07005.
Frank Bauer, Joseph Lizier. Identifying influential spreaders and efficiently estimating infection numbers in epidemic models: A walk counting approach // Europhys Lett. — 2012. — Т. 99 (13 лютого). — С. 68007. — arXiv:1203.0502. — Bibcode:2012EL.....9968007B. — DOI:10.1209/0295-5075/99/68007.
Mile Sikic, Alen Lancic, Nino Antulov-Fantulin, Hrvoje Stefanic. Epidemic centrality -- is there an underestimated epidemic impact of network peripheral nodes? // The European Physical Journal B. — 2013. — Т. 86, № 10 (13 лютого). — arXiv:1110.2558. — DOI:10.1140/epjb/e2013-31025-5.
Ghoshal G., Barabsi A. L. Ranking stability and super-stable nodes in complex networks. // Nat Commun. — 2011. — Т. 2 (13 лютого). — Bibcode:2011NatCo...2E.394G. — DOI:10.1038/ncomms1396.
Glenn Lawyer. Understanding the spreading power of all nodes in a network: a continuous-time perspective // Sci Rep. — 2015. — Т. 5 (13 лютого). — arXiv:1405.6707. — Bibcode:2015NatSR...5E8665L. — DOI:10.1038/srep08665. — PMID:25727453.
Linton C. Freeman. Centrality in social networks: Conceptual clarification // Social networks. — 1979. — Т. 1, вип. 3 (13 лютого). — С. 215–239. — DOI:10.1016/0378-8733(78)90021-7. Архівовано з джерела 22 лютого 2016.
Linton Freeman. A set of measures of centrality based upon betweenness // Sociometry. — 1977. — Т. 40, вип. 1 (13 лютого). — С. 35–41. — DOI:10.2307/3033543.
Alex Bavelas. Communication patterns in task-oriented groups // J. Acoust. Soc. Am. — 1950. — Т. 22, вип. 6 (13 лютого).
Sabidussi G. Sabidussi. The centrality index of a graph // Psychometrika. — 1966. — Т. 31, вип. 4 (13 лютого). — DOI:10.1007/bf02289527. — PMID:5232444.
Massimo Marchiori, Vito Latora. Harmony in the small-world // Physica A: Statistical Mechanics and its Applications. — 2000. — Т. 285, вип. 3–4 (13 лютого). — arXiv:cond-mat/0008357. — Bibcode:2000PhyA..285..539M. — DOI:10.1016/s0378-4371(00)00311-3.
Anthony Dekker. Conceptual Distance in Social Network Analysis // Journal of Social Structure. — 2005. — Т. 6, вип. 3 (13 лютого).
Yannick Rochat. Closeness centrality extended to unconnected graphs: The harmonic centrality index // Applications of Social Network Analysis, ASNA 2009. — 2009.
Ulrik Brandes. A faster algorithm for betweenness centrality // Journal of Mathematical Sociology. — 2001. — Т. 25, вип. 2 (13 лютого). — DOI:10.1080/0022250x.2001.9990249. Процитовано 11 жовтня 2011.
Newman M. E. J. The mathematics of networks. Процитовано 2006-11-09.
Katz L. A New Status Index Derived from Sociometric Index // Psychometrika. — 1953. — 13 лютого. — С. 39–43.
Piraveenan M., Prokopenko M., Hossain L. Percolation Centrality: Quantifying Graph-Theoretic Impact of Nodes during Percolation in Networks // PLOS ONE. — 2013. — Т. 8, вип. 1 (13 лютого). — Bibcode:2013PLoSO...853095P. — DOI:10.1371/journal.pone.0053095. — PMID:23349699.
Mohamamd Reza Faghani. A Study of XSS Worm Propagation and Detection Mechanisms in Online Social Networks // IEEE Transactions on Information Forensics and Security. — 2013. — Т. 8, вип. 11 (13 лютого). — DOI:10.1109/TIFS.2013.2280884.
Alvarez-Socorro A. J., Herrera-Almarza G. C., González-Díaz L. A. Eigencentrality based on dissimilarity measures reveals central nodes in complex networks // Scientific Reports. — 2015. — Т. 5 (11). — Bibcode:2015NatSR...517095A. — DOI:10.1038/srep17095. — PMID:26603652.
Braha D., Bar-Yam Y. From Centrality to Temporary Fame: Dynamic Centrality in Complex Networks // Complexity. — 2006. — Т. 12, вип. 2 (13 лютого). — arXiv:physics/0611295. — Bibcode:2006Cmplx..12b..59B. — DOI:10.1002/cplx.20156.
Hill S.A., Braha D. Dynamic Model of Time-Dependent Complex Networks // Physical Review E. — 2010. — Т. 82, вип. 4 (13 лютого). — arXiv:0901.4407. — Bibcode:2010PhRvE..82d6105H. — DOI:10.1103/physreve.82.046105. — PMID:21230343.
Adaptive Networks: Theory, Models and Applications / Gross T., Sayama H. — Springer, 2009.
Holme P., Saramäki J. Temporal Networks. — Springer, 2013.
Tore Opsahl, Filip Agneessens, John Skvoretz. Node centrality in weighted networks: Generalizing degree and shortest paths // Social Networks. — 2010. — Т. 32, вип. 3 (13 лютого). — DOI:10.1016/j.socnet.2010.03.006. Архівовано з джерела 26 лютого 2018.
Everett M. G., Borgatti S. P. Extending centrality. In P. J. Carrington, J. Scott and S. Wasserman (Eds.) // Models and methods in social network analysis. — New York : Cambridge University Press, 2005. — С. 57–76.
Puzis R., Yagil D., Elovici Y., Braha D. Collaborative attack on Internet users’ anonymity // Internet Research. — 2009. — Т. 19, вип. 1 (13 лютого). Архівовано з джерела 7 грудня 2013.

Література для подальшого читання

Koschützki, D.; Lehmann, K. A.; Peeters, L.; Richter, S.; Tenfelde-Podehl, D. and Zlotowski, O. (2005) Centrality Indices. In Brandes, U. and Erlebach, T. (Eds.) Network Analysis: Methodological Foundations, pp. 16-61, LNCS 3418, Springer-Verlag.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[Мелешко-1] Є.В. Мелешко, В.С. Гермак, С.М. Охотний. Дослідження методів визначення центральності акторіву соціальних мережах для задач інформаційної безпеки (укр.). Процитовано 22 січня 2021.

[FOOTNOTENewman2010-2] Newman, 2010.

[FOOTNOTEBonacich19871170–1182-3] Bonacich, 1987, с. 1170–1182.

[FOOTNOTEBorgatti200555–71-4] Borgatti, 2005, с. 55–71.

[FOOTNOTENegre,_Morzan,_Hendrickson_и_др.2018E12201-E12208-5] Negre, Morzan, Hendrickson и др., 2018, с. E12201-E12208.

[FOOTNOTEBorgatti,_Everett2006466–484-6] Borgatti, Everett, 2006, с. 466–484.

[FOOTNOTEBenzi,_Klymko2013686–706-7] Benzi, Klymko, 2013, с. 686–706.

[FOOTNOTEMichalak,_Aadithya,_Szczepański,_Ravindran,_Jennings2013607-650-8] Michalak, Aadithya, Szczepański, Ravindran, Jennings, 2013, с. 607-650.

[FOOTNOTEKrackhardt1990342–369-9] Krackhardt, 1990, с. 342–369.

[FOOTNOTEFreeman1979215–239-10] Freeman, 1979, с. 215–239.

[FOOTNOTELawyer20158665-11] Lawyer, 2015, с. 8665.

[FOOTNOTEda_Silva,_Viana,_da_F._Costa2012P07005-12] Silva, Viana, da F. Costa, 2012, с. P07005.

[FOOTNOTEBauer,_Lizier201268007-13] Bauer, Lizier, 2012, с. 68007.

[FOOTNOTESikic,_Lancic,_Antulov-Fantulin,_Stefanic20131–13-14] Sikic, Lancic, Antulov-Fantulin, Stefanic, 2013, с. 1–13.

[FOOTNOTEGhoshal,_Barabsi2011394-15] Ghoshal, Barabsi, 2011, с. 394.

[FOOTNOTEBavelas1950725–730-16] Bavelas, 1950, с. 725–730.

[FOOTNOTESabidussi1966581–603-17] Sabidussi, 1966, с. 581–603.

[FOOTNOTEMarchiori,_Latora2000539–546-18] Marchiori, Latora, 2000, с. 539–546.

[FOOTNOTEDekker2005-19] Dekker, 2005.

[FOOTNOTERochat2009-20] Rochat, 2009.

[FOOTNOTEFreeman197735–41-21] Freeman, 1977, с. 35–41.

[FOOTNOTEBrandes2001163–177-22] Brandes, 2001, с. 163–177.

[FOOTNOTENewman20071-12-23] Newman, 2007, с. 1-12.

[ams-24] American Mathematical Society.

[FOOTNOTEKatz195339–43-25] Katz, 1953, с. 39–43.

[FOOTNOTEBonacich1991155–168-26] Bonacich, 1991, с. 155–168.

[ANL-27] How does Google rank webpages? Шаблон:Архивировано 20Q: About Networked Life

[FOOTNOTEPiraveenan,_Prokopenko,_Hossain2013e53095-28] Piraveenan, Prokopenko, Hossain, 2013, с. e53095.

[FOOTNOTEFaghani20131815–1826-29] Faghani, 2013, с. 1815–1826.

[FOOTNOTEAlvarez-Socorro,_Herrera-Almarza,_González-Díaz201517095-30] Alvarez-Socorro, Herrera-Almarza, González-Díaz, 2015, с. 17095.

[SIE-31] Alvarez-Socorro A.J., Herrera-Almarza L. A., González-Díaz. Supplementary Information for Eigencentrality based on dissimilarity measures reveals central nodes in complex networks. Nature Publishing Group.

[FOOTNOTEBraha,_Bar-Yam200659–63-32] Braha, Bar-Yam, 2006, с. 59–63.

[FOOTNOTEHill,_Braha2010046105-33] Hill, Braha, 2010, с. 046105.

[FOOTNOTEGross,_Sayama2009-34] Gross, Sayama, 2009.

[FOOTNOTEHolme,_Saramäki2013-35] Holme, Saramäki, 2013.

[FOOTNOTEOpsahl,_Agneessens,_Skvoretz2010245–251-36] Opsahl, Agneessens, Skvoretz, 2010, с. 245–251.

[FOOTNOTEEverett,_Borgatti200557–76-37] Everett, Borgatti, 2005, с. 57–76.

[FOOTNOTEPuzis,_Yagil,_Elovici,_Braha2009-38] Puzis, Yagil, Elovici, Braha, 2009.