PHP berechnet Zentralität von Knoten in einem Netzwerk

-2

Ich bin auf der Suche nach einem Weg, die closeness- und die Between-Zentralität für einen Satz von Netzknoten zu berechnen.PHP berechnet Zentralität von Knoten in einem Netzwerk

Als Eingabe Ich habe ein Json-Objekt mit dem Start-Knoten Endknoten und den Rand-Informationen:

[{ 
    "publication": 4, 
    "origin": 10, 
    "destination": 11 
}, 

...., 

{ 
    "publication": 5, 
    "origin": 10, 
    "destination": 12 
}, { 
    "publication": 8, 
    "origin": 12, 
    "destination": 13 
}]

Wie mit einer Nachbarschaftsmatrix für sehr große Datensätze ineffizienten bekomme, ich suche eine alternative Möglichkeit, die Zentralität zu berechnen. Wäre Dijkstras Algorithmus eine Option, da ich einen ungerichteten/ungewichteten Graphen habe? Und wie würde ich es implementieren, um diesen JSON als Eingabe zu verwenden?

Quelle

2017-01-12 Phil

Dijkstra-Algorithmus gegeben werden, ist für * gewichtet * Graphen, wie ist diese gewichtet? – Rafael

Ihre Daten sind auch nicht in einer Matrix ... – Rafael

Sie können Dijkstra-Algorithmus verwenden. Auch Dijkstras Algorithmus interessiert nicht, ob Sie eine Adjazenzliste oder eine Adjazenzmatrix verwenden, solange Sie dieses Detail mit Hilfe einer geeigneten Datenstruktur abstrahieren, Sie werden nur eine Geschwindigkeitsstrafe erleiden (was der Kompromiss ist, die Platzstrafe zu vermeiden) Sie haben, wenn eine Matrix für die zugrunde liegende Grafik) – apokryfos

Um Ihnen den Einstieg Sie Folgendes tun:

$edgeList = json_decode($thatJSONDataYouHaveInTheQuestion,true); 
$graph = []; 
foreach ($edgeList as $edgeData) { 
    $graph[$edgeData["origin"]][$edgeData["destination"]] = isset($graph[$edgeData["origin"]][$edgeData["destination"]])?$graph[$edgeData["origin"]][$edgeData["destination"]]+1:1; 
    //$graph[$edgeData["destination"]][$edgeData["origin"]] = isset($graph[$edgeData["destination"]][$edgeData["origin"]])?$graph[$edgeData["destination"]][$edgeData["origin"]]+1:1 //Uncomment for undirected graphs 
}

Beachten Sie, dass Multi-Kanten, die Anzahl an $graph["sourceN"]["targetN"] Jetzt angezeigt sind Sie eine sehr sehr einfache Graphenstruktur haben. Sie können wie die Dinge tun:

function containsEdge($graph, $source, $target) { 
    return isset($graph[$source]) && isset($graph[$source][$target]) && $graph[$source][$target] > 0; 
}

Oder im Grunde tun, was Sie tun müssen, um Dijkstra-Algorithmus in PHP zu implementieren.

Die Knoten von array_keys($graph) zum Beispiel oder alle benachbarten Kanten zu einem Knoten gegeben sind durch array_keys($graph["node"])

Quelle

2017-01-12 16:46:04 apokryfos

Verwendung Dies führt zu einem „undefiniert Offset“ Fehlern in dem if-Bedingung – Phil

@Phil aktualisiert (mit isset Prüfung). – apokryfos

PHP berechnet Zentralität von Knoten in einem Netzwerk

Antwort

Verwandte Themen