Wikiszótár

Girvan-Newman-algoritmus

Magyar

Kiejtés

  • IPA: [ ˈɡirvɒnːɛvmɒnɒlɡoritmuʃ]

Főnév

Girvan-Newman-algoritmus

  1. (matematika) A Girvan-Newman-algoritmus egy közösségfelderítési (community detection) algoritmus, amely a gráf éleinek központosságán (edge betweenness) alapul. Az algoritmus célja, hogy a gráf szerkezetét közösségekre bontsa azáltal, hogy iteratív módon eltávolítja a magas központosságú éleket.


Algoritmus alapelvei

  1. Edge Betweenness:
    • Egy él központossága az azon áthaladó legrövidebb utak számát jelöli.
    • Minél magasabb egy él központossága, annál több kapcsolatot közvetít különböző csomópontok között, ezért ezek eltávolítása valószínűleg szétdarabolja a gráfot.
  2. Közösségek:
    • Az algoritmus iteratív módon eltávolítja a legnagyobb központosságú éleket, amelyek valószínűleg közösségek között helyezkednek el.


Algoritmus működése

Bemenet:

  • Egy gráf ( G = (V, E) ), ahol ( V ) a csúcsok, ( E ) az élek halmaza.

Kimenet:

  • A gráf közösségekre bontott állapota.

Lépések:

  1. Edge betweenness kiszámítása:
    • Számítsd ki minden él központosságát a gráf aktuális állapotában.
  2. Legnagyobb központosságú él eltávolítása:
    • Az élt, amelynek a központossága a legnagyobb, távolítsd el a gráfból.
  3. Közösségek ellenőrzése:
    • Nézd meg, hogyan darabolódott fel a gráf. Egy gráfkomponens egy közösséget jelent.
  4. Ismétlés:
    • Ismételd az 1-3 lépéseket, amíg az összes él el nem tűnik, vagy el nem éred a kívánt közösségek számát.


Pszeudokód

GirvanNewman(G):
    while E nem üres:
        Számítsd ki minden él központosságát
        Távolítsd el a legnagyobb központosságú élt
        Ellenőrizd a gráf komponenseit
        Jegyezd fel a közösségeket
    return közösségek

Időbonyolultság

  • Legrosszabb eset: ( O(V E^2) ), ahol:
    • ( V ): a csúcsok száma,
    • ( E ): az élek száma.

Ez az időbonyolultság a központosság számítási költségéből származik, amely minden iterációban újraszámítandó.


Példa Pythonban

Az alábbi kód az NetworkX könyvtárat használja a Girvan-Newman-algoritmus egyszerű implementálásához: 

import networkx as nx

def girvan_newman(graph):
    def edge_betweenness(graph):
        return nx.edge_betweenness_centrality(graph)

    communities = []
    while graph.number_of_edges() > 0:
        # Élek központosságának kiszámítása
        betweenness = edge_betweenness(graph)
        # Legnagyobb központosságú él eltávolítása
        max_edge = max(betweenness, key=betweenness.get)
        graph.remove_edge(*max_edge)

        # Komponensek meghatározása
        components = [list(c) for c in nx.connected_components(graph)]
        communities.append(components)

    return communities

# Példa gráf
G = nx.karate_club_graph()
communities = girvan_newman(G)

for i, community in enumerate(communities[:5], start=1):
    print(f"Közösségek az {i}. iteráció után: {community}")

Példa C++-ban

A C++-ban történő implementáció bonyolultabb, mivel nincs közvetlen támogatás a Girvan-Newman-algoritmushoz. Az alábbi kód az alapvető elveket mutatja be: 

#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>

using namespace std;

// Gráf reprezentáció
using Graph = map<int, vector<int>>;

// Számítsuk ki az élek központosságát (betweenness centrality)
map<pair<int, int>, double> calculate_edge_betweenness(const Graph& graph) {
    map<pair<int, int>, double> betweenness;
    for (auto& node : graph) {
        int s = node.first;
        queue<int> q;
        map<int, int> dist;
        map<int, vector<int>> pred;
        map<int, double> sigma;

        for (auto& n : graph) {
            dist[n.first] = -1;
            sigma[n.first] = 0;
        }

        dist[s] = 0;
        sigma[s] = 1;
        q.push(s);

        vector<int> stack;
        while (!q.empty()) {
            int v = q.front();
            q.pop();
            stack.push_back(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);
                }
            }
        }

        map<int, double> delta;
        for (auto& n : graph) {
            delta[n.first] = 0;
        }

        while (!stack.empty()) {
            int w = stack.back();
            stack.pop_back();
            for (int v : pred[w]) {
                double c = (sigma[v] / sigma[w]) * (1 + delta[w]);
                delta[v] += c;
                if (v < w) {
                    betweenness[{v, w}] += c;
                } else {
                    betweenness[{w, v}] += c;
                }
            }
        }
    }

    return betweenness;
}

void girvan_newman(Graph& graph) {
    while (!graph.empty()) {
        auto betweenness = calculate_edge_betweenness(graph);
        auto max_edge = max_element(
            betweenness.begin(), betweenness.end(),
            [](const auto& a, const auto& b) { return a.second < b.second; });

        int u = max_edge->first.first;
        int v = max_edge->first.second;
        graph[u].erase(remove(graph[u].begin(), graph[u].end(), v), graph[u].end());
        graph[v].erase(remove(graph[v].begin(), graph[v].end(), u), graph[v].end());

        cout << "Eltávolított él: (" << u << ", " << v << ")\n";

        // Komponensek kiírása
        set<int> visited;
        for (auto& node : graph) {
            if (visited.find(node.first) == visited.end()) {
                cout << "Komponens: ";
                queue<int> q;
                q.push(node.first);
                while (!q.empty()) {
                    int n = q.front();
                    q.pop();
                    if (visited.find(n) == visited.end()) {
                        visited.insert(n);
                        cout << n << " ";
                        for (int neighbor : graph[n]) {
                            q.push(neighbor);
                        }
                    }
                }
                cout << endl;
            }
        }
    }
}

int main() {
    Graph graph = {
        {0, {1, 2}},
        {1, {0, 2, 3}},
        {2, {0, 1, 3}},
        {3, {1, 2}}
    };

    girvan_newman(graph);
    return 0;
}

Előnyök

  1. Közösségek feltárása:
    • Az algoritmus jól működik közösségi struktúrákat tartalmazó gráfokon.
  2. Érthető működés:
    • Az élközpontosság fogalma intuitív és jól interpretálható.


Hátrányok

  1. Nagy számítási költség:
    • Az algoritmus nagy gráfokon lassú lehet (( O(V E^2) )).
  2. Fokozatos szétdarabolás:
    • Nem adja meg egyértelműen, hogy melyik a végleges közösségi struktúra.


Alkalmazások

  1. Szociális hálózatok:
    • Közösségek azonosítása (baráti csoportok, influencerek csoportjai).
  2. Hálózatelemzés:
    • Hálózati struktúrák és kritikus kapcsolatok feltárása.
  3. Biológiai hálózatok:
    • Fehérjék vagy gének közötti kapcsolatok közösségi elemzése.


Összegzés

A Girvan-Newman-algoritmus egy hatékony eszköz a gráf közösségeinek feltárására, különösen kisebb vagy közepes méretű gráfokon. Bár számításigényes, az élközpontosság alapú megközelítés intuitív és informatív, különösen a hálózatelemzés és a közösségi hálók területén.

Fordítások

Tartalom

További információk

A lap eredeti címe: „https://hu.wiktionary.org/w/index.php?title=Girvan-Newman-algoritmus&oldid=3479737”