发现了重要的一点: 对人来说, 1k 节点的图跟 10k 节点的图完全没有差别: 都是一团黑糊糊的看不清的玩意. 所以大规模图可视化没有活路, 取样才是真理.
基于探索(遍历)的取样
简单随机游走 SRW, Simple Random Walk
随机挑一个开始点, 然后随机游走(指每次随机取一个邻居), 当走到新点时就把点加入取样结果中. 如果在一段时间内都没有走到新点, 就随机换一个起始点重新开始.
会影响取样图的平均度数等属性.
带飞回的随机游走 RWF, Random Walk with Fly back probability
设定一个飞回概率 p. 每次随机游走选下一个点的时候, 以 p 的概率飞回起始点重新开始, 以 1-p 的概率进行随机选下一个点.
其能确保起始点的所有邻居被充分地探索. 随着 p 增大, 取样近似于 BFS 的结果.
带导出子图的随机游走 ISRW, Induced Subgraph Random Walk
SRW 跟 RWF 都不能 “完整” 地体现原图的结构: 因为它们每次取样都只选择了一个邻居, 这导致几乎不可能把一个点的所有邻居都保留在取样中 – 于是取样图的平均度数会比原图小. 并且, SRW/RWF 还会影响图的最短路/平均路径长度, 因为有很多的边被忽略了.
于是我们修改 SRW 的单个取样策略 – 每次走到新点的时候, 把这个新点及其全部邻居都加入取样图(也就是将新点的导出子图加入取样图), 这样也许能更好地反映原图的结构.
雪球取样 SB, Snowball Sampling
BFS, 但是限制每次只取 k 个不在取样图里的邻居. (每一片外层雪花负责滚来 k 片不在雪球里的雪花组成新的外层)
林火取样 FF, ForestFire Sampling
BFS, 但是每个邻居都只有一个概率被选中. (类似树林里树把火传到另一颗邻居树的概率)
Metropolis-Hastings 随机游走 MHRW
梅特罗波利斯-黑斯廷斯算法, MH 算法, 是一种马尔可夫蒙特卡洛(MCMC)方法, 参考:
https://zh.wikipedia.org/wiki/梅特罗波利斯－黑斯廷斯算法
随机选一个起始点 v 作为当前点, 记 D(v) 为 v 的度, 随机选一个邻居 w, 如果 p <= D(v)/D(w), 其中 p 是一个[0, 1]的随机数, 那么就把 “当前点” 设成 w (并把 w 加入取样). 一直做到取完样为止.
带子图的 MHRW
如题, 就是取样的时候取导出子图的 MHRW.
基于边的取样
带完全导出子图的边取样 TIES, Total Induction Edge Sampling
先在图中随机选边, 然后将边两端的节点加入选样. 当选样完后, 将选样图中所有节点导出的子图的其他边都补全进选样图中.