526互联

Sampling from Large Graphs

发布时间 2023-10-18 21:49:34作者: 馒头and花卷

目录

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 效果比较好.

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