时间感知社交图 DS/查询
经典社交网络可以表示为图形/矩阵。
通过图形/矩阵，我们可以轻松计算
- 最短路径
- 2 个参与者之间从 A → 可达性的 。 B
- 一般统计数据（互易性、平均连通性等）
- 等
是否存在一种理想的数据结构（或对图形/矩阵的修改），可以在具有时间意识的同时轻松计算上述内容？
例如，
输入
t = 0...100
- A <-> B（当 t = 0...10 时）
- B <-> C(当t＝5...100时)
- C＜-＞ A（当 t = 50...100 时）
示例查询
- A 在任何时候都与 B 关联吗？ （是）
- A 与 B 关联，而 B 与 C 关联吗？ （是的。@t = 5...10）
- C 是否可以从 A 到达（是的。@ t=5 ）
Classic social networks can be represented as a graph/matrix.
With a graph/matrix one can easily compute
- shortest path between 2 participants
- reachability from A -> B
- general statistics (reciprocity, avg connectivity, etc)
- etc
Is there an ideal data structure (or a modification to graph/matrix) that enables easy computation of the above while being time aware?
For example,
Input
t = 0...100
- A <-> B (while t = 0...10)
- B <-> C (while t = 5...100)
- C <-> A (while t = 50...100)
Sample Queries
- Is A associated with B at any time? (yes)
- Is A associated with B while B is associated with C? (yes. @t = 5...10)
- Is C ever reachable from A (yes. @ t=5 )
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
您正在寻找的是一个明确的持久数据结构。关于这一点有大量文献，但并不那么广为人知。克里斯·冈崎（Chris Okasaki）就这个主题写了一本相当丰富的书。看看我对 这个问题。
考虑到 Driscoll 等人的节点分割结构的完整实现，有几种不同的方法来设置查询。如果您想了解特定时间范围内的真实情况，您只需检查包含该时间范围数据的节点。如果你想知道某件事在什么时间范围内是真实的，你将开始搜索，并在探索每个新节点时逐渐收紧你的界限。请记住，您的结果可能并不总是连续的 - 考虑两个人开始约会，分手，然后复合。
我猜想，在如何对持久图进行有趣的查询方面，可能至少有一篇出版物值得探索的领域，如果不是更多的话。
What you're looking for is an explicitly persistent data structure. There's a fair body of literature on this, but it's not that well known. Chris Okasaki wrote a pretty substantial book on the topic. Have a look at my answer to this question.
Given a full implementation of something like Driscoll et al.'s node-splitting structure, there are a few different ways to set up your queries. If you want to know about stuff true in a particular time range, you would only examine nodes containing data about that time range. If you wanted to know what time range something was true, you would start searching, and progressively tighten your bounds as you explore each new node. Just remember that your results might not always be contiguous - consider two people start dating, breaking up, and getting back together.
I would guess that there's probably at least one publication worth of unexplored territory in how to do interesting queries over persistent graphs, if not much more.