如何在具有相似性的节点之间创建边 [英] How to create edges between nodes that have similarities

问题描述

我有一个简单的Graph类，并且必须创建带有节点和边的图。如果 nodeA 上的数组，则两个节点 nodeA ， nodeB 之间有一条边。 code>和 nodeB 有一些相似之处。

I have a simple Graph class, and I have to create the graph with nodes and edges. There is an edge between two nodes, nodeA, nodeB if the array on nodeA and nodeB has some similarities.

例如：

const example = [{
  "node": "A",
  "data": [ 1, 2, 3 ]
}, {
  "node": "B",
  "data": [ 3, 4, 5 ]
}, {
  "node": "C",
  "data": [ 5, 6, 7 ]
}, {
  "node": "D",
  "data": [ 7, 8, 9 ]
}]

这意味着在以下位置之间存在边沿：

This means that there is an edge between:

1. A 和 B ，因为3在两个数据数组上都相同。

1. A and B because 3 apears on both data arrays.

B 和 C ，因为在两个数据数组上都有5个尖。

B and C because 5 apears on both data arrays.

C 和 D ，因为两个数据数组。

因此，从本质上讲，我们从 A-> B-> C-> D

So essentially we have an edge from A -> B -> C -> D

我设法创建了一个图并使用邻接表来存储边，但是问题是，我不知道如何创建具有相似性的节点之间的边缘。天真的解决方案是查看 example [i-1] 和 example [i] 。但这是错误的，因为数据没有按顺序排列。

I managed to create a graph and use adjacency list for storing edges, but the problem is, I don't know how to create edges between nodes that have similarity. The naive solution would be to look at example[i - 1] and example[i]. But this is wrong because the data do not come in order.

class Graph {

  constructor(numOfVertex) {

    this.adj = new Map();

  }

  addNodes(node) {

    this.adj.set(node, []);  

  }

  addEdge(nodeA, nodeB) {

    this.adj.get(nodeA).push(nodeB);

    this.adj.get(nodeA).push(nodeB);

  };

}

然后填充图形，我这样做：

and to populate the graph, I do:

    const graph = new Graph(example.length);

    for (let i = 0; i < example.length; i++) {

      const { node, data } = example[i];

      graph.addVertex(title)

      G.addEdge(...)

    }

关于如何循环遍历每个节点的数据数组以有效查看相似性的任何想法？

Any ideas of how I can loop through the data array of each node to see similarities efficiently?

出于问题的考虑，我给出了一个小的示例数据，实际上，我遍历了大量数据。

For the sake of the question, I gave a small example data, in reality, I loop through a large set of data.

推荐答案

根据数据数组的大小和结果图的稀疏性，有几种方法可以解决此问题：

Depending on the size of data arrays and sparsity of the resulting graph, there is several ways you can approach this problem:

• 遍历所有节点对并计算它们是否具有边。可以在 O（| data [A] | + | data [B] |）中为一对节点（A，B）执行此计算，因此此解决方案是 O（N ^ 2 + N *（所有i上的数据[i]之和））。如果您的图形密集，即边缘的数量为N ² 的量，则此方法效果很好。


• 构建地图（X-> ListOfNodes ），这样每个数字X就会映射到其数据中包含X的所有节点。属于同一列表的每对节点都应连接一条边。此解决方案的复杂度为 O（（所有i上的数据之和）+（难以估计的数量，即每对节点共享一个数据点的次数））。对于稀疏图，这应该比以前的方法更好，但是实际上取决于数据数组的构造方式。

• Iterate over all pairs of nodes and compute whether they have an edge. This computation can be performed in O(|data[A]| + |data[B]|) for a pair of nodes (A, B), so the complexity of this solution is O(N^2 + N * (sum of data[i] over all i)). This works well if you graph is dense, i.e., number of edges in it is on the order of N².
• Build a map (X -> ListOfNodes), such that each number X is mapped to all nodes that contain X in their data. Every pair of nodes that belongs to the same list should be connected with an edge. The complexity of this solution is O((sum of data[i] over all i) + (a hard to estimate quantity that is the number of times each pair of nodes shares a data point)). For sparse graphs, this should work better than the previous approach, but it really depends on how data arrays are constructed.

生成了数据？

这篇关于如何在具有相似性的节点之间创建边的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！