Comparison and selection of objective functions in multiobjective community detection
Comparison and selection of objective functions in multiobjective community detection
复制标题
多目标社区检测中目标函数的比较与选择
DOI：
10.1111/coin.12007
复制
发表时间：
2014
影响因子：
2.8
通讯作者：
Wang Bai
中科院分区：
文献类型：
--
作者：
Shi Chuan;Yu Philip S.;Yan Zhenyu;Huang Yue;Wang Bai
检测复杂网络的群落是识别可能对应于重要功能的子结构的有效方法。传统的社区检测方法通常将社区发现看作一个单目标优化问题，可能会将问题的解限制在特定的社区结构属性上。近年来，一种新的社区检测范式正在兴起：社区检测的多目标优化，即同时优化多个准则并得到一组社区划分。新的范式已经显示出它的优势。然而，一个重要的问题仍然悬而未决：应该优化什么类型的目标来提高多目标社区检测的性能？为了解决这一问题，我们首先提出了一个通用的多目标社区检测解决方案(称为NSGA-Net)，然后分析了由各种目标函数识别的社区的结构特征，这些目标函数已经用于或可能用于社区检测。之后，我们利用任意两个目标函数之间的相关关系(即正相关、独立或负相关)。在人工网络和真实网络上的大量实验表明，NSGA-Net在一对负相关目标上的优化通常会比单目标算法在任何一个原始目标上优化的性能更好，甚至比其他成熟的社区发现方法更好。
Detecting communities of complex networks has been an effective way to identify substructures that could correspond to important functions. Conventional approaches usually consider community detection as a single‐objective optimization problem, which may confine the solution to a particular community structure property. Recently, a new community detection paradigm is emerging: multiobjective optimization for community detection, which means simultaneously optimizing multiple criteria and obtaining a set of community partitions. The new paradigm has shown its advantages. However, an important issue is still open: what type of objectives should be optimized to improve the performance of multiobjective community detection? To exploit this issue, we first proposed a general multiobjective community detection solution (called NSGA‐Net) and then analyzed the structural characteristics of communities identified by a variety of objective functions that have been used or can potentially be used for community detection. After that, we exploited correlation relations (i.e., positively correlated, independent, or negatively correlated) between any two objective functions. Extensive experiments on both artificial and real networks demonstrate that NSGA‐Net optimizing over a pair of negatively correlated objectives usually leads to better performances compared with the single‐objective algorithm optimizing over either of the original objectives, or even to other well‐established community detection approaches.