时间感知社交图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（yes。@ t = 5）

    • 你正在寻找的是一个明确的持久数据结构。 关于这方面的文献有相当多的文献，但并不为人所知。 Chris Okasaki就这个话题撰写了一本相当实用的书。 看看我对这个问题的回答。

    鉴于Driscoll等人的节点分裂结构的完整实现，有几种不同的方式来设置你的查询。 如果您想知道特定时间范围内的真实情况，则只能检查包含有关该时间范围的数据的节点。 如果你想知道什么时间范围是真的，你会开始搜索，并在探索每个新节点时逐渐收紧你的界限。 请记住，你的结果可能并不总是连续的 - 考虑到两个人开始约会，分手，并重新聚在一起。

    我猜可能至少有一篇出版物值得关于如何对持久图进行有趣的查询的未知领域，如果没有更多的话。

    链接地址: http://www.djcxy.com/p/47855.html

    上一篇: Time Aware Social Graph DS/Queries

    下一篇: factor authentication into a Java web app