如何计算网络直径

Question

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

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

“and so on......” 翻译为中文是“等等……”

“如何计算网络的直径？我知道它是任意两个节点之间的最长或最短路径，但我该如何计算它呢？是否有任何PHP脚本或函数可以帮助我完成？”

- ahmed

---

你是说周长吗？网络从何时开始有形状了？ - Joe Phillips

你所说的“直径”具体是什么意思？ - DShook

这是一个与网络分析/图论相关的问题。他指的是http://en.wikipedia.org/wiki/Graph_diameter。 - Noldorin

我猜“查找直径”意味着“对于所有节点对，将‘路径’定义为‘该对之间的最小跳数’，然后将‘直径’定义为‘这些路径中的最大值’”：即直径被定义为每对节点之间的最小距离的最大值。 - ChrisW

Answer 1

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

使用（from_node，to_node，1）种子表格（from，to，distance）。对于每个元组，您必须确保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。

- jmucchiello

Answer 2

在你的例子中，你展示了每个节点都链接到其他每个节点。如果这在你的设置中始终如此，那么直径为1。

如果你的设置是像这样以线性形式排列的：

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

如果您的设置比较规则，有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

- TonyArra

---

这是真的，尽管我怀疑他的例子可能过于简化了情况。 - Noldorin

在线性结构中，直径不是（n-1）吗？这是任意两个节点之间的最长路径，因此线性设置肯定是直径为（n-1），因为从第一个节点到最后一个节点有那么多跳。我认为，简单的循环（其中节点n连接到节点1）的直径为（n-1）/2。此外，在一般情况下，应给出节点之间路径的长度；在没有更好的信息的情况下，我们都假设每次跳跃的长度为1。 - Jonathan Leffler

我是基于节点对之间的平均最短距离来计算的。这也是我找到的所有来源都认同的定义。 - TonyArra

哦 - 维基百科说： 一个顶点v的离心率ε是v和任何其他顶点之间的最大距离。 图的直径是图中任何顶点的最大离心率。也就是说，它是任意两个顶点之间的最大距离。 - Jonathan Leffler

Answer 3

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

如果您不想编写此代码（尽管我认为这不需要太多努力），我建议寻找一个好的网络/图形分析库。虽然有一些库可用，但我不确定您想使用哪些PHP库。（您可能需要使用某种互操作性。）

希望这能帮到您。

- Noldorin

Answer 4

我真的认为你想要找到一个网络的聚类系数。此外，你想用PHP来实现。我不知道有多少好的网络分析库已经被移植成了PHP扩展。

然而，如果你按照这篇文章的方法，应该不会（太）难以自己实现。你不需要生成漂亮的图表，只需要找到系数即可。

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

- Tim Post

Answer 5

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

- Artem Barger

Answer 6

这很简单：

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

这次的最大距离就是您的图/网络的直径。

- MrFox