Lai Darong, Lu Hongtao, Nardini Christine
Department of Computer Science and Engineering, Shanghai Jiao Tong University, 200240 Shanghai, China.
Phys Rev E Stat Nonlin Soft Matter Phys. 2010 Jun;81(6 Pt 2):066118. doi: 10.1103/PhysRevE.81.066118. Epub 2010 Jun 23.
The representation of real systems with network models is becoming increasingly common and critical to both capture and simplify systems' complexity, notably, via the partitioning of networks into communities. In this respect, the definition of modularity, a common and broadly used quality measure for networks partitioning, has induced a surge of efficient modularity-based community detection algorithms. However, recently, the optimization of modularity has been found to show a resolution limit, which reduces its effectiveness and range of applications. Therefore, one recent trend in this area of research has been related to the definition of novel quality functions, alternative to modularity. In this paper, however, instead of laying aside the important body of knowledge developed so far for modularity-based algorithms, we propose to use a strategy to preprocess networks before feeding them into modularity-based algorithms. This approach is based on the observation that dynamic processes triggered on vertices in the same community possess similar behavior patterns but dissimilar on vertices in different communities. Validations on real-world and synthetic networks demonstrate that network preprocessing can enhance the modularity-based community detection algorithms to find more natural clusters and effectively alleviates the problem of resolution limit.
用网络模型来表示实际系统正变得越来越普遍，并且对于捕捉和简化系统的复杂性至关重要，特别是通过将网络划分为不同的社区。在这方面，模块度的定义作为一种常用且广泛应用于网络划分的质量度量，催生了大量基于模块度的高效社区检测算法。然而，最近发现模块度的优化存在分辨率极限，这降低了其有效性和应用范围。因此，该研究领域最近的一个趋势与定义新的质量函数有关，以替代模块度。然而，在本文中，我们并非抛开迄今为止为基于模块度的算法所积累的重要知识体系，而是建议在将网络输入基于模块度的算法之前，采用一种策略对网络进行预处理。这种方法基于这样的观察：在同一社区的顶点上触发的动态过程具有相似的行为模式，但在不同社区的顶点上则不同。对真实世界和合成网络的验证表明，网络预处理可以增强基于模块度的社区检测算法，以找到更自然的聚类，并有效缓解分辨率极限问题。
