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
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ó.
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 =
communities.append(components)
return communities
# Példa gráf
G = nx.karate_club_graph()
communities = girvan_newman(G)
for i, community in enumerate(communities, start=1):
print(f"Közösségek az {i}. iteráció után: {community}")
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 = -1;
sigma = 0;
}
dist = 0;
sigma = 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 < 0) {
q.push(w);
dist = dist + 1;
}
if (dist == dist + 1) {
sigma += sigma;
pred.push_back(v);
}
}
}
map<int, double> delta;
for (auto& n : graph) {
delta = 0;
}
while (!stack.empty()) {
int w = stack.back();
stack.pop_back();
for (int v : pred) {
double c = (sigma / sigma) * (1 + delta);
delta += c;
if (v < w) {
betweenness += c;
} else {
betweenness += 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.erase(remove(graph.begin(), graph.end(), v), graph.end());
graph.erase(remove(graph.begin(), graph.end(), u), graph.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) {
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;
}
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.