cluster-analysis - 无向图中节点和边的权重

Question

当我们在一个简单的无向图中基于密度进行聚类时，我们如何知道节点或边的权重。这里的时间复杂度是多少！

你能从这里指导我吗：

1. 边的权重 (u,v) E ∈ 是节点 u 和 v 的公共邻居的数量。M^2 for u≠v 表示节点 u 和 v 的公共邻居的数量。矩阵乘法的顺序为 N^3。但是，我们只需要 M^2 中 M(u,v) =1 的那些元素。因此，找到边缘权重的复杂度可以降低到 O(N*E)。

2. 节点的权重是连接到该节点的边的权重之和。计算每个节点的权重，然后确定权重最高的节点。找到节点权重的复杂度是 N^2 。我们从作为集群的最高权重节点开始，然后将其扩大。

如果你理解它指导我...

Answer 1

通过时序复杂度，它们实际上是指计算复杂度，用 Big-O 表示法表示，如您帖子中的答案 (1) 所示：O(NE)。

边缘的权重是您决定分配给它的 - 它是问题定义的一部分。在旅行商问题中，它将是旅程的长度，例如以英里或公里为单位。