PHP計算網絡中節點的中心性

-2

我正在尋找一種方法來計算一組網絡節點的親密度和中介度。PHP計算網絡中節點的中心性

由於輸入我有一個JSON對象與起始節點的終端節點和邊緣信息：

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

...., 

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

作爲使用鄰居矩陣非常大的數據集變得inefficent，我在尋找另一種計算中心性的方法。 Dijkstra的算法會成爲一種選擇，因爲我有一個無向/無權圖嗎？我將如何實現它來使用這個json作爲輸入？

來源

2017-01-12 Phil

Dijkstra算法給出爲*加權*圖表，這是怎麼加權？ – Rafael

您的數據也不在矩陣中... – Rafael

您可以使用Dijkstra的算法。此外，只要您使用適當的數據結構抽象出這些細節，Dijkstra的算法並不在乎您是否使用鄰接列表或鄰接矩陣，您只會遭受一些速度損失（這是爲了避免空間損失的折衷您在使用矩陣作爲基礎圖時） – apokryfos

爲了讓您一開始，你可以做到以下幾點：

$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 
}

注意多邊表示，在數$graph["sourceN"]["targetN"] 現在你有一個非常非常簡單的圖形結構。你可以做這樣的事情：

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

或者基本上做你需要做的任何事情來實現Dijkstra的算法在PHP中。

的節點通過array_keys($graph)例如或所有相鄰邊緣到節點給定由array_keys($graph["node"])

來源

2017-01-12 16:46:04 apokryfos

這會導致if條件 – Phil

@Pil更新（使用isset檢查）中的「未定義偏移量」錯誤。 – apokryfos

PHP計算網絡中節點的中心性

回答

相關問題