论文标题
计算社区比找到它们容易吗？
Is it easier to count communities than find them?
论文作者
论文摘要
文献中已经对具有社区结构的随机图模型进行了广泛的研究。对于检测和恢复社区结构的问题，都出现了有趣的统计和计算相变的景观。一个自然的未解决的问题是：即使在实际发现这些社区的情况下，也可以推断社区结构的特性（例如，社区的数量和规模）即使被认为很难计算？我们表明答案是否定的。特别是，我们考虑了具有不同社区结构的模型之间的某些假设测试问题，并且我们（在低级多项式框架中）表明，在两个选项之间进行测试与找到社区一样困难。 我们的方法给出了第一个计算下限，用于在两个不同的``种植''分布之间进行测试，而先前的结果考虑了在种植分布和I.I.D.之间进行测试。 ``null'分布。我们还展示了在种植模型中恢复的低度框架与测试两个种植模型之间的正式关系。
Random graph models with community structure have been studied extensively in the literature. For both the problems of detecting and recovering community structure, an interesting landscape of statistical and computational phase transitions has emerged. A natural unanswered question is: might it be possible to infer properties of the community structure (for instance, the number and sizes of communities) even in situations where actually finding those communities is believed to be computationally hard? We show the answer is no. In particular, we consider certain hypothesis testing problems between models with different community structures, and we show (in the low-degree polynomial framework) that testing between two options is as hard as finding the communities. Our methods give the first computational lower bounds for testing between two different ``planted'' distributions, whereas previous results have considered testing between a planted distribution and an i.i.d. ``null'' distribution. We also show a formal relationship between the low--degree frameworks for recovery in a planted model and for testing two planted models.
