Community Detection via Random and Adaptive Sampling
Community Detection via Random and Adaptive Sampling
复制标题
通过随机和自适应采样进行社区检测
DOI：
--
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
A. Proutière
中科院分区：
文献类型：
--
作者：
Seyoung Yun;A. Proutière
在本文中，我们考虑由有限数量的非重叠社区组成的网络。为了提取这些社区，可以从大的可用数据集中采样节点对之间的交互，这允许对给定的节点对进行多次采样。当对节点对进行采样时，观察到的结果是一个二进制随机变量，如果节点相互作用，则等于1，否则等于0。如果节点属于相同的社区，则结果更有可能是积极的。对于给定的节点对样本或观测预算，我们希望联合设计一个采样策略（采样节点对的序列）和一个聚类算法，以尽可能高的准确度恢复隐藏的社区。我们考虑非自适应和自适应采样策略，并为这两类策略，我们得到的基本性能限制满足任何采样和聚类算法。特别是，我们提供了必要的条件，准确地恢复社区的网络规模越来越大的算法的存在。我们还设计了简单的算法，准确地重建社区时，这是在所有可能的，因此证明了准确的社区检测的必要条件也是足够的。在随机块模型中的社区检测的经典问题可以被看作是这里考虑的问题的一个特殊的例子。但是我们的框架涵盖了更一般的场景，其中采样节点对的序列可以以自适应的方式设计。本文对随机区组模型给出了新的结果，并将分析推广到自适应抽样的情况。
In this paper, we consider networks consisting of a finite number of non-overlapping communities. To extract these communities, the interaction between pairs of nodes may be sampled from a large available data set, which allows a given node pair to be sampled several times. When a node pair is sampled, the observed outcome is a binary random variable, equal to 1 if nodes interact and to 0 otherwise. The outcome is more likely to be positive if nodes belong to the same communities. For a given budget of node pair samples or observations, we wish to jointly design a sampling strategy (the sequence of sampled node pairs) and a clustering algorithm that recover the hidden communities with the highest possible accuracy. We consider both non-adaptive and adaptive sampling strategies, and for both classes of strategies, we derive fundamental performance limits satisfied by any sampling and clustering algorithm. In particular, we provide necessary conditions for the existence of algorithms recovering the communities accurately as the network size grows large. We also devise simple algorithms that accurately reconstruct the communities when this is at all possible, hence proving that the proposed necessary conditions for accurate community detection are also sufficient. The classical problem of community detection in the stochastic block model can be seen as a particular instance of the problems consider here. But our framework covers more general scenarios where the sequence of sampled node pairs can be designed in an adaptive manner. The paper provides new results for the stochastic block model, and extends the analysis to the case of adaptive sampling.