Sampling from Large Graphs

• 概
• 主要内容

Leskovec J. and Faloutsos C. Sampling from large graphs. KDD, 2006.

概

讨论了不同稀疏化方法对于 large-graph 的`结构' 的保持.

主要内容

• 作者本文的目的是希望比较不同的'稀疏化'方法:

  1. 利用一些方法从大图 \(G\) 中采样子图 \(g\) (更少的结点数或更少的边或者二者);
  2. 希望 \(g\) 能够和大图 \(G\) 有一些共同的性质;
  3. 然后我们可以在小图 \(g\) 上做一些大图上难以做到的推理和模拟.

• Sampling by random node selection:

  • RN (Random Node sampling): 随机选择一部分结点;
  • RPN (Random PageRank Node sampling): 首先用 PageRank 算出每个结点的权重, 然后根据权重随机选择点;
  • RDN (Random Degree Node): 根据 degree 随机选择点;

• Sampling by random edge selection:

  • RE (Random Edge sampling): 随机选择边;
  • RNE (Random Node-Edge sampling): 先随机选个点, 然后在选择一条其上的边, 不断重复;
  • HYB (Hybrid): 上述两种策略混合进行;

• Sampling by exploration:

  • RNN (Random Node Neighbor sampling): 选择一个点, 然后随机选一个邻居 (加上边), 重复进行.
  • RW (Random Walk sampling): 带 restart 的随机游走;
  • FF (Forest Fire sampling): 感觉像是扩散, 具体的算法没讲.

• 作者考虑了诸如 degree, hops 等结构的指标, 上表是不同方法展示出来的差异 (越小越好), 虽然各有千秋, 总的来说 RW, FF, RPN 效果比较好.

• 作者还讨论了一些更为复杂的 (动态图) 的采样, 具体请回看原文.