Estimating the resolution limit of the map equation in community detection
Estimating the resolution limit of the map equation in community detection
复制标题
DOI：
10.1103/physreve.91.012809
复制
发表时间：
2015-01-12
影响因子：
2.4
通讯作者：
Rosvall, Martin
中科院分区：
文献类型：
--
作者：
Kawamoto, Tatsuro;Rosvall, Martin
如果可以解析的最小模块的规模取决于所分析子网的大小，则认为团体检测算法具有分辨率限制。已知分辨率限制是为了防止某些社区检测算法准确识别网络的模块化结构。实际上，任何用于度量将节点划分为模块的两级分配的质量的全局目标函数都必须具有某种分辨率限制或外部分辨率参数。然而，目前尚不清楚分辨率限制如何影响所谓的地图方程，而地图方程是已知的社区检测的有效目标函数。我们推导了一个解析估计，并得出映射方程的分辨率极限是由模块间的链路总数而不是整个网络的链路总数来决定的结论。这种机制使得映射方程的分辨率限制比模块化的限制少得多；实际上，它要小几个数量级。此外，我们认为分辨率限制的影响往往是由于将多层模块结构硬塞到两层描述中。如我们所示，层次映射方程有效地消除了嵌套多层模块化结构网络的分辨率限制。
A community detection algorithm is considered to have a resolution limit if the scale of the smallest modules that can be resolved depends on the size of the analyzed subnetwork. The resolution limit is known to prevent some community detection algorithms from accurately identifying the modular structure of a network. In fact, any global objective function for measuring the quality of a two-level assignment of nodes into modules must have some sort of resolution limit or an external resolution parameter. However, it is yet unknown how the resolution limit affects the so-called map equation, which is known to be an efficient objective function for community detection. We derive an analytical estimate and conclude that the resolution limit of the map equation is set by the total number of links between modules instead of the total number of links in the full network as for modularity. This mechanism makes the resolution limit much less restrictive for the map equation than for modularity; in practice, it is orders of magnitudes smaller. Furthermore, we argue that the effect of the resolution limit often results from shoehorning multilevel modular structures into two-level descriptions. As we show, the hierarchical map equation effectively eliminates the resolution limit for networks with nested multilevel modular structures.