ARROW - Approximating Reachability using Random walks Over Web-scale Graphs[ICDE'19]

ICDE19年的一篇论文

解决的问题

给定一个有向图$G=(V,E)$以及一系列顶点对$(u,v)$,判断两个顶点之间是否连通,对应两种查询情况:

  • Chained Queries:查询路径上每条边开始于上一条边结束,并且总时间在规定的范围内
  • Snapshot Queries:对于一个动态变化的图,在给定的时间范围内至少在$c$个快闪图中存在连通

创新之处

  1. 以起始顶点和目的顶点各自进行多次固定长度的随机漫步构建两个集合,两个集合的交集非空说明连通
  2. 对于随机漫步的长度及次数的选取给出了理论证明
    2.1 随机漫步的长度:有向图中最长的最短路径的长度,通过10次的深度优先搜索得到
    2.2 随机漫步的次数:类比于扔球问题,给定$n$个篮子和数量相等的红球与蓝球,需要扔多少个球来保证有一个篮子中同时有红球与蓝球的概率高?红球可以看作起始顶点$u$可以到达的顶点,蓝球可以看作目的顶点$v$可以到达的顶点
  3. 模型的一个假设前提是构建的两个反向的随机漫步的平稳分布应尽可能接近,这对应于正向随机漫步选定一个出边的概率与反向随机漫步选定一个入边的概率相等,而这个概率恰等于顶点度的倒数。使用同配性(assortativity)作为这两个平稳分布接近程度的指标。