У теорії мереж алгоритм Брандеса — це алгоритм для обчислення центральності за посередництвом (betweenness centrality) вершин у графі. Алгоритм був вперше опублікований у 2001 році Ульріком Брандесом. Центральність за посередництвом, поряд з іншими мірами центральності, є важливою метрикою в багатьох реальних мережах, таких як соціальні мережі та комп'ютерні мережі.
Визначення Існує кілька метрик центральності вузла, однією з яких є центральність за посередництвом. Для вузла У зв'язному графі центральность за посередництвом визначається як:де – загальна кількість найкоротших шляхів від вузла до вузла , та – це кількість цих шляхів, які проходять через Для незваженого графа довжина шляху вважається кількістю ребер, які він містить.
За домовленістю завджи, коли , оскільки єдиним шляхом у такому разі є порожній шлях. Також, якщо збігається з або , оскільки найкоротші шляхи не проходять крізь свої кінцеві точки.
Величинавідома як парна залежність і від (або залежність пари від ), і представляє частку найкоротших – шляхів, що проходять через . Центральність за посередництвом – це просто сума парних залежностей за всіма парами вузлів. Окрім парної залежності, також корисно визначити (одиничну) залежність від , відносно конкретної вершини :,за допомогою якої ми можемо отримати стисле формулювання.
Алгоритм Алгоритм Брандеса обчислює центральність за посередництвом усіх вузлів у графі. Для кожної вершини цей процес складається з двох етапів.
Найкоротший шлях із одного джерела Кількість найкоротших шляхів між та кожною вершиною обчислюється за допомогою пошуку в ширину (BFS). Пошук у ширину починається з , при цьому фіксується найкротша відстань кожної вершини від , що дозволяє розділити граф на дискретні рівні (шари). Крім того, для кожної вершини відстежується мноєина вершин , які знаходяться на попередньому рівні та вказують на неї. Використовуючи нотацію побудови множин, це можна записати так:.Це дає змогу вивести просту ітеративну формулу для :,яка, по суті, стверджує, що якщо знаходиться на глибині , то будь-який найкоротший шлях до глибини , продовжений на одне ребро до , стає найкоротшим шляхом до .
Зворотне поширення (або зворотній прохід) Брандес довів наступну рекурсивну формулу для залежностей вершин:,де сумуваня проводитися за всіма вершинами , які знаходяться на одне ребро далі від , ніж Ця лема усуває необхідність явного сумування всіх парних залежностей. Використовуючи цю формулу, одинична залежність від вершини на глибині визначається шаром на глибині Крім того, порядок сумування не має значення, що дозволяє використовувати підхід «знизу вгору», починаючи з найглибшого шару.
Виявляється, що залежності від від усіх інших вершин можна обчислити за час . Під час пошуку в ширину порядок відвідування вершин фіксується у структурі даних стек. Потім на етапі зворотного поширення вершини послідовно витягуються зі стека, що природним чином сортує їх за відстанню від , у порядку спадання.
Для кожного витягнутого зі стека вузла ми перебираємо його попередників : додається внесок у значення , а саме:.Важливо, що кожен шар повністю поширює свої залежності, перш ніж перейти до шару з меншою глибиною, завдяки самій природі пошуку в ширину. Щойно поширення повертається до джерела , кожна вершина тепер містить значення . Ці значення можна просто додати до загальної центральності , оскільки.Після ітерацій пошуку найкоротших шляхів із одного джерела та зворотного поширення, кожне значення містить центральність за посередництвом для .
Псевдокод Наведений нижче псевдокод ілюструє алгоритм Брандеса на незваженому орієнтованому графі. алгоритм Брандеса(Граф) є: для кожного u в Граф.Вершини: CB[u] ← 0
для кожного s в Граф.Вершини: // Ініціалізація для кожного джерела s для кожного v в Граф.Вершини: δ[v] ← 0 // Одинична залежність s від v prev[v] ← порожній список // Безпосередні попередники v під час BFS σ[v] ← 0 // Кількість найкоротших шляхів від s до v dist[v] ← null // Відстані спочатку невідомі
σ[s] ← 1 // Крім початкової вершини dist[s] ← 0
Q ← черга, що містить лише s // Для пошуку в ширину (BFS) S ← порожній стек // Фіксація порядку відвідування вершин
// --- ЕТАП 1: Найкоротші шляхи з одного джерела (SSSP) ---
поки Q не порожня: u ← Q.dequeue() // Витягти з черги S.push(u) // Додати у стек для майбутнього зворотного проходу
для кожного v у Граф.Сусіди[u]: // Якщо вершина v знайдена вперше якщо dist[v] = null: dist[v] ← dist[u] + 1 Q.enqueue(v)
// Якщо шлях через u до v є найкоротшим якщо dist[v] = dist[u] + 1: σ[v] ← σ[v] + σ[u] prev[v].append(u)
// --- ЕТАП 2: Зворотне поширення залежностей (Backpropagation) ---
поки S не порожній: v ← S.pop() // Витягуємо вершини у зворотному порядку (від дальніх до s)
для кожного u в prev[v]: // Накопичення залежності за рекурсивною формулою δ[u] ← δ[u] + (σ[u] / σ[v]) * (1 + δ[v])
// Додаємо обчислену залежність до загальної центральності вузла якщо v ≠ s: CB[v] ← CB[v] + δ[v] // Для неорієнтованих графів результат зазвичай ділять навпіл у кінці
повернути CB
Аналіз часової скласності Час виконання алгоритму виражається через кількість вершин та кількість ребер .
Для кожної вершини ми запускаємо пошук у ширину, який займає часу. Оскільки граф є зв'язним, компонент поглинає термін , оскільки кількість ребер становить щонайменше .
На етапі зворотного поширення кожна вершина витягується зі стека, і проводиться ітерація по її попередниках. Оскільки кожен запис про попередника відповідає ребру в графі, цей етап також обмежений часом .
Таким чином, загальний час виконання алгоритму становить , що є значним покращенням порівняно з часовим обмеження , яких досягли попередні алгоритми. Крім того, алгоритм Брандеса покращує просторову складність наївних алгоритмів, які зазвичай потребують пам'яті. Алгоритм Брандеса зберігає щонайбільше попередників, разом із даними для кожної вершини, що робить його додаткову просторову складність рівною
Варіанти Алгоритм можна узагальнити для зважених графів, використовуючи алгоритм Дейкстри замість пошуку в ширину. При роботі з неорієнтованими графами центральність за посередництвом можна поділити на 2, щоб уникнути подвійного врахування кожного шляху та його зворотного аналога. Також існують варіанти для обчислення різних мір центральності, зокрема посередництва для шляхів довжиною не більше ніж , реберної центральності (edge betweenness), навантажувальної центральності (load betweenness) та стресової центральності (stress betweenness).
Список використаних джерел