时间感知社交网络数据结构/查询

Question

经典社交网络可以表示为图/矩阵。利用图/矩阵可以轻松计算以下内容：

- 2个参与者之间的最短路径 - 从A到B的可达性 - 常规统计数据（互惠性，平均连接度等） - 等等

是否存在一种理想的数据结构（或对图/矩阵的修改），使得可以在时间上进行易于计算的操作呢？

例如，

输入

t = 0...100

A <-> B (当t = 0...10)

B <-> C (当t = 5...100)

C <-> A (当t = 50...100)

示例查询

- 是否在任何时候A与B有关联？（是的） - 当B与C联系时，A是否与B相关？（是的。@ t = 5...10） - C是否从A处可达？（是的。@ t=5）

- jameszhao00

Answer 1

你需要的是显式的持久数据结构。关于这个问题有相当多的文献，但并不是很出名。Chris Okasaki写了一本相当重要的关于这个主题的书。看看我对this question的回答。

给定一个完整的实现类似Driscoll等人的节点分裂结构的东西，有几种不同的方法来设置你的查询。如果你想知道在特定时间范围内的事情是否真实，你只会检查包含该时间范围数据的节点。如果你想知道某件事情的时间范围，请开始搜索，并随着探索每个新节点逐渐缩小你的范围。只要记住你的结果可能不总是连续的-考虑两个人开始约会、分手和重新在一起。

我猜可能还有至少一篇未开发领域的出版物，关于如何在持久图上进行有趣的查询，甚至更多。

- Phil Miller