用Java创建一个图数组(时间演化)

Question

我对Java很陌生，我还在处理图表。我有一个时间演化图(例如，在不同的时间实例中，同一个图的5个快照)，我需要计算一些基本的网络度量，比如密度、大小、中心性等等。我想知道我可以使用什么样的基本数据结构来存储和执行每个图的计算。我尝试使用邻接矩阵，但是节点大小太大，动态，导致效率低下。我遇到了很少的库，特别是JgraphT来保存无向图。

    UndirectedGraph<String, DefaultEdge> G =
          new SimpleGraph<String, DefaultEdge>(DefaultEdge.class);

但这是一张图。是否有一种方法来创建这些无向图的数组，或者其他我所缺少的存储时间演化图的方法？

Answer 1

有几种选择：

(1)可以创建数组(或列表或集合等)。就像你能看到任何其他物体一样。如果所有的时间步骤都能很容易地放入内存中(比如每个1000个节点/边的100个时间步骤)，那么这应该可以很好地工作。下面是一个使用JUNG的示例：

List<Graph<V, E>> graphList = new ArrayList<>(); // Java 7 syntax
Graph<V, E> graph = new DirectedSparseGraph<V, E>();
// populate 'graph'
graphList.add(graph);

(2)如果每个图中的节点都是相同的(即，只是边在变化)，则只存储节点一次，并存储一组边，每个时间步骤一组。

(3)如果整个图是相对静态的，则可以存储原始图，然后为每个时间步骤存储增量(添加/删除节点或边)。这可以大大提高空间效率，但需要重构步骤1-n才能在time n+1上看到状态。

(4)最后，您可以使用单个图，用每个节点/边的存在间隔对其进行注释，并在任何时候应用一个筛选器对该图应用算法。