PHP 计算网络中节点的中心性

Question

我正在寻找一种方法来计算一组网络节点的紧密性和中间性中心性。

作为输入，我有一个 json 对象，其中包含起始节点、结束节点和边缘信息：

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

 ....,

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

由于使用邻域矩阵对于非常大的数据集变得无效，我正在寻找一种替代方法来计算中心性。既然我有一个 undirected/unweighted 图，Dijkstra 的算法会是一个选项吗？我将如何实现它以使用此 json 作为输入？

Answer 1

要开始，您可以执行以下操作：

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

请注意 multi-edges 表示 $graph["sourceN"]["targetN"] 处的数字现在你有一个非常非常简单的图形结构。您可以执行以下操作：

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

或者基本上做任何你需要做的事情来实现 PHP 中的 Dijkstra 算法。

例如，节点由 array_keys($graph) 给出，或者节点的所有相邻边由 array_keys($graph["node"])

给出

PHP 计算网络中节点的中心性

PHP Calculate centrality of nodes in a network

php

json

graph

dijkstra

matrix