Ronhovde Peter, Nussinov Zohar
Department of Physics, Washington University, St. Louis, Missouri 63130, USA.
Phys Rev E Stat Nonlin Soft Matter Phys. 2009 Jul;80(1 Pt 2):016109. doi: 10.1103/PhysRevE.80.016109. Epub 2009 Jul 14.
We use a Potts model community detection algorithm to accurately and quantitatively evaluate the hierarchical or multiresolution structure of a graph. Our multiresolution algorithm calculates correlations among multiple copies ("replicas") of the same graph over a range of resolutions. Significant multiresolution structures are identified by strongly correlated replicas. The average normalized mutual information, the variation in information, and other measures, in principle, give a quantitative estimate of the "best" resolutions and indicate the relative strength of the structures in the graph. Because the method is based on information comparisons, it can, in principle, be used with any community detection model that can examine multiple resolutions. Our approach may be extended to other optimization problems. As a local measure, our Potts model avoids the "resolution limit" that affects other popular models. With this model, our community detection algorithm has an accuracy that ranks among the best of currently available methods. Using it, we can examine graphs over 40 x10;{6} nodes and more than 1 x10;{9} edges. We further report that the multiresolution variant of our algorithm can solve systems of at least 200 000 nodes and 10 x 10;{6} edges on a single processor with exceptionally high accuracy. For typical cases, we find a superlinear scaling O(L1.3) for community detection and O(L1.3 log N) for the multiresolution algorithm, where L is the number of edges and N is the number of nodes in the system.
我们使用一种Potts模型社区检测算法来准确且定量地评估图的层次结构或多分辨率结构。我们的多分辨率算法在一系列分辨率上计算同一图的多个副本（“复制品”）之间的相关性。通过高度相关的复制品来识别显著的多分辨率结构。平均归一化互信息、信息变化及其他度量原则上可对“最佳”分辨率进行定量估计，并表明图中结构的相对强度。由于该方法基于信息比较，原则上它可与任何能够检查多个分辨率的社区检测模型一起使用。我们的方法可扩展到其他优化问题。作为一种局部度量，我们的Potts模型避免了影响其他流行模型的“分辨率极限”。使用此模型，我们的社区检测算法的准确率在当前可用方法中名列前茅。利用它，我们可以检查节点数超过40×10⁶且边数超过1×10⁹的图。我们进一步报告，我们算法的多分辨率变体能够在单处理器上以极高的准确率解决至少包含200000个节点和10×10⁶条边的系统问题。对于典型情况，我们发现社区检测的超线性缩放比例为O(L¹·³)，多分辨率算法的超线性缩放比例为O(L¹·³ log N)，其中L是系统中的边数，N是节点数。
