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.
Enhanced modularity-based community detection by random walk network preprocessing
Nardini Christine
2010
Abstract
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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.