介绍

图的密度

图的密度表示图中存在的边与图可包含的最大边数之间的比率。从概念上讲，它提供了一个关于一个图在边的连接（edge connectivity）方面的密度的概念。当我们有一个庞大的网络并想在网络中添加新的边时，它特别有用。此外，图的密度让我们了解到我们还能在网络中增加多少条边。

现在，在推导图密度的公式之前，让我们谈谈如何计算一个简单的有向图和无向图中的最大边数。让我们看一下一个简单的无向图 G1:

现在，我们要推导出一个标准的公式来计算一个简单的无向图中的最大边数:

同样地，我们可以用有向图中的两条双向边来代替每条无向边。因此，最大的边数可以用类似的公式来计算：

我们现在可以定义图形密度公式。图中存在的边除以该图可包含的最大边数。让我们看看一个简单无向图的公式:

同样地，我们可以为有向图重写前面的密度公式:

对于一个完全有向或无向图，密度总是 1。在一个完全有向图或无向图的情况下，它已经有最大数量的边，我们不能再增加任何边。此外，它还表明该图是完全密集的（fully dense）。

一个具有所有孤立顶点的图的密度为 0。 此外，它表示图中没有边，可以添加到图中的边的数量等于最大可添加的边的数量。

实现

JavaScript

/*
The density of a network is a measure of how many edges exist proportional to
how many edges would exist in a complete network (where all possible edges).
https://networkx.org/documentation/networkx-1.9/reference/generated/networkx.classes.function.density.html
*/
function density (numberOfNodes, numberOfEdges, isDirected = false) {
  const multi = isDirected ? 1 : 2
  return (multi * numberOfEdges) / (numberOfNodes * (numberOfNodes - 1))
}

参考

• Graph Density | Baeldung on Computer Science (opens new window)