论文标题
动态网络抽样以进行社区检测
Dynamic Network Sampling for Community Detection
论文作者
论文摘要
我们提出了一种动态网络采样方案，以优化随机块模型（SBM）的块恢复，如果观察整个图的昂贵，则它非常昂贵。从理论上讲，我们通过Chernoff信息提供了建议的Chernoff最佳动态抽样方案的理由。实际上，我们根据不同域中的几个真实数据集评估了我们方法的性能。理论上和实际的结果都表明，我们的方法可以识别对块结构影响最大的顶点，以便只能检查它们之间是否有边缘以节省大量资源，但仍能恢复块结构。
We propose a dynamic network sampling scheme to optimize block recovery for stochastic blockmodel (SBM) in the case where it is prohibitively expensive to observe the entire graph. Theoretically, we provide justification of our proposed Chernoff-optimal dynamic sampling scheme via the Chernoff information. Practically, we evaluate the performance, in terms of block recovery, of our method on several real datasets from different domains. Both theoretically and practically results suggest that our method can identify vertices that have the most impact on block structure so that one can only check whether there are edges between them to save significant resources but still recover the block structure.
