Community Detection via Random and Adaptive Sampling

摘要: In this paper, we consider networks consisting of a finite number non-overlapping communities. To extract these communities, the interaction between pairs nodes may be sampled from large available data set, which allows given node pair to several times. When is sampled, observed outcome binary random variable, equal 1 if interact and 0 otherwise. The more likely positive belong same For budget samples or observations, wish jointly design sampling strategy (the sequence pairs) clustering algorithm that recover hidden communities with highest possible accuracy. We both non-adaptive adaptive strategies, for classes derive fundamental performance limits satisfied by any algorithm. particular, provide necessary conditions existence algorithms recovering accurately as network size grows large. also devise simple reconstruct when at all possible, hence proving proposed accurate community detection are sufficient. classical problem in stochastic block model can seen particular instance problems here. But our framework covers general scenarios where designed an manner. paper provides new results model, extends analysis case sampling.