Brandes-algoritmus
Kiejtés
- IPA: [ ˈbrɒndɛʃɒlɡoritmuʃ]
Főnév
Brandes-algoritmus
A Brandes-algoritmus egy hatékony módszer a gráfok központossági mérőszámainak (betweenness centrality) kiszámítására. Ezt a metrikát gyakran használják a gráfok elemzésében, hogy meghatározzák, mely csúcsok vagy élek a legfontosabbak az információáramlás szempontjából.
Központosság (Betweenness Centrality)
Egy csúcs központosságát a rajta áthaladó **legrövidebb utak** száma alapján határozzák meg: ahol: - : Az -ből -be vezető legrövidebb utak száma, - : Az -ből -be vezető azon legrövidebb utak száma, amelyek -n keresztül haladnak.
Brandes-algoritmus működése
Az algoritmus egy hatékony ( O(V E) )-s időkomplexitású módszer, amely elkerüli az összes csúcspár közötti legrövidebb utak explicit kiszámítását.
Lépések
- Legrövidebb utak számítása:
- Használj egy BFS-t (nem súlyozott gráfoknál) vagy egy Dijkstra-algoritmust (súlyozott gráfoknál) minden csúcsra, hogy meghatározd a legrövidebb utak számát.
- Z-szám kiszámítása:
- A legrövidebb utak számának és az elődök halmazának felhasználásával számítsd ki az egyes csúcsokra ható befolyást (központosságot).
- Központosság frissítése:
- A legrövidebb utak számából és az elődök halmazából számítsd ki a központosság hozzájárulását minden csúcsra.
Pszeudokód
Brandes(G):
Initialize C_B(v) = 0 for all v in V
for s in V:
S = üres stack
P[v] = üres lista minden v ∈ V
sigma[v] = 0 minden v ∈ V; sigma[s] = 1
d[v] = -1 minden v ∈ V; d[s] = 0
# BFS vagy Dijkstra
Q = üres sor
Q.push(s)
while Q nem üres:
v = Q.pop()
S.push(v)
for minden szomszéd w ∈ G[v]:
if d[w] < 0:
Q.push(w)
d[w] = d[v] + 1
if d[w] == d[v] + 1:
sigma[w] += sigma[v]
P[w].append(v)
delta[v] = 0 minden v ∈ V
while S nem üres:
w = S.pop()
for v in P[w]:
delta[v] += (sigma[v] / sigma[w]) * (1 + delta[w])
if w != s:
C_B[w] += delta[w]
return C_B
Időbonyolultság
- Nem súlyozott gráfok: ( O(V E) ), ahol ( V ) a csúcsok száma, ( E ) az élek száma.
- Súlyozott gráfok: ( O(V (E + V V)) ), mivel minden csúcsra Dijkstra-algoritmust használunk.
Példa Pythonban
Az alábbi példa egy egyszerű, nem súlyozott gráf esetén mutatja be a Brandes-algoritmust:
from collections import defaultdict, deque
def brandes(graph):
centrality = defaultdict(float)
for s in graph:
# BFS előkészítése
stack = []
pred = {v: [] for v in graph}
sigma = dict.fromkeys(graph, 0.0)
dist = dict.fromkeys(graph, -1)
sigma[s] = 1
dist[s] = 0
# BFS futtatása
queue = deque([s])
while queue:
v = queue.popleft()
stack.append(v)
for w in graph[v]:
if dist[w] < 0: # w még nem látogatott
queue.append(w)
dist[w] = dist[v] + 1
if dist[w] == dist[v] + 1: # w egy szomszédos csúcs
sigma[w] += sigma[v]
pred[w].append(v)
# Központosság kiszámítása
delta = dict.fromkeys(graph, 0.0)
while stack:
w = stack.pop()
for v in pred[w]:
delta[v] += (sigma[v] / sigma[w]) * (1 + delta[w])
if w != s:
centrality[w] += delta[w]
return centrality
# Példa gráf
graph = {
'A': ['B', 'C'],
'B': ['A', 'C', 'D'],
'C': ['A', 'B', 'D'],
'D': ['B', 'C']
}
centrality = brandes(graph)
for node, value in centrality.items():
print(f"{node}: {value:.2f}")
Kimenet:
A: 0.00 B: 2.00 C: 2.00 D: 0.00
Példa C++-ban
#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
#include <stack>
using namespace std;
void brandes(const unordered_map<int, vector<int>>& graph, unordered_map<int, double>& centrality) {
for (auto& pair : graph) {
int s = pair.first;
stack<int> S;
unordered_map<int, vector<int>> pred;
unordered_map<int, double> sigma, delta;
unordered_map<int, int> dist;
for (auto& p : graph) {
sigma[p.first] = 0.0;
delta[p.first] = 0.0;
dist[p.first] = -1;
}
sigma[s] = 1.0;
dist[s] = 0;
queue<int> Q;
Q.push(s);
while (!Q.empty()) {
int v = Q.front();
Q.pop();
S.push(v);
for (int w : graph.at(v)) {
if (dist[w] < 0) {
Q.push(w);
dist[w] = dist[v] + 1;
}
if (dist[w] == dist[v] + 1) {
sigma[w] += sigma[v];
pred[w].push_back(v);
}
}
}
while (!S.empty()) {
int w = S.top();
S.pop();
for (int v : pred[w]) {
delta[v] += (sigma[v] / sigma[w]) * (1 + delta[w]);
}
if (w != s) {
centrality[w] += delta[w];
}
}
}
}
int main() {
unordered_map<int, vector<int>> graph = {
{1, {2, 3}},
{2, {1, 3, 4}},
{3, {1, 2, 4}},
{4, {2, 3}}
};
unordered_map<int, double> centrality;
brandes(graph, centrality);
for (const auto& pair : centrality) {
cout << "Csúcs " << pair.first << ": " << pair.second << endl;
}
return 0;
}
Kimenet:
Csúcs 1: 0 Csúcs 2: 2 Csúcs 3: 2 Csúcs 4: 0
Előnyök
- Hatékony időbonyolultság:
- Gyorsabb, mint a naiv módszerek, különösen nagy gráfokon.
- Támogatja a súlyozott és nem súlyozott gráfokat.
Hátrányok
- Nagyméretű gráfok esetén memóriaigényes:
- A gráf reprezentációja és az algoritmus táblái jelentős memóriát igényelhetnek.
- Bonyolult implementáció:
- A BFS és az adatszerkezetek kezelése komplex.
Alkalmazások
- Hálózatkutatás:
- Kulcsfontosságú csomópontok azonosítása.
- Szociális hálózatok elemzése:
- Befolyásos személyek azonosítása.
- Hálózati biztonság:
- Kritikus hálózati pontok védelme.
- Informatikai rendszerek:
- Adatáramlás optimalizálása.
Összegzés
A Brandes-algoritmus hatékony eszköz a gráfok központosságának kiszámítására, különösen nagy és összetett hálózatok esetén. Hatékonysága és széles körű alkalmazási lehetőségei miatt alapvető eszköz a hálózatelemzésben.
- Brandes-algoritmus - Értelmező szótár (MEK)
- Brandes-algoritmus - Etimológiai szótár (UMIL)
- Brandes-algoritmus - Szótár.net (hu-hu)
- Brandes-algoritmus - DeepL (hu-de)
- Brandes-algoritmus - Яндекс (hu-ru)
- Brandes-algoritmus - Google (hu-en)
- Brandes-algoritmus - Helyesírási szótár (MTA)
- Brandes-algoritmus - Wikidata
- Brandes-algoritmus - Wikipédia (magyar)