如何计算网络直径

Question

我的数据存储在关系数据库mysql和PHP中。 我有一个名为“rel”的表，它有两个字段：

from_node  |  to_node
=====================
1               2
1               3
2               3

依此类推......

我如何计算网络的网络直径。 我知道它是任意两对之间最长或最短的路径，但我如何计算它？ 有没有 PHP 脚本或函数可以帮助我做到这一点？

Answer 1

假设你有一个连通图（否则最大距离是无限的）并且所有节点点都是数字......

用（from_node，to_node，1）播种一个表（从，到，距离）。 对于每个元组，必须确保 from_node 的值始终小于 to_node 的值

CREATE TABLE hops (
    from_node int not null,
    to_node int not null,
    distance int not null default 0,
    primary key (from_node, to_node, distance)
)

-- first load:
INSERT INTO hops (from_node, to_node)
SELECT from_node, to_node FROM rel;

-- iterative step
INSERT INTO hops (from_node, to_node, distance)
SELECT a.from_node, b.to_node, min(a.distance+b.distance)
FROM hops a, hops b
WHERE a.to_node = b.from_node
  AND a.from_node <> b.from_node  -- not self
  AND a.to_node <> b.to_node      -- still not self
  AND a.from_node <> b.from_node  -- no loops
  AND NOT EXISTS (                -- avoid duplicates
          SELECT * FROM hops c
          WHERE c.from_node = a.from_node
            AND c.to_node = b.to_node
            AND c.distance = a.distance+b.distance)
GROUP BY a.from_node, b.to_node

重复执行插入，直到没有插入任何行。 然后选择最大距离以获得直径。

编辑：对于具有加权顶点的图，您只需使用权重作为距离场的种子，而不是使用 1。

Answer 2

请参阅维基百科文章，了解与距离和直径相关的图形（网络）术语。 它提到了一些关于如何找到直径的注释。 关于图的连通分量的文章的这一部分还建议了一种算法发现这些连接的组件，可以很容易地调整它们来告诉您图形的直径。 （如果有多个组件，那么我相信直径是无限的。）该算法是一种基于面包/深度优先搜索的简单算法，因此实现起来应该不会很麻烦，而且效率不应该太高。也是一个很大的问题。

如果您不具备编写此内容的能力（尽管我认为不需要花费那么多精力），我建议您寻找一个好的网络/图形分析库。 那里有一些，但我不确定您想使用 PHP 查看哪些。 （您可能必须使用某种互操作性。）

无论如何，希望有所帮助。

Answer 3

我真的认为您的意思是您想要找到网络的集群系数。 此外，您想用 PHP 来完成它。 我不知道有多少好的网络分析库被移植到PHP扩展中。

但是，如果您遵循这篇文章，那么想出自己的文章应该不会（太）困难。 您不需要生成漂亮的图表，您只需找到系数即可。

如果这不是您的意思，请更新/澄清您的问题。

Answer 4

网络是一个连通图。 那么为什么不尝试根据数据构建一些图形表示并对其执行 BFS 或 DFS 呢？ 您将得到您正在寻找的东西。

Answer 5

很简单：

• 准备
  • 添加名为distance的列
  • 给所有节点的距离为-1
• 第一次迭代
  • 选择任意节点（例如第一个）
  • 给它距离1
  • 现在迭代，直到存在距离 -1 的节点
    • 更新表 SET distance=:i+1 WHERE from_node IN (SELECT to_node FROM table WHERE distance=:i)
• 第二次迭代
  • 选择一个具有最大距离（任意）的节点 - 记住它
  • 将所有距离设置回 -1
  • 将您的记住节点设置为 1
  • 再次调用迭代

最大距离是图形/网络的直径。

Answer 6

在您的示例中，您显示每个节点都链接到每个其他节点。 如果您的整个设置都是这种情况，则直径为 1。

如果您的设置是像这样的线性结构的线：

n=1, n = 2, n = 3, ... n

那么您的直径为 (n+1)/3。

如果您的设置更加不规则，具有一系列 N 个节点和 K 个链接，那么您的直径至少 logN/LogK

编辑：

n1 - n2 - n3
(n+1)/3 = 4/3

n1-n2 = 1 hop
n2 - n3 = 1 hop
n1- n2 - n3 = 2 hops
(1+1+2)/3 = 4/3