Theoretical Division, Los Alamos National Laboratory, Los Alamos, NM, United States of America.
Computer, Computational, & Statistical Sciences Division, Los Alamos National Laboratory, Los Alamos, NM, United States of America.
PLoS One. 2020 Feb 13;15(2):e0227538. doi: 10.1371/journal.pone.0227538. eCollection 2020.
A very important problem in combinatorial optimization is the partitioning of a network into communities of densely connected nodes; where the connectivity between nodes inside a particular community is large compared to the connectivity between nodes belonging to different ones. This problem is known as community detection, and has become very important in various fields of science including chemistry, biology and social sciences. The problem of community detection is a twofold problem that consists of determining the number of communities and, at the same time, finding those communities. This drastically increases the solution space for heuristics to work on, compared to traditional graph partitioning problems. In many of the scientific domains in which graphs are used, there is the need to have the ability to partition a graph into communities with the "highest quality" possible since the presence of even small isolated communities can become crucial to explain a particular phenomenon. We have explored community detection using the power of quantum annealers, and in particular the D-Wave 2X and 2000Q machines. It turns out that the problem of detecting at most two communities naturally fits into the architecture of a quantum annealer with almost no need of reformulation. This paper addresses a systematic study of detecting two or more communities in a network using a quantum annealer.
组合优化中的一个非常重要的问题是将网络划分为密集连接节点的社区; 其中，特定社区内节点之间的连接性与属于不同社区的节点之间的连接性相比很大。这个问题被称为社区检测，在化学、生物学和社会科学等各个科学领域都变得非常重要。社区检测问题是一个双重问题，包括确定社区的数量，同时找到这些社区。与传统的图划分问题相比，这大大增加了启发式算法的解决方案空间。在使用图的许多科学领域中，需要能够将图划分为具有“最高质量”的社区，因为即使是很小的孤立社区的存在也可能对解释特定现象变得至关重要。我们已经探索了使用量子退火器的社区检测，特别是 D-Wave 2X 和 2000Q 机器。事实证明，检测最多两个社区的问题自然适合于量子退火器的架构，几乎不需要重新表述。本文针对使用量子退火器在网络中检测两个或更多社区的问题进行了系统研究。
