JSON — PHP Рассчитать центральность узлов в сети
Я ищу способ для вычисления близости и центральности между множеством сетевых узлов.
В качестве входных данных у меня есть json-объект с конечным узлом начального узла и информация о ребре:
[{
"publication": 4,
"origin": 10,
"destination": 11
},
....,
{
"publication": 5,
"origin": 10,
"destination": 12
}, {
"publication": 8,
"origin": 12,
"destination": 13
}]
Поскольку использование матрицы соседей становится неэффективным для очень больших наборов данных, я ищу альтернативный способ вычисления центральности. Будет ли алгоритм Дейкстры вариант, так как у меня есть неориентированный / невзвешенный граф? И как бы я реализовать его, чтобы использовать этот JSON в качестве ввода?
Решение
Для начала вы можете сделать следующее:
$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;
}
Или, в основном, делайте все, что вам нужно для реализации алгоритма Дейкстры в PHP.
Узлы задаются array_keys($graph) например, или все смежные ребра узла array_keys($graph["node"])
Другие решения
Других решений пока нет …